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

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

2016-10-22T14:21:19Z

Лекции

← Предыдущая версия		Версия от 14:21, 22 октября 2016
Строка 22:		Строка 22:
	* '''16 сентября.''' Соотношение классов NP и EXPTIME. Теорема об иерархии задач по времени. Полиномиальная иерархия: классы Σ<sub>''k''</sub>P и Π<sub>''k''</sub>P.		* '''16 сентября.''' Соотношение классов NP и EXPTIME. Теорема об иерархии задач по времени. Полиномиальная иерархия: классы Σ<sub>''k''</sub>P и Π<sub>''k''</sub>P.

	* '''20 сентября.''' Три подхода к решению NP-трудных задач: эффективные алгоритмы для частных случаев, эвристические алгоритмы, экспоненциальные алгоритмы, отличные от полного перебора. Точный алгоритм для поиска вершинного покрытия размера ''k'' в графе с ''m'' ребрами с временем работы ''O''(2<sup>''k''</sup>''m''). Локальный поиск: градиентный спуск и ~~алгоритма~~ Метрополиса, применение к задаче о вершинном покрытии. Имитация отжига.		* '''20 сентября.''' Три подхода к решению NP-трудных задач: эффективные алгоритмы для частных случаев, эвристические алгоритмы, экспоненциальные алгоритмы, отличные от полного перебора. Точный алгоритм для поиска вершинного покрытия размера ''k'' в графе с ''m'' ребрами с временем работы ''O''(2<sup>''k''</sup>''m''). Локальный поиск: градиентный спуск и алгоритм Метрополиса, применение к задаче о вершинном покрытии. Имитация отжига.

	* '''30 сентября.''' Приближенное решение задачи о максимальном разрезе. Эвристика Кернигана – Лина для определения соседних решений при поиске максимального разреза.		* '''30 сентября.''' Приближенное решение задачи о максимальном разрезе. Эвристика Кернигана – Лина для определения соседних решений при поиске максимального разреза.

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

2016-10-22T14:14:37Z

Лекции

← Предыдущая версия		Версия от 14:14, 22 октября 2016
Строка 12:		Строка 12:

	= Лекции =		= Лекции =
	* '''2 сентября.''' Детерминированная одноленточная машина Тьюринга. Детерминированная многоленточная машина Тьюринга. Имитация ~~многоклеточной~~ машины с временем работы ''t''(''n'') > ''n'' на одноленточной машине за время ''O''(''t''(''n'')<sup>2</sup>). Недетерминированная одноленточная машина Тьюринга. Время работы недетерминированной машины Тьюринга. Класс P: определение, примеры задач. Алгоритм верификации. Полиномиальная верифицируемость. Класс NP: определения через алгоритм верификации и недетерминированную машину Тьюринга, их эквивалентность, примеры задач. Класс coNP. Возможное соотношение классов.		* '''2 сентября.''' Детерминированная одноленточная машина Тьюринга. Детерминированная многоленточная машина Тьюринга. Имитация многоленточной машины с временем работы ''t''(''n'') > ''n'' на одноленточной машине за время ''O''(''t''(''n'')<sup>2</sup>). Недетерминированная одноленточная машина Тьюринга. Время работы недетерминированной машины Тьюринга. Класс P: определение, примеры задач. Алгоритм верификации. Полиномиальная верифицируемость. Класс NP: определения через алгоритм верификации и недетерминированную машину Тьюринга, их эквивалентность, примеры задач. Класс coNP. Возможное соотношение классов.

	* '''6 сентября.''' Полиномиальные сведения. NP-трудные и NP-полные задачи. Формулировка теоремы Кука – Левина. Сведение задачи 3SAT к задаче Not-All-Equal-3SAT.		* '''6 сентября.''' Полиномиальные сведения. NP-трудные и NP-полные задачи. Формулировка теоремы Кука – Левина. Сведение задачи 3SAT к задаче Not-All-Equal-3SAT.

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

