Public ATP Wiki - Вклад [ru]

Алгоритмы и структуры данных I. Иностранный поток 2026

2026-11-02T10:32:40Z

Spirina.es: /* Прогресс студентов */

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

== Программа курса ==
Курс двухсеместровый

'''Форма контроля в осеннем семестре:''' экзамен

{| class="wikitable"
! Неделя
! Лекция / Семинар
|-
| 1
| Анализ алгоритмов и асимптотика
|-
| 2
| Бинарный поиск и методы поиска ответа
|-
| 3
| Линейные структуры данных
|-
| 4
| Амортизационный анализ
|-
| 5
| Префиксные суммы и задачи диапазонов
|-
| 6
| Сортировки I: фундаментальные алгоритмы
|-
| 7
| Сортировки II: быстрые алгоритмы
|-
| 8
| Кучи и приоритетные очереди
|-
| 9
| Деревья поиска I
|-
| 10
| Деревья поиска II: самобалансирующиеся деревья
|-
| 11
| Структуры данных для запросов на отрезках
|-
| 12
| Продвинутые структуры данных
|-
| 13
| Хеширование и вероятностные структуры
|-
| 14
| Динамическое программирование
|-
| 15
| Матричные методы и вычислительная геометрия
|}

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

Лектор: Смолин Александр Андреевич

Семинарист: Мешков Владислав Сергеевич

== Коммуникация ==
Канал курса https://t.me/ads_foreigns

== Прогресс студентов ==

таблица с оценками доступна студентам в канале дисциплины

== Критерии оценивания и формы контроля успеваемости ==

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

Экзамен будет проходить в четыре этапа: три основных и один бонусный.

1. Выдается билет, содержащий четыре вопроса из программы. Ответ на каждый вопрос оценивается из 1.5 баллов. При оценке ответа на какой-либо вопрос ниже 0.5 ставится автоматически пересдача. На подготовку ответа дается 1 час. За ответ на эту часть программы дается до шести баллов. Продолжительность ответа в ходе данной части экзамена не должна превышать 45 минут. Экзаменатор имеет право попросить сформулировать смежные по теме определения и формулировки утверждений и теорем, не указанные явно в вопросе. При использовании утверждения или теоремы из данного курса экзаменатор имеет право поинтересоваться ее доказательством.

2. Далее идет блиц-опрос по программе, за который дается не более одного балла. В его ходе экзаменатор имеет право спросить любое определение и формулировку любой теоремы из курса. Также он может поинтересоваться постановкой задачи, которую решает некоторый алгоритм. Отвечать необходимо практически сразу, без долгих размышлений.

'''Если на текущий момент у студента меньше 5.5 баллов, то экзамен заканчивается.'''

3. Заключительная часть экзамена состоит в том, что вам будут предложены для решения две задачи. Сначала идет задача среднего уровня сложности. Ее решение принесет вам два балла и возможность получить задачу на 10, если за первые два этапа было не менее 6.5 баллов. Если же задача не решена, то выдается задача «попроще», за решение которой дается один балл. Время подготовки ответа на задачу попроще составляет 25 минут, на задачу среднего уровня — 40 минут.

4. *В случае, если вы претендуете на отл(10), вам нужно сообщить об этом экзаменатору. После консультации с лектором он выдаст задачу продвинутого уровня сложности. Подготовка и ответ этого этапа не должны превышать полутора часов.
*В случае, если на какой-то из стадий экзамена истекло выделенное время, экзаменатор имеет право прервать экзамен и выставить оценку на основе данных вами ответов.
Если вам необходимо отлучиться в ходе экзамена, это можно сделать только между стадиями или между задачами из третьего этапа.
*В случае несогласия с оценкой вы имеете право отапеллировать ее у лектора до выхода из аудитории.

Алгоритмы и структуры данных I. Иностранный поток 2026

2026-11-02T10:32:14Z

Spirina.es: /* Коммуникация */

ИВТ. Математические основания алгоритмов и сложность вычислений. 2026

2026-10-30T10:13:59Z

Spirina.es: /* Коммуникация */

== О курсе ==

'''Математические основания алгоритмов и сложность вычислений''' — это первый семестр из четырёх, посвящённых алгоритмам.

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

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

* '''Руководитель курса / лектор:''' Троян-Головян Владислав
* '''Преподаватели, семинаристы, ассистенты:'''
** Троян-Головян Владислав
** Бунин Лев Алексеевич

== Программа курса ==

Дисциплина состоит из:

* Математические основания алгоритмов и сложность вычислений

'''Форма контроля:''' экзамен

* Практикум по математическим основаниям алгоритмов

'''Форма контроля:''' Дифференцированный зачет

{| class="wikitable"
! Неделя
! Лекции
! Домашние задания и контест
|-
| 1
| Введение
|
|-
| 2
| Теория множеств
|
|-
| 3
| Бинарная арифметика
|
|-
| 4
| O-нотация и мастер-теорема
|
|-
| 5
| Индукция и комбинаторика
|
|-
| 6
| Теория вероятностей I
|
|-
| 7
| Теория вероятностей II
|
|-
| 8
| Вещественная арифметика
| Контрольная работа
|-
| 9
| Теория чисел I
|
|-
| 10
| Теория чисел II
|
|-
| 11
| Графы I
|
|-
| 12
| Графы II
|
|-
| 13
| Вероятностные алгоритмы
|
|-
| 14
| P/NP: основы
| Контрольная работа
|-
| 15
| Вопрос-ответ
|
|}

== Коммуникация ==

* Ссылка на чат курса в мессенджере
[https://t.me/+nCkriGIkjiM5YTMy [2026<nowiki>]</nowiki>[ИВТ, 1 курс<nowiki>]</nowiki> [Математические основания алгоритмов<nowiki>]</nowiki>]

== Прогресс студентов ==

* Ссылка на таблицу студентов с оценками (будет опубликована ближе к старту семестра).

== Критерии оценивания и формы контроля успеваемости ==

=== Домашние задания ===

По каждой теме выдаётся домашнее задание, оцениваемое от '''0''' до '''10''' баллов.

* Срок выполнения: '''2 недели'''
* Формат выполнения: '''TeX'''

=== Контрольные работы ===

В течение семестра проводятся две контрольные работы:

* после лекции 8;
* после лекции 14.

Каждая контрольная работа оценивается от '''0''' до '''10''' баллов.

=== Допуск к зачёту ===

Если:

* средний балл за контрольные работы меньше '''3''', и/или
* средний балл за домашние задания меньше '''3''',

то итоговая оценка за курс — '''неудовлетворительно'''.

=== Семинарский балл ===

На семинарах преподаватель проводит квизы по материалам лекций, а также учитывает:

* посещаемость;
* активность на занятиях;
* выходы к доске.

По итогам семестра выставляется семинарский балл в диапазоне от '''−1''' до '''+1''', который добавляется к итоговой оценке.

=== Итоговая оценка за зачёт===

0.5*AVG(ДЗ)+0.5*AVG(КР) + Балл от семинариста.

Если итоговая оценка равна '''11''', студент получает бонус к экзамену.

=== Штрафы ===

* Просрочка сдачи до 24 часов — штраф '''25%'''.
* Просрочка до 3 дней — штраф '''50%'''.
* Просрочка более 3 дней — '''0 баллов'''.
'''Исключение:''' официальный допуск или медицинская справка.
* За списывание оба участника получают оценку '''−10 баллов'''.

== Политика списывания ==
'''Политика списывания:''' при подозрении на списывание семинарист/ассистент проводит устную беседу, если факт списывания подтверждается, то зануляется весь контест целиком. При повторном списывании ставится итоговая оценка неуд. 2.

== Материалы курса ==

Презентации и дополнительные материалы будут публиковаться по ходу занятий в чате курса.

Алгоритмы на графах и динамическое программирование 2026

2026-10-30T10:01:51Z

Spirina.es: /* Коммуникация */

==Команда курса==
Лектор: Троян-Головян Владислав

Семинарист: Аксёненко Денис

Ассистенты:

Андреев Ярослав Андреевич

Прохорчук Екатерина Александровна

==Программа курса==
Дисциплина состоит из:

* Алгоритмы на графах и динамическое программирование

'''Форма контроля:''' экзамен

* Практикум по алгоритмам на графах и динамическому программированию

'''Форма контроля:''' Дифференцированный зачет

{| class="wikitable"
! № недели
! Лекция / семинар
|-
| 1
| Основные идеи, базовые задачи: НОП, НВП, Банкомат
|-
| 2
| Динамическое программирование 2: матричное ДП, алгоритм Хиршберга, задача о рюкзаке, ДП по цифрам
|-
| 3
| ДП по битмаскам, гамильтоновы пути, клики; ДП по профилю, скошенному профилю
|-
| 4
| Convex Hull Trick
|-
| 5
| Графы 1: способы хранения, DFS, BFS, цвета вершин
|-
| 6
| Графы 2: DFS и времена входа и выхода, топологическая сортировка, поиск КСС, 2-SAT, мосты и точки сочленения
|-
| 7
| Остовные деревья, СНМ, алгоритм Крускала, алгоритм Прима, матроиды
|-
| 8
| Алгоритм Борувки, LCA: поиск при помощи двух указателей, бинарных подъёмов, сведение LCA к RMQ. Алгоритм Фарака–Колтона и Бендера. Сведение RMQ к LCA
|-
| 9
| Кратчайшие пути 1: алгоритм Дейкстры, алгоритм A*, алгоритм Форда–Беллмана, алгоритм Флойда–Уоршелла
|-
| 10
| Кратчайшие пути 2: алгоритм Джонсона, улучшения алгоритма Дейкстры, двунаправленный A*, алгоритм IDA*
|-
| 11
| Паросочетания: алгоритм Куна, теорема Бержа, теорема Кёнига. Построение минимального вершинного покрытия
|-
| 12
| Потоки 1: основные понятия, теорема о максимальном потоке и минимальном разрезе, метод Форда–Фалкерсона, алгоритм Эдмондса–Карпа. Поиск максимального паросочетания при помощи поиска потока
|-
| 13
| Алгоритмы Диница и Хопкрофта–Карпа
|-
| 14
| Min-cost flow. Задача о назначениях
|}

== Коммуникация ==

Ссылка на чат курса в мессенджере
[https://t.me/+79xMH16hnIU5MTFi [2026<nowiki>]</nowiki>[ИВТ, 2 курс<nowiki>]</nowiki> [Алгоритмы на графах и ДП<nowiki>]</nowiki>]

== Прогресс студентов ==

Ссылка на таблицу студентов с оценками (ближе к старту семестра)

==Критерии оценивания и формы контроля успеваемости==

В течение семестра проводится '''6 контестов''', в каждом из которых одна задача выполняется с последующим '''код-ревью'''.

По задачам на ревью опрелеляется верхняя граница оценки(далее X):

Если пройдено
 Для порога уд. 4 нужно пройти(получить approve) 3,
 Для порога хор. 7, нужно пройти 4,
 Для порога отл. 8-9, нужно пройти 5
 Для порога отл. 10, нужно пройти 6.

=== Контрольные работы ===

В течение семестра проводится '''2 контрольные работы'''. За каждую контрольную можно получить от '''0 до 10 баллов'''.

'''Блокирующее условие на неуд:''' сумма оценок по двум контрольным должна быть хотя бы 6б.

Итоговая оценка рассчитывается на основе трёх составляющих:

* A - контесты(от 1 до 10, выставляется по порогам)
* B - AVG контрольные(от 1 до 10)
* C - оценка от семинариста(от -1 до +1)

Далее вычисляется Y=0.5*A+0.5*B+C

И выставляется Min(X,Y)

Пороги для оценки A:
 >= 50%: уд3,
 >= 55%: уд4,
 >= 65%: хор 5,
 >= 70%: хор 6,
 >= 75%: хор 7,
 >= 85%: отл 8,
 >= 90%: отл 9,
 >= 95%: отл 10,
 Иначе: неуд 1

== Политика списывания ==
'''Политика списывания:''' при подозрении на списывание семинарист/ассистент проводит устную беседу, если факт списывания подтверждается, то зануляется весь контест целиком. При повторном списывании ставится итоговая оценка неуд. 2.

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

2026-10-30T08:17:33Z

Spirina.es:

== О курсе ==
На лекциях разбираются различные модельные задачи и алгоритмы их решения, на семинарах студентам предлагается решать теоретические задачи, обсуждать их решения, реализовывать код избранных алгоритмов, а также сдавать домашние задания.

В третьем семестре рассматриваются три больших блока тем: строковые алгоритмы, вычислительные вопросы теории чисел, алгоритмы в геометрии. Предполагается, что слушатели курса знакомы с основными структурами данных: деревьями отрезков и деревьями поиска. Также необходимо базовое знакомство с понятиями теории графов и основными алгоритмами на графах.

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

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

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

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

Семинаристы: Сбродов Егор Алексеевич

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

Степанов Илья Данилович

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

'''Формы контроля:''' экзамен

{|class="wikitable"
|-
!Неделя!!Лекции!
|-
|1||Хеширование и поиск образца в строке
|-
|2||Префикс-функция, Z-функция и палиндромы
|-
|3||Боры и алгоритм Ахо — Корасик
|-
|4||Суффиксный массив и массив LCP
|-
|5||Дерево палиндромов
|-
|6||Конечные автоматы и суффиксный автомат
|-
|7||Суффиксное дерево и связь суффиксных структур
|-
|8||Быстрое преобразование Фурье
|-
|9||Алгоритмы над многочленами и линейные рекурренты
|-
|10||Теория чисел и алгоритмы над конечными полями
|-
|11||Вычислительная геометрия: базовые примитивы
|-
|12||Триангуляция многоугольников и выпуклая оболочка
|-
|13|| Алгоритмы на выпуклых многоугольниках
|-
|14||Принадлежность точки многоугольнику и пересечение полуплоскостей
|-
|15||Диаграммы Вороного и триангуляция Делоне
|}

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

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

== Критерии оценивания и формы контроля успеваемости ==

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

В течение семестра планируются 5 домашних заданий, разбитых по темам:
# базовые строковые алгоритмы [7–28 сентября];
# суффиксные строковые структуры [28 сентября – 24 октября];
# алгоритмы в теории чисел [21 октября – 15 ноября];
# базовые алгоритмы в геометрии [1 ноября – 21 ноября];
# продвинутые алгоритмы в геометрии [28 ноября – 15 декабря].

В каждой теме планируется большой контест и небольшое теоретическое задание. Чтобы заработать минимальную положительную оценку (уд. 3), нужно набрать примерно 50% баллов от максимума.

Чтобы заработать наивысшую оценку (отл. 10), нужно приблизиться к идеальному студенту, решившему почти все задачи.

Ожидаемый максимальный балл — 120. Оценка за семестр стремится зафиксировать уровень навыков студента в решении и реализации практических задач по алгоритмам.

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

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

== Материалы курса ==

[https://www.youtube.com/playlist?list=PL4_hYwCyhAvYlrKIbN0Qgv9yjClbrIZyG лекции] потока осень 2024

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

Литература:
# Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. – МЦНМО, 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

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

2026-10-30T08:14:38Z

Spirina.es: /* Критерии оценивания и формы контроля успеваемости */

== О курсе ==
На лекциях разбираются различные модельные задачи и алгоритмы их решения, на семинарах студентам предлагается решать теоретические задачи, обсуждать их решения, реализовывать код избранных алгоритмов, а также сдавать домашние задания.

В третьем семестре рассматриваются три больших блока тем: строковые алгоритмы, вычислительные вопросы теории чисел, алгоритмы в геометрии. Предполагается, что слушатели курса знакомы с основными структурами данных: деревьями отрезков и деревьями поиска. Также необходимо базовое знакомство с понятиями теории графов и основными алгоритмами на графах.

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

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

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

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

Семинаристы: Сбродов Егор Алексеевич

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

Степанов Илья Данилович

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

'''Формы контроля:''' экзамен

{|class="wikitable"
|-
!Неделя!!Лекции!
|-
|1||Хеширование и поиск образца в строке
|-
|2||Префикс-функция, Z-функция и палиндромы
|-
|3||Боры и алгоритм Ахо — Корасик
|-
|4||Суффиксный массив и массив LCP
|-
|5||Дерево палиндромов
|-
|6||Конечные автоматы и суффиксный автомат
|-
|7||Суффиксное дерево и связь суффиксных структур
|-
|8||Быстрое преобразование Фурье
|-
|9||Алгоритмы над многочленами и линейные рекурренты
|-
|10||Теория чисел и алгоритмы над конечными полями
|-
|11||Вычислительная геометрия: базовые примитивы
|-
|12||Триангуляция многоугольников и выпуклая оболочка
|-
|13|| Алгоритмы на выпуклых многоугольниках
|-
|14||Принадлежность точки многоугольнику и пересечение полуплоскостей
|-
|15||Диаграммы Вороного и триангуляция Делоне
|}

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

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

== Критерии оценивания и формы контроля успеваемости ==

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

В течение семестра планируются 5 домашних заданий, разбитых по темам:
# базовые строковые алгоритмы [7–28 сентября];
# суффиксные строковые структуры [28 сентября – 24 октября];
# алгоритмы в теории чисел [21 октября – 15 ноября];
# базовые алгоритмы в геометрии [1 ноября – 21 ноября];
# продвинутые алгоритмы в геометрии [28 ноября – 15 декабря].

В каждой теме планируется большой контест и небольшое теоретическое задание. Чтобы заработать минимальную положительную оценку (уд. 3), нужно набрать примерно 50% баллов от максимума.

Чтобы заработать наивысшую оценку (отл. 10), нужно приблизиться к идеальному студенту, решившему почти все задачи.

Ожидаемый максимальный балл — 120. Оценка за семестр стремится зафиксировать уровень навыков студента в решении и реализации практических задач по алгоритмам.

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

== Материалы курса ==

[https://www.youtube.com/playlist?list=PL4_hYwCyhAvYlrKIbN0Qgv9yjClbrIZyG лекции] потока осень 2024

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

Литература:
# Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. – МЦНМО, 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

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

2026-10-30T08:13:08Z

Spirina.es: /* Критерии оценивания и формы контроля успеваемости */

== О курсе ==
На лекциях разбираются различные модельные задачи и алгоритмы их решения, на семинарах студентам предлагается решать теоретические задачи, обсуждать их решения, реализовывать код избранных алгоритмов, а также сдавать домашние задания.

В третьем семестре рассматриваются три больших блока тем: строковые алгоритмы, вычислительные вопросы теории чисел, алгоритмы в геометрии. Предполагается, что слушатели курса знакомы с основными структурами данных: деревьями отрезков и деревьями поиска. Также необходимо базовое знакомство с понятиями теории графов и основными алгоритмами на графах.

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

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

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

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

Семинаристы: Сбродов Егор Алексеевич

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

Степанов Илья Данилович

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

'''Формы контроля:''' экзамен

{|class="wikitable"
|-
!Неделя!!Лекции!
|-
|1||Хеширование и поиск образца в строке
|-
|2||Префикс-функция, Z-функция и палиндромы
|-
|3||Боры и алгоритм Ахо — Корасик
|-
|4||Суффиксный массив и массив LCP
|-
|5||Дерево палиндромов
|-
|6||Конечные автоматы и суффиксный автомат
|-
|7||Суффиксное дерево и связь суффиксных структур
|-
|8||Быстрое преобразование Фурье
|-
|9||Алгоритмы над многочленами и линейные рекурренты
|-
|10||Теория чисел и алгоритмы над конечными полями
|-
|11||Вычислительная геометрия: базовые примитивы
|-
|12||Триангуляция многоугольников и выпуклая оболочка
|-
|13|| Алгоритмы на выпуклых многоугольниках
|-
|14||Принадлежность точки многоугольнику и пересечение полуплоскостей
|-
|15||Диаграммы Вороного и триангуляция Делоне
|}

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

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

== Критерии оценивания и формы контроля успеваемости ==

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

В течение семестра планируются 5 домашних заданий, разбитых по темам: 1) базовые строковые алгоритмы [7–28 сентября]; 2) суффиксные строковые структуры [28 сентября – 24 октября]; 3) алгоритмы в теории чисел [21 октября – 15 ноября]; 4) базовые алгоритмы в геометрии [1 ноября – 21 ноября]; 5) продвинутые алгоритмы в геометрии [28 ноября – 15 декабря]. В каждой теме планируется большой контест и небольшое теоретическое задание. Чтобы заработать минимальную положительную оценку (уд. 3), нужно набрать примерно 50% баллов от максимума. Чтобы заработать наивысшую оценку (отл. 10), нужно приблизиться к идеальному студенту, решившему почти все задачи. Ожидаемый максимальный балл — 120. Оценка за семестр стремится зафиксировать уровень навыков студента в решении и реализации практических задач по алгоритмам.

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

