Содержание

1 Общие сведения

Общие сведения

Семестр: 4/6 (второй/третий курсы)
Формат: очный
Форма контроля: дифференцированный зачет + экзамен

Важные ссылки

Чат курса - там можно задавать вопросы по курсу, задачам, изредка флудить

Канал курса - там будут все важные объявления (домашние задания, оргвопросы, etc.)

Папка с теоретическими заданиями

Ведомость курса

Форма для регистрации на курс

Требования

Физтех-почта (домен phystech.edu)
Аккаунт на Я.Контесте (можно на физтех-почту)
Аккаунт на гитлабе

Обязательно заполнить форму регистрации на курс до 1 апреля! В противном случае считается, что курс вы сдавать не планируете или вы согласны на добровольную пересдачу по обоим предметам.

План курса

1. Обходы графов. DFS
- Хранение графа: матрица и список смежности
- Обход в ширину (DFS)
* Атрибуты вершин: цвета, времена входа и выхода
* Лемма о белых путях
* Топологическая сортировка
* Компоненты сильной связности. Алгоритм Косарайю
* Реберная двусвязность. Поиск мостов
* Поиск точек сочленения
2. Кратчайшие пути
- BFS: классический, 0-1, 1-k, 0-k
- Алгоритм Дейкстры
- Эвристический поиск. Алгоритм A-star
- Алгоритм Форда-Беллмана
- Алгоритм Флойда-Уоршелла
- Поиск циклов отрицательного веса
3. Система непересекающихся множеств
4. Минимальные остовые деревья
- Лемма о безопасном ребре
- Алгоритм Прима. Аналогии с алгоритмом Дейкстры
- Алгоритм Крускала.
5. Наименьший общий предок
- Наивное решение
- Двоичные подъемы
- Сведение LCA <-> RMQ
- Алгоритм Фараха-Колтона-Бендера
- static online RMQ с линейным предподсчетом и константным ответом на запрос
6. Паросочетания
- Двудольные графы
- Теорема Бержа
- Алгоритм Куна
7. Потоки
- Понятие сети, потока, разреза. Модификации сети
- Остаточная сеть
- Соотношение между величинами потоков и разрезов
- Теорема Форда-Фалкерсона
- Схема Форда-Фалкерсона
* Алгоритм Форда-Фалкерсона
* Алгоритм Эдмондса-Карпа
- Схема Диница
* Блокирующий поток
* Удаляющий обход
- Потенциал сети. Первая теорема Карзанова
- Алгоритм Хопкрофта-Карпа
8. Строки
- Поиск паттерна в тексте
* Префикс-функция. Алгоритм Кнута-Морриса-Прата
* Z-функция. Алгоритм Кнута-Морриса-Прата
* Полиномиальное хеширование. Алгоритм Рабина-Карпа
- Поиск множества паттернов в тексте
* Бор
* Автомат Ахо-Корасик
- Алгоритмы на подстроках. Суффиксный автомат
* Теорема Майхилла-Нероуда
* Наивное построение
* Линейный алгоритм
- Поиск паттернов с ошибками
* Метрика Левенштейна. Алгоритм Ландау-Вишкина
* Метрика Хэмминга. Быстрое преобразование Фурье

Оценивание

За курс ставятся сразу две оценки: дифференцированный зачет за "Практикум по алгоритмам и структурам данных", экзамен по дисциплине "Алгоритмы и структуры данных".

Оценивание дифференцированного зачета

Оценка состоит из следующих компонент:

1. Баллы за контесты (далее A): до 7.5 баллов

Пусть X - число набранных баллов студентом, S - число набранных идеальным студентом баллов. Тогда баллы за контесты определяются как A = round(X / S, 2) * 7.5

2. Баллы за теоретические задания (далее B): до 2.5 баллов

Пусть X - число набранных баллов студентом, S - число набранных идеальным студентом баллов. Тогда баллы за теоретические задания определяются как B = round(X / S, 2) * 2.5

3. Бонус от преподавательского состава (далее B): до 1 балла. Ставится семинаристом или лектором с шагом 0.1

4. Пусть F - число задач, в решениях которых студент был уличен в плагиате.

Итоговая оценка: clamp(round(A + B + C - F), 2, 10), однако если F > 2, то итоговая оценка неуд(2).

Последнее требование. В каждом контесте есть две задачи с ревью, проходящем на гитлабе в созданном для вас после заполнения формы репозитории. Для каждого контеста выкладываются требования для сдачи ревью. Для получения чего-либо выше неуд(2) необходимо сдать хотя бы треть задач с ревью.

Оценивание экзамена

Программа и правила проведения экзамена - TBA