Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Лекция 11. Колмогоровская сложность (продолжение). Приближенные алгоритмы для MaxSAT
Обзорный курс по теоретической информатике

Что: Лекция
Когда: Понедельник, 23 ноября 2020, 18:30–19:50
Где: Конференция в zoom, Онлайн

Описание

Невычислимость колмогоровской сложности. Теорема Геделя о неполноте в форме Чайтина. Бесконечность простых чисел. Нижняя оценка на сложность распознавания палиндрома одноленточными машинами Тьюринга.

Приближенные алгоритмы для MaxSAT. Вероятностное округление.

Видео

Другие материалы

Текущая версия конспекта.