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

Материал из Public ATP Wiki
Перейти к: навигация, поиск
(→‎План курса)
(→‎План курса)
Строка 19: Строка 19:
 
|-  
 
|-  
 
! №
 
! №
−
! Дата
 
 
! Тема
 
! Тема
 
|-
 
|-
−
|1|| 05.09.2022 || Введение. Знакомство с Python
+
|1|| Введение. Знакомство с Python
 
|-
 
|-
−
|2|| 12.09.2022 || Управление вычислениями. Контейнеры, итераторы
+
|2|| Управление вычислениями. Контейнеры, итераторы
 
|-
 
|-
−
|3|| 19.09.2022 || Словари, множества. Модуль collection
+
|3|| Словари, множества. Модуль collection
 
|-
 
|-
−
|4|| 26.09.2022 || Функции (часть 1). Базовый синтаксис и генераторы
+
|4|| Функции (часть 1). Базовый синтаксис и генераторы
 
|-
 
|-
−
|5|| 03.10.2022 || Функции (часть 2). Области видимости, замыкания, декораторы
+
|5|| Функции (часть 2). Области видимости, замыкания, декораторы
 
|-
 
|-
−
|6|| 10.10.2022 || Строки и файлы
+
|6|| Строки и файлы
 
|-
 
|-
−
|7|| 17.10.2022 || ООП (часть 1). Основные принципы и определения и базовый синтаксис
+
|7|| ООП (часть 1). Основные принципы и определения и базовый синтаксис
 
|-
 
|-
−
|8|| 24.10.2022 || ООП (часть 2). Magic-методы  
+
|8|| ООП (часть 2). Magic-методы  
 
|-
 
|-
−
|9|| 31.10.2022 || Лучшие практики программирования. Юнит-тестирование
+
|9|| Лучшие практики программирования. Юнит-тестирование
 
|-
 
|-
−
|10|| 07.11.2022 || Работа с сетью. Серверные приложения. Боты
+
|10|| Работа с сетью. Серверные приложения. Боты
 
|-
 
|-
−
|11|| 14.11.2022 || NumPy. Оптимизация кода
+
|11|| NumPy. Оптимизация кода
 
|-
 
|-
−
|12|| 21.11.2022 || Работа с табличными данными. Pandas
+
|12|| Работа с табличными данными. Pandas
 
|-
 
|-
−
|13|| 28.11.2022 || Инструменты визуализации. Matplotlib
+
|13|| Инструменты визуализации. Matplotlib
 
|-
 
|-
−
|14|| 05.12.2022 || Работа с сетью. Клиенты и парсинг
+
|14|| Работа с сетью. Клиенты и парсинг
 
|}
 
|}
−
№ п/п МФТИ, ФПМИ Алгоритмы и структуры данных
 
−
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:39, 4 декабря 2022

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

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

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

Требования

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

План курса

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

Оценивание

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

  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=1469»