Введение в структуры данных — различия между версиями
(→План курса) |
(→Команда курса) |
||
Строка 354: | Строка 354: | ||
== Команда курса == | == Команда курса == | ||
* Преподаватели: | * Преподаватели: | ||
− | ** | + | ** Степанов Илья |
Текущая версия на 01:04, 3 февраля 2023
Содержание
Общие сведения
- Семестр: 1 (первый курс курс)
- Форма контроля: дифференцированный зачет
Важные ссылки
- Регистрация на курс (доступ для физтех-аккаунтов)
- Материалы курсa (доступ для физтех-аккаунтов)
- Чат курса
- Таблица с оценками
Требования
- Физтех-почта (домен phystech.edu)
- Аккаунт на GitHub
- Ноутбук на занятиях
План курса
№ | Тема |
---|---|
1 | Асимптотические обозначения: O, Ω, Θ. Независимость от стартового индекса. |
2 | Сумма на отрезке в статическом массиве: префиксные суммы. |
3 | Проверка вхождения числа в отсортированный массив: бинарный поиск. |
4 | Структура данных стек: реализация на указателях, использование std::stack. |
5 | Поиск ближайшего меньшего/большего слева/справа в статическом массиве. |
6 | Поддержка минимума в стеке. |
7 | Реализация очереди на двух стеках. |
8 | Поддержка минимума в очереди. |
9 | Проверка правильности скобочной последовательности с несколькими типами скобок. |
10 | Доказательство формулы: log(n!) = Θ(n log n). |
11 | Нижняя оценка на число сравнений в сортировке сравнениями. |
12 | Сортировка слиянием (Merge Sort). |
13 | Поиск числа инверсий в массиве. |
14 | Нерекурсивная реализация сортировки слиянием. |
15 | Быстрая сортировка (Quick Sort). Асимптотика — б/д. |
16 | Поиск k-й порядковой статистики с выбором случайного пивота (Quick Select). Асимптотика — б/д. |
17 | Детерминированный алгоритм поиска k-й порядковой статистики за O(n), где n — длина массива. |
18 | Детерминированный алгоритм быстрой сортировки за O(n log n), где n — длина массива. |
19 | Стабильная сортировка подсчётом. Сортировка пар чисел. |
20 | Цифровая сортировка (LSD). |
21 | Двоичная куча: определение и представление в массиве. Требование кучи. |
22 | Операции siftUp и siftDown с доказательством корректности. |
23 | Выражение insert, getMin, extractMin и decreaseKey через siftUp и siftDown. |
24 | Построение кучи (heapify) за линейное время (сходимостью ряда можно пользоваться б/д). |
25 | Сортировка кучей с привлечением O(1) дополнительной памяти (Heap Sort). Несуществование кучи (основанной на сравнениях), обрабатывающей insert и extractMin за O(1). |
26 | Технические сложности и их преодоление для операции decreaseKey в куче. |
27 | Удаление из кучи по значению. |
28 | Удаление из кучи по указателю. |
29 | Биномиальное дерево, биномиальная куча: определение. |
30 | Операции merge, insert, getMin, extractMin и decreaseKey в биномиальной куче. |
31 | Амортизационный анализ, учётное время работы: определение. |
32 | Метод монеток (бухгалтерский учёт). |
33 | Структура данных вектор, реализация на массиве и оценка асимптотики методом монеток. |
34 | Метод потенциалов. |
35 | Вставка в биномиальной куче в отсутствие других операций, применение метода потенциалов. |
36 | Sparse Table: модельная задача, построение за O(n log n), ответ на запрос за O(1). |
37 | Дерево отрезков: модельная задача. Обработка запросов с доказательством времени работы. |
38 | Дерево отрезков: двоичный спуск, поиск k-го нуля на отрезке массива за O(log n). |
39 | Дерево отрезков, отложенные операции: присвоение константы на отрезке, операция push. |
40 | Количество чисел на отрезке, значения которых лежат в отрезке: Fractional Cascading. |
41 | Персистентный массив. |
42 | Персистентное дерево отрезков. |
43 | Количество чисел на отрезке, значения которых лежат в отрезке: решение с персистентным деревом отрезков. |
44 | Динамическое дерево отрезков. |
45 | Онлайн vs. оффлайн: сжатие координат. |
46 | Онлайн vs. оффлайн: дерево поиска оффлайн. |
47 | Онлайн vs. оффлайн: количество чисел на отрезке, значения которых лежат в отрезке. |
48 | Дерево Фенвика: классическая задача, операции update и getSum. |
49 | Обобщение дерева Фенвика на б´oльшие размерности. Изменение асимптотики. |
50 | Обратное дерево Фенвика: максимум на отрезке и изменение (увеличение) в точке (update — без реализации). |
51 | Дерево Фенвика деревьев Фенвика. |
52 | Дерево поиска: определения и операции (без реализации) find, insert, erase, а также опциональные merge и split. |
53 | Наивное дерево поиска, обработка операций. |
54 | AVL-дерево: определение. |
55 | Оценка глубины AVL-дерева на n вершинах. |
56 | Устранение дисбаланса в AVL-дереве для случая ∆(a) = −2. |
57 | AVL-дерево: реализация операций insert и erase. |
58 | Splay-дерево: определение и практическая значимость. |
59 | Splay-дерево: операции zig, zig-zig и zig-zag, операция splay. |
60 | Амортизированное время работы операции splay с помощью метода потенциалов. |
61 | Splay-дерево: реализация insert, erase и find, связь с операцией splay, оценка времени работы. |
62 | B-дерево: определение и практическая значимость. |
63 | Оценка глубины B-дерева на n ключах при фиксированном параметре t. |
64 | Реализация операции insert в B-дереве. |
65 | Реализация операции erase в B-дереве. |
66 | Декартово дерево: определение и теорема о глубине (б/д). |
67 | Реализация операций merge и split в декартовом дереве. |
68 | Выражение insert и erase в декартовом дереве через merge и split. |
69 | Декартово дерево по неявному ключу: в массиве вставить, удалить элемент, узнать сумму на отрезке. |
70 | Красно-чёрное дерево: определение. |
71 | Оценка глубины красно-чёрного дерева на n ключах. |
72 | Реализация операции insert в красно-чёрном дереве. |
73 | Реализация операции erase в красно-чёрном дереве. |
74 | Сравнительный анализ различных реализаций дерева поиска: наивное, AVL-, splay-, B-, декартово и красно-чёрное дерево. |
Оценивание
Оценка по курсу состоит из нескольких частей:
- Тесты
- Контесты
- Практические проекты
- Лабораторная работа
Тесты
- Небольшие тесты на 10 минут в начале каждого занятия
- Вопросы по материалам прошлого занятия
- Для прохождения нужен phystech.edu-аккаунт
- За каждый тест - 10 баллов.
Контесты
- Набор задач с автоматической проверкой тестирующей системой Я.Контест (нужен phystech.edu-аккаунт)
- Всего 6 тестов - после каждой темы базового блока
- Срок решения - 2 недели
- За каждый контест - 10 баллов
- Списывание детектируется и наказуемо!
Практические проекты
- 2 проекта - консольное приложение (после ООП) и серверное приложение (после Сети-2)
- Работа над кодом в несколько итераций на GitHub (нужен аккаунт)
- Срок работы - 2 недели + 1 неделя на каждую следующую итерацию
- Список тем проектов будет позднее
- Оценка за проект: зачет / незачет + до 2 доп. баллов (wow-эффект)
Лабораторная работа
- Анализ данных с помощью Pandas и Matplotlib
- Выдается после “Инструменты визуализации”
- Срок работы - 2 недели
- Оценка - 10 баллов
- Является блокирующей! Для получения зачета за курс необходимо набрать хотя бы 1 балл
Команда курса
- Преподаватели:
- Степанов Илья