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

Материал из Public ATP Wiki
Перейти к: навигация, поиск
(→‎План курса)
(→‎План курса)
 
(не показано 17 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
= Общие сведения =
 
= Общие сведения =
−
* Семестр: 1 (первый курс)
+
* Семестр: 3 (второй курс курс)
 
* Форма контроля: дифференцированный зачет
 
* Форма контроля: дифференцированный зачет
  
 
== Важные ссылки ==
 
== Важные ссылки ==
−
* '''[https://forms.yandex.ru/cloud/631595265bc65eb710f1d164/ Регистрация на курс]''' (доступ для физтех-аккаунтов)
+
* '''Регистрация на курс''' (доступ для физтех-аккаунтов)
−
* '''[https://disk.yandex.ru/d/px7hx-c8PF-0ZA Материалы курсa]''' (доступ для физтех-аккаунтов)
+
* '''Материалы курсa''' (доступ для физтех-аккаунтов)
−
* '''[https://t.me/+WRu3kMtm5KpmNWYy Чат курса]'''
+
* '''Чат курса'''
 
* '''[https://docs.google.com/spreadsheets/d/e/2PACX-1vTMMwi5Al5sqXSAKCrHSFt8Yp3ZA3FymxDqkntP_QXYiOfzrFnJUmFaxIGVM8iQCw/pubhtml?gid=99265951&single=true Таблица с оценками]'''
 
* '''[https://docs.google.com/spreadsheets/d/e/2PACX-1vTMMwi5Al5sqXSAKCrHSFt8Yp3ZA3FymxDqkntP_QXYiOfzrFnJUmFaxIGVM8iQCw/pubhtml?gid=99265951&single=true Таблица с оценками]'''
  
Строка 19: Строка 19:
 
|-  
 
|-  
 
! №
 
! №
−
! Дата
+
! Часть 1. Строки
−
! Тема
 
 
|-
 
|-
−
|1|| 05.09.2022 || Введение. Знакомство с Python
+
 
 +
|1|| Префикс-функция. Линейный алгоритм нахождения. Алгоритм Кнута-Морриса-Пратта.
 +
 
 +
|-
 +
 
 +
|2|| Определение Z-функции. Линейный алгоритм нахождения. Применение для поиска подстроки в строке.
 +
 
 +
|-
 +
 
 +
|3|| Алгоритм Манакера. Поиск максимальной подстроки-палиндрома.
 +
 
 +
|-
 +
 
 +
|4|| Алгоритм Галила-Сейфераса поиска подстроки в строки за O(n) времени и O(1) дополнительной памяти.
 +
 
 +
|-
 +
 
 +
|5|| Структура данных бор. Построение бора, оценка времени и объема памяти. Разные способы хранения детей дерева. Оценка объема памяти для каждого варианта. Понятие суффиксной ссылки. Пример дерева с суффиксными ссылками.
 +
 
 +
|-
 +
 
 +
|6|| Алгоритм построения бора вместе с суффиксными ссылками. Оценка времени работы. Алгоритм Ахо-Корасик. “Сжатые” суффиксные ссылки, то есть ссылки, идущие в следующую терминальную вершину, которая является суффиксом текущей. Оценка времени работы при использовании “сжатых” суффиксных ссылок.
 +
 
 +
|-
 +
 
 +
|7|| Дерево палиндромов. Линейный алгоритм построения дерева палиндромов.
 +
 
 +
|-
 +
 
 +
|8|| Определение суффиксного массива. Построение за O(N log N) с использованием цифровой сортировки для пар. Оптимизация “одна сортировка подсчетом вместо двух”.
 +
 
 
|-
 
|-
−
|2|| 12.09.2022 || Управление вычислениями. Контейнеры, итераторы
+
 
 +
|9|| Алгоритм Арикавы-Аримуры-Касаи-Ли-Парка.
 +
 
 +
|-
 +
 
 +
|10|| Суффиксное дерево. Сжатое суффиксное дерево. Доказательство линейности числа вершин и ребер в сжатом суффиксном дереве.
 +
 
 
|-
 
|-
−
|3|| 19.09.2022 || Словари, множества. Модуль collection
+
 
 +
|11|| Построение суффиксного дерева. Алгоритм Укконена.
 +
 
 
|-
 
|-
−
|4|| 26.09.2022 || Функции (часть 1). Базовый синтаксис и генераторы
+
 
 +
|12|| Суффиксный автомат. Правые контексты, их свойства. Классы эквивалентности подстрок; критерий максимальности подстроки в своем классе эквивалентности. Линейность числа вершин и ребер, достижимость оценок.
 +
 
 
|-
 
|-
−
|5|| 03.10.2022 || Функции (часть 2). Области видимости, замыкания, декораторы
+
 
 +
|13|| Суффиксный автомат. Линейный алгоритм построения.
 +
|}
 +
 
 +
{| class="wikitable"
 +
|-
 +
! №
 +
! Часть 2. Геометрия
 
|-
 
|-
−
|6|| 10.10.2022 || Строки и файлы
+
 
 +
|1|| Прямые, отрезки, плоскости. Скалярное произведение, векторное произведение, их свойства. Угол между векторами, функция atan2. Коллинеарность прямых. Проверка принадлежности точки прямой, отрезку.
 +
 
 
|-
 
|-
−
|7|| 17.10.2022 || ООП (часть 1). Основные принципы и определения и базовый синтаксис
+
 
 +
|2|| Поиск пересечения прямых - два способа: система уравнений и векторное произведение. Поиск пересечения окружности и прямой: два способа. Проверка наличия пересечения отрезков без вычисления точки пересечения прямых.
 +
 
 
|-
 
|-
−
|8|| 24.10.2022 || ООП (часть 2). Magic-методы
+
 
 +
|3|| Поиск ориентированной площади многоугольника: метод “векторных произведений” и “метод трапеций”.. Знак площади и проверка того факта, что вершины многоугольника заданы в порядке обхода против часовой стрелки. Поиск площади пересечения многоугольника и круга как модификация метода “векторных произведений”.
 +
 
 
|-
 
|-
−
|9|| 31.10.2022 || Лучшие практики программирования. Юнит-тестирование
+
 
 +
|4|| Проверка принадлежности точки многоугольнику. Проблема вершины на луче. Три способа решения проблемы: случайный луч, вычисление “хорошего” луча, решение с горизонтальным лучом. Проверка принадлежности точки выпуклому многоугольнику за O(log n). Поиск правой касательной из точки к выпуклому многоугольнику за O(log n).
 +
 
 
|-
 
|-
−
|10|| 07.11.2022 || Работа с сетью. Серверные приложения. Боты
+
 
 +
|5|| Выпуклая оболочка. Алгоритмы Джарвиса, Грэхема, Эндрю, Киркпатрика, Чена.
 +
 
 
|-
 
|-
−
|11|| 14.11.2022 || NumPy. Оптимизация кода
+
 
 +
|6|| Convex Hull Trick: версия с добавлением в структуру точек и поиском точки с минимальной проекцией на заданное направление.
 +
 
 
|-
 
|-
−
|12|| 21.11.2022 || Работа с табличными данными. Pandas
+
 
 +
|7|| Convex Hull Trick: версия с добавлением в структуру прямых и поиском прямой с минимальным y при заданном х. Дерево Ли-Чао.
 +
 
 
|-
 
|-
−
|13|| 28.11.2022 || Инструменты визуализации. Matplotlib
+
 
 +
|8|| Выпуклая оболочка 3D. Построение за O(n4), за O(n2).
 +
 
 
|-
 
|-
−
|14|| 05.12.2022 || Работа с сетью. Клиенты и парсинг
+
 
 +
|9|| Тернарный поиск. Выпуклые функции и их свойства, необходимые для корректного применения тернарного поиска. Вложенный тернарный поиск. Примеры: задача о фотографии, задача о максимальной вложенной в выпуклый многоугольник окружности..
 +
 
 +
|-
 +
 
 +
|10|| Поиск пары ближайших точек на плоскости. Алгоритм Препараты. O(n log n). Поиск треугольника с минимальным периметром за O(n log n).
 +
 
 +
|-
 +
 
 +
|11|| Поиск диаметра множества на плоскости за O(n log n). Поиск накрывающего прямоугольника минимального периметра за O(n log n). Поиск накрывающего прямоугольника минимальной площади за O(n log n).
 +
 
 +
|-
 +
 
 +
|12|| Поиск граней связного плоского графа за O(n log n).
 +
 
 +
|-
 +
 
 +
|13|| Нахождение суммы Минковского двух выпуклых многоугольников за O(m + n).Проверка наличия пересечения двух выпуклых многоугольников и поиск расстояния между ними за O(m + n). Задача о роботе и препятствиях (“задача про коридор и столы”; требуемое время O(n2*B), где n - число препятствий; робот и препятствия - выпуклые многоугольники с не более чем В вершинами)
 +
 
 +
|-
 +
 
 +
|14|| Сканирующая прямая. Поиск наибольшего креста. Проверка факта пересечения отрезков. Площадь объединения прямоугольников за O(n log n).
 +
 
 +
|-
 +
 
 +
|15|| Пересечение полуплоскостей: O(n3), O(n2), O(n log n).
 +
 
 +
|-
 +
 
 +
|16|| Статическая задача поиска точек в подпрямоугольнике. Решения за (O(n^5), O(log n)), (O(n^3), O(log n)), (O(n^2), O(log n)). Fractional Cascading. Времена построения и вычисления ответа на запрос.
 +
 
 +
|-
 +
 
 +
|17|| KD-дерево. Времена построения и вычисления ответа на запрос. Поиск ближайших точек множества с помощью KD-дерева, “контрпример”.
 +
 
 +
|-
 +
 
 +
|18|| Диаграмма Вороного. Базовые свойства: структура ячеек, связность, оценки на количества ребер и вершин. Критерий совпадения точки с вершиной ДВ, попадания на внутреннюю часть ребра.
 +
 
 +
|-
 +
 
 +
|19|| Построение диаграммы Вороного: O(n3), O(n2 log n), O(n2). Алгоритм Форчуна за O(n log n).
 +
 
 +
|-
 +
 
 +
|20|| Триангуляция Делоне. Определение триангуляции. Теорема Фалеса. Флипы. Неправильное ребро, критерий неправильности.
 +
 
 +
|-
 +
 
 +
|21|| Планарность триангуляции. Правильная триангуляция. Эквивалентность триангуляции Делоне и правильной триангуляции.
 +
|}
 +
 
 +
{|  class="wikitable"
 +
|-
 +
! №
 +
! Часть 3. Вероятностные алгоритмы и Ко
 +
|-
 +
 
 +
|1|| QSort, OrderStatistics: время работы в среднем и худшем случаях. Вероятностное определение цены игры на дереве. Алгоритм RandomGameTreeEval, его среднее время работы.
 +
 
 +
|-
 +
 
 +
|2|| Задача о минимальном разрезе, алгоритм Каргера.
 +
 
 +
|-
 +
 
 +
|3|| Задача о минимальном разрезе, алгоритм Каргера-Штайна.
 +
 
 +
|-
 +
 
 +
|4|| Поиск минимального остовного дерева, алгоритм Борувки (б/д). Алгоритм Каргера - Клейна - Тарьяна. Время работы в среднем случае. Поиск минимального остовного дерева, алгоритм Борувки (б/д). Алгоритм Каргера - Клейна - Тарьяна. Время работы в худшем случае.
 +
 
 +
|-
 +
 
 +
|5|| Задачи APD и APSP. APD для невзвешенных неориентированных графов, алгоритм APD-MM. Свидетели булевого перемножения матриц, алгоритм BPWM. Решение задачи APSP при помощи BPWM.
 
|}
 
