Вычислительная сложность

49 Просмотры

  • Спасибо! Поделитесь с друзьями!

    Вам не понравилось видео. Спасибо за то что поделились своим мнением!

admin
Издатель
Эта лекция посвящена вычислительной сложности и является второй частью лекции о вычислимости

Мы поговорим о важности недетерминизма в разнообразных машинах, о классах P, NP и PSPACE, о полиномиальной сводимости разных задач и о многом другом

Предыдущая лекция: https://youtu.be/4EGAF_xPmis
Следующая лекция: TBD

Лектор: Константин Владимиров

Дата лекции: 12 июня 2021 года
Съёмка и звук: Дмитрий Рябцев

Слайды к лекциям автора по логике и вычислимости: https://sourceforge.net/projects/cpp-lects-rus/files/logic

Timeline

00:00 Введение
04:45 Конечные автоматы
14:10 Эпсилон переходы и NFA
25:40 Автоматы с магазинной памятью
41:34 Недетерминированная машина Тьюринга, P и NP
55:20 SAT и варианты SAT
01:07:00 NP-полнота и теорема Кука
01:15:11 Cведения к SAT и друг другу самых разных задач
01:52:15 TAUT и co-NP
02:02:41 QBF и класс PSPACE
02:20:10 Заключение

Errata:
* тут пока пусто
Категория
Занимательная химия
Комментариев нет.

Следующее