Public ATP Wiki - Свежие правки [ru]

Программирование на Go весна 2026

Leo.ivanov — Wed, 08 Apr 2026 11:53:33 GMT

‎Баллы

Базы данных весна 2026

Yakusheva — Sat, 04 Apr 2026 05:20:16 GMT

‎Важные ссылки

Databases весна 2026

Yakusheva — Wed, 01 Apr 2026 09:15:09 GMT

‎Grading

Технологии программирования на Java весна 2026

Aermakov — Tue, 31 Mar 2026 12:47:30 GMT

ИВТ. Алгоритмы обработки строк и теории чисел весна 2026

Irinaiv — Fri, 27 Mar 2026 21:25:13 GMT

Новая страница: « == Общие сведения == * Семестр: 4 (второй курс) * Форма контроля: отдельно зачет и отдельно э…»

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

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

* Семестр: 4 (второй курс)
* Форма контроля: отдельно зачет и отдельно экзамен
* [https://t.me/+d5W6x0-N-kU4ODhi]
* [https://docs.google.com/spreadsheets/d/1fK86rv2Le-IkhwDYEnokq2xXBnY1lTiH5umIJqCHwGo/edit?gid=0#gid=0 Таблица с оценками]

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

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

Семинаристы:
* Аксененко Денис
* Троян-Головян Владислав

Учебные ассистенты
* Прохорчук Екатерина
* Черевичная Наталья

Контакт для организационных вопросов: @vhdev

== План лекций ==

# z-функция, префикс-функция, алгоритм Рабина-Карпа
# Ахо-Корасик
# Алгоритм Укконена
# Суффиксный автомат 1
# Суффиксный автомат 2
# Введение в ТЧ(поиск обратных по модулю, решето Эратосфена, линейное решето Эратосфена). Быстрое преобразование Фурье.
# Многомерное преобразование фурье. Деление многочленов.
# Дополнительные алгоритмы ТЧ.
# Геометрия: примитивы, многоугольники, выпуклые 2Д оболочки.
# Суммы Минковского, 3Д-оболочка
# Диаграммы Вороного
# Триангуляция Делоне
# Запасная лекция

== Формула оценивания зачета ==

Блокирующие условия:
# на уд сдать 3 ревью задачи
# на хор сдать 4 ревью задачи
# на отл сдать 5 ревью задач
# на отл 10 сдать все 6 ревью задач
'''Итоговая оценка выставляется по формуле: 0.4C+0.6L+S.'''

Пороги для оценки:
* >= 50%: 3
* >= 55%: 4
* >= 65%: 5
* >= 70%: 6
* >= 75%: 7
* >= 85%: 8
* >= 90%: 9
* >= 95%: 10

Параллельные и распределенные вычисления весна 2026

Killerrati — Wed, 25 Mar 2026 12:09:28 GMT

Автоматизация программирования весна 2026

Yakusheva — Tue, 24 Mar 2026 16:34:28 GMT

‎Дедлайны

НИС 2026

Semenyuk olya — Tue, 24 Mar 2026 10:34:18 GMT

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

Базы данных весна 2025

Killerrati — Fri, 20 Mar 2026 15:49:28 GMT

Теория и практика многопоточной синхронизации

Irinaiv — Tue, 17 Mar 2026 14:26:28 GMT

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

Внесённые изменения

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

Irinaiv — Mon, 16 Mar 2026 20:29:09 GMT

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

Irinaiv — Mon, 16 Mar 2026 20:27:10 GMT

Новая страница: «## Общие сведения Целями освоения дисциплины «Алгоритмы и структуры данных – 2» являются…»

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

## Общие сведения
Целями освоения дисциплины «Алгоритмы и структуры данных – 2» являются ознакомление с основами теории вычислительной сложности, приближенными и вероятностными методами решения труднорешаемых задач, в том числе задач, возникающих в анализе данных. В курсе дается представление о классах сложности P, NP и coNP и NP-полных задачах, изучаются способы доказательства NP-полноты задач и подходы к решению таких задач, в т.ч. экспоненциальные алгоритмы, отличные от полного перебора, приближенные алгоритмы и эффективные алгоритмы для частных случаев. Также рассматриваются потоковые алгоритмы, алгоритмы эффективного перечисления последовательностей и способы оценки их вычислительной сложности (задержка, кумулятивная задержка, сложность относительно размера входа и выхода).

- Форма контроля: дифф зачет + экзамен.

- Канал курса: https://t.me/ads_foreings

- Руководитель курса: Александр Смолин

## План курса
1. Обходы графов. DFS.
- Способы хранение графа: матрица и список смежности.
- Алгоритм DFS.
- Атрибуты вершин: цвета, времена входа и выхода.
- Лемма о белых путях.
- Топологическая сортировка.
- Компоненты сильной связности.
- Алгоритм Косарайю.
- Реберная двусвязность.
- Поиск мостов.
- Поиск точек сочленения

2. Кратчайшие пути.
- BFS: классический, 0-1, 1-k, 0-k.
- Алгоритм Дейкстры.
- Эвристический поиск.
- Алгоритм A*.
- Алгоритм Форда-Беллмана.
- Алгоритм Флойда-Уоршелла.
- Поиск циклов отрицательного веса.

3. Система непересекающихся множеств.

4. Минимальные остовые деревья.
- Лемма о безопасном ребре
- Алгоритм Прима.
- Алгоритм Крускала.
- Алгоритм Борувки.

5. Наименьший общий предок.
- Наивное решение.
- Двоичные подъемы.
- Сведение LCA <-> RMQ.
- Алгоритм Фараха-Колтона и Бендера.
- Static online RMQ с линейным предподсчетом и константным ответом на запрос.

6. Паросочетания.
- Двудольные графы.
- Теорема Бержа.
- Алгоритм Куна.

7. Потоки
- Понятие сети, потока, разреза.
- Остаточная сеть.
- Соотношение между величинами потоков и разрезов.
- Теорема Форда-Фалкерсона.
- Алгоритм Форда-Фалкерсона.
- Алгоритм Эдмондса-Карпа.
- Схема Диница.
- Потенциал сети.
- Алгоритм Хопкрофта-Карпа.

8. Строки
- Поиск паттерна в тексте.
* Префикс-функция. Алгоритм Кнута-Морриса-Прата.
* Z-функция. Алгоритм Кнута-Морриса-Прата.
* Полиномиальное хеширование. Алгоритм Рабина-Карпа.
- Поиск множества паттернов в тексте.
* Бор.
* Автомат Ахо-Корасик.
- Алгоритмы на подстроках. Суффиксный автомат.
* Наивное построение.
* Линейный алгоритм.

9. Быстрое преобразование Фурье

## Домашние задания
Контесты и теоретические задания. Информация о них будет публиковаться на канале.

## Оценки
### Оценивание зачета
До 7 баллов за контесты, до 3 баллов за теор задания, 1 бонусный балл от семинариста за активность.

Сумма — оценка за зачёт.

### Оценка за экзамен.
Оценка за экзамен ставится исходя из непосредственно экзамена.

До 6 баллов за ответ билета, до 1 балла за блиц опрос. Далее, если студент получил менее 5.5, то экзамен заканчивается и студент получает оценку равную наборанному числу баллов округленную по правилам математического округления. Иначе студент получает задачу "на отл(9)". Если решить ее не получается, то студент получает задачу "на отл(8)". Если студент решает задачу "на отл(9)", то получает задачу "на отл(10)".

@@ Строка 59: / Строка 59: @@
 * За успешное ревью кода также начисляется +1 балл, однако множитель за задачу с ревью равен 0.5, то есть суммарно за задачу с ревью 1 балл.
 * Штраф за опоздание по дедлайну: -50%
-* [https://docs.google.com/spreadsheets/d/e/2PACX-1vRLV3BCprfjXkQ9nJwBAmgcG4vKfkU9VtwPd-1PffxvKOVC4D_lBojQdJK0Ia-ai3kRjXx3il4CjA31/pubhtml?gid=218390600&single=true Таблица с баллами]
+* [https://docs.google.com/spreadsheets/d/e/2PACX-1vRLV3BCprfjXkQ9nJwBAmgcG4vKfkU9VtwPd-1PffxvKOVC4D_lBojQdJK0Ia-ai3kRjXx3il4CjA31/pubhtml?gid=218390600&single=true Таблица с баллами] [https://docs.google.com/spreadsheets/d/e/2PACX-1vQHyFNraLLGQwZUVbCvvWZxShfQuJEgf6TNze2v4Jy3Rex9Hk8YRyR8LfzmmezMQtfetZp4t0ZRarfp/pubhtml?gid=218390600&single=true Таблица с баллами (быстрая загрузка)]
 * [https://docs.google.com/forms/d/e/1FAIpQLSfzIeU0oxU6Hy2T6pgCloVYcgAwAS6xDFyoNpX-HpI3-63obw/viewform?usp=dialog Продление дедлайнов]

@@ Строка 11: / Строка 11: @@
 == Важные ссылки ==
-'''[https://us06web.zoom.us/j/83359694524?pwd=4giVovYBr6Pg5zWezqeiDMkWuh6JPX.1 Онлайн-лекции]''' и '''[https://disk.yandex.ru/d/MFMCO6h7gdGfNQ записи (и презентации!)]'''
+'''[https://telemost.360.yandex.ru/j/9363336603 Онлайн-лекции]''' и '''[https://disk.yandex.ru/d/MFMCO6h7gdGfNQ записи (и презентации!)]'''
 апреля лекция пройдет ОЧНО в Большой Химической аудитории.

@@ Строка 4: / Строка 4: @@
 * project - 3 points
 * final oral exam - from -2 to +5 points
 == Major rules ==

@@ Строка 61: / Строка 61: @@
 |[https://docs.google.com/document/d/1q3M9TWoVJOO1Bkhm3L32uMm-t7AmxE4A Java Reflection] || 16.04.26 || 23.04.26
 |-
-|[https://docs.google.com/document/d/1YsQfssZFXhkvK8T6h8BRB5fDNNpimEhE Java Spring]  || 07.05.26 || 14.05.26
+|[https://docs.google.com/document/d/1NM1k_a7QG21aBZyGM5MTK0w6baJEzUxQ Java Spring]  || 07.05.26 || 14.05.26
 |}

@@ Строка 42: / Строка 42: @@
 ==== Сервера ====
-* MPI & OpenMP: <pre>ssh <user>@185.81.248.52 -p 2222</pre>
+* MPI & OpenMP: <pre>ssh <user>@185.81.248.52 -p 2236</pre>
 * CUDA: <pre>ssh <user>@lorien.atp-fivt.org</pre>

@@ Строка 14: / Строка 14: @@
 == Дедлайны ==
 * Лабораторная 0 - 17.02
-* Лабораторная 1 - 24.02
+* Лабораторная 1 - 03.03
 == Альтернативные варианты сдачи курса ==

@@ Строка 4: / Строка 4: @@
 ** Гладченко Ирина Алексеевна, кандидат политических наук
 * Форма контроля: диф. зачет
-* Куратор: Семенюк Ольга Леонидовна, https://t.me/sekretar_atp
+* Куратор: Семенюк Ольга Леонидовна, https://t.me/sekretar_atp,
 = Важные ссылки =

@@ Строка 551: / Строка 551: @@
 |Сазанович    ||Михаил	        ||Ассистент||	@Sazan1209
 |-
-|Собол	      ||Жан		||Ассистент||	@Jan4ikS7
+|Собол	      ||Жан		||Ассистент||
 |-
 |Хусрабов    ||Рустам		||Ассистент||	@khusrabov

@@ Строка 1: / Строка 1: @@
-## Общие сведения
+==Общие сведения==
 Целями освоения дисциплины «Алгоритмы и структуры данных – 2» являются ознакомление с основами теории вычислительной сложности, приближенными и вероятностными методами решения труднорешаемых задач, в том числе задач, возникающих в анализе данных. В курсе дается представление о классах сложности P, NP и coNP и NP-полных задачах, изучаются способы доказательства NP-полноты задач и подходы к решению таких задач, в т.ч. экспоненциальные алгоритмы, отличные от полного перебора, приближенные алгоритмы и эффективные алгоритмы для частных случаев. Также рассматриваются потоковые алгоритмы, алгоритмы эффективного перечисления последовательностей и способы оценки их вычислительной сложности (задержка, кумулятивная задержка, сложность относительно размера входа и выхода).
@@ Строка 8: / Строка 8: @@
 - Руководитель курса: Александр Смолин
-## План курса
+==План курса==
 . Обходы графов. DFS.
      - Способы хранение графа: матрица и список смежности.
@@ Строка 75: / Строка 75: @@
 . Быстрое преобразование Фурье
-## Домашние задания
 Контесты и теоретические задания. Информация о них будет публиковаться на канале.
-## Оценки
-### Оценивание зачета
+== Оценки ==
 До 7 баллов за контесты, до 3 баллов за теор задания, 1 бонусный балл от семинариста за активность.
 Сумма — оценка за зачёт.
-### Оценка за экзамен.
+'''Оценка за экзамен'''
 Оценка за экзамен ставится исходя из непосредственно экзамена.
 До 6 баллов за ответ билета, до 1 балла за блиц опрос. Далее, если студент получил менее 5.5, то экзамен заканчивается и студент получает оценку равную наборанному числу баллов округленную по правилам математического округления. Иначе студент получает задачу "на отл(9)". Если решить ее не получается, то студент получает задачу "на отл(8)". Если студент решает задачу "на отл(9)", то получает задачу "на отл(10)".