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

Июль 30, 2022

Главная
Информатика
Недетерминированные алгоритмы

Содержание

2. Цель и задачи Цель работы: изучение np-алгоритмов. Задачи: Выяснить, что такое np-алгоритмы и в чем их
3. Определение NP-алгоритмов NP (non-deterministic polynomial) - это класс задач, которые можно решить на недетерминированной машине Тьюринга
4. Машина Тьюринга В недетерминированной машине Тьюринга для каждой комбинации состояния и символа существует несколько вариантов перехода
5. NP-сложные и NP-полные задачи Класс NP-сложные задачи – это задачи, к которым может быть сведена любая
6. P = NP?
7. Раскраска графа Раскрасить заданный граф в n-е количество цветов.
8. Раскладка по ящикам
9. Задача о ранце
10. Задача о сумме подмножеств
11. Задача коммивояжера
12. Задача коммивояжера
14. Скачать презентацию

Слайд 2

Цель и задачи
Цель работы: изучение np-алгоритмов.
Задачи:
Выяснить, что такое np-алгоритмы и в

чем их отличительная черта.
Рассмотреть типовые np-задачи.
Рассмотреть проблему P ≠ NP

Слайд 3

Определение NP-алгоритмов
NP (non-deterministic polynomial) - это класс задач, которые можно решить

на недетерминированной машине Тьюринга за полиномиальное время.

Слайд 4

Машина Тьюринга
В недетерминированной машине Тьюринга для каждой комбинации состояния и символа

существует несколько вариантов перехода и действия.

Слайд 5

NP-сложные и NP-полные задачи
Класс NP-сложные задачи – это задачи, к которым

может быть сведена любая другая NP задача за полиномиальное время.

NP-полные задачи – это задачи класса NP, к которым можно свести любую другую задачу этого класса за полиномиальное время.

Слайд 6

P = NP?

Слайд 7

Раскраска графа
Раскрасить заданный граф в n-е количество цветов.

Слайд 8

Раскладка по ящикам

Слайд 9

Задача о ранце

Слайд 10

Задача о сумме подмножеств

Слайд 11

Задача коммивояжера

Слайд 12

Задача коммивояжера