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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(→‎NP-полные задачи)
 
(не показаны 4 промежуточные версии этого же участника)
Строка 11: Строка 11:
 
* наличие гамильтонова пути в ориентированном графе;
 
* наличие гамильтонова пути в ориентированном графе;
 
* наличие гамильтонова цикла в ориентированном графе;
 
* наличие гамильтонова цикла в ориентированном графе;
−
* существование раскраски графа в три цвета, такой что никакие две смежные вершины не окрашены в один цвет;
+
* существование раскраски графа в ''k'' цветов, такой что никакие две смежные вершины не окрашены в один цвет (''k'' > 2 — константа);
 
* наличие разреза размера не менее заданного в неориентированном графе;
 
* наличие разреза размера не менее заданного в неориентированном графе;
 
* возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;
 
* возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;
Строка 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
 +
|}
 +
 +
=Оценки=
 +
 +
{| 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
 +
|}

Текущая версия на 23:20, 23 октября 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

Оценки

Студенты д/з 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
Источник — «http://wiki.cs.hse.ru/index.php?title=Алгоритмы_и_структуры_данных_2_2016/2017/152-2&oldid=21414»