Алгоритмы и структуры данных семинары 155-2

Первый семинар 11.01.2016

Рекурсия и ханойские башни. Другие применения рекурсии. Анализ сложности алгоритмов.

Второй семинар 13.01.2016

Основы амортизационного анализа: банковский метод, метод потенциалов. k-битовый счетчик. Вектор или массив переменного размера.

Третий семинар 18.01.2016

Понятие асимптотики. О-исчисление. Решение теоретических задач.

Четвертый семинар 20.01.2016

Merge, сортировка слиянием, partition, быстрая сортировка. Практика. Реализация сортировок. https://official.contest.yandex.ru/contest/2007/

Пятый семинар 25.01.2016

Порядковые статистики. Алгоритм и анализ сложности. Практика. Реализация сортировок. https://official.contest.yandex.ru/contest/2007/

Шестой семинар 27.01.2016

Основная теорема о рекуррентных асимптотических соотношениях. Маленькая самостоятельная работа на асимптотики.

Седьмой семинар 01.02.2016

Devide and conquer! Примеры применения: сортировки, выпуклая оболочка, бинарный поиск. Примеры невозможности решения задачи этим методом: остовное дерево. Анализ сложности полученных алгоритмов.

Восьмой семинар 03.02.2016

Динамическое программирование. Типы динамики: одномерная и многомерная, восходящая и нисходящая, ленивая и явная. Решение задачи максимального пути по таблице всеми возможными способами.

Девятый семинар 08.02.2016

Динамическое программирование. Общий подход к решению задач методом динамического программирования. Практика по решению задач. https://official.contest.yandex.ru/contest/2185/

Десятый семинар 10.02.2016

Динамическое программирование. Практика по решению задач. https://official.contest.yandex.ru/contest/2185/

Одиннадцатый семинар 15.02.2016

Графы. Представление графов в памяти: матрицы смежности, списки смежности, список ребер. Виды графов: ориентированные и нет, с петлями и без них, с кратными ребрами и без них. Обходы графов. Обход в глубину. Реализация обхода в глубину. Связность графа. Число компонент связности.

Двенадцатый семинар 17.02.2016

Графы. Обход в глубину. Топологическая сортировка. Практика по решению задач. https://official.contest.yandex.ru/contest/2218/

Тринадцатый семинар 22.02.2016

Графы. Обход в ширину. Поиск кратчайших расстояний в невзвешенных графах. Практика по решению задач. https://official.contest.yandex.ru/contest/2243/

Четырнадцатый семинар 24.02.2016

Обход в ширину. 0-kBFS. Практика по решению задач. https://official.contest.yandex.ru/contest/2243/

Пятнадцатый семинар 29.02.2016

Алгоритм Деикстры. Описание, обоснование корректности. Оценка времени работы. Реализация с кучей и без кучи.

Шестнадцатый семинар 02.03.2016

Алгоритм Деикстры. Практика по решению задач. https://official.contest.yandex.ru/contest/2270/

Семнадцатый семинар 09.03.2016

Алгоритмы Форда-Беллмана и Флойда. Практика по решению задач. https://official.contest.yandex.ru/contest/2270/

Восемнадцатый семинар 14.03.2016

Алгоритмы Форда-Беллмана и Флойда. Практика по решению задач. https://official.contest.yandex.ru/contest/2270/

Девятнадцатый семинар 16.03.2016

vector, stack, stack_max, queue, queue_max - построение и амортизационный анализ сложности работы. Методы амортизационного анализа - прямой подсчет и банковский метод.

Двадцатый семинар 21.03.2016

Хеш-функции, хеш-таблицы, метод разрешения коллизий методом цепочек. https://official.contest.yandex.ru/contest/2333/

Первое домашнее задание

Распределение задач:

Студенты	Сортировка-1	Сортировка-2	Асимптотика – 1	Асимптотика – 2	Асимптотика – 3	Рекуррентности – 1	Рекуррентности – 2
Артемьев Максим	Перевертыш	Гармония	2	4	1	7	8
Богдашевская Мария	Коллекционер Диего	Маляры	4	1	2	7	6
Бочкарева Мария	Коллекционер Диего	Маляры	3	8	4	3	1
Додихудоев Бехзод	Перевертыш	Гармония	2	8	4	5	6
Дурдыева Кумуш	Коллекционер Диего	Гармония	3	5	1	5	1
Журавлев Виталий	Коллекционер Диего	Гармония	7	3	4	7	2
Маркович Александр	Коллекционер Диего	Маляры	4	2	3	7	3
Салимов Фирдавс	Перевертыш	Маляры	3	1	4	7	8
Сердюков Иннокентий	Перевертыш	Маляры	1	5	1	4	1
Соловьев Алексей	Перевертыш	Гармония	7	1	4	8	5
Старков Александр	Перевертыш	Маляры	8	5	1	7	3
Тарасов Денис	Коллекционер Диего	Гармония	3	6	4	3	5
Третьяков Александр	Перевертыш	Гармония	5	2	4	8	4
Тумашова Анна	Коллекционер Диего	Маляры	7	1	3	8	4
Шибанкова Екатерина	Перевертыш	Маляры	2	6	1	2	6

О второй части домашнего задания будет сообщено дополнительно.

Сдавать домашние задания необходимо в AnyTask. Курс и задачи в нем вскоре появятся. Сдача происходит в формате PDF, так что изучайте основы LaTeX, они вам еще много раз пригодятся. Делайн по теории - 15 февраля.

Контест с дополнительными задачами: https://official.contest.yandex.ru/contest/2187/

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

Распределение задач:

Студенты	Динамика-1	Динамика-2	Графы-1	Графы-2
Артемьев Максим	1	2	1	1
Богдашевская Мария	2	1	1	1
Бочкарева Мария	1	1	2	1
Додихудоев Бехзод	2	2	2	2
Дурдыева Кумуш	1	1	2	1
Журавлев Виталий	1	2	2	2
Маркович Александр	2	2	1	1
Салимов Фирдавс	2	1	2	1
Сердюков Иннокентий	2	1	2	1
Соловьев Алексей	1	2	2	2
Старков Александр	1	2	1	1
Тарасов Денис	1	2	1	1
Третьяков Александр	1	1	1	2
Тумашова Анна	1	1	1	1
Шибанкова Екатерина	2	1	2	2

О второй части домашнего задания будет сообщено дополнительно.

Сдавать домашние задания необходимо в AnyTask, теория сдается в PDF. Делайн - 29 февраля. Дедлайн по второй части - 14 марта.

Третье домашнее задание

Распределение задач:

Студенты	Графы-1	Графы-2
Артемьев Максим	1	2
Богдашевская Мария	1	1
Бочкарева Мария	1	1
Додихудоев Бехзод	1	2
Дурдыева Кумуш	1	1
Журавлев Виталий	1	1
Маркович Александр	1	1
Салимов Фирдавс	1	1
Сердюков Иннокентий	1	1
Соловьев Алексей	1	2
Старков Александр	1	1
Тарасов Денис	1	1
Третьяков Александр	1	1
Тумашова Анна	1	1
Шибанкова Екатерина	1	2

Сдавать домашние задания необходимо в AnyTask, теория сдается в PDF. Дедлайн - 3 апреля.