== Материалы курса ==

[https://www.youtube.com/playlist?list=PL4_hYwCyhAvYlrKIbN0Qgv9yjClbrIZyG лекции] потока осень 2024

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

Литература:
# Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. – МЦНМО, 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

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

2026-10-29T15:38:41Z

Spirina.es: /* Критерии оценивания и формы контроля успеваемости */

== О курсе ==
На лекциях разбираются различные модельные задачи и алгоритмы их решения, на семинарах студентам предлагается решать теоретические задачи, обсуждать их решения, реализовывать код избранных алгоритмов, а также сдавать домашние задания.

В третьем семестре рассматриваются три больших блока тем: строковые алгоритмы, вычислительные вопросы теории чисел, алгоритмы в геометрии. Предполагается, что слушатели курса знакомы с основными структурами данных: деревьями отрезков и деревьями поиска. Также необходимо базовое знакомство с понятиями теории графов и основными алгоритмами на графах.

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

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

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

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

Семинаристы: Сбродов Егор Алексеевич

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

Степанов Илья Данилович

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

'''Формы контроля:''' экзамен

{|class="wikitable"
|-
!Неделя!!Лекции!
|-
|1||Хеширование и поиск образца в строке
|-
|2||Префикс-функция, Z-функция и палиндромы
|-
|3||Боры и алгоритм Ахо — Корасик
|-
|4||Суффиксный массив и массив LCP
|-
|5||Дерево палиндромов
|-
|6||Конечные автоматы и суффиксный автомат
|-
|7||Суффиксное дерево и связь суффиксных структур
|-
|8||Быстрое преобразование Фурье
|-
|9||Алгоритмы над многочленами и линейные рекурренты
|-
|10||Теория чисел и алгоритмы над конечными полями
|-
|11||Вычислительная геометрия: базовые примитивы
|-
|12||Триангуляция многоугольников и выпуклая оболочка
|-
|13|| Алгоритмы на выпуклых многоугольниках
|-
|14||Принадлежность точки многоугольнику и пересечение полуплоскостей
|-
|15||Диаграммы Вороного и триангуляция Делоне
|}

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

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

== Критерии оценивания и формы контроля успеваемости ==

В конце семестра экзамен.

В течение семестра планируются 5 домашних заданий, разбитых по темам: 1) базовые строковые алгоритмы [7–28 сентября]; 2) суффиксные строковые структуры [28 сентября – 24 октября]; 3) алгоритмы в теории чисел [21 октября – 15 ноября]; 4) базовые алгоритмы в геометрии [1 ноября – 21 ноября]; 5) продвинутые алгоритмы в геометрии [28 ноября – 15 декабря]. В каждой теме планируется большой контест и небольшое теоретическое задание. Чтобы заработать минимальную положительную оценку (уд. 3), нужно набрать примерно 50% баллов от максимума. Чтобы заработать наивысшую оценку (отл. 10), нужно приблизиться к идеальному студенту, решившему почти все задачи. Ожидаемый максимальный балл — 120. Оценка за семестр стремится зафиксировать уровень навыков студента в решении и реализации практических задач по алгоритмам.

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

== Материалы курса ==

