Алгоритмы и структуры данных 2 2016/2017/152-2 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(→‎NP-полные задачи)
Строка 19: Строка 19:
  
 
Всеми этим задачами можно пользоваться для доказательства NP-полноты других задач (если явно не указано иное).
 
Всеми этим задачами можно пользоваться для доказательства NP-полноты других задач (если явно не указано иное).
 +
 +
=Первое домашнее задание=
 +
 +
Распределение задач:
 +
{| class="wikitable"
 +
|-
 +
! Студенты !! задачи [https://www.dropbox.com/s/l7pug7ahj3hbis9/algo2-hw2.pdf?dl=0 второй части]
 +
|-
 +
| Иван Аустер || 1
 +
|-
 +
| Валерий Батурин || 2
 +
|-
 +
| Алексей Гавриков || 3
 +
|-
 +
| Сергей Горбачев || 4
 +
|-
 +
| Петр Жижин || 5
 +
|-
 +
| Ксения Закирова || 6
 +
|-
 +
| Камиль Лотфуллин || 7
 +
|-
 +
| Екатерина Минеева || 8
 +
|-
 +
| Никита Нестеров || 9
 +
|-
 +
| Олег Николаев || 10
 +
|-
 +
| Ярослав Ребенко || 11
 +
|-
 +
| Андрей Соколов || 12
 +
|-
 +
| Михаил Флоринский || 13
 +
|-
 +
| Александр Чернявский || 14
 +
|-
 +
| Антон Чернявский || 2
 +
|-
 +
| Александр Шарипов || 3
 +
|}

Версия 17:22, 17 сентября 2016

NP-полные задачи

На лекциях и семинарах обсуждалась NP-полнота следующих задач:

  • выполнимость булевой формулы (SAT);
  • выполнимость 3-КНФ (3SAT);
  • существование означивания для 3-КНФ, дающего не менее одной истинной и не менее одной ложной литеры в каждой скобке (Not-All-Equal-3SAT);
  • существование клики заданного размера в графе;
  • существование вершинного покрытия заданного размера в графе;
  • существование независимого множества заданного размера в графе;
  • наличие гамильтонова пути в ориентированном графе;
  • наличие гамильтонова цикла в ориентированном графе;
  • существование раскраски графа в k цветов, такой что никакие две смежные вершины не окрашены в один цвет (k > 2 — константа);
  • наличие разреза размера не менее заданного в неориентированном графе;
  • возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;
  • задача о расписании экзаменов: можно ли провести k экзаменов за n пар так, чтобы ни одному из m студентов не пришлось сдавать два экзамена одновременно? (для каждого студента указаны экзамены, которые ему нужно сдать; на проведение одного экзамена достаточно одной пары);
  • задача о сумме подмножества;
  • задача о рюкзаке.

Всеми этим задачами можно пользоваться для доказательства NP-полноты других задач (если явно не указано иное).

Первое домашнее задание

Распределение задач:

Студенты задачи второй части
Иван Аустер 1
Валерий Батурин 2
Алексей Гавриков 3
Сергей Горбачев 4
Петр Жижин 5
Ксения Закирова 6
Камиль Лотфуллин 7
Екатерина Минеева 8
Никита Нестеров 9
Олег Николаев 10
Ярослав Ребенко 11
Андрей Соколов 12
Михаил Флоринский 13
Александр Чернявский 14
Антон Чернявский 2
Александр Шарипов 3
Источник — «http://wiki.cs.hse.ru/index.php?title=Алгоритмы_и_структуры_данных_2_2016/2017/152-2&oldid=20436»