Алгоритмы и структуры данных III. Основной поток 2026: различия между версиями
| Строка 90: | Строка 90: | ||
Литература: | Литература: | ||
# | # Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. – МЦНМО, 2014 | ||
# Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов – «Мир», 1979 | |||
# Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов | # Препарата Ф., Шеймос М. Вычислительная геометрия: введение – «Мир», 1989 | ||
# | # Gusfield D. Algorithms on Strings, Trees, and Sequences – Cambridge University Press, 1997 | ||
# De Berg M. et al. Computational Geometry. Algorithms and Applications – Springer, 2008 | |||
# | |||
# | |||
Версия от 15:34, 29 октября 2026
О курсе
Курс алгоритмов и структур данных — одна из ключевых дисциплин в области теоретической информатики на ФПМИ. Он посвящён изучению методов эффективного решения вычислительных задач и принципов организации данных, лежащих в основе современных программных систем. В рамках курса рассматриваются как фундаментальные теоретические вопросы, так и практические аспекты применения алгоритмических подходов в реальных задачах, возникающих в индустрии.
В первом (осеннем) семестре основное внимание будет сосредоточено на разнообразных структурах данных, которые нужны будут в роли «чёрных ящиков» для более продвинутых алгоритмов. Для формирования необходимой базы в начале курса разбираются:
- классические линейные алгоритмы,
- принцип бинарного поиска,
- основные алгоритмы сортировки.
Далее курс переходит к систематическому изучению структур данных, включая:
- линейные структуры,
- кучи (приоритетные очереди),
- деревья отрезков,
- деревья поиска,
- хеш-таблицы,
- а также ряд менее стандартных, но практически значимых подходов к организации данных.
Курс ориентирован как на студентов, изучающих его в рамках обязательной программы, так и на всех, кто заинтересован в углублённом понимании алгоритмов и стремится научиться разрабатывать эффективные и масштабируемые программные решения.
Пререквизиты:
Студенты имеют первичное представление о языках программирования. Например, студенты в прошлом сдавали ЕГЭ по информатике или участвовали в разработке ИТ-проектов. От желающих сдавать курс факультативно (по выбору) ожидается знакомство с одним из языков программирования в рамках любого университетского курса.
Команда курса
Лектор: Степанов Илья Данилович
Семинаристы: Сбродов Егор Алексеевич
Вашкевич Егор Сергеевич
Степанов Илья Данилович
Программа курса
В семестре 15 лекций и 30 семинаров (практических занятий).
Формы контроля: Дифференцированный зачет и экзамен
| Неделя | Лекции! |
|---|---|
| 1 | Хеширование и поиск образца в строке |
| 2 | Префикс-функция, Z-функция и палиндромы |
| 3 | Боры и алгоритм Ахо — Корасик |
| 4 | Суффиксный массив и массив LCP |
| 5 | Дерево палиндромов |
| 6 | Конечные автоматы и суффиксный автомат |
| 7 | Суффиксное дерево и связь суффиксных структур |
| 8 | Быстрое преобразование Фурье |
| 9 | Алгоритмы над многочленами и линейные рекурренты |
| 10 | Теория чисел и алгоритмы над конечными полями |
| 11 | Вычислительная геометрия: базовые примитивы |
| 12 | Триангуляция многоугольников и выпуклая оболочка |
| 13 | Алгоритмы на выпуклых многоугольниках |
| 14 | Принадлежность точки многоугольнику и пересечение полуплоскостей |
| 15 | Диаграммы Вороного и триангуляция Делоне |
Коммуникация
За каждой группой закреплён семинарист и ассистент, к которым можно обращаться за помощью.
Прогресс студентов
Таблица с оценками доступна студентам в канале дисциплины
Критерии оценивания и формы контроля успеваемости
В конце семестра экзамен.
Материалы курса
Примерная программа экзамена
Литература:
- Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. – МЦНМО, 2014
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов – «Мир», 1979
- Препарата Ф., Шеймос М. Вычислительная геометрия: введение – «Мир», 1989
- Gusfield D. Algorithms on Strings, Trees, and Sequences – Cambridge University Press, 1997
- De Berg M. et al. Computational Geometry. Algorithms and Applications – Springer, 2008