Алгоритмы и структуры данных семинары 154-2 156-2 — различия между версиями
Aumnov (обсуждение | вклад) (→Семинары 24-25) |
Aumnov (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| + | == Общая информация == | ||
| + | |||
Инвайт на AnyTask для 154-2: ixrgnZU (действителен до 20 марта) | Инвайт на AnyTask для 154-2: ixrgnZU (действителен до 20 марта) | ||
Инвайт на AnyTask для 156-2: yryF8xy (действителен до 20 марта) | Инвайт на AnyTask для 156-2: yryF8xy (действителен до 20 марта) | ||
| + | == Семинары == | ||
| − | == Семинар 1 == | + | === Семинар 1 === |
Тренировались в рекурсии на примере Ханойских башен. [https://www.dropbox.com/s/i21924ziqu6cayr/hanoi.pdf?dl=0 Задачи], нужно решить все, кроме 4. | Тренировались в рекурсии на примере Ханойских башен. [https://www.dropbox.com/s/i21924ziqu6cayr/hanoi.pdf?dl=0 Задачи], нужно решить все, кроме 4. | ||
| − | == Семинар 2 == | + | === Семинар 2 === |
Разбирали, как тестировать программы на примере сортировки пузырьком: [https://www.dropbox.com/s/mv0v7xy87ob0lx5/bubble_sort.cpp?dl=0 код]. | Разбирали, как тестировать программы на примере сортировки пузырьком: [https://www.dropbox.com/s/mv0v7xy87ob0lx5/bubble_sort.cpp?dl=0 код]. | ||
| Строка 16: | Строка 19: | ||
* Написать двоичный поиск с тестами как в примере выше. При этом функция должна быть реализована максимально абстрактно на шаблонах. После написания тестов и полной отладки задачу нужно сдать [http://informatics.mccme.ru/mod/statements/view3.php?id=192&chapterid=4 сюда]. А потом еще и сдать задачу устно. | * Написать двоичный поиск с тестами как в примере выше. При этом функция должна быть реализована максимально абстрактно на шаблонах. После написания тестов и полной отладки задачу нужно сдать [http://informatics.mccme.ru/mod/statements/view3.php?id=192&chapterid=4 сюда]. А потом еще и сдать задачу устно. | ||
| − | == Семинар 3 == | + | === Семинар 3 === |
Обсуждали разные сортировки (вставками, слиянием, быструю). Их нужно сдать в [https://official.contest.yandex.ru/contest/2007/enter/ контест]. | Обсуждали разные сортировки (вставками, слиянием, быструю). Их нужно сдать в [https://official.contest.yandex.ru/contest/2007/enter/ контест]. | ||
| − | == Семинар 4 == | + | === Семинар 4 === |
Обсуждали асимптотики и O-символику. Начали решать [https://www.dropbox.com/s/dt0p5oqfr8sgjpu/Asymptotic.pdf?dl=0 листок]. | Обсуждали асимптотики и O-символику. Начали решать [https://www.dropbox.com/s/dt0p5oqfr8sgjpu/Asymptotic.pdf?dl=0 листок]. | ||
| − | == Cеминары 5-6 == | + | === Cеминары 5-6 === |
Дорешивали старые задачи. | Дорешивали старые задачи. | ||
| − | == Семинары 7-8 == | + | === Семинары 7-8 === |
Разбирали алгоритмы с лекций: выбор порядковой статистики и поиск пары ближайших точек. | Разбирали алгоритмы с лекций: выбор порядковой статистики и поиск пары ближайших точек. | ||
| Строка 36: | Строка 39: | ||
Писали [https://www.dropbox.com/s/dli9d8wbbj4e6wk/Asymptotic.pdf?dl=0 контрольную.] Если вы плохо написали контрольную или пропустили ее, несданные задачи можно сдавать как обычный листок, но с частичным понижением оценки. | Писали [https://www.dropbox.com/s/dli9d8wbbj4e6wk/Asymptotic.pdf?dl=0 контрольную.] Если вы плохо написали контрольную или пропустили ее, несданные задачи можно сдавать как обычный листок, но с частичным понижением оценки. | ||
| − | == Семинары 9-10 == | + | === Семинары 9-10 === |
Дорешивали старые задачи. | Дорешивали старые задачи. | ||
| − | == Семинары 11-12 == | + | === Семинары 11-12 === |
Разбирали контест на дин. программирование, решали [https://official.contest.yandex.ru/contest/2185/enter/ контест]. | Разбирали контест на дин. программирование, решали [https://official.contest.yandex.ru/contest/2185/enter/ контест]. | ||
| − | == Семинары 13-14 == | + | === Семинары 13-14 === |
Обсуждали редакционное расстояние. Его нужно запрограммировать [https://official.contest.yandex.ru/contest/2206/enter/ здесь]. | Обсуждали редакционное расстояние. Его нужно запрограммировать [https://official.contest.yandex.ru/contest/2206/enter/ здесь]. | ||
| Строка 50: | Строка 53: | ||
Обсуждали обход в ширину и в глубину на графах. Решали [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 == | + | === Семинары 15-16 === |
Обсуждали топологическую сортировку и вычисление компонент связности. | Обсуждали топологическую сортировку и вычисление компонент связности. | ||
| − | == Семинары 17-20 == | + | === Семинары 17-20 === |
Обсуждали поиск путей и кратчайших путей в графе. Обсуждали алгоритмы Флойда-Уоршелла и Беллмана-Форда. | Обсуждали поиск путей и кратчайших путей в графе. Обсуждали алгоритмы Флойда-Уоршелла и Беллмана-Форда. | ||
| Строка 61: | Строка 64: | ||
Также доступно несколько контестов по старым темам для тренировки: [https://official.contest.yandex.ru/contest/2210/enter/ контест подсчет количества путей] и [https://official.contest.yandex.ru/contest/2155/enter/ контест на стратегию "разделяй и властвуй"]. | Также доступно несколько контестов по старым темам для тренировки: [https://official.contest.yandex.ru/contest/2210/enter/ контест подсчет количества путей] и [https://official.contest.yandex.ru/contest/2155/enter/ контест на стратегию "разделяй и властвуй"]. | ||
| − | == Семинары 21-22 == | + | === Семинары 21-22 === |
Обсуждали хеширование. | Обсуждали хеширование. | ||
| Строка 67: | Строка 70: | ||
Писали [https://www.dropbox.com/s/f32y5wra3jjpsjr/Mid-term.pdf?dl=0 контрольную работу]. Задачи, которые вы не решили на контрольной можно будет сдать на следующем семинаре (на нем же будет разбор). | Писали [https://www.dropbox.com/s/f32y5wra3jjpsjr/Mid-term.pdf?dl=0 контрольную работу]. Задачи, которые вы не решили на контрольной можно будет сдать на следующем семинаре (на нем же будет разбор). | ||
| − | == Семинары 23-24 == | + | === Семинары 23-24 === |
Разбирали контрольную работу. Обсуждали красно-черные деревья. | Разбирали контрольную работу. Обсуждали красно-черные деревья. | ||
| − | == Семинары 25-26 == | + | === Семинары 25-26 === |
Обсуждали деревья отрезков, динамические порядковые статистики, жадные алгоритмы, алгоритм Дейкстры. | Обсуждали деревья отрезков, динамические порядковые статистики, жадные алгоритмы, алгоритм Дейкстры. | ||
| Строка 78: | Строка 81: | ||
с ассистентом. [https://www.dropbox.com/s/mod3k3twslrbdvp/Mid-term-2nd-attempt.pdf?dl=0 Условия]. За каждую задачу | с ассистентом. [https://www.dropbox.com/s/mod3k3twslrbdvp/Mid-term-2nd-attempt.pdf?dl=0 Условия]. За каждую задачу | ||
ставится 1.5 балла. | ставится 1.5 балла. | ||
| + | |||
| + | === Семинары 27-28 === | ||
| + | |||
| + | Обсуждали двоичную кучу, повторяли разные вопросы для дз по хешированию. | ||
Версия 18:13, 25 апреля 2016
Содержание
Общая информация
Инвайт на AnyTask для 154-2: ixrgnZU (действителен до 20 марта)
Инвайт на AnyTask для 156-2: yryF8xy (действителен до 20 марта)
Семинары
Семинар 1
Тренировались в рекурсии на примере Ханойских башен. Задачи, нужно решить все, кроме 4.
Семинар 2
Разбирали, как тестировать программы на примере сортировки пузырьком: код.
Задачи:
- Доказать корректность работы сортировки пузырьком.
- Написать двоичный поиск с тестами как в примере выше. При этом функция должна быть реализована максимально абстрактно на шаблонах. После написания тестов и полной отладки задачу нужно сдать сюда. А потом еще и сдать задачу устно.
Семинар 3
Обсуждали разные сортировки (вставками, слиянием, быструю). Их нужно сдать в контест.
Семинар 4
Обсуждали асимптотики и O-символику. Начали решать листок.
Cеминары 5-6
Дорешивали старые задачи.
Семинары 7-8
Разбирали алгоритмы с лекций: выбор порядковой статистики и поиск пары ближайших точек.
Начали решать листок по рекуррентам.
Писали контрольную. Если вы плохо написали контрольную или пропустили ее, несданные задачи можно сдавать как обычный листок, но с частичным понижением оценки.
Семинары 9-10
Дорешивали старые задачи.
Семинары 11-12
Разбирали контест на дин. программирование, решали контест.
Семинары 13-14
Обсуждали редакционное расстояние. Его нужно запрограммировать здесь.
Обсуждали обход в ширину и в глубину на графах. Решали контест на обход в глубину и контест на обход в ширину.
Семинары 15-16
Обсуждали топологическую сортировку и вычисление компонент связности.
Семинары 17-20
Обсуждали поиск путей и кратчайших путей в графе. Обсуждали алгоритмы Флойда-Уоршелла и Беллмана-Форда. Начали решать контест на кратчайшие пути.
Также доступно несколько контестов по старым темам для тренировки: контест подсчет количества путей и контест на стратегию "разделяй и властвуй".
Семинары 21-22
Обсуждали хеширование.
Писали контрольную работу. Задачи, которые вы не решили на контрольной можно будет сдать на следующем семинаре (на нем же будет разбор).
Семинары 23-24
Разбирали контрольную работу. Обсуждали красно-черные деревья.
Семинары 25-26
Обсуждали деревья отрезков, динамические порядковые статистики, жадные алгоритмы, алгоритм Дейкстры.
Если вы не писали к/р 2 или написали ее на 5 баллов или ниже, можете ее пересдать на консультациях с ассистентом. Условия. За каждую задачу ставится 1.5 балла.
Семинары 27-28
Обсуждали двоичную кучу, повторяли разные вопросы для дз по хешированию.
