Алгоритмы и структуры данных 5SE 2018-2019 — различия между версиями

Материал из CSC Wiki
Перейти к:навигация, поиск
(Первая версия программы)
Строка 1: Строка 1:
 
 
== Лекции ==
 
== Лекции ==
 
Преподаватель: Смаль Александр Владимирович
 
Преподаватель: Смаль Александр Владимирович
Строка 11: Строка 10:
 
* '''18 сентября.''' Рекуррентные соотношения. Метод ”разделяй и властвуй“. Умножение n-битовых чисел: простой рекурсивный алгоритм, улучшенный рекурсивный алгоритм. Рекуррентные соотношения: основная теорема. Двоичный поиск. Сортировка слиянием: с рекурсией и без. Нижняя оценка <math>\Omega(n\log n)</math> для сортировки сравнениями.
 
* '''18 сентября.''' Рекуррентные соотношения. Метод ”разделяй и властвуй“. Умножение n-битовых чисел: простой рекурсивный алгоритм, улучшенный рекурсивный алгоритм. Рекуррентные соотношения: основная теорема. Двоичный поиск. Сортировка слиянием: с рекурсией и без. Нижняя оценка <math>\Omega(n\log n)</math> для сортировки сравнениями.
  
* '''24 сентября 13:40.''' Алгоритмы сортировки.  Квадратичные сортировки. Сортировка с помощью кучи: очередь с приоритетами, построение кучи за линейное время, частичная сортировка. Быстрая сортировка: анализ среднего времени работы, анализ глубины рекурсии, элиминация хвостовой рекурсии, IntroSort, массивы с малым количеством различных элементов, QuickSort3. Сортировка подсчётом, стабильность. Цифровая сортировка.
+
* '''24 сентября 13:40.''' Алгоритмы сортировки.  Квадратичные сортировки. Сортировка с помощью кучи: очередь с приоритетами, построение кучи за линейное время, частичная сортировка. Быстрая сортировка: анализ среднего времени работы, анализ средней глубины рекурсии, элиминация хвостовой рекурсии, IntroSort, массивы с малым количеством различных элементов, QuickSort3. Сортировка подсчётом, стабильность. Цифровая сортировка.
  
 
* '''25 сентября.''' Порядковые статистики. Порядковые статистики, нахождение за линейное в среднем время. Медиана медиан
 
* '''25 сентября.''' Порядковые статистики. Порядковые статистики, нахождение за линейное в среднем время. Медиана медиан
  
* '''1 октября 13:40.''' Жадные алгоритмы. Задача о выборе заявок. Коды Хаффмена. Хорновские формулы. Задача о покрытии множествами. Минимальное покрывающее дерево: свойство разреза, жадная стратегия, алгоритм Прима, алгоритм Краскала.
+
* '''1 октября 13:40.''' Динамическое программирование. Общие принципы динамического программирования, часто используемые подзадачи. Кратчайшие пути в ациклических ориентированных графах. Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач, сравнение с рекурсивным алгоритмом; нахождение не только длины, но и самой подпоследовательности.
  
* '''2 октября.''' Система непересекающихся множеств. Представление множеств с помощью деревьев, эвристика сжатия путей, верхняя оценка <math>O(m \log^* n)</math> на время работы m операций.
+
* '''2 октября.''' Динамическое программирование (продолжение). Редакционное расстояние: граф на подзадачах, нахождение кратчайшего пути в данном графе; нахождение оптимального выравнивания с использованием линейной памяти. Кратчайшие пути в ациклических ориентированных графах. Кратчайшие пути между всеми парами вершин: алгоритм Флойда-Уоршолла, алгоритм Джонсона.
  
* '''23 октября.''' Динамическое программирование. Общие принципы динамического программирования, часто используемые подзадачи. Кратчайшие пути в ациклических ориентированных графах. Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач, сравнение с рекурсивным алгоритмом; нахождение не только длины, но и самой подпоследовательности.
+
* '''23 октября.''' Жадные алгоритмы. Задача о выборе заявок. Коды Хаффмена. Хорновские формулы. Задача о покрытии множествами. Минимальное покрывающее дерево: свойство разреза, жадная стратегия, алгоритм Прима, алгоритм Краскала.
  