[https://www.youtube.com/playlist?list=PL4_hYwCyhAvYlrKIbN0Qgv9yjClbrIZyG лекции] потока осень 2024

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

Литература:
# Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. – МЦНМО, 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

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

2026-10-29T15:36:25Z

Spirina.es: /* Материалы курса */

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

2026-10-29T15:35:20Z

Spirina.es: /* Программа курса */

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

2026-10-29T15:35:09Z

Spirina.es: /* О курсе */

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

2026-10-29T15:34:53Z

Spirina.es: /* О курсе */

== О курсе ==
В семестре планируется 15 лекций и 30 семинаров (практических занятий). На лекциях разбираются различные модельные задачи и алгоритмы их решения, на семинарах студентам предлагается решать теоретические задачи, обсуждать их решения, реализовывать код избранных алгоритмов, а также сдавать домашние задания.

В третьем семестре рассматриваются три больших блока тем: строковые алгоритмы, вычислительные вопросы теории чисел, алгоритмы в геометрии. Предполагается, что слушатели курса знакомы с основными структурами данных: деревьями отрезков и деревьями поиска. Также необходимо базовое знакомство с понятиями теории графов и основными алгоритмами на графах.

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

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

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

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

Семинаристы: Сбродов Егор Алексеевич

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

Степанов Илья Данилович

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

'''Формы контроля:''' Дифференцированный зачет и экзамен

{|class="wikitable"
|-
!Неделя!!Лекции!
|-
|1||Хеширование и поиск образца в строке
|-
|2||Префикс-функция, Z-функция и палиндромы
|-
|3||Боры и алгоритм Ахо — Корасик
|-
|4||Суффиксный массив и массив LCP
|-
|5||Дерево палиндромов
|-
|6||Конечные автоматы и суффиксный автомат
|-
|7||Суффиксное дерево и связь суффиксных структур
|-
|8||Быстрое преобразование Фурье
|-
|9||Алгоритмы над многочленами и линейные рекурренты
|-
|10||Теория чисел и алгоритмы над конечными полями
|-
|11||Вычислительная геометрия: базовые примитивы
|-
|12||Триангуляция многоугольников и выпуклая оболочка
|-
|13|| Алгоритмы на выпуклых многоугольниках
|-
|14||Принадлежность точки многоугольнику и пересечение полуплоскостей
|-
|15||Диаграммы Вороного и триангуляция Делоне
|}

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

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

== Критерии оценивания и формы контроля успеваемости ==

В конце семестра экзамен.

== Материалы курса ==

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

Литература:
# Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. – МЦНМО, 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

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

2026-10-29T15:34:08Z

Spirina.es: /* Материалы курса */

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

2026-10-29T15:33:22Z

Spirina.es: /* Прогресс студентов */

Алгоритмы и структуры данных I. Базовый поток 2026

2026-10-29T15:29:16Z

Spirina.es: /* 5. Прогресс студентов */

== О курсе ==

'''Алгоритмы и структуры данных'''

''1 курс, осенний семестр''

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

=== Пререквизиты ===

* Базовые знания математики.
* Базовые знания и навыки работы с алгоритмами.

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

'''Лектор курса:''' Никулов Сергей.

'''Семинаристы:''' Мусаев Садык, Середа Андрей, Якушева София, Старокожко Иван, Бунин Лев.

== Программа курса ==

{| class="wikitable"
! Неделя
! Лекция
! Семинар
|-
| 1
| '''Асимптотика. Анализ алгоритмов.'''
 O-, Ω- и Θ-нотации. Временная сложность алгоритма. Модель вычисления.
| Практика и задачи по теме лекции.
|-
| 2
| '''Рекурренты. Алгоритм Евклида. Бинарный поиск.'''
 Рекуррентные соотношения и способы их решения: метод подстановки, деревья рекурсии, Мастер-теорема (б/д).
 Алгоритм Евклида. Бинарный поиск по ответу. Примеры задач.
| Практика и задачи по теме лекции.
|-
| 3
| '''Квадратичные сортировки.'''
 Сортировки выбором, вставками и пузырьком.
 Реализация, время работы и доказательство.
| Практика и задачи по теме лекции.
|-
| 4
| '''Merge sort (сортировка слиянием).'''
 Сортировка слиянием с дополнительной памятью и Inplace.
 Реализация и анализ времени работы.
| Практика и задачи по теме лекции.
|-
| 5
| '''Быстрая сортировка (Quicksort).'''
 Реализация. Разбиение Ломуто и Хоара. Доказательство времени работы. Барьер Ω(n log n) (б/д).
| Практика и задачи по теме лекции.
|-
| 6
| '''Пирамидная сортировка (HeapSort).'''
 Бинарная пирамида. SiftUp и SiftDown. Построение пирамиды, пирамидальная сортировка и анализ времени работы.
| Практика и задачи по теме лекции.
|-
| 7
| '''Лист. Стек. Очередь.'''
 Односвязные и двусвязные списки. Стек и очередь. Реализация на списках.
| Практика и задачи по теме лекции.
|-
| 8
| '''Бинарное дерево поиска.'''
 Способы обхода. Поиск, вставка и удаление элемента. Анализ времени работы.
| Практика и задачи по теме лекции.
|-
| 9
| '''AVL-дерево.'''
 Анализ высоты AVL-дерева. Balance-фактор. Повороты. Поиск, вставка и удаление элементов. Анализ времени работы.
| Практика и задачи по теме лекции.
|-
| 10
| '''Амортизационный анализ.'''
 Методы подсчёта, банковский метод и метод потенциалов. Очередь на двух стеках. Двоичный счётчик.
| Практика и задачи по теме лекции.
|-
| 11
| '''Splay-дерево.'''
 Повороты. Splay, Split и Merge. Поиск, вставка и удаление элементов. Анализ времени работы.
| Практика и задачи по теме лекции.
|-
| 12
| '''Динамическое программирование.'''
 Критерии применимости, порядки пересчёта, одномерная и двумерная динамика.
 Задача о рюкзаке: дискретная и непрерывная постановки, реализация и анализ времени работы.
| Практика и задачи по теме лекции.
|-
| 13
| '''НОП и НВП.'''
 Наибольшая общая подпоследовательность: оптимальная подструктура, реализация и анализ времени.
 Наибольшая возрастающая подпоследовательность: решения за O(n²) и O(n log n), реализация и анализ времени.
| Практика и задачи по теме лекции.
|-
| 14
| '''Контрольная работа'''
| Разбор сложных тем семестра.
|}

== Контрольные активности ==

В течение семестра предусмотрены три контеста и итоговая контрольная работа. Точные недели публикации контестов и дедлайны будут объявлены отдельно в чате курса.

{| class="wikitable"
! Активность
! Срок / неделя
! Формат
|-
| Контест №1
| 2–3 недели на выполнение
| 10–20 задач
|-
| Контест №2
| 2–3 недели на выполнение
| 10–20 задач
|-
| Контест №3
| 2–3 недели на выполнение
| 10–20 задач
|-
| Итоговая контрольная работа
| Конец семестра
| Письменный формат
|}

=== Контесты ===

За семестр студент выполняет 3 контеста. В каждом контесте от 10 до 18 задач и выделены обязательные задачи, необходимые для получения удовлетворительной оценки.

* Выполнение обязательных задач соответствует оценке 3 из 10 за контест.
* Каждая следующая решённая задача добавляет 1 балл к оценке за контест.
* Максимальная оценка за контест — 10 баллов.
* Контесты проверяются ассистентами.

=== Итоговая контрольная работа ===

В конце семестра проводится контрольная работа. Она оценивается по 10-балльной шкале и учитывается при расчёте итоговой оценки с весом 30%.

== 4. Коммуникация ==

[https://t.me/+ykSAeh2wxNphNTFi чат] курса

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

== 5. Прогресс студентов ==

Таблица с оценками доступна студентам в канале дисциплины

== 6. Критерии оценивания и формы контроля успеваемости ==

'''Обязательное условие:''' если хотя бы один из трёх контестов выполнен на оценку ниже 3 баллов из 10, итоговая оценка за курс является неудовлетворительной.

Если обязательное условие выполнено, итоговая оценка рассчитывается по формуле:

'''Итог = 0,7 × средняя оценка за контесты + 0,3 × оценка за контрольную + бонус за активность'''

* Средняя оценка за контесты рассчитывается по трём контестам и имеет вес 70% в итоговой оценке.
* Оценка за итоговую контрольную работу имеет вес 30%.
* Семинарист может добавить до 1 балла за активность студента на семинарах.

=== Бонус за активность ===

Семинарист может добавить к итоговой оценке до 1 балла за активную работу на семинарах. Конкретный размер бонуса определяется семинаристом по итогам семестра.

=== Дедлайны и штрафы ===

Для каждого контеста устанавливается дедлайн. После дедлайна задачи могут быть оценены максимум в 50% от количества баллов, предусмотренных за них в соответствующем домашнем задании.

== Правила курса ==

# Для получения положительной итоговой оценки каждый из трёх контестов должен быть выполнен минимум на 3 балла из 10.

# В каждом контесте три обязательные задачи формируют минимальную удовлетворительную оценку; дополнительные задачи повышают оценку за контест.

# После дедлайна обязательные задачи оцениваются с ограничением не более 50% от предусмотренных за них баллов.

# Итоговая контрольная работа является частью итоговой оценки.

# Активность на семинарах может дать до 1 дополнительного балла к итоговой оценке.

# Актуальные дедлайны и организационные объявления публикуются в чате курса.

== Материалы курса ==

'''Папка с материалами:''' [ссылка будет добавлена]

* Презентации лекций, материалы семинаров и условия контестов.
* Материалы для подготовки к итоговой контрольной работе.

Алгоритмы и структуры данных I. Базовый поток 2026

2026-10-29T15:28:47Z

Spirina.es: /* 4. Коммуникация */

== О курсе ==

'''Алгоритмы и структуры данных'''

''1 курс, осенний семестр''

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

=== Пререквизиты ===

* Базовые знания математики.
* Базовые знания и навыки работы с алгоритмами.

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

'''Лектор курса:''' Никулов Сергей.

'''Семинаристы:''' Мусаев Садык, Середа Андрей, Якушева София, Старокожко Иван, Бунин Лев.

== Программа курса ==

{| class="wikitable"
! Неделя
! Лекция
! Семинар
|-
| 1
| '''Асимптотика. Анализ алгоритмов.'''
 O-, Ω- и Θ-нотации. Временная сложность алгоритма. Модель вычисления.
| Практика и задачи по теме лекции.
|-
| 2
| '''Рекурренты. Алгоритм Евклида. Бинарный поиск.'''
 Рекуррентные соотношения и способы их решения: метод подстановки, деревья рекурсии, Мастер-теорема (б/д).
 Алгоритм Евклида. Бинарный поиск по ответу. Примеры задач.
| Практика и задачи по теме лекции.
|-
| 3
| '''Квадратичные сортировки.'''
 Сортировки выбором, вставками и пузырьком.
 Реализация, время работы и доказательство.
| Практика и задачи по теме лекции.
|-
| 4
| '''Merge sort (сортировка слиянием).'''
 Сортировка слиянием с дополнительной памятью и Inplace.
 Реализация и анализ времени работы.
| Практика и задачи по теме лекции.
|-
| 5
| '''Быстрая сортировка (Quicksort).'''
 Реализация. Разбиение Ломуто и Хоара. Доказательство времени работы. Барьер Ω(n log n) (б/д).
| Практика и задачи по теме лекции.
|-
| 6
| '''Пирамидная сортировка (HeapSort).'''
 Бинарная пирамида. SiftUp и SiftDown. Построение пирамиды, пирамидальная сортировка и анализ времени работы.
| Практика и задачи по теме лекции.
|-
| 7
| '''Лист. Стек. Очередь.'''
 Односвязные и двусвязные списки. Стек и очередь. Реализация на списках.
| Практика и задачи по теме лекции.
|-
| 8
| '''Бинарное дерево поиска.'''
 Способы обхода. Поиск, вставка и удаление элемента. Анализ времени работы.
| Практика и задачи по теме лекции.
|-
| 9
| '''AVL-дерево.'''
 Анализ высоты AVL-дерева. Balance-фактор. Повороты. Поиск, вставка и удаление элементов. Анализ времени работы.
| Практика и задачи по теме лекции.
|-
| 10
| '''Амортизационный анализ.'''
 Методы подсчёта, банковский метод и метод потенциалов. Очередь на двух стеках. Двоичный счётчик.
| Практика и задачи по теме лекции.
|-
| 11
| '''Splay-дерево.'''
 Повороты. Splay, Split и Merge. Поиск, вставка и удаление элементов. Анализ времени работы.
| Практика и задачи по теме лекции.
|-
| 12
| '''Динамическое программирование.'''
 Критерии применимости, порядки пересчёта, одномерная и двумерная динамика.
 Задача о рюкзаке: дискретная и непрерывная постановки, реализация и анализ времени работы.
| Практика и задачи по теме лекции.
|-
| 13
| '''НОП и НВП.'''
 Наибольшая общая подпоследовательность: оптимальная подструктура, реализация и анализ времени.
 Наибольшая возрастающая подпоследовательность: решения за O(n²) и O(n log n), реализация и анализ времени.
| Практика и задачи по теме лекции.
|-
| 14
| '''Контрольная работа'''
| Разбор сложных тем семестра.
|}

== Контрольные активности ==

В течение семестра предусмотрены три контеста и итоговая контрольная работа. Точные недели публикации контестов и дедлайны будут объявлены отдельно в чате курса.

{| class="wikitable"
! Активность
! Срок / неделя
! Формат
|-
| Контест №1
| 2–3 недели на выполнение
| 10–20 задач
|-
| Контест №2
| 2–3 недели на выполнение
| 10–20 задач
|-
| Контест №3
| 2–3 недели на выполнение
| 10–20 задач
|-
| Итоговая контрольная работа
| Конец семестра
| Письменный формат
|}

=== Контесты ===

За семестр студент выполняет 3 контеста. В каждом контесте от 10 до 18 задач и выделены обязательные задачи, необходимые для получения удовлетворительной оценки.

* Выполнение обязательных задач соответствует оценке 3 из 10 за контест.
* Каждая следующая решённая задача добавляет 1 балл к оценке за контест.
* Максимальная оценка за контест — 10 баллов.
* Контесты проверяются ассистентами.

=== Итоговая контрольная работа ===

В конце семестра проводится контрольная работа. Она оценивается по 10-балльной шкале и учитывается при расчёте итоговой оценки с весом 30%.

== 4. Коммуникация ==

[https://t.me/+ykSAeh2wxNphNTFi чат] курса

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

== 5. Прогресс студентов ==

'''Таблица с оценками:''' [ссылка будет добавлена ближе к старту семестра]

В таблице фиксируются результаты трёх контестов, итоговой контрольной работы и бонус за активность на семинарах.

== 6. Критерии оценивания и формы контроля успеваемости ==

'''Обязательное условие:''' если хотя бы один из трёх контестов выполнен на оценку ниже 3 баллов из 10, итоговая оценка за курс является неудовлетворительной.

Если обязательное условие выполнено, итоговая оценка рассчитывается по формуле:

'''Итог = 0,7 × средняя оценка за контесты + 0,3 × оценка за контрольную + бонус за активность'''

* Средняя оценка за контесты рассчитывается по трём контестам и имеет вес 70% в итоговой оценке.
* Оценка за итоговую контрольную работу имеет вес 30%.
* Семинарист может добавить до 1 балла за активность студента на семинарах.

=== Бонус за активность ===

Семинарист может добавить к итоговой оценке до 1 балла за активную работу на семинарах. Конкретный размер бонуса определяется семинаристом по итогам семестра.

=== Дедлайны и штрафы ===

Для каждого контеста устанавливается дедлайн. После дедлайна задачи могут быть оценены максимум в 50% от количества баллов, предусмотренных за них в соответствующем домашнем задании.

== Правила курса ==

# Для получения положительной итоговой оценки каждый из трёх контестов должен быть выполнен минимум на 3 балла из 10.

# В каждом контесте три обязательные задачи формируют минимальную удовлетворительную оценку; дополнительные задачи повышают оценку за контест.

# После дедлайна обязательные задачи оцениваются с ограничением не более 50% от предусмотренных за них баллов.

# Итоговая контрольная работа является частью итоговой оценки.

# Активность на семинарах может дать до 1 дополнительного балла к итоговой оценке.

# Актуальные дедлайны и организационные объявления публикуются в чате курса.

== Материалы курса ==

'''Папка с материалами:''' [ссылка будет добавлена]

* Презентации лекций, материалы семинаров и условия контестов.
* Материалы для подготовки к итоговой контрольной работе.

ММТУ. Введение в программирование

2026-10-29T15:26:49Z

Spirina.es: /* Коммуникация */

== О курсе ==
Это годовой курс С++, предназначенный для будущих ученых в области численного моделирования. Он рассчитан как на новичков, так и на студентов с опытом программирования, и существенно опирается на хорошее понимание физики. Первый семестр посвящен фундаментальным темам в области алгоритмов и техническим аспектам работы с памятью. Второй семестр посвящен проектной деятельности, объектно-ориентированному программированию и STL C++17.

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

Лектор и руководитель курса: Беклемышева Катерина Алексеевна, к.ф.-м.н.

Семинаристы: Лавренков Степан и Ильин Евгений.

== Программа курса ==
'''Форма контроля:''' Дифференцированный зачет

{|class="wikitable"
|-
!Неделя!!Лекции!!Контроль/ событие
|-
|1||Переменные, циклы, условия.||Контест.
|-
|2||Функции.||Контест.
|-
|3||Побитовые операции и хранение переменных.||Контест.
|-
|4||Массивы.||Контест.
|-
|5||Сортировки. Вычислительная сложность. Оптимизация кода, флаги оптимизации.||Лабораторная.
|-
|6||Хранение переменных типа float. Проблемы и рецепты для их решения.||Лабораторная.
|-
|7||Дискретная оптимизация. Жадные алгоритмы. Динамическое программирование.||Контест.
|-
|8||Лекция: ответы на вопросы.||Контрольная №1.
|-
|9||Указатели I. Модель памяти .flat. Правила работы стека и кучи.||Контест.
|-
|10||Технические аспекты. Linux, WSL, valgrind.(практика).||Лабораторная
|-
|11||Указатели II. Двойные указатели, двухмерные и расширяемые массивы.||Контест.
|-
|12||Стек и очередь на массивах и на списках. Обзор структур данных STL.||Лабораторная.
|-
|13||Списки.||Лабораторная.
|-
|14||Деревья.||Лабораторная.
|-
|15||Лекция: ответы на вопросы.||Теоретический опрос.
|}

*Контесты - самостоятельная работа, не сдается и не оценивается.
*Лабораторные (5 шт) - в течение недели каждая по 2 балла, потом 1 балл.
*Теоретический опрос – стандартная сдача теории лектору или семинаристу.
*Проект - можно делать с начала семестра, сдача на зачетной неделе, дает дополнительные баллы.

== Коммуникация ==
• чат курса – по группам, создает семинарист и приглашает студентов по списку группы

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

== Критерии оценивания и формы контроля успеваемости ==

*0.33*A + 0.33*B + 0.33*C + D, где
*A -- оценка за первую контрольную (от 1 до 10)
*B -- оценка за теоретический опрос (от 1 до 10)
*C -- оценка за лабораторные (от 0 до 10)

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

*D -- оценка за проект (от 0 до 5)

'''Дедлайн'''

Дедлайн по всем заданиям – зачетная неделя.

== Материалы курса ==

https://disk.yandex.ru/d/FqkEeFej_4e8NQ
https://www.youtube.com/playlist?list=PLecy9mZ2ycLK4kjnS2SXSUVY2w044lxGd

ММТУ. Введение в программирование

2026-10-29T15:26:27Z

Spirina.es: /* Прогресс студентов */

== О курсе ==
Это годовой курс С++, предназначенный для будущих ученых в области численного моделирования. Он рассчитан как на новичков, так и на студентов с опытом программирования, и существенно опирается на хорошее понимание физики. Первый семестр посвящен фундаментальным темам в области алгоритмов и техническим аспектам работы с памятью. Второй семестр посвящен проектной деятельности, объектно-ориентированному программированию и STL C++17.

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

Лектор и руководитель курса: Беклемышева Катерина Алексеевна, к.ф.-м.н.

Семинаристы: Лавренков Степан и Ильин Евгений.

== Программа курса ==
'''Форма контроля:''' Дифференцированный зачет

{|class="wikitable"
|-
!Неделя!!Лекции!!Контроль/ событие
|-
|1||Переменные, циклы, условия.||Контест.
|-
|2||Функции.||Контест.
|-
|3||Побитовые операции и хранение переменных.||Контест.
|-
|4||Массивы.||Контест.
|-
|5||Сортировки. Вычислительная сложность. Оптимизация кода, флаги оптимизации.||Лабораторная.
|-
|6||Хранение переменных типа float. Проблемы и рецепты для их решения.||Лабораторная.
|-
|7||Дискретная оптимизация. Жадные алгоритмы. Динамическое программирование.||Контест.
|-
|8||Лекция: ответы на вопросы.||Контрольная №1.
|-
|9||Указатели I. Модель памяти .flat. Правила работы стека и кучи.||Контест.
|-
|10||Технические аспекты. Linux, WSL, valgrind.(практика).||Лабораторная
|-
|11||Указатели II. Двойные указатели, двухмерные и расширяемые массивы.||Контест.
|-
|12||Стек и очередь на массивах и на списках. Обзор структур данных STL.||Лабораторная.
|-
|13||Списки.||Лабораторная.
|-
|14||Деревья.||Лабораторная.
|-
|15||Лекция: ответы на вопросы.||Теоретический опрос.
|}

*Контесты - самостоятельная работа, не сдается и не оценивается.
*Лабораторные (5 шт) - в течение недели каждая по 2 балла, потом 1 балл.
*Теоретический опрос – стандартная сдача теории лектору или семинаристу.
*Проект - можно делать с начала семестра, сдача на зачетной неделе, дает дополнительные баллы.

== Коммуникация ==
• чат курса – по группам, создает семинарист (Telegram или другой мессенджер)

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

== Критерии оценивания и формы контроля успеваемости ==

*0.33*A + 0.33*B + 0.33*C + D, где
*A -- оценка за первую контрольную (от 1 до 10)
*B -- оценка за теоретический опрос (от 1 до 10)
*C -- оценка за лабораторные (от 0 до 10)

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

*D -- оценка за проект (от 0 до 5)

'''Дедлайн'''

Дедлайн по всем заданиям – зачетная неделя.

== Материалы курса ==

https://disk.yandex.ru/d/FqkEeFej_4e8NQ
https://www.youtube.com/playlist?list=PLecy9mZ2ycLK4kjnS2SXSUVY2w044lxGd

Программирование на языке C++. (односеместровый) 2026

2026-10-29T15:25:05Z

Spirina.es: /* Прогресс студентов */

== О курсе ==

Односеместровый курс (основной поток).

'''Форма контроля:''' Дифференцированный зачёт

{| class="wikitable"
! Параметр
! Значение
|-
| Формат
| 15 лекций + 15 семинаров (1 пара лекция + 1 пара семинар в неделю)
|-
| Стандарт языка
| C++17 (отдельные элементы C++20)
|-
| Среда разработки
| MSVC / g++ / clang++ — на выбор студента
|-
| Система сборки
| CMake или встроенная сборка IDE (без отдельной лекции)
|-
| Домашние работы
| 5 блоковых заданий (1–2 недели каждое) + итоговый проект
|-
| Использование LLM
| Разрешено при обязательной устной защите решения
|}

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

Особое внимание уделяется объектно-ориентированному программированию, принципам проектирования (SOLID), шаблонам, исключениям, RAII, умным указателям, move-семантике и современным возможностям C++17/20. Отдельный блок посвящён стандартной библиотеке STL, алгоритмам, контейнерам и современному стилю разработки.

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

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

Для успешного освоения курса слушателю достаточно иметь базовые навыки программирования: понимать, что такое переменные, типы данных, условные операторы, циклы и функции. Желателен опыт написания простых программ на любом языке программирования (например, Python, Pascal). Специальных знаний по C++ не требуется, так как курс начинается с основ языка.

== Команда курса ==
* '''Руководитель и лектор курса:''' Виденин Сергей Александрович

* '''Семинаристы:'''
** Виденин Сергей Александрович
** Обжерин Евсей Романович
** Халтурин Евгений Александрович

* '''Ассистенты:'''
** Пелевин Леонид Андреевич
** Черноморцев Ярослав Сергеевич
** Якупов Динар Элинарович
** Шелегеда Наталья Андреевна
** Хомченко Илья Романович

== Коммуникация ==

Ссылка на чат курса [https://t.me/+8AWYEeSgSKMzMDk6 в Tg]

== Прогресс студентов ==

Таблица с оценками доступна в чате дисциплины

== Программа курса ==

{| class="wikitable"
! Неделя
! Темы лекций
! Темы семинаров
! Домашние задания
|-
| 1
| Введение в C++ и первая программа
| Знакомство со средой и первые программы
| '''ДЗ 1.''' Основы C++: текстовый обработчик данных. Срок сдачи: после 4-го семинара.
|-
| 2
| Объявления, выражения, управление потоком, ошибки
| Разбор ошибок и управляющих конструкций
|
|-
| 3
| Указатели, память, массивы
| Работа с указателями и динамической памятью
|
|-
| 4
| Функции, ссылки, const
| Функции и эффективная передача данных
| '''Сдача ДЗ 1'''
|-
| 5
| Классы и инкапсуляция
| Проектирование простых классов
| '''ДЗ 2.''' ООП: полиморфная предметная область.
|-
| 6
| Конструкторы, деструкторы, правило трёх
| Класс с управлением ресурсом (Rule of Three)
|
|-
| 7
| Наследование, интерфейсы и полиморфизм
| Полиморфная иерархия классов
|
|-
| 8
| SOLID, композиция, агрегация, паттерны
| Рефакторинг и проектирование
| '''Сдача ДЗ 2'''
|-
| 9
| Шаблоны
| Шаблоны на практике
| '''ДЗ 3.''' Шаблоны и исключения: generic-контейнер.
|-
| 10
| Исключения и RAII
| Безопасный код с исключениями
| '''Сдача ДЗ 3'''
|-
| 11
| Умные указатели
| Умные указатели вместо new/delete
| '''ДЗ 4.''' Современный C++: ресурсный менеджер.
|-
| 12
| Move-семантика и приведения типов
| Move и cast на практике
|
|-
| 13
| Вывод типов, лямбды, std::function
| Современный стиль C++
| '''Сдача ДЗ 4'''
|-
| 14
| STL: контейнеры, итераторы, алгоритмы
| STL на практике
| '''ДЗ 5.''' STL: прикладная задача на контейнерах и алгоритмах. Итоговый проект (параллельно с ДЗ 5).
|-
| 15
| Итоги: современный C++ и перспективы
| Итоговое занятие
| '''Сдача ДЗ 5.''' Защита итогового проекта.
|}

Более подробную программу курса можно посмотреть здесь:

[https://drive.google.com/file/d/13DYwVY4MAYvptY9fY_Gb8ZStGUsFwxlF/view?usp=drive_link Подробная программа курса]

== Критерии оценивания и формы контроля успеваемости ==

'''Описание и критерии оценивания домашних заданий и итогового проекта'''
{| class="wikitable"
!Название
!Срок сдачи
|-
|'''Домашнее задание 1. Основы C++: текстовый обработчик данных'''

'''Цель:''' Закрепить базовый синтаксис, работу с vector/map/string, функциями и корректной обработкой ошибок без ООП.
|После семинара 4 (конец 4-й недели)
|-
|'''Домашнее задание 2. ООП: полиморфная предметная область'''

'''Цель:''' Закрепить инкапсуляцию, правило трёх, наследование, полиморфизм и базовое проектирование (композиция предпочтительнее лишнего наследования).
| После семинара 8 (конец 8-й недели)
|-
|'''Домашнее задание 3. Шаблоны и исключения: generic-контейнер'''

'''Цель:''' Закрепить шаблоны классов, RAII, обработку ошибок и exception-safety.
|После семинара 10 (конец 10-й недели)
|-
|'''Домашнее задание 4. Современный C++: ресурсный менеджер'''

'''Цель:''' Закрепить умные указатели, move-семантику, правило пяти/нуля и современный стиль.
|После семинара 13 (конец 13-й недели)
|-
|'''Домашнее задание 5. STL: прикладная задача на контейнерах и алгоритмах'''

'''Цель:''' Закрепить выбор контейнеров, итераторы, алгоритмы STL и современный стиль.
|После семинара 14 (начало 15-й недели)
|-
|'''Итоговый проект'''

'''Цель:''' интегрировать все темы курса в законченную программу.

'''Формат защиты:''' Презентация 10 мин+ вопросы.
|Конец семестра
|}

'''Итоговая оценка по курсу''' формируется суммой баллов из следующих компонентов:

* Домашние задания: максимум 5 баллов (5 заданий по 1 баллу).
* Устный зачет: до 3 баллов.
* Командный проект: до 2 баллов.

Ни один из компонентов не является обязательным. Вы можете набрать необходимое число баллов любым удобным способом.
Набранные баллы напрямую переводятся в итоговую оценку по дисциплине.

== Материалы курса==

'''Список вопросов к экзамену можно посмотреть [https://drive.google.com/file/d/1TQ98OMNn5WlozV1mpayfIUXVPKqypSR0/view?usp=sharing здесь].'''

'''Рекомендуемая литература'''

'''Основы и синтаксис (с нуля)'''

# '''Бьерн Страуструп''' — ''«Программирование. Принципы и практика использования C++»''
#: Один из лучших вводных курсов от создателя языка. Много примеров, объясняет не только «как», но и «почему».
#
# '''Стенли Липпман, Жози Лажойе, Барбара Му''' — ''«Язык программирования C++. Базовый курс»'' (5-е издание)
#: Системное введение в язык и STL, с акцентом на правильные привычки и современные возможности C++.
#
# '''Герберт Шилдт''' — ''«C++: базовый курс»'' (3-е издание)
#: Более «школьный» формат: много задач, пошаговое объяснение синтаксиса.

'''Для тех, кто уже знает синтаксис'''

# '''Скотт Мейерс''' — ''«Эффективное использование C++»'' и ''«Наиболее эффективное использование C++»''
#: Классика: более 55 советов по стилю, управлению ресурсами, RAII, const и правильному использованию STL.
#
# '''Герб Саттер''' — ''«Новые сложные задачи на C++»'' и ''«Решение сложных задач на C++»''
#: Примеры нетривиальных ситуаций, показывают, как думать о коде, а не только о синтаксисе.
#
# '''Николай Джосаттис''' — ''«C++. Стандартная библиотека»''
#: Подробный справочник по STL: контейнеры, алгоритмы, итераторы, с примерами и замечаниями по эффективности.

'''Современный C++17/20 и продвинутые темы'''

# '''Бьерн Страуструп''' — ''«A Tour of C++»'' (2-е и 3-е издания)
#: Обзор современного C++ для опытных программистов: кратко, но полно о возможностях C++11/14/17/20, идеях дизайна и типичных паттернах.
#
# '''Андрей Александреску, Герб Саттер''' — ''«C++ Coding Standards: 101 Rules, Guidelines, and Best Practices»''
#: Стандарты кода, именование, безопасность, производительность, использование шаблонов и STL.
#
# '''Николай Джосаттис''' — ''«C++20. The Complete Guide»''
#: Обзор новых возможностей C++20: modules, coroutines, ranges, константные вычисления и улучшения шаблонов.

Программирование на языке C++. Продвинутый поток 2026

2026-10-29T15:24:08Z

Spirina.es: /* Коммуникация */

== О курсе ==

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

== Команда курса ==
Руководитель, лектор и семинарист: Мещерин Илья
 Семинарист (некоторые занятия): Долта Артём
 Ассистенты:
*Краснов Илья Витальевич
*Трофимов Михаил Алексеевич

== Программа курса ==
'''Форма контроля в осеннем семестре:''' дифференцированный зачет

{| class="wikitable"
! Неделя
! Лекция/ Семинар
|-
| 1
| Основные термины языка C++. Объекты, значения, переменные, типы. Объявления и определения, области видимости. Основные типы и операции над ними. Выражения и операторы. Приоритет операторов и порядок вычислений. Виды ошибок: ошибки компиляции (CE), ошибки времени выполнения (RE). Понятие неопределенного поведения (UB).
|-
| 2
| Указатели. Взятие адреса и разыменование. Арифметика указателей. Функции. Пергрузка функций. Указатели на функции. Массивы. Сходства и различия между массивами и указателями. Передача массивов в функции. Динамическая память, функции malloc/free, операторы new/delete. Статическая память и стек. Проблемы утечек памяти.
|-
| 3
| Ссылки. Особенности инициализации ссылок. Возврат ссылок из функций. Проблема висячих ссылок. Константы. Константные указатели и указатели на константу. Константные ссылки. Способы передачи аргументов в функцию. Способы приведения типов: static_cast, reinterpret_cast, const_cast.
|-
| 4
| Структуры и классы. Члены классов. Модификаторы доступа. Перегрузка операторов. Конструкторы и деструкторы. Операторы присваивания. Правило трех. Списки инициализации в конструкторах. Идиома copy-and-swap. Статические члены классов. Внутренние классы и локальные классы. Константные методы. Указатели на поля и методы.
|-
| 5
| Наследование. Публичное и приватное наследование. Видимость и доступность членов класса при наследовании. Использование using. Размещение объектов в памяти при наследовании. Приведения типов при наследовании. Принцип подстановки Лисков. Множественное наследование. Diamond problem. Виртуальное наследование.
|-
| 6
| Полиморфизм. Виртуальные функции. Ключевое слово override. Чисто виртуальные функции. Таблицы виртуальных функций. Внутреннее устройство vtable. Понятие ABI. Внутреннее устройство указателей на члены класса. Проблема виртуальных функций в конструкторах. Ошибка pure vitrual method call.
|-
| 7
| Стадии компиляции. Препроцессинг. Ассемблирование. Линковка, единицы трансляции. Ключевое слово extern. Правило одного определения и ключевое слово inline. Оптимизации компилятора. Примеры нетривиального UB из-за оптимизаций. Санитайзеры.
|-
| 8
| Шаблоны классов, функций, типов, переменных. Перегрузка шаблонных функций. Частичная и полная специализация шаблонов. Особенности определения шаблонных функций. Числовые параметры шаблонов. Простейшие compile-time вычисления. Шаблонные параметры шаблонов. Простейшие метафункции и их реализация. Зависимые имена. Шаблоны с переменным числом аргументов. Выражения свертки.
|-
| 9
| Исключения. Отличие исключений от RE. Особенности перехвата исключений. Проблема исключений в конструкторах и деструкторах. Идиома RAII и умные указатели. Множественные исключения, функция uncaught_exceptions. Иерархия стандартных исключений. Внутреннее устройство механизма обработки исключений.
|-
| 10
| Устройство стандартных контейнеров: vector, list, deque, map, unordered_map. Особенности vector<bool>. Реализация методов push_back и reserve для vector. Конструкция placement new. Итераторы. Инвалидация итераторов. Константные и неконстантные итераторы. Обратные итераторы. Категории итераторов.
|}

==Коммуникация==
Чат приватный. В чат студенты добавляются только по результату контеста.

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

Алгоритмы и структуры данных I. Иностранный поток 2026

2026-10-29T15:05:36Z

Spirina.es: /* Прогресс студентов */

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

== Программа курса ==
Курс двухсеместровый

'''Форма контроля в осеннем семестре:''' экзамен

{| class="wikitable"
! Неделя
! Лекция / Семинар
|-
| 1
| Анализ алгоритмов и асимптотика
|-
| 2
| Бинарный поиск и методы поиска ответа
|-
| 3
| Линейные структуры данных
|-
| 4
| Амортизационный анализ
|-
| 5
| Префиксные суммы и задачи диапазонов
|-
| 6
| Сортировки I: фундаментальные алгоритмы
|-
| 7
| Сортировки II: быстрые алгоритмы
|-
| 8
| Кучи и приоритетные очереди
|-
| 9
| Деревья поиска I
|-
| 10
| Деревья поиска II: самобалансирующиеся деревья
|-
| 11
| Структуры данных для запросов на отрезках
|-
| 12
| Продвинутые структуры данных
|-
| 13
| Хеширование и вероятностные структуры
|-
| 14
| Динамическое программирование
|-
| 15
| Матричные методы и вычислительная геометрия
|}

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

Лектор: Смолин Александр Андреевич

Семинарист: Мешков Владислав Сергеевич

== Коммуникация ==

== Прогресс студентов ==

таблица с оценками доступна студентам в канале дисциплины

== Критерии оценивания и формы контроля успеваемости ==

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

Экзамен будет проходить в четыре этапа: три основных и один бонусный.

1. Выдается билет, содержащий четыре вопроса из программы. Ответ на каждый вопрос оценивается из 1.5 баллов. При оценке ответа на какой-либо вопрос ниже 0.5 ставится автоматически пересдача. На подготовку ответа дается 1 час. За ответ на эту часть программы дается до шести баллов. Продолжительность ответа в ходе данной части экзамена не должна превышать 45 минут. Экзаменатор имеет право попросить сформулировать смежные по теме определения и формулировки утверждений и теорем, не указанные явно в вопросе. При использовании утверждения или теоремы из данного курса экзаменатор имеет право поинтересоваться ее доказательством.

2. Далее идет блиц-опрос по программе, за который дается не более одного балла. В его ходе экзаменатор имеет право спросить любое определение и формулировку любой теоремы из курса. Также он может поинтересоваться постановкой задачи, которую решает некоторый алгоритм. Отвечать необходимо практически сразу, без долгих размышлений.

'''Если на текущий момент у студента меньше 5.5 баллов, то экзамен заканчивается.'''

3. Заключительная часть экзамена состоит в том, что вам будут предложены для решения две задачи. Сначала идет задача среднего уровня сложности. Ее решение принесет вам два балла и возможность получить задачу на 10, если за первые два этапа было не менее 6.5 баллов. Если же задача не решена, то выдается задача «попроще», за решение которой дается один балл. Время подготовки ответа на задачу попроще составляет 25 минут, на задачу среднего уровня — 40 минут.

4. *В случае, если вы претендуете на отл(10), вам нужно сообщить об этом экзаменатору. После консультации с лектором он выдаст задачу продвинутого уровня сложности. Подготовка и ответ этого этапа не должны превышать полутора часов.
*В случае, если на какой-то из стадий экзамена истекло выделенное время, экзаменатор имеет право прервать экзамен и выставить оценку на основе данных вами ответов.
Если вам необходимо отлучиться в ходе экзамена, это можно сделать только между стадиями или между задачами из третьего этапа.
*В случае несогласия с оценкой вы имеете право отапеллировать ее у лектора до выхода из аудитории.

Программирование на языке C++. Продвинутый поток 2026

2026-10-29T15:02:53Z

Spirina.es: /* Прогресс студентов */

== О курсе ==

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

== Команда курса ==
Руководитель, лектор и семинарист: Мещерин Илья
 Семинарист (некоторые занятия): Долта Артём
 Ассистенты:
*Краснов Илья Витальевич
*Трофимов Михаил Алексеевич

== Программа курса ==
'''Форма контроля в осеннем семестре:''' дифференцированный зачет

{| class="wikitable"
! Неделя
! Лекция/ Семинар
|-
| 1
| Основные термины языка C++. Объекты, значения, переменные, типы. Объявления и определения, области видимости. Основные типы и операции над ними. Выражения и операторы. Приоритет операторов и порядок вычислений. Виды ошибок: ошибки компиляции (CE), ошибки времени выполнения (RE). Понятие неопределенного поведения (UB).
|-
| 2
| Указатели. Взятие адреса и разыменование. Арифметика указателей. Функции. Пергрузка функций. Указатели на функции. Массивы. Сходства и различия между массивами и указателями. Передача массивов в функции. Динамическая память, функции malloc/free, операторы new/delete. Статическая память и стек. Проблемы утечек памяти.
|-
| 3
| Ссылки. Особенности инициализации ссылок. Возврат ссылок из функций. Проблема висячих ссылок. Константы. Константные указатели и указатели на константу. Константные ссылки. Способы передачи аргументов в функцию. Способы приведения типов: static_cast, reinterpret_cast, const_cast.
|-
| 4
| Структуры и классы. Члены классов. Модификаторы доступа. Перегрузка операторов. Конструкторы и деструкторы. Операторы присваивания. Правило трех. Списки инициализации в конструкторах. Идиома copy-and-swap. Статические члены классов. Внутренние классы и локальные классы. Константные методы. Указатели на поля и методы.
|-
| 5
| Наследование. Публичное и приватное наследование. Видимость и доступность членов класса при наследовании. Использование using. Размещение объектов в памяти при наследовании. Приведения типов при наследовании. Принцип подстановки Лисков. Множественное наследование. Diamond problem. Виртуальное наследование.
|-
| 6
| Полиморфизм. Виртуальные функции. Ключевое слово override. Чисто виртуальные функции. Таблицы виртуальных функций. Внутреннее устройство vtable. Понятие ABI. Внутреннее устройство указателей на члены класса. Проблема виртуальных функций в конструкторах. Ошибка pure vitrual method call.
|-
| 7
| Стадии компиляции. Препроцессинг. Ассемблирование. Линковка, единицы трансляции. Ключевое слово extern. Правило одного определения и ключевое слово inline. Оптимизации компилятора. Примеры нетривиального UB из-за оптимизаций. Санитайзеры.
|-
| 8
| Шаблоны классов, функций, типов, переменных. Перегрузка шаблонных функций. Частичная и полная специализация шаблонов. Особенности определения шаблонных функций. Числовые параметры шаблонов. Простейшие compile-time вычисления. Шаблонные параметры шаблонов. Простейшие метафункции и их реализация. Зависимые имена. Шаблоны с переменным числом аргументов. Выражения свертки.
|-
| 9
| Исключения. Отличие исключений от RE. Особенности перехвата исключений. Проблема исключений в конструкторах и деструкторах. Идиома RAII и умные указатели. Множественные исключения, функция uncaught_exceptions. Иерархия стандартных исключений. Внутреннее устройство механизма обработки исключений.
|-
| 10
| Устройство стандартных контейнеров: vector, list, deque, map, unordered_map. Особенности vector<bool>. Реализация методов push_back и reserve для vector. Конструкция placement new. Итераторы. Инвалидация итераторов. Константные и неконстантные итераторы. Обратные итераторы. Категории итераторов.
|}

==Коммуникация==
Ссылка на чат курса в мессенджере (ближе к старту семестра)

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

Программирование на языке C++. Основной поток 2026

2026-10-29T14:52:29Z

Spirina.es: /* Прогресс студентов */

== О курсе ==

'''Первый (осенний) семестр''' предназначен для начинающих разработчиков на C++.

'''Второй (весенний) семестр''' даёт углублённое понимание тонкостей языка и раскрывает особенности возможностей новых стандартов. Подойдёт как для тех, у кого C++ является первым опытом программирования, так и для тех, кто переходит на C++ с других языков.

Важной особенностью курса является то, что упор делается на большое количество практики, код-ревью и устные сдачи. Данный подход позволяет выстроить сильный фундамент для дальнейшего профессионального развития как C++-разработчика, так и в любой другой IT-специальности.

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

'''Руководитель курса и лектор:''' Попов Павел Александрович

'''Семинаристы:'''
* Драгун Константин Юрьевич
* Гарбузов Николай Алексеевич
* Русецкий Дмитрий Сергеевич
* Вашкевич Егор Сергеевич
* Лунга Артём Романович
* Погадаев Никита Максимович

== Программа курса ==

'''Формы контроля:'''

'''Осенний семестр''' — дифференцированный зачёт.

'''Весенний семестр''' — экзамен.

'''Программа курса осеннего семестра'''
{| class="wikitable"
! Неделя
! Тема
! Задачи
|-
| 1
| Введение. Простейшая программа. Объявления и определения, скоупы.
|
|-
| 2
| Основные типы и операции над ними. Выражения и операторы.
|
|-
| 3
| Control statements. Compile-time errors, runtime errors. Undefined behavior и unspecified behavior.
|
|-
| 4
| Указатели. Виды памяти.
|
|-
| 5
| Динамическая память. Массивы. Указатели на функции.
|Stack
|-
| 6
| Ссылки. Константы. Константные указатели и ссылки.
| Stack
|-
| 7
| Приведения типов. Классы и структуры. Модификаторы доступа.
| String
|-
| 8
| Конструкторы и деструкторы. Оператор присваивания. Правило трёх.
|
|-
| 9
| Перегрузка операторов. Const-, static-, explicit-методы. Указатели на члены.
| BigInteger
|-
| 10
| Наследование и его виды. Видимость и доступность методов при наследовании. Конструкторы и деструкторы при наследовании.
| Rational
|-
| 11
| Приведения типов при наследовании. Множественное наследование. Виртуальные функции и полиморфные типы.
|
|-
| 12
| Абстрактные классы. Pure virtual функции. RTTI и dynamic_cast. Таблицы виртуальных функций.
| Geometry
|-
| 13
| Виртуальные функции (окончание). Шаблоны. Перегрузка и специализация шаблонов.
|
|-
| 14
| Вычисления на шаблонах. Метафункции. Зависимые имена.
| Matrix
|-
| 15
| Вариативные шаблоны. Исключения. Идиома RAII.
|
|}

'''Весенний семестр'''

{| class="wikitable"
! Неделя
! Лекции
! Задачи
|-
| 16
| Исключения в конструкторах и деструкторах. noexcept. Exception-safety.
| Residue
|-
| 17
| Контейнеры. Внутреннее устройство vector и deque.
|
|-
| 18
| Устройство deque. Итераторы, виды итераторов, инвалидация итераторов. Внутреннее устройство list.
| Deque
|-
| 19
| Внутреннее устройство map. Классы string_view и span. Идея аллокаторов.
|
|-
| 20
| Внутреннее устройство unordered_map. Allocator traits. Allocator-aware контейнеры.
|
|-
| 21
| Выравнивания. Перегрузка new/delete. Идея move-семантики. Move-конструкторы и move-assignment операторы.
| List and StackAllocator
|-
| 22
| Определения lvalue и rvalue. Rvalue-ссылки. Reference qualifiers. Perfect forwarding. Универсальные ссылки. std::forward.
|
|-
| 23
| Реализация std::move и std::forward. xvalues, RVO, copy elision, temporary materialization. Функция move_if_noexcept.
|
|-
| 24
| Вывод типов auto, decltype. CTAD, template deduction guides. Tuples, structured bindings, tuple-like types.
| Unordered Map
|-
| 25
| unique_ptr, shared_ptr, weak_ptr, make_shared, enable_shared_from_this. Type erasure. std::any.
|
|-
| 26
| Стирание типов в shared_ptr. Шаблонное метапрограммирование. Идиома SFINAE. Реализация is_class. Метафункция enable_if.
| SharedPtr
|-
| 27
| Реализация has_method_construct, is_base_of. Спецификатор и оператор requires. Концепты.
|
|-
| 28
| Лямбды. Замыкания. Списки захвата. Захват с инициализацией. Захват this. Обобщённые лямбды.
| Tuple
|-
| 29
| Шаблонные лямбды. std::function, std::bind, std::reference_wrapper, std::invoke. Идея реализации std::function.
|
|-
| 30
| Constexpr-переменные и функции. Compile-time вычисления.
| Function
|}

'''На каждую задачу:'''

срок сдачи в контест — 3 недели (2 недели без штрафа);

срок прохождения ревью (в том числе устного) — 4 недели с момента релиза задачи и 3 попытки;

== Коммуникация ==

Ссылка на чат курса в мессенджере (будет опубликована ближе к старту семестра).

== Прогресс студентов ==

таблица с оценками доступна студентам в канале дисциплины

== Критерии оценивания и формы контроля успеваемости ==

'''Осенний семестр'''

Итоговая оценка по задачам вычисляется по формуле:

Итоговая оценка по задачам считается так:

* формула: (кол-во баллов по сданным задачам - штрафы за скат) / кол-во баллов за все задачи * 7
* финальная контрольная работа является блокирующей и приносит от 0 до 3 баллов (при баллах ниже порога, который считается после сдачи кр, зачет считается не сданным и переходит в ранг пересдачи)
* Итоговая оценка складывается из максимальных баллов (7 за задачи + 3 за к.р. + 1 от семинариста) и итог округляется вниз.

'''Весенний семестр'''

1. Баллы за сданные задачи ограничивают оценку таким образом:
*учитываются 6 задач с коэффициентом (о нем ниже) + баллы за задачу reze
*нормировка выглядит следующим образом
1) 1 задача -> ее баллы * 1.0
2) 2 задачи -> их баллы * 1.1
3) 3 задачи -> их баллы * 1.2
4) 4 задачи -> их баллы * 1.3
5) 5 задачи -> их баллы * 1.4
6) 6 задачи -> их баллы * 1.5

