Решение NP-полных задач. Параллель A. 27.03.2021

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

Видео Решение NP-полных задач. Параллель A. 27.03.2021 канала Т-Образование