Spirina.es: Новая страница: «== О курсе == Курс алгоритмов и структур данных — одна из ключевых дисциплин в области тео…»

2026-06-15T08:46:03Z

Новая страница: «== О курсе == Курс алгоритмов и структур данных — одна из ключевых дисциплин в области тео…»

Новая страница

== О курсе ==
Курс алгоритмов и структур данных — одна из ключевых дисциплин в области теоретической информатики на ФПМИ. Он посвящён изучению методов эффективного решения вычислительных задач и принципов организации данных, лежащих в основе современных программных систем.
В рамках курса рассматриваются как фундаментальные теоретические вопросы, так и практические аспекты применения алгоритмических подходов в реальных задачах, возникающих в индустрии.

В первом (осеннем) семестре основное внимание будет сосредоточено на разнообразных структурах данных, которые нужны будут в роли «чёрных ящиков» для более продвинутых алгоритмов.
Для формирования необходимой базы в начале курса разбираются:
*классические линейные алгоритмы,
*принцип бинарного поиска,
*основные алгоритмы сортировки.

Далее курс переходит к систематическому изучению структур данных, включая:
*линейные структуры,
*кучи (приоритетные очереди),
*деревья отрезков,
*деревья поиска,
*хеш-таблицы,
*а также ряд менее стандартных, но практически значимых подходов к организации данных.

Курс ориентирован как на студентов, изучающих его в рамках обязательной программы, так
и на всех, кто заинтересован в углублённом понимании алгоритмов и стремится научиться разрабатывать эффективные и масштабируемые программные решения.

'''Пререквизиты:'''

Студенты имеют первичное представление о языках программирования. Например, студенты в прошлом сдавали ЕГЭ по информатике или участвовали в разработке ИТ-проектов.
От желающих сдавать курс факультативно (по выбору) ожидается знакомство с одним из языков программирования в рамках любого университетского курса.

== Команда курса ==
Лектор: Степанов Илья

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

== Программа курса ==
В семестре 15 лекций и 30 семинаров (практических занятий).

{|class="wikitable"
|-
!Неделя!!Лекции!!Домашние задания и контест
|-
|1||Асимптоматика. Бинарный поиск.||Бинарный поиск, два указателя
|-
|2||MergeSoft. QuickSort.||
|-
|3||Derandomized. QuickSort. LSDSort.||Сортировки.
|-
|4||Кучи. HeapSort.||
|-
|5||Кучи(продолжение). Динамический массив||Кучи, линейные контейнеры.
|-
|6||Связные списки. Кучи Фибоначчи.||
|-
|7||Стеки. Очередь.||
|-
|8||Дерево отрезков.||Дерево отрезков, дерево Фенвика.
|-
|9||Динамическое ДО. Персистентные структуры данных
|-
|10||Деревья поиска:AVL-деревья, Splay-дерево.||Деревья поиска.
|-
|11||Неявное дерево поиска.||
|-
|12||Декартово дерево. В-дерево.||
|-
|13||Красно-чёрное дерево.||
|-
|14||Хэш-таблицы.||Хеш-таблицы.
|-
|15||Хэш-таблицы (продолжение).||
|}

== Коммуникация ==
За каждой группой закреплён семинарист и ассистент, к которым можно обращаться за помощью.

Чат курса (Telegram)

== Прогресс студентов ==
Таблица с оценками, доступная студентам

== Критерии оценивания и формы контроля успеваемости ==
За курс предусмотрены '''две''' независимые оценки: за '''зачёт''' и за '''экзамен'''.

Оценка за семестр считается по формуле в общей табличке.
Оценка за зачёт ставится за работу в семестре: за сдачу теоретических и практических домашних задач, а также за активность на семинарах и помощь в развитии курса (исправление опечаток в условиях, подготовка более сильных тестов к задачам, разработка собственных задач и пр.).

Список задач будет окончательно известен только ближе к концу семестра, поэтому заранее невозможно спрогнозировать, какие будут пороги на каждую оценку.
Чтобы заработать минимальную положительную оценку (уд. 3), нужно набрать примерно 50% баллов от максимума.
Чтобы заработать наивысшую оценку (отл. 10), нужно приблизиться к идеальному студенту, решившему все задачи. Решить всё возможно: в семестре будет много бонусных задач, которые идут в зачёт
Ожидаемый максимальный балл ~150.

