Алгоритмы и структуры данных семинары 155-2 — различия между версиями
Melnichuk (обсуждение | вклад) (→Двадцать второй семинар 06.04.2016) |
Melnichuk (обсуждение | вклад) (→Двадцать пятый семинар 18.04.2016) |
||
Строка 126: | Строка 126: | ||
===Двадцать пятый семинар 18.04.2016=== | ===Двадцать пятый семинар 18.04.2016=== | ||
+ | Практика по решению задач. https://official.contest.yandex.ru/contest/2381/ | ||
===Первое домашнее задание=== | ===Первое домашнее задание=== |
Версия 10:43, 18 апреля 2016
Содержание
- 1 Первый семинар 11.01.2016
- 2 Второй семинар 13.01.2016
- 3 Третий семинар 18.01.2016
- 4 Четвертый семинар 20.01.2016
- 5 Пятый семинар 25.01.2016
- 6 Шестой семинар 27.01.2016
- 7 Седьмой семинар 01.02.2016
- 8 Восьмой семинар 03.02.2016
- 9 Девятый семинар 08.02.2016
- 10 Десятый семинар 10.02.2016
- 11 Одиннадцатый семинар 15.02.2016
- 12 Двенадцатый семинар 17.02.2016
- 13 Тринадцатый семинар 22.02.2016
- 14 Четырнадцатый семинар 24.02.2016
- 15 Пятнадцатый семинар 29.02.2016
- 16 Шестнадцатый семинар 02.03.2016
- 17 Семнадцатый семинар 09.03.2016
- 18 Восемнадцатый семинар 14.03.2016
- 19 Девятнадцатый семинар 16.03.2016
- 20 Двадцатый семинар 21.03.2016
- 21 Двадцать первый семинар 04.04.2016
- 22 Двадцать второй семинар 06.04.2016
- 23 Двадцать третий семинар 11.04.2016
- 24 Двадцать четвертый семинар 13.04.2016
- 25 Двадцать пятый семинар 18.04.2016
- 26 Первое домашнее задание
- 27 Второе домашнее задание
- 28 Третье домашнее задание
Первый семинар 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/
Первое домашнее задание
Распределение задач:
Студенты | Сортировка-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.