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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

Первый семинар 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/

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

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

Студенты Сортировка-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 марта.