*чтобы иметь возможность получить оценку уд. необходимо сдать 1-2 задачи (не учитывая Residue) + сумма баллов всех сданных задач 250-449.
*чтобы иметь возможность получить оценку хор. необходимо сдать 3-4 задачи (не учитывая Residue) + сумма баллов всех сданных задач 450-749.
*чтобы иметь возможность получить оценку отл. необходимо сдать 5-6 задачи (не учитывая Residue) + сумма баллов всех сданных задач 750-1000+.
*финальная сумма баллов переводится в оценку по формуле баллы / 100. Например, 740 баллов переходят в оценку 7, а 755 в оценку 8 по правилу округления.

2. Сам процесс сдачи экзамена:
* при сдаче на уд. - отвечаются 2 билета на уд.
* при сдаче на хор. - отвечаются 2 билета на уд. и 2 билета на хор.
* при сдаче на отл. - отвечаются 2 билета на хор и 2 билета на отл.

3. Если у вас одна из следующих ситуаций, то есть возможность повысить оценку:
* 2 (не учитывая Residue) задачи и больше 500 баллов, то можно ответить на оценку хор 5 (для этого необходимо успешно ответить все билеты на оценку уд. и затем 2 дополнительных билета на хор.)
* 4 (не учитывая Residue) задачи и больше 800 баллов, то можно ответить на оценку отл 8 (для этого необходимо успешно ответить все билеты на оценку хор. и затем 2 дополнительных билета на отл.)