2016-10-22T14:06:19Z

Лекции

← Предыдущая версия		Версия от 14:06, 22 октября 2016
Строка 37:		Строка 37:

	* '''18 октября.''' Рандомизированный и детерминированный алгоритмы для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ. Потоковые алгоритмы. Алгоритм SpaceSaving для поиска частых элементов в потоке.		* '''18 октября.''' Рандомизированный и детерминированный алгоритмы для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ. Потоковые алгоритмы. Алгоритм SpaceSaving для поиска частых элементов в потоке.

			* '''21 октября.''' Алгоритм Count-Min Sketch для поиска частых элементов в потоке. Переборные алгоритмы. Полиномиальная задержка, инкрементальная (кумулятивная) полиномиальная задержка, оценка времени работы алгоритма относительно комбинированного размера входа и выхода. Перечисление всех путей между двумя заданными вершинами в графе. Перечисление всех максимальных клик графа.

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

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

2016-10-18T11:33:53Z

Лекции

← Предыдущая версия		Версия от 11:33, 18 октября 2016
Строка 35:		Строка 35:

	* '''15 октября.''' Корректность 2-приближенного алгоритма кластеризации, минимизирующего максимальное внутрикластерное расстояние. Невозможность лучшего приближения для этой задачи. Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ.		* '''15 октября.''' Корректность 2-приближенного алгоритма кластеризации, минимизирующего максимальное внутрикластерное расстояние. Невозможность лучшего приближения для этой задачи. Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ.

			* '''18 октября.''' Рандомизированный и детерминированный алгоритмы для вычисления означивания переменных, делающего истинным не менее 7/8 всех дизъюнктов в 3-КНФ. Потоковые алгоритмы. Алгоритм SpaceSaving для поиска частых элементов в потоке.

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

.obj в 14:44, 17 октября 2016

2016-10-17T14:44:14Z

← Предыдущая версия		Версия от 14:44, 17 октября 2016
Строка 6:		Строка 6:

	'''Консультации:'''<br/>		'''Консультации:'''<br/>
	понедельник 18:00 – 20:00, к. 324<br />		понедельник 18:00 – 20:00, к. 324 '''(17 октября консультации не будет)'''<br />
	четверг 16:30 – 18:00, к. 324 (по предварительной договоренности)		четверг 16:30 – 18:00, к. 324 (по предварительной договоренности)

.obj: /* Второе домашнее задание */

2016-10-17T12:02:52Z

Второе домашнее задание

