Просмотр исходного текста страницы Введение в структуры данных

= Общие сведения =
* Семестр: 1 (первый курс курс)
* Форма контроля: дифференцированный зачет

== Важные ссылки ==
* '''Регистрация на курс''' (доступ для физтех-аккаунтов)
* '''Материалы курсa''' (доступ для физтех-аккаунтов)
* '''Чат курса'''
* '''[https://docs.google.com/spreadsheets/d/e/2PACX-1vTMMwi5Al5sqXSAKCrHSFt8Yp3ZA3FymxDqkntP_QXYiOfzrFnJUmFaxIGVM8iQCw/pubhtml?gid=99265951&single=true Таблица с оценками]'''

== Требования ==
* Физтех-почта (домен phystech.edu)
* Аккаунт на GitHub
* Ноутбук на занятиях

== План курса ==

{|  class="wikitable"
|- 
! №
! Тема
|-

|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 балл

== Команда курса ==
* Преподаватели:
** Степанов Илья