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

.obj в 15:55, 20 октября 2019

2019-10-20T15:55:55Z

← Предыдущая версия		Версия от 15:55, 20 октября 2019
Строка 76:		Строка 76:
	== Письменный тест ==		== Письменный тест ==
	Письменный тест состоится 1 октября в 9:00 – 10:30. Группы 185-1, 186 и 187 пишут тест в ауд. R404, прочие группы — в аудиториях, указанных в расписании.		Письменный тест состоится 1 октября в 9:00 – 10:30. Группы 185-1, 186 и 187 пишут тест в ауд. R404, прочие группы — в аудиториях, указанных в расписании.

			=Экзамен=
			Экзамен пройдет 21 октября в 9:00 – 11:50 в ауд. R204 (группы 182, 184 и 185) и ауд. R205 (группы 186, 187 и 188). Экзамен — письменный. С собой на экзамен можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается.

			Показ работ — 23 октября в 9:00 – 9:50 в ауд. R407.

	= Оценки =		= Оценки =

.obj: /* Лекции */

2019-10-19T19:08:09Z

Лекции

← Предыдущая версия		Версия от 19:08, 19 октября 2019
Строка 32:		Строка 32:
	# '''11 октября.''' Потоковые алгоритмы. Алгоритмы SpaceSaving и Count-Min Sketch для поиска частых элементов в потоке.		# '''11 октября.''' Потоковые алгоритмы. Алгоритмы SpaceSaving и Count-Min Sketch для поиска частых элементов в потоке.
	# '''14 октября.''' Эффективное перечисление решений. Полиномиальная задержка, инкрементальная (кумулятивная) полиномиальная задержка, оценка времени работы алгоритма относительно комбинированного размера входа и выхода. [https://www.dropbox.com/s/mfebtpkl1dfuvvf/algo2-13-enumeration.pdf?dl=0 Перечисление всех путей между двумя заданными вершинами в графе.] Перечисление всех максимальных (по вложению) клик графа.		# '''14 октября.''' Эффективное перечисление решений. Полиномиальная задержка, инкрементальная (кумулятивная) полиномиальная задержка, оценка времени работы алгоритма относительно комбинированного размера входа и выхода. [https://www.dropbox.com/s/mfebtpkl1dfuvvf/algo2-13-enumeration.pdf?dl=0 Перечисление всех путей между двумя заданными вершинами в графе.] Перечисление всех максимальных (по вложению) клик графа.
	# [https://www.dropbox.com/s/~~a56j7nvqjqkwn7y~~/~~algo2sample~~.pdf?dl=0 18 октября.] Задачи для подготовки к экзамену.		# [https://www.dropbox.com/s/8uuueyzonjo7jya/algo2-14-problems.pdf?dl=0 18 октября.] Задачи для подготовки к экзамену.

	= Домашние задания =		= Домашние задания =

.obj: /* Лекции */

2019-10-17T17:43:20Z

Лекции

← Предыдущая версия		Версия от 17:43, 17 октября 2019
Строка 32:		Строка 32:
	# '''11 октября.''' Потоковые алгоритмы. Алгоритмы SpaceSaving и Count-Min Sketch для поиска частых элементов в потоке.		# '''11 октября.''' Потоковые алгоритмы. Алгоритмы SpaceSaving и Count-Min Sketch для поиска частых элементов в потоке.
	# '''14 октября.''' Эффективное перечисление решений. Полиномиальная задержка, инкрементальная (кумулятивная) полиномиальная задержка, оценка времени работы алгоритма относительно комбинированного размера входа и выхода. [https://www.dropbox.com/s/mfebtpkl1dfuvvf/algo2-13-enumeration.pdf?dl=0 Перечисление всех путей между двумя заданными вершинами в графе.] Перечисление всех максимальных (по вложению) клик графа.		# '''14 октября.''' Эффективное перечисление решений. Полиномиальная задержка, инкрементальная (кумулятивная) полиномиальная задержка, оценка времени работы алгоритма относительно комбинированного размера входа и выхода. [https://www.dropbox.com/s/mfebtpkl1dfuvvf/algo2-13-enumeration.pdf?dl=0 Перечисление всех путей между двумя заданными вершинами в графе.] Перечисление всех максимальных (по вложению) клик графа.
			# [https://www.dropbox.com/s/a56j7nvqjqkwn7y/algo2sample.pdf?dl=0 18 октября.] Задачи для подготовки к экзамену.

	= Домашние задания =		= Домашние задания =

