Алгоритмы и структуры данных семинары 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/

Двадцать первый семинар 04.04.2016

Тест по материалам первого модуля. https://yadi.sk/i/t-lK2on5qn53L

Двадцать второй семинар 06.04.2016

Разбор теста. Разбор домашнего задания. Классические деревья поиска, типичная Си реализация. https://yadi.sk/d/MbRJhW2xqn4jH

Двадцать третий семинар 11.04.2016

Юнит-тестирование деревьев поиска. Красно-черное дерево. Свойства красно-черного дерева. Один из случаев вставки в красно-черное дерево. https://yadi.sk/d/DVuJlkT8qtqV3

Двадцать четвертый семинар 13.04.2016

Вставка в красно-черное дерево. Проверка дерева на красно-черность. Практика по решению задач. https://official.contest.yandex.ru/contest/2381/

Двадцать пятый семинар 18.04.2016

Практика по решению задач. https://official.contest.yandex.ru/contest/2381/

Двадцать шестой семинар 20.04.2016

RMQ, RSQ, реализация на дереве отрезков. Рекурсивная реализация дерева отрезков на основе массива. Ленивые вычисления. Ленивое присвоение в дереве отрезков.

Двадцать седьмой семинар 25.04.2016

Минимальные остовные деревья. Алгоритм Крускала. Генерация лабиринтов.

Двадцать восьмой семинар 27.04.2016

DSU. Интерфейс, реализация, эвристика сжатия путей, ранговая эвристика. Применение в минимальных оставных деревьях. Генерация лабиринтов.

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

Разбор задачи про хеширование чисел Фиббоначчи. Минимальные остовные деревья. Алгоритм Прима. Приближенное решение задачи коммивояжера. Практика по решению задач. https://official.contest.yandex.ru/contest/2464/

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

Жадные алгоритмы. Решение теоретических задач.

Тридцать первый семинар 18.05.2016

Матроид. Жадные алгоритмы на матроиде. Решение теоретических задач.

Тридцать второй семинар 23.05.2016

Конечный автомат. Способы задания конечного автомата. Разница ДКА и НКА.

Тридцать третий семинар 30.05.2016

НКА, сведение к ДКА. Алгоритм построения минимального ДКА, эквивалентного данному.

Тридцать четвертый семинар 01.06.2016

Контекстно-свободные грамматики, нормальная форма Хомского.

Тридцать пятый семинар 06.06.2016

Сети, потоки, максимальный поток. Практика по решению задач. https://official.contest.yandex.ru/contest/2531/

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

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

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

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

Дедлайн по второй части - 26 апреля. Как обычно, сдаем в anytask, теоретическую часть присылаем в pdf.

Медленное решение задачи А1 https://yadi.sk/i/xipVWP0HrgZDq

Четвертое домашнее задание

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

Студенты	Ртуть	Электросхема	Дерево
Артемьев Максим	1	2	1
Богдашевская Мария	1	2	1
Бочкарева Мария	1	1	1
Додихудоев Бехзод	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	1
Тумашова Анна	1	2	1
Шибанкова Екатерина	1	1	1

Пятое домашнее задание

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

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

Контрольная работа

https://official.contest.yandex.ru/contest/2558

Оценки

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

Частичные баллы проставлены исходя из того, сколько ошибок надо было исправить, чтобы код заработал. Советую вам попробовать разобраться и доделать-таки задачу, это полезно.

За полные решения я немного понизил баллы за качество кода. Помните: чем более структурировано ваше решение, тем проще искать в нем ошибку.

Итоги

В таблице https://docs.google.com/spreadsheets/d/1JO-tZOPb4rJupnNsx8XozAGWc5hCiWk3CEdk2MP5c9k/edit?usp=sharing