Алгоритмы и структуры данных I. Основной поток 2026 — различия между версиями
(→Материалы курса) |
(→О курсе) |
||
| (не показаны 23 промежуточные версии этого же участника) | |||
| Строка 3: | Строка 3: | ||
Курс алгоритмов и структур данных — одна из ключевых дисциплин в области теоретической информатики на ФПМИ. Он посвящён изучению методов эффективного решения вычислительных задач и принципов организации данных, лежащих в основе современных программных систем. | Курс алгоритмов и структур данных — одна из ключевых дисциплин в области теоретической информатики на ФПМИ. Он посвящён изучению методов эффективного решения вычислительных задач и принципов организации данных, лежащих в основе современных программных систем. | ||
В рамках курса рассматриваются как фундаментальные теоретические вопросы, так и практические аспекты применения алгоритмических подходов в реальных задачах, возникающих в индустрии. | В рамках курса рассматриваются как фундаментальные теоретические вопросы, так и практические аспекты применения алгоритмических подходов в реальных задачах, возникающих в индустрии. | ||
| − | В первом (осеннем) семестре основное внимание | + | |
| + | В первом (осеннем) семестре основное внимание будет сосредоточено на разнообразных структурах данных, которые нужны будут в роли «чёрных ящиков» для более продвинутых алгоритмов. | ||
Для формирования необходимой базы в начале курса разбираются: | Для формирования необходимой базы в начале курса разбираются: | ||
| − | классические линейные алгоритмы, | + | *классические линейные алгоритмы, |
| − | принцип бинарного поиска, | + | *принцип бинарного поиска, |
| − | основные алгоритмы сортировки. | + | *основные алгоритмы сортировки. |
| + | |||
Далее курс переходит к систематическому изучению структур данных, включая: | Далее курс переходит к систематическому изучению структур данных, включая: | ||
| − | линейные структуры, | + | *линейные структуры, |
| − | кучи (приоритетные очереди), | + | *кучи (приоритетные очереди), |
| − | деревья отрезков, | + | *деревья отрезков, |
| − | деревья поиска, | + | *деревья поиска, |
| − | хеш-таблицы, | + | *хеш-таблицы, |
| − | а также ряд менее стандартных, но практически значимых подходов к организации данных. | + | *а также ряд менее стандартных, но практически значимых подходов к организации данных. |
| + | |||
Курс ориентирован как на студентов, изучающих его в рамках обязательной программы, так | Курс ориентирован как на студентов, изучающих его в рамках обязательной программы, так | ||
и на всех, кто заинтересован в углублённом понимании алгоритмов и стремится научиться разрабатывать эффективные и масштабируемые программные решения. | и на всех, кто заинтересован в углублённом понимании алгоритмов и стремится научиться разрабатывать эффективные и масштабируемые программные решения. | ||
| − | Пререквизиты: Студенты имеют первичное представление о языках программирования. Например, студенты в прошлом сдавали ЕГЭ по информатике или участвовали в разработке ИТ-проектов. | + | |
| + | '''Пререквизиты:''' | ||
| + | |||
| + | Студенты имеют первичное представление о языках программирования. Например, студенты в прошлом сдавали ЕГЭ по информатике или участвовали в разработке ИТ-проектов. | ||
От желающих сдавать курс факультативно (по выбору) ожидается знакомство с одним из языков программирования в рамках любого университетского курса. | От желающих сдавать курс факультативно (по выбору) ожидается знакомство с одним из языков программирования в рамках любого университетского курса. | ||
| − | == | + | == Программа курса == |
В семестре 15 лекций и 30 семинаров (практических занятий). | В семестре 15 лекций и 30 семинаров (практических занятий). | ||
| Строка 66: | Строка 72: | ||
Таблица с оценками, доступная студентам | Таблица с оценками, доступная студентам | ||
| − | + | == Критерии оценивания и формы контроля успеваемости == | |
| − | == | + | За курс предусмотрены '''две''' независимые оценки: за '''зачёт''' и за '''экзамен'''. |
| − | За курс предусмотрены две независимые оценки: за зачёт и за экзамен. | ||
Оценка за семестр считается по формуле в общей табличке. | Оценка за семестр считается по формуле в общей табличке. | ||
| Строка 78: | Строка 83: | ||
Ожидаемый максимальный балл ~150. | Ожидаемый максимальный балл ~150. | ||
| − | Если в течение семестра студент не набирает баллов на | + | Если в течение семестра студент не набирает баллов на уд 3, он получает пересдачу. |
| + | На пересдачу можно сдавать те же самые практические (в первую очередь задачи без код-ревью) | ||
| + | и теоретические задачи. Начать дорешивать можно сразу после зачётной недели и вплоть до пересдачи в начале следующего семестра. | ||
Оценка за экзамен ставится исключительно исходя из качества устного ответа на экзамене. | Оценка за экзамен ставится исключительно исходя из качества устного ответа на экзамене. | ||
| Строка 84: | Строка 91: | ||
В течение семестра планируются 5–6 домашних заданий. | В течение семестра планируются 5–6 домашних заданий. | ||
Выдаются примерно каждые три недели сроком на три недели. | Выдаются примерно каждые три недели сроком на три недели. | ||
| − | + | # введение, бинарный поиск; | |
| − | + | # сортировки; | |
| − | + | # кучи, линейные контейнеры; | |
| − | + | # дерево отрезков, дерево Фенвика; | |
| − | + | # деревья поиска; | |
| − | + | # хеш-таблицы. | |
| − | В каждой теме планируется большой контест и небольшое теоретическое задание. | + | '''В каждой теме планируется большой контест и небольшое теоретическое задание.''' |
| + | |||
1. Теоретические задания | 1. Теоретические задания | ||
Теоретические домашние задания сдаются устно семинаристу. | Теоретические домашние задания сдаются устно семинаристу. | ||
| + | |||
Формат предполагает: | Формат предполагает: | ||
| − | объяснение решения, | + | *объяснение решения, |
| − | ответы на уточняющие вопросы, | + | *ответы на уточняющие вопросы, |
| − | демонстрацию понимания используемых идей и методов. | + | *демонстрацию понимания используемых идей и методов. |
| + | |||
2. Практические задания | 2. Практические задания | ||
Практические задачи делятся на два типа: | Практические задачи делятся на два типа: | ||
| − | + | ||
| + | '''Задачи с код-ревью''' | ||
| + | |||
Чтобы задача считалась решённой: | Чтобы задача считалась решённой: | ||
| − | Необходимо загрузить код в указанный репозиторий (который укажут семинарист и ассистент). | + | *Необходимо загрузить код в указанный репозиторий (который укажут семинарист и ассистент). |
| − | Ассистент проводит код-ревью. | + | *Ассистент проводит код-ревью. |
| − | По результатам ревью код может быть отправлен на доработку. | + | *По результатам ревью код может быть отправлен на доработку. |
| − | После успешного прохождения всех итераций ревью задача засчитывается, и за неё выставляется балл. | + | *После успешного прохождения всех итераций ревью задача засчитывается, и за неё выставляется балл. |
| − | Дополнительные правила: | + | |
| − | число итераций ревью не ограничено; | + | '''Дополнительные правила:''' |
| − | при этом ассистент может отказать в дальнейшем ревью, если считает, что было сделано чрезмерное количество некачественных попыток. | + | *число итераций ревью не ограничено; |
| − | + | *при этом ассистент может отказать в дальнейшем ревью, если считает, что было сделано чрезмерное количество некачественных попыток. | |
| − | решения таких задач не предполагает обязательного просмотра кода решения со стороны ассистента. | + | |
| − | такие задачи должны пройти все тесты в системе. | + | '''Задачи без код-ревью''' |
| − | + | *решения таких задач не предполагает обязательного просмотра кода решения со стороны ассистента. | |
| − | однако семинарист может выборочно запросить устную сдачу. | + | *такие задачи должны пройти все тесты в системе. |
| − | Устная защита решений | + | *пройти встроенную автоматическую проверку на кодстайл (то есть в самом яндекс-контесте настроены некоторые минимальные требования, чтобы код был не совсем плохой). |
| + | *однако семинарист может выборочно запросить устную сдачу. | ||
| + | |||
| + | '''Устная защита решений''' | ||
Для части задач из контестов предусмотрена устная защита. | Для части задач из контестов предусмотрена устная защита. | ||
Цель защиты: | Цель защиты: | ||
| − | подтвердить самостоятельность решения, | + | *подтвердить самостоятельность решения, |
| − | проверить понимание алгоритма и структуры кода. | + | *проверить понимание алгоритма и структуры кода. |
Такая система позволяет оценить: | Такая система позволяет оценить: | ||
| − | теоретическую подготовку, | + | *теоретическую подготовку, |
| − | практические навыки программирования, | + | *практические навыки программирования, |
| − | глубину понимания алгоритмов. | + | *глубину понимания алгоритмов. |
| + | |||
| + | '''Бонусы''' | ||
| − | |||
Семинарист может ставить небольшие бонусы за активность на семинарах. Уточняйте правила их выставления у семинаристов. | Семинарист может ставить небольшие бонусы за активность на семинарах. Уточняйте правила их выставления у семинаристов. | ||
Если понимаете, что в какой-то задаче очень слабые тесты (заходят решения, которые не должны), можете подготовить более сильные тесты. Их добавят в систему, а вам дадут бонусные баллы. | Если понимаете, что в какой-то задаче очень слабые тесты (заходят решения, которые не должны), можете подготовить более сильные тесты. Их добавят в систему, а вам дадут бонусные баллы. | ||
| − | Штрафы | + | '''Штрафы''' |
| + | |||
Ближе к концу семестра будет проведена проверка на списывание (антиплагиат). Пойманные на списывании получат штраф к баллам за семестр, включая автоматический «неуд». Списыванием может быть рассчитано и независимое использование одного и того же открытого кода. Поэтому пишите полностью свой код, не прибегая к помощи готовых библиотек. Исключение — код, приводимый на лекциях и семинарах. | Ближе к концу семестра будет проведена проверка на списывание (антиплагиат). Пойманные на списывании получат штраф к баллам за семестр, включая автоматический «неуд». Списыванием может быть рассчитано и независимое использование одного и того же открытого кода. Поэтому пишите полностью свой код, не прибегая к помощи готовых библиотек. Исключение — код, приводимый на лекциях и семинарах. | ||
| − | |||
== Правила курса == | == Правила курса == | ||
| Строка 138: | Строка 154: | ||
== Команда курса == | == Команда курса == | ||
| − | Лектор Степанов Илья | + | Лектор: Степанов Илья |
| − | Семинаристы: | + | |
| + | Семинаристы: | ||
== Материалы курса == | == Материалы курса == | ||
| Строка 147: | Строка 164: | ||
Литература: | Литература: | ||
| − | Абрамов С. А. Лекции о сложности алгоритмов. МЦНМО, 2020. | + | # Абрамов С. А. Лекции о сложности алгоритмов. МЦНМО, 2020. |
| − | Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. «Мир», 1980. | + | # Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. «Мир», 1980. |
| − | Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. «Мир», 1979. | + | # Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. «Мир», 1979. |
| − | Кнут Д. Э. Искусство программирования, Т. 1. «ИД Вильямс», 2018. | + | # Кнут Д. Э. Искусство программирования, Т. 1. «ИД Вильямс», 2018. |
| − | Кнут Д. Э. Искусство программирования, Т. 3. «ИД Вильямс», 2018. | + | # Кнут Д. Э. Искусство программирования, Т. 3. «ИД Вильямс», 2018. |
| − | Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах // Доклады АН СССР, 1962, 145(2). | + | # Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах // Доклады АН СССР, 1962, 145(2). |
| − | Strassen V. Gaussian elimination is not optimal // Numerische Mathematik, 1969, 13(4). | + | # Strassen V. Gaussian elimination is not optimal // Numerische Mathematik, 1969, 13(4). |
| − | Кормен Т. и др. Алгоритмы. Построение и анализ. «ИД Вильямс», 2011. | + | # Кормен Т. и др. Алгоритмы. Построение и анализ. «ИД Вильямс», 2011. |
Текущая версия на 12:48, 13 мая 2026
Содержание
О курсе
Курс алгоритмов и структур данных — одна из ключевых дисциплин в области теоретической информатики на ФПМИ. Он посвящён изучению методов эффективного решения вычислительных задач и принципов организации данных, лежащих в основе современных программных систем. В рамках курса рассматриваются как фундаментальные теоретические вопросы, так и практические аспекты применения алгоритмических подходов в реальных задачах, возникающих в индустрии.
В первом (осеннем) семестре основное внимание будет сосредоточено на разнообразных структурах данных, которые нужны будут в роли «чёрных ящиков» для более продвинутых алгоритмов. Для формирования необходимой базы в начале курса разбираются:
- классические линейные алгоритмы,
- принцип бинарного поиска,
- основные алгоритмы сортировки.
Далее курс переходит к систематическому изучению структур данных, включая:
- линейные структуры,
- кучи (приоритетные очереди),
- деревья отрезков,
- деревья поиска,
- хеш-таблицы,
- а также ряд менее стандартных, но практически значимых подходов к организации данных.
Курс ориентирован как на студентов, изучающих его в рамках обязательной программы, так и на всех, кто заинтересован в углублённом понимании алгоритмов и стремится научиться разрабатывать эффективные и масштабируемые программные решения.
Пререквизиты:
Студенты имеют первичное представление о языках программирования. Например, студенты в прошлом сдавали ЕГЭ по информатике или участвовали в разработке ИТ-проектов. От желающих сдавать курс факультативно (по выбору) ожидается знакомство с одним из языков программирования в рамках любого университетского курса.
Программа курса
В семестре 15 лекций и 30 семинаров (практических занятий).
| Неделя | Лекции | Домашние задания и контест |
|---|---|---|
| 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. Практические задания Практические задачи делятся на два типа:
Задачи с код-ревью
Чтобы задача считалась решённой:
- Необходимо загрузить код в указанный репозиторий (который укажут семинарист и ассистент).
- Ассистент проводит код-ревью.
- По результатам ревью код может быть отправлен на доработку.
- После успешного прохождения всех итераций ревью задача засчитывается, и за неё выставляется балл.
Дополнительные правила:
- число итераций ревью не ограничено;
- при этом ассистент может отказать в дальнейшем ревью, если считает, что было сделано чрезмерное количество некачественных попыток.
Задачи без код-ревью
- решения таких задач не предполагает обязательного просмотра кода решения со стороны ассистента.
- такие задачи должны пройти все тесты в системе.
- пройти встроенную автоматическую проверку на кодстайл (то есть в самом яндекс-контесте настроены некоторые минимальные требования, чтобы код был не совсем плохой).
- однако семинарист может выборочно запросить устную сдачу.
Устная защита решений
Для части задач из контестов предусмотрена устная защита. Цель защиты:
- подтвердить самостоятельность решения,
- проверить понимание алгоритма и структуры кода.
Такая система позволяет оценить:
- теоретическую подготовку,
- практические навыки программирования,
- глубину понимания алгоритмов.
Бонусы
Семинарист может ставить небольшие бонусы за активность на семинарах. Уточняйте правила их выставления у семинаристов. Если понимаете, что в какой-то задаче очень слабые тесты (заходят решения, которые не должны), можете подготовить более сильные тесты. Их добавят в систему, а вам дадут бонусные баллы.
Штрафы
Ближе к концу семестра будет проведена проверка на списывание (антиплагиат). Пойманные на списывании получат штраф к баллам за семестр, включая автоматический «неуд». Списыванием может быть рассчитано и независимое использование одного и того же открытого кода. Поэтому пишите полностью свой код, не прибегая к помощи готовых библиотек. Исключение — код, приводимый на лекциях и семинарах.
Правила курса
Более подробно и во избежание спорных ситуаций в конце семестра читайте о правилах курса здесь
Команда курса
Лектор: Степанов Илья
Семинаристы:
Материалы курса
лекции потока 2024 года
Примерная программа экзамена
Литература:
- Абрамов С. А. Лекции о сложности алгоритмов. МЦНМО, 2020.
- Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. «Мир», 1980.
- Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. «Мир», 1979.
- Кнут Д. Э. Искусство программирования, Т. 1. «ИД Вильямс», 2018.
- Кнут Д. Э. Искусство программирования, Т. 3. «ИД Вильямс», 2018.
- Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах // Доклады АН СССР, 1962, 145(2).
- Strassen V. Gaussian elimination is not optimal // Numerische Mathematik, 1969, 13(4).
- Кормен Т. и др. Алгоритмы. Построение и анализ. «ИД Вильямс», 2011.