← Предыдущая версия		Версия от 12:02, 17 октября 2016
Строка 61:		Строка 61:

	# Предложите и реализуйте линейный алгоритм, вычисляющий паросочетание в произвольном неориентированном графе без весов, отличающееся по размеру от наибольшего (по размеру) паросочетания в этом графе не более, чем вдвое. Напомним, что паросочетанием называется подмножество ребер графа, в котором ни у каких двух ребер нет одинаковых вершин. Докажите корректность алгоритма. Формат входного файла: на первой строке — разделенные пробелом число вершин ''n'' и число ребер ''m'', на каждой следующей из ''m'' строк — разделенные пробелом номера вершин очередного ребра (от 1 до ''n'').		# Предложите и реализуйте линейный алгоритм, вычисляющий паросочетание в произвольном неориентированном графе без весов, отличающееся по размеру от наибольшего (по размеру) паросочетания в этом графе не более, чем вдвое. Напомним, что паросочетанием называется подмножество ребер графа, в котором ни у каких двух ребер нет одинаковых вершин. Докажите корректность алгоритма. Формат входного файла: на первой строке — разделенные пробелом число вершин ''n'' и число ребер ''m'', на каждой следующей из ''m'' строк — разделенные пробелом номера вершин очередного ребра (от 1 до ''n'').
	# Будем считать расстояние между двумя битовыми строками равным числу позиций, в которых значения битов у этих строк различаются. Например, расстояние между строками 10001 и 11011 равно двум, а между строками 10001 и 01010 — четырем. Требуется разбить заданный массив строк на максимально возможное число кластеров так, чтобы расстояние между строками из разных кластеров было не меньше трех. Например, для массива из файла [https://www.dropbox.com/s/8a53wv0gdxi9ibm/b7x5.txt?dl=0 b7x5.txt] такое число равно двум. Ориентируйтесь на следующие параметры входных данных: в массиве 200 тыс. 32-битовых строк ([https://www.dropbox.com/s/45g08yx7lr31yrm/b200000x32.txt?dl=0 пример]). Предложите и реализуйте эффективный алгоритм, решающий эту задачу, докажите его корректность и оцените время работы. Формат входного файла: на первой строке — разделенные пробелом число битовых строк ''n'' и число бит в строке ''m''; на каждой следующей из ''n'' строк — битовая строка, заданная последовательностью из ''m'' нулей и единиц (см. примеры по ссылкам выше).		# Будем считать расстояние между двумя битовыми строками равным числу позиций, в которых значения битов у этих строк различаются. Например, расстояние между строками 10001 и 11011 равно двум, а между строками 10001 и 01010 — четырем. Требуется разбить заданный массив строк на максимально возможное число кластеров так, чтобы расстояние между строками из разных кластеров было не меньше трех. Например, для массива из файла [https://www.dropbox.com/s/8a53wv0gdxi9ibm/b7x5.txt?dl=0 b7x5.txt] такое число равно двум. Ориентируйтесь на следующие параметры входных данных: в массиве 200 тыс. 32-битовых строк ([https://www.dropbox.com/s/45g08yx7lr31yrm/b200000x32.txt?dl=0 пример]). Предложите и реализуйте эффективный алгоритм, решающий эту задачу, докажите его корректность и оцените время работы. Формат входного файла: на первой строке — разделенные пробелом число битовых строк ''n'' и число бит в строке ''m''; на каждой следующей из ''n'' строк — битовая строка, заданная последовательностью из ''m'' нулей и единиц (см. примеры по ссылкам выше). Алгоритм должен вычислять число кластеров, сами кластеры возвращать не нужно.

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

2016-10-16T10:24:03Z

Лекции

← Предыдущая версия		Версия от 10:24, 16 октября 2016
Строка 34:		Строка 34:
	* '''14 октября.''' NP-трудность кластеризации, минимизирующей максимальное внутрикластерное расстояние. Приближенный алгоритм кластеризации, минимизирующий максимальное внутрикластерное расстояние. Приближенное решение задачи коммивояжера.		* '''14 октября.''' NP-трудность кластеризации, минимизирующей максимальное внутрикластерное расстояние. Приближенный алгоритм кластеризации, минимизирующий максимальное внутрикластерное расстояние. Приближенное решение задачи коммивояжера.

	* '''15 октября.''' Корректность 2-приближенного алгоритма кластеризации, ~~минимизирующий~~ максимальное внутрикластерное расстояние. Невозможность лучшего приближения для этой задачи. Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ.		* '''15 октября.''' Корректность 2-приближенного алгоритма кластеризации, минимизирующего максимальное внутрикластерное расстояние. Невозможность лучшего приближения для этой задачи. Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ.

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

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

2016-10-16T10:23:27Z

Лекции

← Предыдущая версия		Версия от 10:23, 16 октября 2016
Строка 31:		Строка 31:

	* '''11 октября.''' Анализ приближенного алгоритма сегментации изображений на несколько классов. Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние.		* '''11 октября.''' Анализ приближенного алгоритма сегментации изображений на несколько классов. Кластеризация на основе минимального остовного дерева, максимизирующая минимальное межкластерное расстояние.

			* '''14 октября.''' NP-трудность кластеризации, минимизирующей максимальное внутрикластерное расстояние. Приближенный алгоритм кластеризации, минимизирующий максимальное внутрикластерное расстояние. Приближенное решение задачи коммивояжера.

			* '''15 октября.''' Корректность 2-приближенного алгоритма кластеризации, минимизирующий максимальное внутрикластерное расстояние. Невозможность лучшего приближения для этой задачи. Рандомизированные алгоритмы. Монте-Карло и Лас-Вегас. Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ.

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

