Формальные языки и сложность вычислений. Лекция 14. Задача оптимизации. Вероятностная МТ

Дата лекции: 06.12.24 Лектор: Зухба Анастасия Викторовна Оператор: Дмитрий Достовалов Редактор: Илья Оплачкин 00:00:00 - Введение 00:00:45 - Задача оптимизации 00:03:45 - Оптимум (OPT) 00:05:50 - Алгоритм ε-аппроксимации 00:09:50 - Порог аппроксимации 00:13:25 - Доказательство оценки порога аппроксимации в 1/2 для NP 00:22:10 - Порог аппроксимации задачи коммивояжера 00:28:00 - Полиномиальная аппроксимационная схема 00:36:00 - Вероятностное решение 00:38:10 - Вероятностная МТ 00:45:11 - Типы ошибок 00:48:10 - Класс BPP 00:52:50 - Класс RP 00:54:00 - Класс ZPP 00:56:40 - Амплификация Сайт ВШПИ: https://hsse.mipt.ru