Алгоритмы и структуры данных семинары 154-2 156-2 — различия между версиями
Aumnov (обсуждение | вклад) (→Семинары 29-30) |
Aumnov (обсуждение | вклад) (→Семинары 37-38) |
||
(не показаны 2 промежуточные версии этого же участника) | |||
Строка 90: | Строка 90: | ||
Обсуждали двоичную кучу, повторяли разные вопросы для дз по хешированию. | Обсуждали двоичную кучу, повторяли разные вопросы для дз по хешированию. | ||
− | === Семинары 29- | + | === Семинары 29-32 === |
Обсуждали минимальные остовные деревья, алогритмы Крускала и Прима, структуру данных "Система непересекающихся множеств". | Обсуждали минимальные остовные деревья, алогритмы Крускала и Прима, структуру данных "Система непересекающихся множеств". | ||
Строка 96: | Строка 96: | ||
Написали класс связный список, чтобы поразбираться с реализацией классов на C++: [https://www.dropbox.com/s/o15sdpgndk282h0/linked_list.cpp?dl=0 код]. | Написали класс связный список, чтобы поразбираться с реализацией классов на C++: [https://www.dropbox.com/s/o15sdpgndk282h0/linked_list.cpp?dl=0 код]. | ||
(Сейчас класс немного недоделанный, если кто-нибудь его доделает пришлет, я выложу новую версию). | (Сейчас класс немного недоделанный, если кто-нибудь его доделает пришлет, я выложу новую версию). | ||
+ | |||
+ | === Семинары 33-36 === | ||
+ | |||
+ | Обсуждали автоматы, регулярные и нерегулярные языки. | ||
+ | |||
+ | [https://www.dropbox.com/s/nrflfpfcwojkp3o/Automatons.pdf?dl=0 Листок] по всему этому. | ||
+ | |||
+ | === Семинары 37-38 === | ||
+ | |||
+ | Обсуждали контекстно-свободные грамматики, и еще немного регулярные языки. | ||
+ | |||
+ | Почитать всю теорию можно, например, [https://www.dropbox.com/s/a1lxwgfdn0s31z7/%D0%9F%D0%B5%D0%BD%D1%82%D1%83%D1%81.%20%D0%A4%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5%20%D1%8F%D0%B7%D1%8B%D0%BA%D0%B8.pdf?dl=0 тут] (некоторые обозначения могут отличаться от обозначений на лекциях). | ||
+ | |||
+ | === Семинары 39-40 === | ||
+ | |||
+ | Обсуждали задачу у максимальном потоке. Потренироваться в реализации можно [https://official.contest.yandex.ru/contest/2531/enter/ тут]. |
Текущая версия на 10:56, 9 июня 2016
Содержание
- 1 Общая информация
- 2 Семинары
- 2.1 Семинар 1
- 2.2 Семинар 2
- 2.3 Семинар 3
- 2.4 Семинар 4
- 2.5 Cеминары 5-6
- 2.6 Семинары 7-8
- 2.7 Семинары 9-10
- 2.8 Семинары 11-12
- 2.9 Семинары 13-14
- 2.10 Семинары 15-16
- 2.11 Семинары 17-20
- 2.12 Семинары 21-22
- 2.13 Семинары 23-24
- 2.14 Семинары 25-26
- 2.15 Семинары 27-28
- 2.16 Семинары 29-32
- 2.17 Семинары 33-36
- 2.18 Семинары 37-38
- 2.19 Семинары 39-40
Общая информация
Все домашки сдаются на ревью в AnyTask (anytask.org), для получения доступа нужно ввести инвайт в соответствии с группой:
Инвайт на AnyTask для 154-2: b002kz4 (действителен до 25 мая)
Инвайт на AnyTask для 156-2: MXyU2zi (действителен до 25 мая)
Все оценки и варианты заданий можно найти тут.
Семинары
Семинар 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
Обсуждали двоичную кучу, повторяли разные вопросы для дз по хешированию.
Семинары 29-32
Обсуждали минимальные остовные деревья, алогритмы Крускала и Прима, структуру данных "Система непересекающихся множеств".
Написали класс связный список, чтобы поразбираться с реализацией классов на C++: код. (Сейчас класс немного недоделанный, если кто-нибудь его доделает пришлет, я выложу новую версию).
Семинары 33-36
Обсуждали автоматы, регулярные и нерегулярные языки.
Листок по всему этому.
Семинары 37-38
Обсуждали контекстно-свободные грамматики, и еще немного регулярные языки.
Почитать всю теорию можно, например, тут (некоторые обозначения могут отличаться от обозначений на лекциях).
Семинары 39-40
Обсуждали задачу у максимальном потоке. Потренироваться в реализации можно тут.