Приклад задач

До задач класу складності NP належать:

1. Розв'язність логічного виразу.

2. Три-кольорове розфарбування графу.

3. Побудова кліки з k вершин на неорієнтованому графі.

Покриття множин: нехай задане сімейство F підмножин Ei деякої множини E; необхідно знайти підсемейство G із F, так, що:

4. Існування гамільтонового циклу на неорієнтованому графі.

Що таке NP повна задача?

Що таке NP важка задача?

Які ви знаєте властивості NP важких задач?

Приклади NP важких задач.

Л ітература

1. В.А.Носов. Основы теории алгоритмов и анализ их сложности. К.л. М.: 1992. – 140 с.

2. А. А. Марков. Теория алгоритмов // М.: 1961

3. В.М. Зюзьков. Лекции по теории алгоритмов.

4. А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.–536с.

5. Э. Рейнгольд, Ю. Нивергельт, Н. Део. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980.–480с.

6.. Кристофидес. Теория графов. Алгоритмический подоход. – М.: Мир, 1978.-432с.

7. В.А. Горбатов. Основы дискретной математики: Уч. пос. для студентов вузов. – М.: Высш. шк., 1986.-311с.

8. П. олл. Вычислительные структуры. Введение в нечисленное программирование. –М.: Мир, 1978.-216с.

9. Н. Вирт. Алгоритмы + структуры данных=программы.-М.: 1985.-406с.

10. А.Т. Берзтисс. Структуры данных.-М.:Статистика, 1974.-408с.

11. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов.-М.: Мир, 1981.-368с.

12. М.А. Айзерман и др. Логика. Автоматы. –М.: Физматгиз, 1963.-556с.