Алгоритмы и структуры данных (продвинутый поток) — различия между версиями

Материал из Public ATP Wiki
Перейти к: навигация, поиск
(Новая страница: «= Общие сведения = * Семестр: 1 (первый курс) * Форма контроля: дифференцированный зачет == В…»)
 
(→‎План курса)
Строка 50: Строка 50:
 
|14|| 05.12.2022 || Работа с сетью. Клиенты и парсинг
 
|14|| 05.12.2022 || Работа с сетью. Клиенты и парсинг
 
|}
 
|}
 +
№ п/п МФТИ, ФПМИ Алгоритмы и структуры данных
 +
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-, декартово и красно-чёрное дерево.
  
 
== Оценивание ==
 
== Оценивание ==

Версия 16:38, 4 декабря 2022

Общие сведения

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

Важные ссылки

Требования

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

План курса

№ Дата Тема
1 05.09.2022 Введение. Знакомство с Python
2 12.09.2022 Управление вычислениями. Контейнеры, итераторы
3 19.09.2022 Словари, множества. Модуль collection
4 26.09.2022 Функции (часть 1). Базовый синтаксис и генераторы
5 03.10.2022 Функции (часть 2). Области видимости, замыкания, декораторы
6 10.10.2022 Строки и файлы
7 17.10.2022 ООП (часть 1). Основные принципы и определения и базовый синтаксис
8 24.10.2022 ООП (часть 2). Magic-методы
9 31.10.2022 Лучшие практики программирования. Юнит-тестирование
10 07.11.2022 Работа с сетью. Серверные приложения. Боты
11 14.11.2022 NumPy. Оптимизация кода
12 21.11.2022 Работа с табличными данными. Pandas
13 28.11.2022 Инструменты визуализации. Matplotlib
14 05.12.2022 Работа с сетью. Клиенты и парсинг

№ п/п МФТИ, ФПМИ Алгоритмы и структуры данных 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-, декартово и красно-чёрное дерево.

Оценивание

Оценка по курсу состоит из нескольких частей:

  1. Тесты
  2. Контесты
  3. Практические проекты
  4. Лабораторная работа

Тесты

  • Небольшие тесты на 10 минут в начале каждого занятия
  • Вопросы по материалам прошлого занятия
  • Для прохождения нужен phystech.edu-аккаунт
  • За каждый тест - 10 баллов.

Контесты

  • Набор задач с автоматической проверкой тестирующей системой Я.Контест (нужен phystech.edu-аккаунт)
  • Всего 6 тестов - после каждой темы базового блока
  • Срок решения - 2 недели
  • За каждый контест - 10 баллов
  • Списывание детектируется и наказуемо!

Практические проекты

  • 2 проекта - консольное приложение (после ООП) и серверное приложение (после Сети-2)
  • Работа над кодом в несколько итераций на GitHub (нужен аккаунт)
  • Срок работы - 2 недели + 1 неделя на каждую следующую итерацию
  • Список тем проектов будет позднее
  • Оценка за проект: зачет / незачет + до 2 доп. баллов (wow-эффект)

Лабораторная работа

  • Анализ данных с помощью Pandas и Matplotlib
  • Выдается после “Инструменты визуализации”
  • Срок работы - 2 недели
  • Оценка - 10 баллов
  • Является блокирующей! Для получения зачета за курс необходимо набрать хотя бы 1 балл

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

  • Преподаватели:
    • Андрианов Артем
    • Богдан Давид
    • Боярников Илья
    • Евдокимова Анастасия
    • Реброва Алина
    • Рошиору Светлана
    • Честнов Никита
    • Якушева Софья
  • Ассистенты:
    • Бояров Алексей
    • Кротов Андрей
    • Омирзак Дастан
    • Прохорчук Екатерина
Источник — «http://wiki.atp-fivt.org/index.php?title=Алгоритмы_и_структуры_данных_(продвинутый_поток)&oldid=1468»