|}
−
№ п/п МФТИ, ФПМИ Алгоритмы и структуры данных
 
−
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-, декартово и красно-чёрное дерево.
 
  
 
== Оценивание ==
 
== Оценивание ==
Строка 162: Строка 223:
 
== Команда курса ==
 
== Команда курса ==
 
* Преподаватели:
 
* Преподаватели:
−
** Андрианов Артем
+
** Рухович Филипп
−
** Богдан Давид
+
** Белый Антон
−
** Боярников Илья
 
−
** Евдокимова Анастасия
 
−
** Реброва Алина
 
−
** Рошиору Светлана
 
−
** Честнов Никита
 
−
** Якушева Софья
 
−
 
 
−
* Ассистенты:
 
−
** Бояров Алексей
 
−
** Кротов Андрей
 
−
** Омирзак Дастан
 
−
** Прохорчук Екатерина
 

Текущая версия на 17:47, 4 декабря 2022

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

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

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

  • Регистрация на курс (доступ для физтех-аккаунтов)
  • Материалы курсa (доступ для физтех-аккаунтов)
  • Чат курса
  • Таблица с оценками

Требования

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

План курса

№ Часть 1. Строки
1 Префикс-функция. Линейный алгоритм нахождения. Алгоритм Кнута-Морриса-Пратта.
2 Определение Z-функции. Линейный алгоритм нахождения. Применение для поиска подстроки в строке.
3 Алгоритм Манакера. Поиск максимальной подстроки-палиндрома.
4 Алгоритм Галила-Сейфераса поиска подстроки в строки за O(n) времени и O(1) дополнительной памяти.
5 Структура данных бор. Построение бора, оценка времени и объема памяти. Разные способы хранения детей дерева. Оценка объема памяти для каждого варианта. Понятие суффиксной ссылки. Пример дерева с суффиксными ссылками.
6 Алгоритм построения бора вместе с суффиксными ссылками. Оценка времени работы. Алгоритм Ахо-Корасик. “Сжатые” суффиксные ссылки, то есть ссылки, идущие в следующую терминальную вершину, которая является суффиксом текущей. Оценка времени работы при использовании “сжатых” суффиксных ссылок.
7 Дерево палиндромов. Линейный алгоритм построения дерева палиндромов.
8 Определение суффиксного массива. Построение за O(N log N) с использованием цифровой сортировки для пар. Оптимизация “одна сортировка подсчетом вместо двух”.
9 Алгоритм Арикавы-Аримуры-Касаи-Ли-Парка.
10 Суффиксное дерево. Сжатое суффиксное дерево. Доказательство линейности числа вершин и ребер в сжатом суффиксном дереве.
11 Построение суффиксного дерева. Алгоритм Укконена.
12 Суффиксный автомат. Правые контексты, их свойства. Классы эквивалентности подстрок; критерий максимальности подстроки в своем классе эквивалентности. Линейность числа вершин и ребер, достижимость оценок.
13 Суффиксный автомат. Линейный алгоритм построения.
№ Часть 2. Геометрия
1 Прямые, отрезки, плоскости. Скалярное произведение, векторное произведение, их свойства. Угол между векторами, функция atan2. Коллинеарность прямых. Проверка принадлежности точки прямой, отрезку.
2 Поиск пересечения прямых - два способа: система уравнений и векторное произведение. Поиск пересечения окружности и прямой: два способа. Проверка наличия пересечения отрезков без вычисления точки пересечения прямых.
3 Поиск ориентированной площади многоугольника: метод “векторных произведений” и “метод трапеций”.. Знак площади и проверка того факта, что вершины многоугольника заданы в порядке обхода против часовой стрелки. Поиск площади пересечения многоугольника и круга как модификация метода “векторных произведений”.
4 Проверка принадлежности точки многоугольнику. Проблема вершины на луче. Три способа решения проблемы: случайный луч, вычисление “хорошего” луча, решение с горизонтальным лучом. Проверка принадлежности точки выпуклому многоугольнику за O(log n). Поиск правой касательной из точки к выпуклому многоугольнику за O(log n).
5 Выпуклая оболочка. Алгоритмы Джарвиса, Грэхема, Эндрю, Киркпатрика, Чена.
6 Convex Hull Trick: версия с добавлением в структуру точек и поиском точки с минимальной проекцией на заданное направление.
7 Convex Hull Trick: версия с добавлением в структуру прямых и поиском прямой с минимальным y при заданном х. Дерево Ли-Чао.
8 Выпуклая оболочка 3D. Построение за O(n4), за O(n2).
9 Тернарный поиск. Выпуклые функции и их свойства, необходимые для корректного применения тернарного поиска. Вложенный тернарный поиск. Примеры: задача о фотографии, задача о максимальной вложенной в выпуклый многоугольник окружности..
10 Поиск пары ближайших точек на плоскости. Алгоритм Препараты. O(n log n). Поиск треугольника с минимальным периметром за O(n log n).
11 Поиск диаметра множества на плоскости за O(n log n). Поиск накрывающего прямоугольника минимального периметра за O(n log n). Поиск накрывающего прямоугольника минимальной площади за O(n log n).
12 Поиск граней связного плоского графа за O(n log n).
13 Нахождение суммы Минковского двух выпуклых многоугольников за O(m + n).Проверка наличия пересечения двух выпуклых многоугольников и поиск расстояния между ними за O(m + n). Задача о роботе и препятствиях (“задача про коридор и столы”; требуемое время O(n2*B), где n - число препятствий; робот и препятствия - выпуклые многоугольники с не более чем В вершинами)
14 Сканирующая прямая. Поиск наибольшего креста. Проверка факта пересечения отрезков. Площадь объединения прямоугольников за O(n log n).
15 Пересечение полуплоскостей: O(n3), O(n2), O(n log n).
16 Статическая задача поиска точек в подпрямоугольнике. Решения за (O(n^5), O(log n)), (O(n^3), O(log n)), (O(n^2), O(log n)). Fractional Cascading. Времена построения и вычисления ответа на запрос.
17 KD-дерево. Времена построения и вычисления ответа на запрос. Поиск ближайших точек множества с помощью KD-дерева, “контрпример”.
18 Диаграмма Вороного. Базовые свойства: структура ячеек, связность, оценки на количества ребер и вершин. Критерий совпадения точки с вершиной ДВ, попадания на внутреннюю часть ребра.
19 Построение диаграммы Вороного: O(n3), O(n2 log n), O(n2). Алгоритм Форчуна за O(n log n).
20 Триангуляция Делоне. Определение триангуляции. Теорема Фалеса. Флипы. Неправильное ребро, критерий неправильности.
21 Планарность триангуляции. Правильная триангуляция. Эквивалентность триангуляции Делоне и правильной триангуляции.
№ Часть 3. Вероятностные алгоритмы и Ко
1 QSort, OrderStatistics: время работы в среднем и худшем случаях. Вероятностное определение цены игры на дереве. Алгоритм RandomGameTreeEval, его среднее время работы.
2 Задача о минимальном разрезе, алгоритм Каргера.
3 Задача о минимальном разрезе, алгоритм Каргера-Штайна.
4 Поиск минимального остовного дерева, алгоритм Борувки (б/д). Алгоритм Каргера - Клейна - Тарьяна. Время работы в среднем случае. Поиск минимального остовного дерева, алгоритм Борувки (б/д). Алгоритм Каргера - Клейна - Тарьяна. Время работы в худшем случае.
5 Задачи APD и APSP. APD для невзвешенных неориентированных графов, алгоритм APD-MM. Свидетели булевого перемножения матриц, алгоритм BPWM. Решение задачи APSP при помощи BPWM.

Оценивание

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

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