.obj: /* Второе домашнее задание */

2016-10-16T10:12:38Z

Второе домашнее задание

← Предыдущая версия		Версия от 10:12, 16 октября 2016
Строка 57:		Строка 57:

	# Предложите и реализуйте линейный алгоритм, вычисляющий паросочетание в произвольном неориентированном графе без весов, отличающееся по размеру от наибольшего (по размеру) паросочетания в этом графе не более, чем вдвое. Напомним, что паросочетанием называется подмножество ребер графа, в котором ни у каких двух ребер нет одинаковых вершин. Докажите корректность алгоритма. Формат входного файла: на первой строке — разделенные пробелом число вершин ''n'' и число ребер ''m'', на каждой следующей из ''m'' строк — разделенные пробелом номера вершин очередного ребра (от 1 до ''n'').		# Предложите и реализуйте линейный алгоритм, вычисляющий паросочетание в произвольном неориентированном графе без весов, отличающееся по размеру от наибольшего (по размеру) паросочетания в этом графе не более, чем вдвое. Напомним, что паросочетанием называется подмножество ребер графа, в котором ни у каких двух ребер нет одинаковых вершин. Докажите корректность алгоритма. Формат входного файла: на первой строке — разделенные пробелом число вершин ''n'' и число ребер ''m'', на каждой следующей из ''m'' строк — разделенные пробелом номера вершин очередного ребра (от 1 до ''n'').
	# Будем считать расстояние между двумя битовыми строками равным числу позиций, в которых значения битов у этих строк различаются. Например, расстояние между строками 10001 и 11011 равно двум, а между строками 10001 и 01010 — четырем. Требуется разбить заданный массив строк на максимально возможное число кластеров так, чтобы расстояние между строками из разных кластеров было не меньше трех. Например, для массива из файла [https://www.dropbox.com/s/8a53wv0gdxi9ibm/b7x5.txt?dl=0 b7x5.txt] такое число равно двум. Ориентируйтесь на следующие параметры входных данных: в массиве 200 тыс. 32-битовых строк ([https://www.dropbox.com/s/45g08yx7lr31yrm/b200000x32.txt?dl=0 пример]). Предложите и реализуйте алгоритм, решающий эту задачу, докажите его корректность и оцените время работы. Формат входного файла: на первой строке — разделенные пробелом число битовых строк ''n'' и число бит в строке ''m''; на каждой следующей из ''n'' строк — битовая строка, заданная последовательностью из ''m'' нулей и единиц (см. примеры по ссылкам выше).		# Будем считать расстояние между двумя битовыми строками равным числу позиций, в которых значения битов у этих строк различаются. Например, расстояние между строками 10001 и 11011 равно двум, а между строками 10001 и 01010 — четырем. Требуется разбить заданный массив строк на максимально возможное число кластеров так, чтобы расстояние между строками из разных кластеров было не меньше трех. Например, для массива из файла [https://www.dropbox.com/s/8a53wv0gdxi9ibm/b7x5.txt?dl=0 b7x5.txt] такое число равно двум. Ориентируйтесь на следующие параметры входных данных: в массиве 200 тыс. 32-битовых строк ([https://www.dropbox.com/s/45g08yx7lr31yrm/b200000x32.txt?dl=0 пример]). Предложите и реализуйте эффективный алгоритм, решающий эту задачу, докажите его корректность и оцените время работы. Формат входного файла: на первой строке — разделенные пробелом число битовых строк ''n'' и число бит в строке ''m''; на каждой следующей из ''n'' строк — битовая строка, заданная последовательностью из ''m'' нулей и единиц (см. примеры по ссылкам выше).


	За теоретическое решение каждой задачи можно получить до четырех баллов. При наличии теоретического решения задачи, за ее практическую реализацию можно получить еще до четырех баллов. Разумеется, оценка за все домашнее задание — не более десяти баллов.		За теоретическое решение каждой задачи можно получить до четырех баллов. При наличии теоретического решения задачи за ее практическую реализацию можно получить еще до четырех баллов. Во второй задаче теоретическое решение без практической реализации засчитывается только, если предложенный алгоритм применим на практике к данным указанных размеров. Разумеется, оценка за все домашнее задание — не более десяти баллов.

	Срок выполнения — вечер 22 октября.		Срок выполнения — вечер 22 октября.

