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

Материал из Wiki - Факультет компьютерных наук
Перейти к навигации Перейти к поиску
← Предыдущая правка
.obj (обсуждение | вклад)
1001 правка
.obj (обсуждение | вклад)
1001 правка
Нет описания правки
 
(не показано 5 промежуточных версий этого же участника)
Строка 11: Строка 11:
* наличие гамильтонова пути в ориентированном графе;
* наличие гамильтонова пути в ориентированном графе;
* наличие гамильтонова цикла в ориентированном графе;
* наличие гамильтонова цикла в ориентированном графе;
* существование раскраски графа в три цвета, такой что никакие две смежные вершины не окрашены в один цвет;
* существование раскраски графа в ''k'' цветов, такой что никакие две смежные вершины не окрашены в один цвет (''k'' > 2 — константа);
* наличие разреза размера не менее заданного в неориентированном графе;
* наличие разреза размера не менее заданного в неориентированном графе;
* возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;
* возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;
* задача о расписании экзаменов: можно ли провести ''k'' экзаменов за n пар так, чтобы ни одному из m студентов не пришлось сдавать два экзамена одновременно? (для каждого студента указаны экзамены, которые ему нужно сдать; на проведение одного экзамена достаточно одной пары);   
* задача о расписании экзаменов: можно ли провести ''k'' экзаменов за ''n'' пар так, чтобы ни одному из ''m'' студентов не пришлось сдавать два экзамена одновременно? (для каждого студента указаны экзамены, которые ему нужно сдать; на проведение одного экзамена достаточно одной пары);   
* задача о сумме подмножества;
* задача о сумме подмножества;
* задача о рюкзаке.
* задача о рюкзаке.


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

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