4. При успешной сдаче 3+ задач (то есть вы успешно сдали 4-6 задач) в семестре (не учитывая Residue) билеты на уд. отвечать не обязательно.

5. При успешной сдаче 4+ задач (то есть вы успешно сдали 5-6 задач, не учитывая Residue), есть возможность вытянуть 3 билета на хор и 3 билета на отл, но выбрать из каждого множества по 2 для ответа на экзамене.

Крайне рекомендуем досдать все задачи как можно раньше, чтобы идти на экзамен с максимально возможным количеством баллов))))

'''Пример расчёта баллов.'''
Сиксевенов Пабло Ильич решил за семестр Residue на 90 баллов, list на 180, tuple на 200.
Получаем такую формулу расчёта его баллов: (180 + 200) * 1.1 + 90 = 508. - Ему необходимо ответить 2 билета на уд тк на уд достаточно решено задач и баллов.
Если все успешно, он может попробовать сдать на хор, тк у него 500+ баллов, для получения оценки хор 5 ему необходимо успешно ответить 2 билета на хор.

== Материалы курса ==

Видеолекции

* [https://vkvideo.ru/playlist/-206078025_142 Видеолекции первого семестра]
* [https://vkvideo.ru/playlist/-206078025_238/season_undefined Видеолекции второго семестра]

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

Программирование на языке C++. Основной поток 2026

2026-10-29T14:50:04Z

Spirina.es: /* Команда курса */

== О курсе ==

'''Первый (осенний) семестр''' предназначен для начинающих разработчиков на C++.

'''Второй (весенний) семестр''' даёт углублённое понимание тонкостей языка и раскрывает особенности возможностей новых стандартов. Подойдёт как для тех, у кого C++ является первым опытом программирования, так и для тех, кто переходит на C++ с других языков.

Важной особенностью курса является то, что упор делается на большое количество практики, код-ревью и устные сдачи. Данный подход позволяет выстроить сильный фундамент для дальнейшего профессионального развития как C++-разработчика, так и в любой другой IT-специальности.

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

'''Руководитель курса и лектор:''' Попов Павел Александрович

'''Семинаристы:'''
* Драгун Константин Юрьевич
* Гарбузов Николай Алексеевич
* Русецкий Дмитрий Сергеевич
* Вашкевич Егор Сергеевич
* Лунга Артём Романович
* Погадаев Никита Максимович

== Программа курса ==

'''Формы контроля:'''

'''Осенний семестр''' — дифференцированный зачёт.

'''Весенний семестр''' — экзамен.

'''Программа курса осеннего семестра'''
{| class="wikitable"
! Неделя
! Тема
! Задачи
|-
| 1
| Введение. Простейшая программа. Объявления и определения, скоупы.
|
|-
| 2
| Основные типы и операции над ними. Выражения и операторы.
|
|-
| 3
| Control statements. Compile-time errors, runtime errors. Undefined behavior и unspecified behavior.
|
|-
| 4
| Указатели. Виды памяти.
|
|-
| 5
| Динамическая память. Массивы. Указатели на функции.
|Stack
|-
| 6
| Ссылки. Константы. Константные указатели и ссылки.
| Stack
|-
| 7
| Приведения типов. Классы и структуры. Модификаторы доступа.
| String
|-
| 8
| Конструкторы и деструкторы. Оператор присваивания. Правило трёх.
|
|-
| 9
| Перегрузка операторов. Const-, static-, explicit-методы. Указатели на члены.
| BigInteger
|-
| 10
| Наследование и его виды. Видимость и доступность методов при наследовании. Конструкторы и деструкторы при наследовании.
| Rational
|-
| 11
| Приведения типов при наследовании. Множественное наследование. Виртуальные функции и полиморфные типы.
|
|-
| 12
| Абстрактные классы. Pure virtual функции. RTTI и dynamic_cast. Таблицы виртуальных функций.
| Geometry
|-
| 13
| Виртуальные функции (окончание). Шаблоны. Перегрузка и специализация шаблонов.
|
|-
| 14
| Вычисления на шаблонах. Метафункции. Зависимые имена.
| Matrix
|-
| 15
| Вариативные шаблоны. Исключения. Идиома RAII.
|
|}

'''Весенний семестр'''

{| class="wikitable"
! Неделя
! Лекции
! Задачи
|-
| 16
| Исключения в конструкторах и деструкторах. noexcept. Exception-safety.
| Residue
|-
| 17
| Контейнеры. Внутреннее устройство vector и deque.
|
|-
| 18
| Устройство deque. Итераторы, виды итераторов, инвалидация итераторов. Внутреннее устройство list.
| Deque
|-
| 19
| Внутреннее устройство map. Классы string_view и span. Идея аллокаторов.
|
|-
| 20
| Внутреннее устройство unordered_map. Allocator traits. Allocator-aware контейнеры.
|
|-
| 21
| Выравнивания. Перегрузка new/delete. Идея move-семантики. Move-конструкторы и move-assignment операторы.
| List and StackAllocator
|-
| 22
| Определения lvalue и rvalue. Rvalue-ссылки. Reference qualifiers. Perfect forwarding. Универсальные ссылки. std::forward.
|
|-
| 23
| Реализация std::move и std::forward. xvalues, RVO, copy elision, temporary materialization. Функция move_if_noexcept.
|
|-
| 24
| Вывод типов auto, decltype. CTAD, template deduction guides. Tuples, structured bindings, tuple-like types.
| Unordered Map
|-
| 25
| unique_ptr, shared_ptr, weak_ptr, make_shared, enable_shared_from_this. Type erasure. std::any.
|
|-
| 26
| Стирание типов в shared_ptr. Шаблонное метапрограммирование. Идиома SFINAE. Реализация is_class. Метафункция enable_if.
| SharedPtr
|-
| 27
| Реализация has_method_construct, is_base_of. Спецификатор и оператор requires. Концепты.
|
|-
| 28
| Лямбды. Замыкания. Списки захвата. Захват с инициализацией. Захват this. Обобщённые лямбды.
| Tuple
|-
| 29
| Шаблонные лямбды. std::function, std::bind, std::reference_wrapper, std::invoke. Идея реализации std::function.
|
|-
| 30
| Constexpr-переменные и функции. Compile-time вычисления.
| Function
|}

'''На каждую задачу:'''

срок сдачи в контест — 3 недели (2 недели без штрафа);

срок прохождения ревью (в том числе устного) — 4 недели с момента релиза задачи и 3 попытки;

== Коммуникация ==

Ссылка на чат курса в мессенджере (будет опубликована ближе к старту семестра).

== Прогресс студентов ==

Ссылка на таблицу студентов с оценками (будет опубликована ближе к старту семестра).

== Критерии оценивания и формы контроля успеваемости ==

'''Осенний семестр'''

Итоговая оценка по задачам вычисляется по формуле:

Итоговая оценка по задачам считается так:

* формула: (кол-во баллов по сданным задачам - штрафы за скат) / кол-во баллов за все задачи * 7
* финальная контрольная работа является блокирующей и приносит от 0 до 3 баллов (при баллах ниже порога, который считается после сдачи кр, зачет считается не сданным и переходит в ранг пересдачи)
* Итоговая оценка складывается из максимальных баллов (7 за задачи + 3 за к.р. + 1 от семинариста) и итог округляется вниз.

'''Весенний семестр'''

1. Баллы за сданные задачи ограничивают оценку таким образом:
*учитываются 6 задач с коэффициентом (о нем ниже) + баллы за задачу reze
*нормировка выглядит следующим образом
1) 1 задача -> ее баллы * 1.0
2) 2 задачи -> их баллы * 1.1
3) 3 задачи -> их баллы * 1.2
4) 4 задачи -> их баллы * 1.3
5) 5 задачи -> их баллы * 1.4
6) 6 задачи -> их баллы * 1.5

