City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Лекция 11. Колмогоровская сложность (продолжение). Приближенные алгоритмы для MaxSAT
Introduction to theoretical computer science

What: Lecture
When: Monday, 23 November 2020, 18:30–19:50
Where: Конференция в zoom, Онлайн

Description

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

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

Video

Other materials

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