Алгоритмы и структуры данных семинары 154-2 156-2 — различия между версиями
Aumnov (обсуждение | вклад) |
Aumnov (обсуждение | вклад) (→Семинары 15-18) |
||
Строка 47: | Строка 47: | ||
Обсуждали обход в ширину и в глубину на графах. Решали [https://official.contest.yandex.ru/contest/2218/enter/ контест на обход в глубину] и [https://official.contest.yandex.ru/contest/2243/enter/ контест на обход в ширину]. | Обсуждали обход в ширину и в глубину на графах. Решали [https://official.contest.yandex.ru/contest/2218/enter/ контест на обход в глубину] и [https://official.contest.yandex.ru/contest/2243/enter/ контест на обход в ширину]. | ||
+ | |||
+ | == Семинары 15-16 == | ||
+ | |||
+ | Обсуждали топологическую сортировку и вычисление компонент связности. | ||
+ | |||
+ | == Семинары 17-18 == | ||
+ | |||
+ | Обсуждали поиск путей и кратчайших путей в графе. Обсуждали алгоритмы Флойда-Уоршелла и Беллмана-Форда. | ||
+ | Начали решать [https://official.contest.yandex.ru/contest/2270/enter/ контест на кратчайшие пути]. | ||
+ | |||
+ | Также доступно несколько контестов по старым темам для тренировки: [https://official.contest.yandex.ru/contest/2210/enter/ контест по динамическому программированию] и [https://official.contest.yandex.ru/contest/2155/enter/ контест на стратегию "разделяй и властвуй"]. |
Версия 15:32, 8 марта 2016
Инвайт на AnyTask: CBXezV5 (действителен до 12 марта)
Содержание
Семинар 1
Тренировались в рекурсии на примере Ханойских башен. Задачи, нужно решить все, кроме 4.
Семинар 2
Разбирали, как тестировать программы на примере сортировки пузырьком: код.
Задачи:
- Доказать корректность работы сортировки пузырьком.
- Написать двоичный поиск с тестами как в примере выше. При этом функция должна быть реализована максимально абстрактно на шаблонах. После написания тестов и полной отладки задачу нужно сдать сюда. А потом еще и сдать задачу устно.
Семинар 3
Обсуждали разные сортировки (вставками, слиянием, быструю). Их нужно сдать в контест.
Семинар 4
Обсуждали асимптотики и O-символику. Начали решать листок.
Cеминары 5-6
Дорешивали старые задачи.
Семинары 7-8
Разбирали алгоритмы с лекций: выбор порядковой статистики и поиск пары ближайших точек.
Начали решать листок по рекуррентам.
Писали контрольную. Если вы плохо написали контрольную или пропустили ее, несданные задачи можно сдавать как обычный листок, но с частичным понижением оценки.
Семинары 9-10
Дорешивали старые задачи.
Семинары 11-12
Разбирали контест на дин. программирование, решали контест.
Семинары 13-14
Обсуждали редакционное расстояние. Его нужно запрограммировать здесь.
Обсуждали обход в ширину и в глубину на графах. Решали контест на обход в глубину и контест на обход в ширину.
Семинары 15-16
Обсуждали топологическую сортировку и вычисление компонент связности.
Семинары 17-18
Обсуждали поиск путей и кратчайших путей в графе. Обсуждали алгоритмы Флойда-Уоршелла и Беллмана-Форда. Начали решать контест на кратчайшие пути.
Также доступно несколько контестов по старым темам для тренировки: контест по динамическому программированию и контест на стратегию "разделяй и властвуй".