*чтобы иметь возможность получить оценку уд. необходимо сдать 1-2 задачи (не учитывая Residue) + сумма баллов всех сданных задач 250-449.
*чтобы иметь возможность получить оценку хор. необходимо сдать 3-4 задачи (не учитывая Residue) + сумма баллов всех сданных задач 450-749.
*чтобы иметь возможность получить оценку отл. необходимо сдать 5-6 задачи (не учитывая Residue) + сумма баллов всех сданных задач 750-1000+.
*финальная сумма баллов переводится в оценку по формуле баллы / 100. Например, 740 баллов переходят в оценку 7, а 755 в оценку 8 по правилу округления.

2. Сам процесс сдачи экзамена:
* при сдаче на уд. - отвечаются 2 билета на уд.
* при сдаче на хор. - отвечаются 2 билета на уд. и 2 билета на хор.
* при сдаче на отл. - отвечаются 2 билета на хор и 2 билета на отл.

3. Если у вас одна из следующих ситуаций, то есть возможность повысить оценку:
* 2 (не учитывая Residue) задачи и больше 500 баллов, то можно ответить на оценку хор 5 (для этого необходимо успешно ответить все билеты на оценку уд. и затем 2 дополнительных билета на хор.)
* 4 (не учитывая Residue) задачи и больше 800 баллов, то можно ответить на оценку отл 8 (для этого необходимо успешно ответить все билеты на оценку хор. и затем 2 дополнительных билета на отл.)

4. При успешной сдаче 3+ задач (то есть вы успешно сдали 4-6 задач) в семестре (не учитывая Residue) билеты на уд. отвечать не обязательно.

5. При успешной сдаче 4+ задач (то есть вы успешно сдали 5-6 задач, не учитывая Residue), есть возможность вытянуть 3 билета на хор и 3 билета на отл, но выбрать из каждого множества по 2 для ответа на экзамене.

Крайне рекомендуем досдать все задачи как можно раньше, чтобы идти на экзамен с максимально возможным количеством баллов))))

'''Пример расчёта баллов.'''
Сиксевенов Пабло Ильич решил за семестр Residue на 90 баллов, list на 180, tuple на 200.
Получаем такую формулу расчёта его баллов: (180 + 200) * 1.1 + 90 = 508. - Ему необходимо ответить 2 билета на уд тк на уд достаточно решено задач и баллов.
Если все успешно, он может попробовать сдать на хор, тк у него 500+ баллов, для получения оценки хор 5 ему необходимо успешно ответить 2 билета на хор.

== Материалы курса ==

Видеолекции