* '''30 октября.''' Динамическое программирование (продолжение). Редакционное расстояние: граф на подзадачах, нахождение кратчайшего пути в данном графе; нахождение оптимального выравнивания с использованием линейной памяти. Кратчайшие пути в ациклических ориентированных графах. Кратчайшие пути между всеми парами вершин: алгоритм Флойда-Уоршолла, алгоритм Джонсона.
+
* '''30 октября.''' Система непересекающихся множеств. Представление множеств с помощью деревьев, эвристика сжатия путей, верхняя оценка <math>O(m \log^* n)</math> на время работы m операций.
  
 
* '''6 ноября.''' Поиск в глубину. Графы и способы их представления, способы использования графов. Поиск в глубину в неориентированных графах, выделение компонент связности. Поиск в глубину в ориентированных графах: ориентированные ациклические графы, топологическая сортировка вершин, наличие стока и истока в ациклическом графе, выделение компонент сильной связности. Мосты и точки сочленения (на практике).
 
* '''6 ноября.''' Поиск в глубину. Графы и способы их представления, способы использования графов. Поиск в глубину в неориентированных графах, выделение компонент связности. Поиск в глубину в ориентированных графах: ориентированные ациклические графы, топологическая сортировка вершин, наличие стока и истока в ациклическом графе, выделение компонент сильной связности. Мосты и точки сочленения (на практике).
  
* '''13 ноября''' Кратчайшие пути в графах. Нахождение кратчайших путей из одной вершины в невзвешенных графах, поиск в ширину. Нахождение кратчайших путей из одной вершины в графах с положительными весами, алгоритм Дейкстры, оценка времени работы при различных реализациях очереди с приоритетами (массивом, двоичной кучей, d-чной кучей). Нахождение кратчайших путей из одной вершины в графах, в которых есть рёбра отрицательного веса, алгоритм Беллмана-Форда, проверка наличия цикла отрицательного веса.
+
* '''13 ноября''' Кратчайшие пути в графах. Нахождение кратчайших путей из одной вершины в невзвешенных графах, поиск в ширину. Нахождение кратчайших путей из одной вершины в графах с положительными весами, алгоритм Дейкстры, оценка времени работы при различных реализациях очереди с приоритетами (массивом, двоичной кучей, d-ичной кучей). Нахождение кратчайших путей из одной вершины в графах, в которых есть рёбра отрицательного веса, алгоритм Беллмана-Форда, проверка наличия цикла отрицательного веса.
  
 
* '''20 ноября.''' Деревья поиска. Дерево поиска: поиск, вставка, удаление, поиск следующего и предыдущего элемента за время, пропорциональное высоте. АВЛ-дерево: верхняя оценка O(log n) на высоту, сохранение свойства при помощи малых и больших вращений.
 
* '''20 ноября.''' Деревья поиска. Дерево поиска: поиск, вставка, удаление, поиск следующего и предыдущего элемента за время, пропорциональное высоте. АВЛ-дерево: верхняя оценка O(log n) на высоту, сохранение свойства при помощи малых и больших вращений.
Строка 46: Строка 45:
 
