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

.obj в 20:20, 23 октября 2016

2016-10-23T20:20:46Z

@@ Строка 58: / Строка 58: @@
 |-
 | Александр Шарипов || 3
 |}

.obj в 14:22, 17 сентября 2016

2016-09-17T14:22:55Z

← Предыдущая версия		Версия от 14:22, 17 сентября 2016
Строка 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
			\|}

.obj: /* NP-полные задачи */

2016-09-17T13:35:28Z

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

← Предыдущая версия		Версия от 13:35, 17 сентября 2016
Строка 11:		Строка 11:
	* наличие гамильтонова пути в ориентированном графе;		* наличие гамильтонова пути в ориентированном графе;
	* наличие гамильтонова цикла в ориентированном графе;		* наличие гамильтонова цикла в ориентированном графе;
	* существование раскраски графа в ''k'' цветов, такой что никакие две смежные вершины не окрашены в один цвет (''k'' > — константа);		* существование раскраски графа в ''k'' цветов, такой что никакие две смежные вершины не окрашены в один цвет (''k'' > 2 — константа);
	* наличие разреза размера не менее заданного в неориентированном графе;		* наличие разреза размера не менее заданного в неориентированном графе;
	* возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;		* возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;

.obj: /* NP-полные задачи */

2016-09-17T13:35:19Z

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

← Предыдущая версия		Версия от 13:35, 17 сентября 2016
Строка 11:		Строка 11:
	* наличие гамильтонова пути в ориентированном графе;		* наличие гамильтонова пути в ориентированном графе;
	* наличие гамильтонова цикла в ориентированном графе;		* наличие гамильтонова цикла в ориентированном графе;
	* существование раскраски графа в ''k'' цветов, такой что никакие две смежные вершины не окрашены в один цвет (''k'' > ~~2 ---~~ константа);		* существование раскраски графа в ''k'' цветов, такой что никакие две смежные вершины не окрашены в один цвет (''k'' > — константа);
	* наличие разреза размера не менее заданного в неориентированном графе;		* наличие разреза размера не менее заданного в неориентированном графе;
	* возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;		* возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;

.obj: /* NP-полные задачи */

2016-09-17T13:35:00Z

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

← Предыдущая версия		Версия от 13:35, 17 сентября 2016
Строка 11:		Строка 11:
	* наличие гамильтонова пути в ориентированном графе;		* наличие гамильтонова пути в ориентированном графе;
	* наличие гамильтонова цикла в ориентированном графе;		* наличие гамильтонова цикла в ориентированном графе;
	* существование раскраски графа в ~~три цвета~~, такой что никакие две смежные вершины не окрашены в один цвет;		* существование раскраски графа в ''k'' цветов, такой что никакие две смежные вершины не окрашены в один цвет (''k'' > 2 --- константа);
	* наличие разреза размера не менее заданного в неориентированном графе;		* наличие разреза размера не менее заданного в неориентированном графе;
	* возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;		* возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;

.obj: /* NP-полные задачи */

2016-09-17T13:33:44Z

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

← Предыдущая версия		Версия от 13:33, 17 сентября 2016
Строка 14:		Строка 14:
	* наличие разреза размера не менее заданного в неориентированном графе;		* наличие разреза размера не менее заданного в неориентированном графе;
	* возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;		* возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;
	* задача о расписании экзаменов: можно ли провести ''k'' экзаменов за n пар так, чтобы ни одному из m студентов не пришлось сдавать два экзамена одновременно? (для каждого студента указаны экзамены, которые ему нужно сдать; на проведение одного экзамена достаточно одной пары);		* задача о расписании экзаменов: можно ли провести ''k'' экзаменов за ''n'' пар так, чтобы ни одному из ''m'' студентов не пришлось сдавать два экзамена одновременно? (для каждого студента указаны экзамены, которые ему нужно сдать; на проведение одного экзамена достаточно одной пары);
	* задача о сумме подмножества;		* задача о сумме подмножества;
	* задача о рюкзаке.		* задача о рюкзаке.

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

.obj: /* NP-полные задачи */

2016-09-17T13:33:26Z

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

← Предыдущая версия		Версия от 13:33, 17 сентября 2016
Строка 14:		Строка 14:
	* наличие разреза размера не менее заданного в неориентированном графе;		* наличие разреза размера не менее заданного в неориентированном графе;
	* возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;		* возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;
			* задача о расписании экзаменов: можно ли провести ''k'' экзаменов за n пар так, чтобы ни одному из m студентов не пришлось сдавать два экзамена одновременно? (для каждого студента указаны экзамены, которые ему нужно сдать; на проведение одного экзамена достаточно одной пары);
	* задача о сумме подмножества;		* задача о сумме подмножества;
	* задача о рюкзаке.		* задача о рюкзаке.

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

.obj: /* NP-полные задачи */

2016-09-14T14:15:28Z

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

← Предыдущая версия		Версия от 14:15, 14 сентября 2016
Строка 8:		Строка 8:
	* существование клики заданного размера в графе;		* существование клики заданного размера в графе;
	* существование вершинного покрытия заданного размера в графе;		* существование вершинного покрытия заданного размера в графе;
			* существование независимого множества заданного размера в графе;
	* наличие гамильтонова пути в ориентированном графе;		* наличие гамильтонова пути в ориентированном графе;
	* наличие гамильтонова цикла в ориентированном графе;		* наличие гамильтонова цикла в ориентированном графе;

.obj: Новая страница: «=NP-полные задачи= На лекциях и семинарах обсуждалась NP-полнота следующих задач: * выполн…»

2016-09-14T14:14:43Z

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

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

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

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

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

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