Лекция 6. P, NP, NP-полнота

Автор: Computer Science Center

Загружено: 20 апр. 2021 г.

Просмотров: 4 387 просмотров

Описание:

https://compscicenter.ru/

Лекция №6 курса «Алгоритмы и структуры данных, часть 2» (весна 2020).
Преподаватель — Нияз Габдуллазянович Нигматуллин
Страница лекции на сайте CS центра: https://bit.ly/3bzLxF4

Лекция 6. P, NP, NP-полнота

Доступные форматы для скачивания:

Скачать видео mp4

Информация по загрузке:

Скачать аудио mp3

Похожие видео

Лекция 7. Приближённые алгоритмы

Лекция 7. Приближённые алгоритмы

Лекция 1. Введение в алгоритмы на графах

Лекция 1. Введение в алгоритмы на графах

Сложность вычислений 2. Классы P и NP

Сложность вычислений 2. Классы P и NP

МЕХАНИЗМЫ, УСТОЙЧИВЫЕ К СГОВОРУ: ЛЕКЦИЯ В НИЖНЕМ НОВГОРОДЕ 12 СЕНТЯБРЯ!

МЕХАНИЗМЫ, УСТОЙЧИВЫЕ К СГОВОРУ: ЛЕКЦИЯ В НИЖНЕМ НОВГОРОДЕ 12 СЕНТЯБРЯ!

16. Complexity: P, NP, NP-completeness, Reductions

16. Complexity: P, NP, NP-completeness, Reductions

Лекция 1. Понятие и оценка алгоритмов

Лекция 1. Понятие и оценка алгоритмов

Теория сложности - классы P и NP, два определения NP, сведение по Карпу, NP-трудность и NP-полнота

Теория сложности - классы P и NP, два определения NP, сведение по Карпу, NP-трудность и NP-полнота

Жадные алгоритмы

Жадные алгоритмы

Science show. Выпуск № 69. Равенство классов P и NP

Science show. Выпуск № 69. Равенство классов P и NP

Сложность вычислений 3. Препятствия в доказательстве P=NP

Сложность вычислений 3. Препятствия в доказательстве P=NP