* [https://vkvideo.ru/playlist/-206078025_142 Видеолекции первого семестра]
* [https://vkvideo.ru/playlist/-206078025_238/season_undefined Видеолекции второго семестра]

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

Алгоритмы и структуры данных I. Основной поток 2026

2026-10-29T14:49:09Z

Spirina.es: /* Прогресс студентов */

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

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

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

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

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

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

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

'''Семинаристы:'''
 Спицын Николай Антонович
 Смышляев Федор Витальевич
 Белков Иван Иванович
 Подзорова Полина Владимировна
 Халтурин Евгений Александрович
 Чернецкий Аркадий Михайлович
 Сбродов Егор Алексеевич
 Вашкевич Егор Сергеевич
 Чубенко Полина Николаевна
 Савичев Дмитрий Александрович
 Нагибин Всеволод Владимирович
 Климанова Ирина Евгеньевна
 Кулешов Игорь Вячеславович
 Цой Максим Вячеславович
 Клячин Артемий Владиславович

== Программа курса ==
В семестре 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||Хэш-таблицы (продолжение).||
|}

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

[https://t.me/ads_general2026 чат] курса

== Прогресс студентов ==

таблица с оценками доступна студентам в канале дисциплины

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

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

Список задач будет окончательно известен только ближе к концу семестра, поэтому заранее невозможно спрогнозировать, какие будут пороги на каждую оценку.
Чтобы заработать минимальную положительную оценку (уд. 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.

Формальные языки и трансляции 2026

2026-10-29T14:23:19Z

Spirina.es:

== О курсе ==

Курс отвечает на четыре вопроса, и все они про то, как машина понимает текст:

* Как автоматически определять типы слов?
* Как автоматически разбирать предложения на слова?
* Как разбор связан с машинами Тьюринга?
* Как разбор работает в компиляторах?

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

Курс математический: почти каждое утверждение доказывается на лекции целиком, а не предъявляется готовым. Практическая часть при этом никуда не девается, потому что каждый изученный объект превращается в алгоритм с оценкой сложности.

== Пререквизиты ==

* '''Дискретная математика и математическая логика.''' Отношения эквивалентности, индукция, разрешимость и неразрешимость. Неразрешимость мы не доказываем заново, а пользуемся ей.
* '''Алгебра.''' Понятие моноида и подмоноида приходит из теории групп, здесь оно применяется к языкам.
* '''Алгоритмы и структуры данных.''' Обходы графов, динамическое программирование, оценка асимптотики.
* '''Программирование''' на любом языке, если выбирается практический вариант отчётности.

== Результаты обучения ==

К концу семестра студент умеет:

* Строить конечный автомат по регулярному выражению и обратно, минимизировать автомат и доказывать, что он минимальный.
* Доказывать, что язык не является автоматным или не является контекстно-свободным, причём тремя разными способами: леммой о разрастании, теоремой Майхилла и Нероуда и замкнутостью относительно операций.
* Приводить грамматику к нормальным формам Хомского и Грейбах и понимать, зачем нужна каждая.
* Разбирать слово по грамматике алгоритмами Кока, Янгера и Касами, Эрли и LR(k), оценивая стоимость каждого.
* Строить конечный преобразователь для заданного преобразования и раскладывать его по теореме Нива.

== Команда курса ==
'''Лектор:''' Ахтямов Павел Ибрагимович
'''Семинаристы:''' Обжерин Евсей Романович
Горбулев Алексей Ильич
Шпилевой Денис
Терехова Ольга Алексеевна
Накорнеева Юлия Альбертовна
Сазанович Михаил Дмитриевич
Спицын Николай Антонович
Игнатьев Николай Эдуардович

== Как устроены занятия ==

Семестр идёт 15 недель. Каждая неделя состоит из одной лекции и одного семинара, оба занятия по два академических часа, то есть по час двадцать.

Лекция даёт конструкцию вместе с её доказательством, семинар отрабатывает применение на задачах.

Домашние задания выдаются примерно раз в две недели и написаны сюжетом: орочья война, кобольды с драконом, Великая Библиотека Грамматик. Формулировки от этого не становятся проще, зато условие запоминается.

== Программа курса ==

Семестр рассчитан на 15 недель. Темы восстановлены по материалам потока 2025 года, контрольные стоят на неделях 6 и 15.

{| class="wikitable"
! № недели
! Лекция
! Семинар
! Домашнее задание
|-
| 1
| НКА, конфигурации, упрощения автомата
| Регулярные выражения
| ДЗ 1. Регулярные языки
|-
| 2
| Удаление ε-переходов, распознавание слова, переход к ДКА
| Конечные автоматы
| ДЗ 2. Автоматы и ε-переходы
|-
| 3
| Построение ДКА, замкнутость, теорема Клини
| Построение ДКА, теорема Клини
| ДЗ 3. Детерминизация и дополнение
|-
| 4
| Лемма о разрастании, эквивалентность слов, классы Σ*/∼
| Теорема Клини, лемма о разрастании, минимизация
|
|-
| 5
| Единственность и построение МПДКА, Майхилл и Нероуд
| Лемма о разрастании, эквивалентность языков
| ДЗ 4. Минимизация, Майхилл и Нероуд
|-
| 6
| Иерархия Хомского, деревья вывода, однозначность
| '''Контрольная 1''' (весь семинар)
|
|-
| 7
| Форма Хомского, CYK, разрастание
| Контекстно-свободные грамматики
| ДЗ 5. Грамматики и иерархия Хомского
|-
| 8
| Автоматы с магазинной памятью, эквивалентность с КС-грамматиками
| Форма Хомского, CYK, разрастание
| ДЗ 6. Нормальная форма Хомского и CYK
|-
| 9
| Алгоритм Эрли: ситуации, корректность, сложность
| МП-автоматы
| ДЗ 7. МП-автоматы
|-
| 10
| Форма Грейбах, пересечение с регулярным языком
| Алгоритм Эрли
|
|-
| 11
| LR(k): восходящий разбор, активные префиксы, LR(k)-ситуации
| Лемма Огдена, перенос-свёртка
|
|-
| 12
| LR(k): построение таблиц, критерий класса
| LR(k)-разбор
| ДЗ 8. LR(k)-грамматики
|-
| 13
| LR(k): корректность разбора и линейность
| Преобразователи, контекстная замена
|
|-
| 14
| Преобразователи: определение и примеры
| Лемма о накачке, теорема Хомского и Шютценберже
| ДЗ 9. Преобразователи, лемма о накачке
|-
| 15
| Композиция, теорема Нива, замкнутость КС-языков
| '''Контрольная 2''' (весь семинар)
|
|}

Контрольная работа занимает семинар целиком, поэтому на неделях 6 и 15 семинарской темы нет. Отсюда общий сдвиг: начиная с седьмой недели семинар отрабатывает материал предыдущей лекции, и для этого курса так даже лучше, потому что между доказательством и задачами появляется пауза.

'''Контрольная 1''' закрывает автоматный блок: регулярные выражения, построение и минимизацию автомата, доказательство неавтоматности.

'''Контрольная 2''' проходит на последней неделе и закрывает контекстно-свободный блок вместе с алгоритмами разбора.

Домашние задания в начале семестра идут еженедельно, а дальше выдаются раз в две недели, когда тема требует больше времени на осмысление. Задачи девятого задания про разложение по теореме Нива опираются на лекцию последней недели, поэтому дедлайн у него уходит за конец семестра.

== Дополнительные темы для сильных групп ==

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

* '''Лемма Огдена''' и доказательство существенной неоднозначности языков (семинар 9).
* '''Теорема Париха''', полулинейные множества и следствие про однобуквенный алфавит (дополнительный семинар).
* '''Теорема Хомского и Шютценберже''' в слабой и сильной формах через язык Дика (семинары 12 и 13).
* '''Индексированные грамматики''' как взгляд за пределы иерархии.

== Оценивание ==

=== Как складывается итоговая оценка ===

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

'''Экзамен блокирующий.''' Семестровые баллы не компенсируют его провал, каким бы высоким ни был их запас. Смысл такого правила простой: курс проверяет умение доказывать, а доказательство защищается в разговоре, а не накапливается баллами.

=== Баллы за семестр ===

Максимум за семестр составляет 50 баллов, и эти 50 баллов и есть первая половина итоговой оценки.

{| class="wikitable"
! Составляющая
! Баллы
! Когда
|-
| Контрольная работа 1
| 10
| Неделя 6, весь семинар
|-
| Контрольная работа 2
| 10
| Неделя 15, весь семинар
|-
| Сдача домашних заданий
| 10
| Девять заданий за семестр
|-
| Активность на семинарах
| До 3 бонусных
| В течение семестра
|}

Оставшиеся 25 баллов зависят от выбранного потока.

'''Теоретический поток''' сдаёт коллоквиум на 10 баллов и делает доклад на 10 баллов. В этом году коллоквиум проводится только здесь.

'''Практический поток''' делает практикум на 10 баллов, реализуя изученные в курсе алгоритмы, и защищает его устно ещё на 10 баллов. Устная защита практикума заменяет коллоквиум: разговор с преподавателем происходит в обоих потоках, просто в одном он идёт про доказательство сложного факта, а в другом про собственный код.

=== Выбор потока ===

Решение принимается до середины октября. Время на выбор даётся специально: сначала мы пробуем и то и другое, а потом каждый решает, что ему ближе. Раньше середины октября выбирать не нужно, а после этого срока поток менять уже поздно, потому что подготовка доклада и написание практикума занимают остаток семестра.

Разница между потоками не в сложности, а в характере работы. Теоретический поток ближе тем, кому нравится разбираться в доказательствах и рассказывать их; практический подойдёт тем, кто хочет увидеть, как изученные алгоритмы ведут себя на реальном входе.

=== Контрольные работы ===

Каждая контрольная занимает семинар целиком.

Первая проверяет автоматный блок: построение и минимизацию автомата, переход между автоматами и регулярными выражениями, доказательство неавтоматности языка.

Вторая проходит на последней неделе и проверяет контекстно-свободный блок вместе с алгоритмами разбора.

=== Домашние задания ===

За семестр выдаётся девять заданий. Первые три идут еженедельно, пока в курсе автоматный блок с короткими формулировками, дальше задания выдаются раз в две недели.

Задачи внутри задания оцениваются отдельно, и вес задачи указан в условии.

== Экзамен ==

Экзамен устный. Структура экзамена будет известна позднее.

== Литература ==

* М. Р. Пентус. ''Математическая теория формальных языков''.
* А. Ахо, Д. Ульман. ''Теория синтаксического анализа, перевода и компиляции'', том 1. Основной источник для блока про LR-разбор, нумерация теорем в лекциях 11–13 идёт по этой книге.
* А. Ахо, Р. Сети, Д. Ульман. ''Компиляторы: принципы, технологии и инструменты (Dragon Book)''.
* В. Пырэу, Н. Ефанов. ''Формальные языки (черновик)''.

Алгоритмы и структуры данных I. Иностранный поток 2026

2026-10-29T14:17:05Z

Spirina.es:

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

== Программа курса ==
Курс двухсеместровый

'''Форма контроля в осеннем семестре:''' экзамен

{| class="wikitable"
! Неделя
! Лекция / Семинар
|-
| 1
| Анализ алгоритмов и асимптотика
|-
| 2
| Бинарный поиск и методы поиска ответа
|-
| 3
| Линейные структуры данных
|-
| 4
| Амортизационный анализ
|-
| 5
| Префиксные суммы и задачи диапазонов
|-
| 6
| Сортировки I: фундаментальные алгоритмы
|-
| 7
| Сортировки II: быстрые алгоритмы
|-
| 8
| Кучи и приоритетные очереди
|-
| 9
| Деревья поиска I
|-
| 10
| Деревья поиска II: самобалансирующиеся деревья
|-
| 11
| Структуры данных для запросов на отрезках
|-
| 12
| Продвинутые структуры данных
|-
| 13
| Хеширование и вероятностные структуры
|-
| 14
| Динамическое программирование
|-
| 15
| Матричные методы и вычислительная геометрия
|}

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

Лектор: Смолин Александр Андреевич

Семинарист: Мешков Владислав Сергеевич

== Коммуникация ==

== Прогресс студентов ==

[https://docs.google.com/spreadsheets/d/1RnkI99hoPM61eVqnjLb-zGLQQW9eOwBrkwcrwcAdr7Y/edit?usp=sharing таблица] с оценками

== Критерии оценивания и формы контроля успеваемости ==

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

Экзамен будет проходить в четыре этапа: три основных и один бонусный.

1. Выдается билет, содержащий четыре вопроса из программы. Ответ на каждый вопрос оценивается из 1.5 баллов. При оценке ответа на какой-либо вопрос ниже 0.5 ставится автоматически пересдача. На подготовку ответа дается 1 час. За ответ на эту часть программы дается до шести баллов. Продолжительность ответа в ходе данной части экзамена не должна превышать 45 минут. Экзаменатор имеет право попросить сформулировать смежные по теме определения и формулировки утверждений и теорем, не указанные явно в вопросе. При использовании утверждения или теоремы из данного курса экзаменатор имеет право поинтересоваться ее доказательством.

2. Далее идет блиц-опрос по программе, за который дается не более одного балла. В его ходе экзаменатор имеет право спросить любое определение и формулировку любой теоремы из курса. Также он может поинтересоваться постановкой задачи, которую решает некоторый алгоритм. Отвечать необходимо практически сразу, без долгих размышлений.

'''Если на текущий момент у студента меньше 5.5 баллов, то экзамен заканчивается.'''

3. Заключительная часть экзамена состоит в том, что вам будут предложены для решения две задачи. Сначала идет задача среднего уровня сложности. Ее решение принесет вам два балла и возможность получить задачу на 10, если за первые два этапа было не менее 6.5 баллов. Если же задача не решена, то выдается задача «попроще», за решение которой дается один балл. Время подготовки ответа на задачу попроще составляет 25 минут, на задачу среднего уровня — 40 минут.

4. *В случае, если вы претендуете на отл(10), вам нужно сообщить об этом экзаменатору. После консультации с лектором он выдаст задачу продвинутого уровня сложности. Подготовка и ответ этого этапа не должны превышать полутора часов.
*В случае, если на какой-то из стадий экзамена истекло выделенное время, экзаменатор имеет право прервать экзамен и выставить оценку на основе данных вами ответов.
Если вам необходимо отлучиться в ходе экзамена, это можно сделать только между стадиями или между задачами из третьего этапа.
*В случае несогласия с оценкой вы имеете право отапеллировать ее у лектора до выхода из аудитории.

Алгоритмы и структуры данных III. Иностранный поток 2026

2026-10-29T14:03:46Z

Spirina.es:

ИВТ. Математические основания алгоритмов и сложность вычислений. 2026

2026-10-29T13:59:28Z

Spirina.es: /* Материалы курса */

== О курсе ==

'''Математические основания алгоритмов и сложность вычислений''' — это первый семестр из четырёх, посвящённых алгоритмам.

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

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

* '''Руководитель курса / лектор:''' Троян-Головян Владислав
* '''Преподаватели, семинаристы, ассистенты:'''
** Троян-Головян Владислав
** Бунин Лев Алексеевич

== Программа курса ==

Дисциплина состоит из:

* Математические основания алгоритмов и сложность вычислений

'''Форма контроля:''' экзамен

* Практикум по математическим основаниям алгоритмов

'''Форма контроля:''' Дифференцированный зачет

{| class="wikitable"
! Неделя
! Лекции
! Домашние задания и контест
|-
| 1
| Введение
|
|-
| 2
| Теория множеств
|
|-
| 3
| Бинарная арифметика
|
|-
| 4
| O-нотация и мастер-теорема
|
|-
| 5
| Индукция и комбинаторика
|
|-
| 6
| Теория вероятностей I
|
|-
| 7
| Теория вероятностей II
|
|-
| 8
| Вещественная арифметика
| Контрольная работа
|-
| 9
| Теория чисел I
|
|-
| 10
| Теория чисел II
|
|-
| 11
| Графы I
|
|-
| 12
| Графы II
|
|-
| 13
| Вероятностные алгоритмы
|
|-
| 14
| P/NP: основы
| Контрольная работа
|-
| 15
| Вопрос-ответ
|
|}

== Коммуникация ==

* Ссылка на чат курса в мессенджере (будет опубликована ближе к старту семестра).

== Прогресс студентов ==

* Ссылка на таблицу студентов с оценками (будет опубликована ближе к старту семестра).

== Критерии оценивания и формы контроля успеваемости ==

=== Домашние задания ===

По каждой теме выдаётся домашнее задание, оцениваемое от '''0''' до '''10''' баллов.

* Срок выполнения: '''2 недели'''
* Формат выполнения: '''TeX'''

=== Контрольные работы ===

В течение семестра проводятся две контрольные работы:

* после лекции 8;
* после лекции 14.

Каждая контрольная работа оценивается от '''0''' до '''10''' баллов.

=== Допуск к зачёту ===

Если:

* средний балл за контрольные работы меньше '''3''', и/или
* средний балл за домашние задания меньше '''3''',

то итоговая оценка за курс — '''неудовлетворительно'''.

=== Семинарский балл ===

На семинарах преподаватель проводит квизы по материалам лекций, а также учитывает:

* посещаемость;
* активность на занятиях;
* выходы к доске.

По итогам семестра выставляется семинарский балл в диапазоне от '''−1''' до '''+1''', который добавляется к итоговой оценке.

=== Итоговая оценка за зачёт===

0.5*AVG(ДЗ)+0.5*AVG(КР) + Балл от семинариста.

Если итоговая оценка равна '''11''', студент получает бонус к экзамену.

=== Штрафы ===

* Просрочка сдачи до 24 часов — штраф '''25%'''.
* Просрочка до 3 дней — штраф '''50%'''.
* Просрочка более 3 дней — '''0 баллов'''.
'''Исключение:''' официальный допуск или медицинская справка.
* За списывание оба участника получают оценку '''−10 баллов'''.

== Политика списывания ==
'''Политика списывания:''' при подозрении на списывание семинарист/ассистент проводит устную беседу, если факт списывания подтверждается, то зануляется весь контест целиком. При повторном списывании ставится итоговая оценка неуд. 2.

== Материалы курса ==

Презентации и дополнительные материалы будут публиковаться по ходу занятий в чате курса.

Алгоритмы и структуры данных III. Иностранный поток 2026

2026-10-29T13:57:49Z

Spirina.es: Полностью удалено содержимое страницы

Алгоритмы и структуры данных I. Иностранный поток 2026

2026-10-29T13:56:26Z

Spirina.es: Удалено перенаправление на Алгоритмы и структуры данных III. Иностранный поток 2026

Информация о курсе с осени 2025 г. Курс будет меняться.

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

== Программа курса ==
Курс двухсеместровый

'''Форма контроля в осеннем семестре:''' экзамен

{| class="wikitable"
! Неделя
! Лекция / Семинар
|-
| 1
| Анализ алгоритмов и асимптотика
|-
| 2
| Бинарный поиск и методы поиска ответа
|-
| 3
| Линейные структуры данных
|-
| 4
| Амортизационный анализ
|-
| 5
| Префиксные суммы и задачи диапазонов
|-
| 6
| Сортировки I: фундаментальные алгоритмы
|-
| 7
| Сортировки II: быстрые алгоритмы
|-
| 8
| Кучи и приоритетные очереди
|-
| 9
| Деревья поиска I
|-
| 10
| Деревья поиска II: самобалансирующиеся деревья
|-
| 11
| Структуры данных для запросов на отрезках
|-
| 12
| Продвинутые структуры данных
|-
| 13
| Хеширование и вероятностные структуры
|-
| 14
| Динамическое программирование
|-
| 15
| Матричные методы и вычислительная геометрия
|}

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

Лектор: Смолин Александр Андреевич

Семинарист: Мешков Владислав Сергеевич

== Коммуникация ==

== Прогресс студентов ==

[https://docs.google.com/spreadsheets/d/1RnkI99hoPM61eVqnjLb-zGLQQW9eOwBrkwcrwcAdr7Y/edit?usp=sharing таблица] с оценками

== Критерии оценивания и формы контроля успеваемости ==

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

Экзамен будет проходить в четыре этапа: три основных и один бонусный.

1. Выдается билет, содержащий четыре вопроса из программы. Ответ на каждый вопрос оценивается из 1.5 баллов. При оценке ответа на какой-либо вопрос ниже 0.5 ставится автоматически пересдача. На подготовку ответа дается 1 час. За ответ на эту часть программы дается до шести баллов. Продолжительность ответа в ходе данной части экзамена не должна превышать 45 минут. Экзаменатор имеет право попросить сформулировать смежные по теме определения и формулировки утверждений и теорем, не указанные явно в вопросе. При использовании утверждения или теоремы из данного курса экзаменатор имеет право поинтересоваться ее доказательством.

2. Далее идет блиц-опрос по программе, за который дается не более одного балла. В его ходе экзаменатор имеет право спросить любое определение и формулировку любой теоремы из курса. Также он может поинтересоваться постановкой задачи, которую решает некоторый алгоритм. Отвечать необходимо практически сразу, без долгих размышлений.

'''Если на текущий момент у студента меньше 5.5 баллов, то экзамен заканчивается.'''

3. Заключительная часть экзамена состоит в том, что вам будут предложены для решения две задачи. Сначала идет задача среднего уровня сложности. Ее решение принесет вам два балла и возможность получить задачу на 10, если за первые два этапа было не менее 6.5 баллов. Если же задача не решена, то выдается задача «попроще», за решение которой дается один балл. Время подготовки ответа на задачу попроще составляет 25 минут, на задачу среднего уровня — 40 минут.

4. *В случае, если вы претендуете на отл(10), вам нужно сообщить об этом экзаменатору. После консультации с лектором он выдаст задачу продвинутого уровня сложности. Подготовка и ответ этого этапа не должны превышать полутора часов.
*В случае, если на какой-то из стадий экзамена истекло выделенное время, экзаменатор имеет право прервать экзамен и выставить оценку на основе данных вами ответов.
Если вам необходимо отлучиться в ходе экзамена, это можно сделать только между стадиями или между задачами из третьего этапа.
*В случае несогласия с оценкой вы имеете право отапеллировать ее у лектора до выхода из аудитории.

Алгоритмы и структуры данных III. Иностранный поток 2026

2026-10-29T13:29:06Z

Spirina.es: /* Прогресс студентов */

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

2026-10-29T13:25:05Z

Spirina.es: /* Программа курса */

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

2026-10-29T13:24:12Z

Spirina.es: /* Программа курса */

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

2026-10-29T13:23:53Z

Spirina.es: /* Программа курса */

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

2026-10-29T13:23:32Z

Spirina.es: /* Программа курса */

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

2026-10-29T13:23:17Z

Spirina.es: /* Программа курса */

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

2026-10-29T13:22:51Z

Spirina.es: /* Материалы курса */

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

2026-10-29T13:20:01Z

Spirina.es: /* Правила курса */

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

2026-10-29T13:19:48Z

Spirina.es: /* Критерии оценивания и формы контроля успеваемости */

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

2026-10-29T13:10:40Z

Spirina.es: /* Команда курса */

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

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

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

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

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

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

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

Семинаристы: Сбродов Егор Алексеевич

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

Степанов Илья Данилович

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

'''Формы контроля:''' Дифференцированный зачет и экзамен

{|class="wikitable"
|-
!Неделя!!Лекции!!
|-
|1||Хеширование и поиск образца в строке||
|-
|2||Префикс-функция, Z-функция и палиндромы||
|-
|3||Боры и алгоритм Ахо — Корасик||
|-
|4||Суффиксный массив и массив LCP||
|-
|5||Дерево палиндромов||
|-
|6||Конечные автоматы и суффиксный автомат||
|-
|7||Суффиксное дерево и связь суффиксных структур||
|-
|8||Быстрое преобразование Фурье||
|-
|9||Алгоритмы над многочленами и линейные рекурренты||
|-
|10||Теория чисел и алгоритмы над конечными полями||
|-
|11||Вычислительная геометрия: базовые примитивы||
|-
|12||Триангуляция многоугольников и выпуклая оболочка||
|-
|13|| Алгоритмы на выпуклых многоугольниках||
|-
|14||Принадлежность точки многоугольнику и пересечение полуплоскостей||
|-
|15||Диаграммы Вороного и триангуляция Делоне||
|}

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

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

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

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

Список задач будет окончательно известен только ближе к концу семестра, поэтому заранее невозможно спрогнозировать, какие будут пороги на каждую оценку.
Чтобы заработать минимальную положительную оценку (уд. 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

2026-10-29T13:07:36Z

Spirina.es: /* Коммуникация */

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

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

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

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

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

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

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

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

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

'''Формы контроля:''' Дифференцированный зачет и экзамен

{|class="wikitable"
|-
!Неделя!!Лекции!!
|-
|1||Хеширование и поиск образца в строке||
|-
|2||Префикс-функция, Z-функция и палиндромы||
|-
|3||Боры и алгоритм Ахо — Корасик||
|-
|4||Суффиксный массив и массив LCP||
|-
|5||Дерево палиндромов||
|-
|6||Конечные автоматы и суффиксный автомат||
|-
|7||Суффиксное дерево и связь суффиксных структур||
|-
|8||Быстрое преобразование Фурье||
|-
|9||Алгоритмы над многочленами и линейные рекурренты||
|-
|10||Теория чисел и алгоритмы над конечными полями||
|-
|11||Вычислительная геометрия: базовые примитивы||
|-
|12||Триангуляция многоугольников и выпуклая оболочка||
|-
|13|| Алгоритмы на выпуклых многоугольниках||
|-
|14||Принадлежность точки многоугольнику и пересечение полуплоскостей||
|-
|15||Диаграммы Вороного и триангуляция Делоне||
|}

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

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

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

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

Список задач будет окончательно известен только ближе к концу семестра, поэтому заранее невозможно спрогнозировать, какие будут пороги на каждую оценку.
Чтобы заработать минимальную положительную оценку (уд. 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

2026-10-29T13:07:05Z

Spirina.es: /* Программа курса */

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

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

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

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

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

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

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

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

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

'''Формы контроля:''' Дифференцированный зачет и экзамен

{|class="wikitable"
|-
!Неделя!!Лекции!!
|-
|1||Хеширование и поиск образца в строке||
|-
|2||Префикс-функция, Z-функция и палиндромы||
|-
|3||Боры и алгоритм Ахо — Корасик||
|-
|4||Суффиксный массив и массив LCP||
|-
|5||Дерево палиндромов||
|-
|6||Конечные автоматы и суффиксный автомат||
|-
|7||Суффиксное дерево и связь суффиксных структур||
|-
|8||Быстрое преобразование Фурье||
|-
|9||Алгоритмы над многочленами и линейные рекурренты||
|-
|10||Теория чисел и алгоритмы над конечными полями||
|-
|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.

Алгоритмы и структуры данных I. Основной поток 2026

2026-10-29T13:01:48Z

Spirina.es: /* Прогресс студентов */

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

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

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

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

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

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

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

'''Семинаристы:'''
 Спицын Николай Антонович
 Смышляев Федор Витальевич
 Белков Иван Иванович
 Подзорова Полина Владимировна
 Халтурин Евгений Александрович
 Чернецкий Аркадий Михайлович
 Сбродов Егор Алексеевич
 Вашкевич Егор Сергеевич
 Чубенко Полина Николаевна
 Савичев Дмитрий Александрович
 Нагибин Всеволод Владимирович
 Климанова Ирина Евгеньевна
 Кулешов Игорь Вячеславович
 Цой Максим Вячеславович
 Клячин Артемий Владиславович

== Программа курса ==
В семестре 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||Хэш-таблицы (продолжение).||
|}

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

[https://t.me/ads_general2026 чат] курса

== Прогресс студентов ==

[https://docs.google.com/spreadsheets/d/1wlVfS7ck6oFHgoY2_hH4r5QWvRwyGVvmYy98FBBAFOk/edit?gid=0#gid=0 таблица] с оценками, доступная студентам

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

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

Список задач будет окончательно известен только ближе к концу семестра, поэтому заранее невозможно спрогнозировать, какие будут пороги на каждую оценку.
Чтобы заработать минимальную положительную оценку (уд. 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.

Алгоритмы и структуры данных I. Основной поток 2026

2026-10-29T13:01:23Z

Spirina.es: /* Прогресс студентов */

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

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

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

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

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

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

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

'''Семинаристы:'''
 Спицын Николай Антонович
 Смышляев Федор Витальевич
 Белков Иван Иванович
 Подзорова Полина Владимировна
 Халтурин Евгений Александрович
 Чернецкий Аркадий Михайлович
 Сбродов Егор Алексеевич
 Вашкевич Егор Сергеевич
 Чубенко Полина Николаевна
 Савичев Дмитрий Александрович
 Нагибин Всеволод Владимирович
 Климанова Ирина Евгеньевна
 Кулешов Игорь Вячеславович
 Цой Максим Вячеславович
 Клячин Артемий Владиславович

== Программа курса ==
В семестре 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||Хэш-таблицы (продолжение).||
|}

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

[https://t.me/ads_general2026 чат] курса

== Прогресс студентов ==
Таблица с оценками, доступная студентам
[https://docs.google.com/spreadsheets/d/1wlVfS7ck6oFHgoY2_hH4r5QWvRwyGVvmYy98FBBAFOk/edit?gid=0#gid=0 таблица]

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

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

Список задач будет окончательно известен только ближе к концу семестра, поэтому заранее невозможно спрогнозировать, какие будут пороги на каждую оценку.
Чтобы заработать минимальную положительную оценку (уд. 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.

Алгоритмы и структуры данных I. Основной поток 2026

2026-10-29T13:00:15Z

Spirina.es: /* Коммуникация */

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

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

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

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

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

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

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

'''Семинаристы:'''
 Спицын Николай Антонович
 Смышляев Федор Витальевич
 Белков Иван Иванович
 Подзорова Полина Владимировна
 Халтурин Евгений Александрович
 Чернецкий Аркадий Михайлович
 Сбродов Егор Алексеевич
 Вашкевич Егор Сергеевич
 Чубенко Полина Николаевна
 Савичев Дмитрий Александрович
 Нагибин Всеволод Владимирович
 Климанова Ирина Евгеньевна
 Кулешов Игорь Вячеславович
 Цой Максим Вячеславович
 Клячин Артемий Владиславович

== Программа курса ==
В семестре 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||Хэш-таблицы (продолжение).||
|}

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

[https://t.me/ads_general2026 чат] курса

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

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

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

Список задач будет окончательно известен только ближе к концу семестра, поэтому заранее невозможно спрогнозировать, какие будут пороги на каждую оценку.
Чтобы заработать минимальную положительную оценку (уд. 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.

Алгоритмы и структуры данных I. Основной поток 2026

2026-10-29T12:59:49Z

Spirina.es: /* Коммуникация */

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

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

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

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

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

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

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

'''Семинаристы:'''
 Спицын Николай Антонович
 Смышляев Федор Витальевич
 Белков Иван Иванович
 Подзорова Полина Владимировна
 Халтурин Евгений Александрович
 Чернецкий Аркадий Михайлович
 Сбродов Егор Алексеевич
 Вашкевич Егор Сергеевич
 Чубенко Полина Николаевна
 Савичев Дмитрий Александрович
 Нагибин Всеволод Владимирович
 Климанова Ирина Евгеньевна
 Кулешов Игорь Вячеславович
 Цой Максим Вячеславович
 Клячин Артемий Владиславович

== Программа курса ==
В семестре 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||Хэш-таблицы (продолжение).||
|}

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

[https://t.me/ads_general2026] чат курса

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

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

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

Список задач будет окончательно известен только ближе к концу семестра, поэтому заранее невозможно спрогнозировать, какие будут пороги на каждую оценку.
Чтобы заработать минимальную положительную оценку (уд. 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.

Алгоритмы и структуры данных I. Основной поток 2026

2026-10-29T12:59:21Z

Spirina.es: /* Коммуникация */

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

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

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

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

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

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

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

'''Семинаристы:'''
 Спицын Николай Антонович
 Смышляев Федор Витальевич
 Белков Иван Иванович
 Подзорова Полина Владимировна
 Халтурин Евгений Александрович
 Чернецкий Аркадий Михайлович
 Сбродов Егор Алексеевич
 Вашкевич Егор Сергеевич
 Чубенко Полина Николаевна
 Савичев Дмитрий Александрович
 Нагибин Всеволод Владимирович
 Климанова Ирина Евгеньевна
 Кулешов Игорь Вячеславович
 Цой Максим Вячеславович
 Клячин Артемий Владиславович

== Программа курса ==
В семестре 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||Хэш-таблицы (продолжение).||
|}

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

[https://t.me/ads_general2026_чат] курса

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

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

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

Список задач будет окончательно известен только ближе к концу семестра, поэтому заранее невозможно спрогнозировать, какие будут пороги на каждую оценку.
Чтобы заработать минимальную положительную оценку (уд. 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.

Алгоритмы и структуры данных I. Основной поток 2026

2026-10-29T12:58:46Z

Spirina.es: /* Коммуникация */

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

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

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

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

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

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

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

'''Семинаристы:'''
 Спицын Николай Антонович
 Смышляев Федор Витальевич
 Белков Иван Иванович
 Подзорова Полина Владимировна
 Халтурин Евгений Александрович
 Чернецкий Аркадий Михайлович
 Сбродов Егор Алексеевич
 Вашкевич Егор Сергеевич
 Чубенко Полина Николаевна
 Савичев Дмитрий Александрович
 Нагибин Всеволод Владимирович
 Климанова Ирина Евгеньевна
 Кулешов Игорь Вячеславович
 Цой Максим Вячеславович
 Клячин Артемий Владиславович

== Программа курса ==
В семестре 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||Хэш-таблицы (продолжение).||
|}

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

[https://t.me/ads_general2026_чат курса]

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

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

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

Список задач будет окончательно известен только ближе к концу семестра, поэтому заранее невозможно спрогнозировать, какие будут пороги на каждую оценку.
Чтобы заработать минимальную положительную оценку (уд. 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.

Робастные методы в математической статистике 2026

2026-09-07T09:31:42Z

Spirina.es: /* Коммуникация */

== О курсе ==
'''КУРС РАСЧИТАН ДЛЯ СТУДЕНТОВ 4го КУРСА'''

Учебная дисциплина «Робастные методы в статистике» является продолжением курса «Теория вероятностей и математическая статистика» и посвящена изучению методов статистического анализа, позволяющих получать надежные выводы при обработке данных с учетом особенностей их формирования и качества доступной информации.
В рамках курса рассматриваются основные задачи математической статистики: оценка параметров распределений, проверка статистических гипотез, последовательный статистический анализ, непараметрические методы и робастное оценивание параметров распределений. Особое внимание уделяется ограничениям классических статистических методов, принципам построения робастных статистических решений и выбору адекватных методов анализа данных в зависимости от поставленной задачи.
Курс формирует у студентов теоретические знания в области непараметрической математической статистики и развивает навыки постановки статистических задач, выбора методов обработки данных и интерпретации получаемых статистических выводов.

=== Цели дисциплины ===

Целями дисциплины являются:

* объяснить, почему классическая математическая статистика вводит пользователя в заблуждение;
* показать, как правильно ставить задачу извлечения информации из данных с заданным качеством;
* показать, каким образом можно устранить обнаруженные недостатки классической математической статистики и построить робастное гарантийное статистическое решение;
* сформировать теоретические знания в области непараметрической математической статистики;
* научить студентов методике постановки конкретных задач анализа статистических данных в зависимости от природы формирования данных и целей их обработки, выбора адекватных статистических методов решения задачи и правильной интерпретации получаемых статистических выводов.

=== Задачи дисциплины ===

Задачами дисциплины являются:

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

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

'''Руководитель / лектор курса:''' д.ф.-м.н., профессор Цитович Иван Иванович

== Программа курса ==

{| class="wikitable"
! Неделя !! Темы лекций и семинаров !! Активности
|-
| 1 || Введение ||
|-
| 2 || Сведения из теории вероятностей и смежных областей ||
|-
| 3 || Оценка параметров распределения ||
|-
| 4 || Проверка гипотез ||
|-
| 5 || Последовательная проверка простых гипотез ||
|-
| 6-8 || Предмет математической статистики ||
|-
| 9-10 || Последовательная проверка непараметрических гипотез ||
|-
| 11-12 || Субоптимальная проверка непараметрических гипотез ||
|-
| 13-14 || Робастное оценивание параметров распределения ||
|-
| 15 || Итоги и выводы ||
|}

== Особенности курса ==

Большая часть теоретического материала будет предложена в виде видеофайлов лекций по данному курсу, которые доступны в телеграмм канале RSMS25.

На самих лекциях будет только анонс материала следующего занятия и разбор тех мест, по поводу которых у студентов есть вопросы.

Отсутствие вопросов означает усвоение материала студентом.

Вопросы можно задавать в письменном виде (в том числе обезличено) через систему коммуникаций студент–преподаватель Piazza.

Сэкономленное время будет использовано для семинаров и консультаций.

== Коммуникация ==

'''Телеграм-канал курса:'''

RSMS26

https://t.me/+_q3FmrVowPoxY2Iy

'''Ссылка на чат'''

https://t.me/+HSwiiCpvORRkMzli

'''Система коммуникаций студент–преподаватель:'''

Piazza

== Прогресс студентов ==

Информация появится позже

== Критерии оценивания и формы контроля успеваемости ==

Текущий контроль:
<math>О = ДЗ1 + ДЗ2 + КР + К1 + К2 + К3 + К4 + К5 + А + Б</math>

где:
* '''ДЗ1, ДЗ2''' — два индивидуальных домашних задания;
* '''КР''' — письменная аудиторная контрольная работа;
* '''К1–К5''' — аудиторные работы по теории;
* '''А''' — активность на занятиях (коллекционирование «+» и «−»);
* '''Б''' — бонус (за тяготы и лишения).

Письменная аудиторная контрольная работа (КР) и два индивидуальных домашних задания (ДЗ1 и ДЗ2) оцениваются по 10 баллов.
Аудиторные работы по теории — до 2 баллов.

Пересдача, переписывание и пр. не допускаются, кроме экзамена.

'''Домашние задания'''

В рамках курса предусмотрено два индивидуальных домашних задания.

Темы подбираются индивидуально для каждого студента.

Несвоевременная сдача домашней работы наказывается снятием 2 баллов с результата.

Домашнюю работу можно исправить после проверки. В этом случае дополнительно набранные баллы делятся на 2.

Если исправленную домашнюю работу прислать до дедлайна, то штрафы не начисляются.

'''Бонусная программа'''

По умолчанию все являются участниками бонусной программы.

Из программы можно выйти полностью или частично в любой момент, прислав соответствующее письмо. Вернуться обратно в полную бонусную программу нельзя.

Участники полной бонусной программы имеют право написать эссе, а также получают дополнительные баллы (Б), величина которых определяется в конце семестра.

Для участников полной бонусной программы итоговое число баллов делится на 4 и получается значение бонуса.

Для участников частичной бонусной программы итоговое число баллов делится на 2 или больше в зависимости от степени участия в бонусной программе и получается значение бонуса.

'''Итоговый контроль''' — экзамен.

За ответ на экзамене можно получить до 10 баллов.

Если величина бонуса с точностью до округления устраивает студента, то её можно использовать как итоговую оценку, прислав соответствующее письмо.

Если студент участвовал в бонусной программе частично, то без экзамена можно получить не более 7 баллов или написать контрольную работу.

Если величина бонуса с точностью до округления не устраивает студента (или он хочет сдавать экзамен), то студент сдаёт экзамен.

В этом случае к результату ответа на экзамене добавляется 50% от значения бонуса, и полученная величина округляется до целого числа. Это и есть итоговая оценка по курсу.

При пересдаче экзамена бонус не учитывается.

== Материалы курса ==

Большая часть теоретического материала представлена в виде видеофайлов лекций по данному курсу.

Материалы доступны в телеграмм канале RSMS25.

Дополнительная коммуникация по вопросам курса осуществляется через систему Piazza.