Сайт использует сервис веб-аналитики Яндекс Метрика с помощью технологии «cookie». Пользуясь сайтом, вы даете согласие на использование данной технологии.
00:00:00 - Разбор тематического контеста 00:08:07 - Задача разрешимости 00:10:53 - Машина Тьюринга 00:16:36 - Пример задачи 00:21:19 - Задача останова 00:25:30 - Разрешимые множества 00:28:32 - Перечислимые множества 00:34:07 - Альтернативные модели вычисления 00:36:04 - Классы сложности (P, DTime, EXP, NP, NP-Hard, NP-Complete) 01:03:06 - Примеры и доказательства NP-полноты задач (SAT, 3-SAT, k-Clique,3-Coloring) 01:17:03 - RP, coRP, ZPP, BPP 01:22:46 - Поиск мажорирующего элемента и арифметической прогрессии длины ≥ n/2 01:25:56 - ZPP и связь с RP 01:31:45 - 3-SAT (random walk) 01:40:46 - Приближенные и параметризованные алгоритмы 02:00:39 - Решаем задачи с помощью SAT-solver
