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

  • Либеральная партия

    Конечно, либералы победят. Их победа давно запланирована, они ждут своего часа и лишь притворяются оппозицией, поскольку они — дети и…

  • Кто в молодости... нет сердца, кто в зрелости... нет мозгов.

    Написал в КПРФ и СР о своём желании быть выдвинутым в депутаты ГД (а почему бы и нет?). Пока что как-то непонятно всё. А тут ЕР продлила своё…

  • Две страны, одна система

    Перестройка и реформы 90-х — неудачная попытка повторить китайский путь. В Китае делали примерно всё то же самое. Одна страна — две системы:…

  • 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