* [https://stepik.org/course/217/syllabus Алгоритмы: теория и практика. Методы]
 
* [https://stepik.org/course/217/syllabus Алгоритмы: теория и практика. Методы]
 
* [https://stepik.org/course/1547/syllabus Алгоритмы: теория и практика. Структуры данных]
 
* [https://stepik.org/course/1547/syllabus Алгоритмы: теория и практика. Структуры данных]
 
  
 
== Практика ==
 
== Практика ==

Версия 16:43, 20 сентября 2018

Лекции

Преподаватель: Смаль Александр Владимирович

Первая версия программы
  • 4 сентября. Введение. Алгоритм. Память и время как ресурсы. Вычисление чисел Фибоначчи: экспоненциальный рекурсивный алгоритм, полиномиальный алгоритм, более детальный анализ. 𝑃-символика как инструмент оценки ресурсов, различные асимптотики (логарифм, полином, экспонента).
  • 11 сентября. Элементарные структуры данных. Абстрактные типы данных, интерфейс и реализация. Стек, очередь, дек; моделирование на основе массива. Моделирование очереди с помощью двух стеков. Односвязный список, двусвязный список. Корневое дерево: бинарное дерево, дерево с произвольным ветвлением, представление ”левый ребёнок — правый сосед“. Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ учётных стоимостей операций: функция потенциала, истинные и учётные стоимости. Метод ростовщика.
  • 18 сентября. Рекуррентные соотношения. Метод ”разделяй и властвуй“. Умножение n-битовых чисел: простой рекурсивный алгоритм, улучшенный рекурсивный алгоритм. Рекуррентные соотношения: основная теорема. Двоичный поиск. Сортировка слиянием: с рекурсией и без. Нижняя оценка для сортировки сравнениями.
  • 24 сентября 13:40. Алгоритмы сортировки. Квадратичные сортировки. Сортировка с помощью кучи: очередь с приоритетами, построение кучи за линейное время, частичная сортировка. Быстрая сортировка: анализ среднего времени работы, анализ средней глубины рекурсии, элиминация хвостовой рекурсии, IntroSort, массивы с малым количеством различных элементов, QuickSort3. Сортировка подсчётом, стабильность. Цифровая сортировка.
  • 25 сентября. Порядковые статистики. Порядковые статистики, нахождение за линейное в среднем время. Медиана медиан
  • 1 октября 13:40. Динамическое программирование. Общие принципы динамического программирования, часто используемые подзадачи. Кратчайшие пути в ациклических ориентированных графах. Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач, сравнение с рекурсивным алгоритмом; нахождение не только длины, но и самой подпоследовательности.
  • 2 октября. Динамическое программирование (продолжение). Редакционное расстояние: граф на подзадачах, нахождение кратчайшего пути в данном графе; нахождение оптимального выравнивания с использованием линейной памяти. Кратчайшие пути в ациклических ориентированных графах. Кратчайшие пути между всеми парами вершин: алгоритм Флойда-Уоршолла, алгоритм Джонсона.
  • 23 октября. Жадные алгоритмы. Задача о выборе заявок. Коды Хаффмена. Хорновские формулы. Задача о покрытии множествами. Минимальное покрывающее дерево: свойство разреза, жадная стратегия, алгоритм Прима, алгоритм Краскала.
  • 30 октября. Система непересекающихся множеств. Представление множеств с помощью деревьев, эвристика сжатия путей, верхняя оценка на время работы m операций.
  • 6 ноября. Поиск в глубину. Графы и способы их представления, способы использования графов. Поиск в глубину в неориентированных графах, выделение компонент связности. Поиск в глубину в ориентированных графах: ориентированные ациклические графы, топологическая сортировка вершин, наличие стока и истока в ациклическом графе, выделение компонент сильной связности. Мосты и точки сочленения (на практике).
  • 13 ноября Кратчайшие пути в графах. Нахождение кратчайших путей из одной вершины в невзвешенных графах, поиск в ширину. Нахождение кратчайших путей из одной вершины в графах с положительными весами, алгоритм Дейкстры, оценка времени работы при различных реализациях очереди с приоритетами (массивом, двоичной кучей, d-ичной кучей). Нахождение кратчайших путей из одной вершины в графах, в которых есть рёбра отрицательного веса, алгоритм Беллмана-Форда, проверка наличия цикла отрицательного веса.
  • 20 ноября. Деревья поиска. Дерево поиска: поиск, вставка, удаление, поиск следующего и предыдущего элемента за время, пропорциональное высоте. АВЛ-дерево: верхняя оценка O(log n) на высоту, сохранение свойства при помощи малых и больших вращений.
  • 27 ноября. Splay-дерево. Splay-дерево: дерево, которое остаётся сбалансированным в среднем и при этом не хранит никакой дополнительной информации в вершинах; реализация основных операций через операцию splay; верхняя оценка на среднюю стоимость операций.
  • 4 декабря. Декартово дерево. Декартово дерево: построение декартова дерева за линейное время (при предварительно отсортированных ключах), реализация операций вставки и удаления через split и merge. Дуча: верхняя оценка на мат. ожидание глубины. Использование неявного ключа, rope.
  • 11 декабря. Задачи RMQ и LCA. Дерево отрезков, двоичный подъём. Динамическая задача RMQ/RSQ: оценка для запросов суммы/минимума и изменения элемента. Статический вариант задачи RMQ: полное предвычисление ( на предобработку, на запрос), метод разреженной таблицы ( на предобработку, на запрос). Задача LCA: эйлеров обход дерева, сведение к задаче RMQ. Сведение задачи RMQ к задаче LCA через декартово дерево.
  • 18 декабря запасная лекция

Литература

Онлайн-курсы

Практика

Мишунин

Контакты: alexander.mishunin[at]gmail.com

Дедлайны по теоретическому ДЗ: до начала занятия для правок уже присланых ранее задач, и до начала суток, в которые будет занятие, для новых задач.

Таблица с результатами

Слабодкин

Контакты: slabodkin.m[at]gmail.com

Смаль

Контакты: avsmal[at]gmail.com