.obj: /* Второе домашнее задание */

2016-10-16T10:03:34Z

Второе домашнее задание

← Предыдущая версия		Версия от 10:03, 16 октября 2016
Строка 56:		Строка 56:
	==Второе домашнее задание==		==Второе домашнее задание==

	# Предложите и реализуйте линейный алгоритм, вычисляющий паросочетание в произвольном неориентированном графе без весов, отличающееся по размеру от наибольшего (по размеру) паросочетания в этом графе не более, чем вдвое. Докажите корректность алгоритма.		# Предложите и реализуйте линейный алгоритм, вычисляющий паросочетание в произвольном неориентированном графе без весов, отличающееся по размеру от наибольшего (по размеру) паросочетания в этом графе не более, чем вдвое. Напомним, что паросочетанием называется подмножество ребер графа, в котором ни у каких двух ребер нет одинаковых вершин. Докажите корректность алгоритма. Формат входного файла: на первой строке — разделенные пробелом число вершин ''n'' и число ребер ''m'', на каждой следующей из ''m'' строк — разделенные пробелом номера вершин очередного ребра (от 1 до ''n'').
	# Будем считать расстояние между двумя битовыми строками равным числу позиций, в которых значения битов у этих строк различаются. Например, расстояние между строками 10001 и 11011 равно двум, а между строками 10001 и 01010 — четырем. Требуется разбить заданный массив строк на максимально возможное число кластеров так, чтобы расстояние между строками из разных кластеров было не меньше трех. Например, для массива из файла [https://www.dropbox.com/s/8a53wv0gdxi9ibm/b7x5.txt?dl=0 b7x5.txt] такое число равно двум. Ориентируйтесь на следующие параметры входных данных: в массиве 200 тыс. 32-битовых строк ([https://www.dropbox.com/s/45g08yx7lr31yrm/b200000x32.txt?dl=0 пример]). Предложите и реализуйте алгоритм, решающий эту задачу, докажите его корректность и оцените время работы. Формат входного файла: на первой строке — разделенные пробелом число битовых строк и число бит в строке; на каждой следующей ~~строке~~ — битовая строка, заданная последовательностью нулей и единиц (см. примеры по ссылкам выше).		# Будем считать расстояние между двумя битовыми строками равным числу позиций, в которых значения битов у этих строк различаются. Например, расстояние между строками 10001 и 11011 равно двум, а между строками 10001 и 01010 — четырем. Требуется разбить заданный массив строк на максимально возможное число кластеров так, чтобы расстояние между строками из разных кластеров было не меньше трех. Например, для массива из файла [https://www.dropbox.com/s/8a53wv0gdxi9ibm/b7x5.txt?dl=0 b7x5.txt] такое число равно двум. Ориентируйтесь на следующие параметры входных данных: в массиве 200 тыс. 32-битовых строк ([https://www.dropbox.com/s/45g08yx7lr31yrm/b200000x32.txt?dl=0 пример]). Предложите и реализуйте алгоритм, решающий эту задачу, докажите его корректность и оцените время работы. Формат входного файла: на первой строке — разделенные пробелом число битовых строк ''n'' и число бит в строке ''m''; на каждой следующей из ''n'' строк — битовая строка, заданная последовательностью из ''m'' нулей и единиц (см. примеры по ссылкам выше).