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

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


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


=== Контесты ===
=== Контесты ===
Строка 122: Строка 141:
== 4. Коммуникация ==
== 4. Коммуникация ==


'''Чат курса:''' [ссылка будет добавлена ближе к старту семестра]
[https://t.me/+ykSAeh2wxNphNTFi чат] курса


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


'''Таблица с оценками:''' [ссылка будет добавлена ближе к старту семестра]
Таблица с оценками доступна студентам в канале дисциплины
 
В таблице фиксируются результаты трёх контестов, итоговой контрольной работы и бонус за активность на семинарах.


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

Текущая версия от 15:29, 29 октября 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 Контрольная работа Разбор сложных тем семестра.

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

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

Активность Срок / неделя Формат
Контест №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. Коммуникация

чат курса

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

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=5457