Если в течение семестра студент не набирает баллов на уд 3, он получает пересдачу.
На пересдачу можно сдавать те же самые практические (в первую очередь задачи без код-ревью)
и теоретические задачи. Начать дорешивать можно сразу после зачётной недели и вплоть до пересдачи в начале следующего семестра.

Оценка за экзамен ставится исключительно исходя из качества устного ответа на экзамене.

В течение семестра планируются 5–6 домашних заданий.
Выдаются примерно каждые три недели сроком на три недели.
# введение, бинарный поиск;
# сортировки;
# кучи, линейные контейнеры;
# дерево отрезков, дерево Фенвика;
# деревья поиска;
# хеш-таблицы.

'''В каждой теме планируется большой контест и небольшое теоретическое задание.'''

1. Теоретические задания
Теоретические домашние задания сдаются устно семинаристу.

Формат предполагает:
*объяснение решения,
*ответы на уточняющие вопросы,
*демонстрацию понимания используемых идей и методов.

2. Практические задания
Практические задачи делятся на два типа:

'''Задачи с код-ревью'''

Чтобы задача считалась решённой:
*Необходимо загрузить код в указанный репозиторий (который укажут семинарист и ассистент).
*Ассистент проводит код-ревью.
*По результатам ревью код может быть отправлен на доработку.
*После успешного прохождения всех итераций ревью задача засчитывается, и за неё выставляется балл.

'''Дополнительные правила:'''
*число итераций ревью не ограничено;
*при этом ассистент может отказать в дальнейшем ревью, если считает, что было сделано чрезмерное количество некачественных попыток.

'''Задачи без код-ревью'''
*решения таких задач не предполагает обязательного просмотра кода решения со стороны ассистента.
*такие задачи должны пройти все тесты в системе.
*пройти встроенную автоматическую проверку на кодстайл (то есть в самом яндекс-контесте настроены некоторые минимальные требования, чтобы код был не совсем плохой).
*однако семинарист может выборочно запросить устную сдачу.

'''Устная защита решений'''

Для части задач из контестов предусмотрена устная защита.
Цель защиты:
*подтвердить самостоятельность решения,
*проверить понимание алгоритма и структуры кода.

Такая система позволяет оценить:
*теоретическую подготовку,
*практические навыки программирования,
*глубину понимания алгоритмов.

'''Бонусы'''

Семинарист может ставить небольшие бонусы за активность на семинарах. Уточняйте правила их выставления у семинаристов.
Если понимаете, что в какой-то задаче очень слабые тесты (заходят решения, которые не должны), можете подготовить более сильные тесты. Их добавят в систему, а вам дадут бонусные баллы.

'''Штрафы'''

Ближе к концу семестра будет проведена проверка на списывание (антиплагиат). Пойманные на списывании получат штраф к баллам за семестр, включая автоматический «неуд». Списыванием может быть рассчитано и независимое использование одного и того же открытого кода. Поэтому пишите полностью свой код, не прибегая к помощи готовых библиотек. Исключение — код, приводимый на лекциях и семинарах.

== Правила курса ==
Более подробно и во избежание спорных ситуаций в конце семестра читайте о правилах курса [https://docs.google.com/document/d/1TNoAMWFGZHsEigH9BlM_lGI4jdHxxR66Y3jHGtntQME/edit здесь]

== Материалы курса ==
[https://www.youtube.com/playlist?list=PL4_hYwCyhAvbR2onqJWW7JQi8TYEaQN_p лекции] потока 2024 года

Примерная [https://drive.google.com/file/d/1ZU6efLnjNXPEA5iwgfmMoBwaTvZWiICn/view?usp=sharing программа] экзамена

Литература:
# Абрамов С. А. Лекции о сложности алгоритмов. МЦНМО, 2020.
# Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. «Мир», 1980.
# Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. «Мир», 1979.
# Кнут Д. Э. Искусство программирования, Т. 1. «ИД Вильямс», 2018.
# Кнут Д. Э. Искусство программирования, Т. 3. «ИД Вильямс», 2018.
# Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах // Доклады АН СССР, 1962, 145(2).
# Strassen V. Gaussian elimination is not optimal // Numerische Mathematik, 1969, 13(4).
# Кормен Т. и др. Алгоритмы. Построение и анализ. «ИД Вильямс», 2011.

Алгоритмы и структуры данных III. Основной поток 2026 - История изменений

Spirina.es: Новая страница: «== О курсе == Курс алгоритмов и структур данных — одна из ключевых дисциплин в области тео…»