Алгоритмы и структуры данных (Русскоязычные иностранцы) 2024 весна

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

• Семестр: 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

Команда курса

Лектор курса Кулапин Артур

Семинаристы:

Семинарист Б05-251 - Филатенков Артур

Семинарист Б05-252 - Смолин Александр

Семинарист Б05-253 - Долта Артем

Cеминарист Б05-(153-155) - Козловский Владислав

Ассистенты

Вашкевич Егор

Павлов Михаил

Мешков Владислав

Драчёв Данила

Стешенко Александр

Аминов Шахром

Сушков Богдан

Дополнительные материалы

Записи лекций 2023-2024 года