Что: | Лекция |
Когда: | Понедельник, 23 ноября 2020, 22:30–23:50 |
Где: | Конференция в zoom, Онлайн |
Невычислимость колмогоровской сложности. Теорема Геделя о неполноте в форме Чайтина. Бесконечность простых чисел. Нижняя оценка на сложность распознавания палиндрома одноленточными машинами Тьюринга.
Приближенные алгоритмы для MaxSAT. Вероятностное округление.
Текущая версия конспекта.