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

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


Версия от 07:13, 27 августа 2026

О курсе

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

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

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

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

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

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

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

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

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

Неделя Лекция Семинар
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 Контрольная работа Разбор сложных тем семестра.

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

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

Активность Срок / неделя

Контесты

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Для получения положительной итоговой оценки каждый из трёх контестов должен быть выполнен минимум на 3 балла из 10.
  1. В каждом контесте три обязательные задачи формируют минимальную удовлетворительную оценку; дополнительные задачи повышают оценку за контест.
  1. После дедлайна обязательные задачи оцениваются с ограничением не более 50% от предусмотренных за них баллов.
  1. Итоговая контрольная работа является частью итоговой оценки.
  1. Активность на семинарах может дать до 1 дополнительного балла к итоговой оценке.
  1. Актуальные дедлайны и организационные объявления публикуются в чате курса.

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

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

  • Презентации лекций, материалы семинаров и условия контестов.
  • Материалы для подготовки к итоговой контрольной работе.
Источник — https://wiki.atp-fivt.org/index.php?title=Алгоритмы_и_структуры_данных_I._Базовый_поток_2026&oldid=5162