Алгоритмы и структуры данных 5SE 2020-2021

Лекции

Лектор: Александр Смаль

Контакты:

• avsmal[at]gmail.com
• Telegram: avsmal

Рабочая программа

Осень

• 8 сентября. Введение. Алгоритм. Модель вычисления RAM-машина. Память и время как ресурсы. Вычисление чисел Фибоначчи: экспоненциальный рекурсивный алгоритм, полиномиальный алгоритм, более детальный анализ. O-символика как инструмент оценки ресурсов, различные асимптотики (логарифм, полином, экспонента).

• 15 сентября. Элементарные структуры данных. Массивы переменного размера: аддитивная и мультипликативная схемы аллокации. Односвязный список, двусвязный список. Абстрактные типы данных, интерфейс и реализация. Стек, очередь, дек; моделирование на основе массива. Моделирование очереди с помощью двух стеков. Анализ учётных стоймостей операций при помощи функция потенциала, истинные и учётные стоимости.

• 22 сентября. Рекуррентные соотношения. Метод ”разделяй и властвуй“. Умножение n-битовых чисел: простой рекурсивный алгоритм, улучшенный рекурсивный алгоритм. Рекуррентные соотношения: основная теорема. Двоичный поиск. Сортировка слиянием: с рекурсией и без. Нижняя оценка $\Omega(n\log n)$ для сортировки сравнениями.

• 29 сентября. Алгоритмы сортировки. Квадратичные сортировки. Сортировка с помощью кучи: очередь с приоритетами, построение кучи за линейное время, частичная сортировка.

• 6 октября. Быстрая сортировка: понятие вероятностного алгоритма, время работы в среднем, анализ средней глубины рекурсии, элиминация хвостовой рекурсии, IntroSort. Быстрая сортировка: анализ среднего времени работы, массивы с малым количеством различных элементов, QuickSort3.

• 13 октября Частичная сортировка. Сортировка подсчётом, стабильность. Цифровая сортировка. Bucket sort для равномерно распределённых вещественных чисел. Порядковые статистики, нахождение за линейное в среднем время. Медиана медиан.

• 20 октября. Динамическое программирование. Общие принципы динамического программирования. Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач, сравнение с рекурсивным алгоритмом; нахождение не только длины, но и самой подпоследовательности. Кратчайшие пути в ациклических ориентированных графах. Дискретная задача о рюкзаке.

• 27 октября. Динамическое программирование (продолжение). Дискретная задача о рюкзаке. Умножение матриц. Независимые множества максимального веса в деревьях. Редакционное расстояние: граф на подзадачах, нахождение кратчайшего пути в данном графе; нахождение оптимального выравнивания с использованием линейной памяти.

• 3 ноября. Жадные алгоритмы. Покрытие точек единичными отрезками. Непрерывный рюкзак. Задача о выборе заявок. Максимальные независимые множества в деревьях. Код Хаффмена.

• 10 ноября. Задача о покрытии множествами. Минимальное покрывающее дерево: свойство разреза, жадная стратегия, алгоритм Прима, алгоритм Краскала.

• 17 ноября. Система непересекающихся множеств. Представление множеств с помощью деревьев, эвристика сжатия путей, верхняя оценка $O(m \log^* n)$ на время работы m операций. Анализ учётных стоймостей операций: метод ростовщика.

• 24 ноября Способы хранения графов: матрица смежности, списки смежности, матрица инцидентности. Поиск в глубину. Графы и способы их представления, способы использования графов. Поиск в глубину в неориентированных графах, выделение компонент связности. Поиск в глубину в ориентированных графах: ориентированные ациклические графы, топологическая сортировка вершин. Мосты и точки сочленения (на практике).

• 1 декабря. Выделение компонент сильной связности в орграфах. Кратчайшие пути в графах. Нахождение кратчайших путей из одной вершины в невзвешенных графах, поиск в ширину.

• 7 декабря. Нахождение кратчайших путей из одной вершины в графах с положительными весами, алгоритм Дейкстры, оценка времени работы при различных реализациях очереди с приоритетами (массивом, двоичной кучей, d-ичной кучей).

• 14 декабря. Нахождение кратчайших путей из одной вершины в графах, в которых есть рёбра отрицательного веса, алгоритм Беллмана-Форда, проверка наличия цикла отрицательного веса. Кратчайшие пути в ациклических ориентированных графах. Кратчайшие пути между всеми парами вершин: алгоритм Флойда-Уоршолла.

• 21 декабря. Альтернативные модели вычисления. Модель внешней памяти. Сортировка слиянием в модели внешней памяти. Модель cache-oblivios. Модель PRAM, вычисление максимума за константу. Модель BSP. Сортировка методом регулярного сэмплирования.

Литература

• Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы.
• Т.Кормен, Ч.Лейзерсон, Р.Ривест, К.Штайн - Алгоритмы. Построение и анализ.
• А. Шень. Программирование: теоремы и задачи.
• М. А. Бабенко, М. В. Левин. Введение в теорию алгоритмов и структур данных.

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

• Алгоритмы: теория и практика. Методы
• Алгоритмы: теория и практика. Структуры данных
• Data Structures and Algorithms Specialization on Coursera
• Algorithmic Toolbox — часть специализации из предыдущего пункта

Практика

Условия задач

Telegram-чат для обсуждений лекций и практик: https://t.me/joinchat/AgI1lFXil8U6VnPofgfOdA

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

TeX-шаблон для домашек

Условия зачёта

(предварительные)

• 0.85 * (количество обязательных задач в домашних заданиях)
• 0.75 * (количество задач в контестах)

Александр Мишунин

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

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

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

Алексей Лапенок

Контакты:

• lapenok.aleksej@gmail.com
• Telegram: @Aleksej_Lapenok

Правила сдачи:

• Решение нужно присылать в виде pfd-ки на почту, указанную выше. Рекомендуется использовать шаблон, которые лежит выше.

Дедлайны по теоретическому ДЗ:

• мягкий дедлайн 23:59 воскресенья. Решения присланные до него, гарантированно проверятся как минимум 1 раз до начала занятия.
• жесткий дедлайн - до начала занятия (09:30 четверга).

Таблица с баллами

Владислав Кораблинов

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

Картинки с практик

Контакты:

• vladislav.korablinov+itmo_20_algo@gmail.com
• Telegram: ladine0n

Правила сдачи:

• Решения нужно присылать в виде pdf-ки на почту, указанную выше. Еще выше лежит ссылка на удобный и простой шаблон, рекомендую им пользоваться, если у вас нет собственных разработок.

Правила зачета:

• Для получения зачета по теоретическим задачам нужно набрать $\sum (hw_{i}-d_{i})$ баллов, где $hw_{i}$ -- сумма баллов за обязательные задачи $i$-го домашнего задания, $d_{i}$ почти всегда равно 2.

Дедлайны по теоретическому ДЗ:

• мягкий дедлайн в воскресенье в 22:00, задачи, присланные до него, гарантированно проверяются как минимум 1 раз до жесткого дедлайна
• жёсткий дедлайн в среду в 23:59, после него до начала занятия можно присылать только исправления по задачам, по которым было написано что-то разумное (в ваших интересах прислать пораньше, чтобы я успел посмотреть и было понятно, что исправлять)