imported>.obj: Migrated current public revision from wiki.cs.hse.ru

2016-10-23T20:20:46Z

Migrated current public revision from wiki.cs.hse.ru

Новая страница

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

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

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

Всеми этим задачами можно пользоваться для доказательства 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
|}

=Оценки=

{| class="wikitable"
|-
! Студенты !! д/з 1 !! д/з 2 !! аудиторная работа !! накопленная оценка
|-
| Иван Аустер || 5 || 7 || 7 || 6
|-
| Валерий Батурин || 8 || 10 || 8 || 9
|-
| Алексей Гавриков || 9 || 10 || 8 || 9
|-
| Сергей Горбачев || 5 || 10 || 10 || 8
|-
| Петр Жижин || 7 || 10 || 7 || 8
|-
| Ксения Закирова || 9 || 10 || 6 || 9
|-
| Камиль Лотфуллин || 8 || 7 || 6 || 7
|-
| Екатерина Минеева || 10 || 10 || 10 || 10
|-
| Никита Нестеров || 8 || 7 || 6 || 7
|-
| Олег Николаев || 2 || 7 || 2 || 4
|-
| Андрей Соколов || 5 || 8 || 5 || 6
|-
| Михаил Флоринский || 8 || 10 || 4 || 8
|-
| Александр Чернявский || 9 || 10 || 7 || 9
|-
| Антон Чернявский || 9 || 10 || 7 || 9
|-
| Александр Шарипов || 1 || 9 || 1 || 4
|}

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

imported>.obj: Migrated current public revision from wiki.cs.hse.ru