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

Материал из Public ATP Wiki
Перейти к: навигация, поиск
(→‎Штрафы)
(→‎Программа курса)
Строка 14: Строка 14:
 
== Программа курса ==
 
== Программа курса ==
  
−
# Введение
+
{| class="wikitable"
−
# Теория множеств
+
! Неделя
−
# Бинарная арифметика
+
! Лекции
−
# O-нотация и мастер-теорема
+
! Домашние задания и контест
−
# Индукция и комбинаторика
+
|-
−
# Теория вероятностей I
+
| 1
−
# Теория вероятностей II
+
| Асимптотика. Бинарный поиск.
−
# Вещественная арифметика
+
| Бинарный поиск, два указателя.
−
# Теория чисел I
+
|-
−
# Теория чисел II
+
| 2
−
# Графы I
+
| MergeSort. QuickSort.
−
# Графы II
+
|
−
# Вероятностные алгоритмы
+
|-
−
# P/NP: основы
+
| 3
 +
| Derandomized QuickSort. LSDSort.
 +
| Сортировки.
 +
|-
 +
| 4
 +
| Кучи. HeapSort.
 +
|
 +
|-
 +
| 5
 +
| Кучи (продолжение). Динамический массив.
 +
| Кучи, линейные контейнеры.
 +
|-
 +
| 6
 +
| Связные списки. Кучи Фибоначчи.
 +
|
 +
|-
 +
| 7
 +
| Стеки. Очередь.
 +
|
 +
|-
 +
| 8
 +
| Дерево отрезков.
 +
| Дерево отрезков, дерево Фенвика.
 +
|-
 +
| 9
 +
| Динамическое ДО. Персистентные структуры данных.
 +
|
 +
|-
 +
| 10
 +
| Деревья поиска: AVL-деревья, Splay-дерево.
 +
| Деревья поиска.
 +
|-
 +
| 11
 +
| Неявное дерево поиска.
 +
|
 +
|-
 +
| 12
 +
| Декартово дерево. B-дерево.
 +
|
 +
|-
 +
| 13
 +
| Красно-чёрное дерево.
 +
|
 +
|-
 +
| 14
 +
| Хэш-таблицы.
 +
| Хэш-таблицы.
 +
|-
 +
| 15
 +
| Хэш-таблицы (продолжение).
 +
|
 +
|}
  
 
== Коммуникация ==
 
== Коммуникация ==

Версия 12:05, 16 июня 2026

О курсе

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

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

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

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

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

Неделя Лекции Домашние задания и контест
1 Асимптотика. Бинарный поиск. Бинарный поиск, два указателя.
2 MergeSort. QuickSort.
3 Derandomized QuickSort. LSDSort. Сортировки.
4 Кучи. HeapSort.
5 Кучи (продолжение). Динамический массив. Кучи, линейные контейнеры.
6 Связные списки. Кучи Фибоначчи.
7 Стеки. Очередь.
8 Дерево отрезков. Дерево отрезков, дерево Фенвика.
9 Динамическое ДО. Персистентные структуры данных.
10 Деревья поиска: AVL-деревья, Splay-дерево. Деревья поиска.
11 Неявное дерево поиска.
12 Декартово дерево. B-дерево.
13 Красно-чёрное дерево.
14 Хэш-таблицы. Хэш-таблицы.
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 баллов.

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

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

Источник — «http://wiki.atp-fivt.org/index.php?title=ИВТ._Математические_основания_алгоритмов_и_сложность_вычислений._2026&oldid=4808»