kray_zemli (kray_zemli) wrote,
kray_zemli
kray_zemli

Category:

проблема дедекинда: кол-во монотонных булевых функций

Нашёл на винте текст своего доклада для студенческой конференции 2002 года. Всю ночь пытался в нём разобраться. Только к утру начал что-то понимать. Старею, блин. :-(

Целью работы было повторить вычисления числа монотонных булевых функций (проблема Дедекинда). К тому времени, было известно число булевых функций до 8 переменных. Собственно, все 8 были повторены на 266 пне с 64 метрами памяти, который современная шалупонь называет безнадёжным тормозом. Ранее существовавшие данные были получены на суперкомпах. Чтобы получить, например, D(8), надо умножить две матрицы D(6) x D(6), т. е. примерно 8 на 8 мильёнов. Мною был использован специально разработанный совместно с научруком алгоритм, для которого достаточно матриц 7581x168.

Кому интересно. Полное число булевых функций N переменных равно 2^(2^N).

Из них, монотонных:
 N            D(N)
---  -----------------------
 0                         2
 1                         3
 2                         6
 3                        20
 4                       168
 5                      7581
 6                   7828354
 7             2414682040998
 8   56130437228687557907788


За сим прощаюсь. Молитесь и дрочите (уж кто что предпочитает)!
Tags: e
Subscribe

  • Метал бисер

    ... в комментах к видеопосту одного известного покерного шулера про финансовые пирамиды, где он обвиняет в их существовании государство. >…

  • Географический детерминизм

    Сегодня опять звонили банковские мошенники — выпрашивали код из СМС. Сразу бросилось в граза сходство в манерности речи мошенников и…

  • Бутерброд с "новичком"

    Вот так вот станешь в 2024 президентом, инаугурация, помпезность, все дела. Выходишь довольный такой, размахивая "ядерным чемоданчиком". И тут…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 8 comments