.obj: /* Третье */

2019-10-15T13:46:15Z

Третье

← Предыдущая версия		Версия от 13:46, 15 октября 2019
Строка 71:		Строка 71:

	===Третье===		===Третье===
	[https://www.dropbox.com/s/wfgjj00yycvkiyf/algo2-clustering.pdf?dl=0 Описание задания], [https://www.dropbox.com/s/h2f2e6gukzyxxz7/task.zip?dl=0 заготовка кода и тестовые данные] к нему. Срок сдачи — 18 ~~сентября~~, 9:00.		[https://www.dropbox.com/s/wfgjj00yycvkiyf/algo2-clustering.pdf?dl=0 Описание задания], [https://www.dropbox.com/s/h2f2e6gukzyxxz7/task.zip?dl=0 заготовка кода и тестовые данные] к нему. Срок сдачи — 18 октября, 9:00.

	== Письменный тест ==		== Письменный тест ==

.obj: /* Лекции */

2019-10-14T17:30:21Z

Лекции

← Предыдущая версия		Версия от 17:30, 14 октября 2019
Строка 31:		Строка 31:
	# '''7 октября.''' Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ. Рандомизированный алгоритм для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ, его дерандомизация.		# '''7 октября.''' Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ. Рандомизированный алгоритм для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ, его дерандомизация.
	# '''11 октября.''' Потоковые алгоритмы. Алгоритмы SpaceSaving и Count-Min Sketch для поиска частых элементов в потоке.		# '''11 октября.''' Потоковые алгоритмы. Алгоритмы SpaceSaving и Count-Min Sketch для поиска частых элементов в потоке.
	# '''14 октября.''' Эффективное перечисление решений. Полиномиальная задержка, инкрементальная (кумулятивная) полиномиальная задержка, оценка времени работы алгоритма относительно комбинированного размера входа и выхода. [https://www.dropbox.com/s/mfebtpkl1dfuvvf/algo2-13-enumeration.pdf?dl=0 Перечисление всех путей между двумя заданными вершинами в графе.] Перечисление всех максимальных клик графа.		# '''14 октября.''' Эффективное перечисление решений. Полиномиальная задержка, инкрементальная (кумулятивная) полиномиальная задержка, оценка времени работы алгоритма относительно комбинированного размера входа и выхода. [https://www.dropbox.com/s/mfebtpkl1dfuvvf/algo2-13-enumeration.pdf?dl=0 Перечисление всех путей между двумя заданными вершинами в графе.] Перечисление всех максимальных (по вложению) клик графа.

	= Домашние задания =		= Домашние задания =

.obj: /* Лекции */

2019-10-14T17:29:48Z

Лекции

← Предыдущая версия		Версия от 17:29, 14 октября 2019
Строка 31:		Строка 31:
	# '''7 октября.''' Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ. Рандомизированный алгоритм для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ, его дерандомизация.		# '''7 октября.''' Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ. Рандомизированный алгоритм для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ, его дерандомизация.
	# '''11 октября.''' Потоковые алгоритмы. Алгоритмы SpaceSaving и Count-Min Sketch для поиска частых элементов в потоке.		# '''11 октября.''' Потоковые алгоритмы. Алгоритмы SpaceSaving и Count-Min Sketch для поиска частых элементов в потоке.
			# '''14 октября.''' Эффективное перечисление решений. Полиномиальная задержка, инкрементальная (кумулятивная) полиномиальная задержка, оценка времени работы алгоритма относительно комбинированного размера входа и выхода. [https://www.dropbox.com/s/mfebtpkl1dfuvvf/algo2-13-enumeration.pdf?dl=0 Перечисление всех путей между двумя заданными вершинами в графе.] Перечисление всех максимальных клик графа.

	= Домашние задания =		= Домашние задания =

.obj: /* Задания на программирование */

2019-10-11T21:58:42Z

Задания на программирование

← Предыдущая версия		Версия от 21:58, 11 октября 2019
Строка 68:		Строка 68:

	Видны ли отличия в качестве кластеризации визуально? Соответствует ли меньшее значение штрафа интуитивно лучшей кластеризации?		Видны ли отличия в качестве кластеризации визуально? Соответствует ли меньшее значение штрафа интуитивно лучшей кластеризации?

			===Третье===
			[https://www.dropbox.com/s/wfgjj00yycvkiyf/algo2-clustering.pdf?dl=0 Описание задания], [https://www.dropbox.com/s/h2f2e6gukzyxxz7/task.zip?dl=0 заготовка кода и тестовые данные] к нему. Срок сдачи — 18 сентября, 9:00.

	== Письменный тест ==		== Письменный тест ==

.obj: /* Домашние задания */

2019-10-11T17:27:10Z

Домашние задания

← Предыдущая версия		Версия от 17:27, 11 октября 2019
Строка 35:		Строка 35:
	[https://official.contest.yandex.ru/contest/13942 Первое домашнее задание]: 13 – 29 сентября.		[https://official.contest.yandex.ru/contest/13942 Первое домашнее задание]: 13 – 29 сентября.

	[https://official.contest.yandex.ru/contest/14358 Второе домашнее задание]: 27 сентября — 15 октября. Третья задача ~~будет~~ добавлена ~~позже~~.		[https://official.contest.yandex.ru/contest/14358 Второе домашнее задание]: 27 сентября — 15 октября. (Третья задача уже добавлена.)

	= Аудиторная работа =		= Аудиторная работа =

.obj: /* Лекции */

2019-10-11T10:38:53Z

Лекции

← Предыдущая версия		Версия от 10:38, 11 октября 2019
Строка 30:		Строка 30:
	# [https://www.dropbox.com/s/w6kfnslk78sw49d/algo2-10-sat.pdf?dl=0 5 октября.] Теорема Кука – Левина.		# [https://www.dropbox.com/s/w6kfnslk78sw49d/algo2-10-sat.pdf?dl=0 5 октября.] Теорема Кука – Левина.
	# '''7 октября.''' Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ. Рандомизированный алгоритм для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ, его дерандомизация.		# '''7 октября.''' Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ. Рандомизированный алгоритм для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ, его дерандомизация.
			# '''11 октября.''' Потоковые алгоритмы. Алгоритмы SpaceSaving и Count-Min Sketch для поиска частых элементов в потоке.

	= Домашние задания =		= Домашние задания =

.obj: /* Лекции */

2019-10-07T23:39:43Z

Лекции

← Предыдущая версия		Версия от 23:39, 7 октября 2019
Строка 29:		Строка 29:
	# '''4 октября.''' Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние. NP-трудность кластеризации, минимизирующей максимальное внутрикластерное расстояние. Приближенный алгоритм кластеризации, минимизирующий максимальное внутрикластерное расстояние. Невозможность лучшего приближения для этой задачи (если P ≠ NP).		# '''4 октября.''' Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние. NP-трудность кластеризации, минимизирующей максимальное внутрикластерное расстояние. Приближенный алгоритм кластеризации, минимизирующий максимальное внутрикластерное расстояние. Невозможность лучшего приближения для этой задачи (если P ≠ NP).
	# [https://www.dropbox.com/s/w6kfnslk78sw49d/algo2-10-sat.pdf?dl=0 5 октября.] Теорема Кука – Левина.		# [https://www.dropbox.com/s/w6kfnslk78sw49d/algo2-10-sat.pdf?dl=0 5 октября.] Теорема Кука – Левина.
			# '''7 октября.''' Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ. Рандомизированный алгоритм для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ, его дерандомизация.

	= Домашние задания =		= Домашние задания =