Алгоритмы и структуры данных, часть 1
Санкт-Петербург, осень 2013
Описание
Курс знакомит слушателей с базовыми алгоритмическими приёмами и структурами данных. В частности, мы узнаем следующее:
- Почему не стоит вычислять числа Фибоначчи рекурсивно.
- Как отсортировать массив размера \(n\) за время \(O(n\log n)\) и почему в общем случае быстрее сделать не получится.
- Как послать закодированное сообщение другу так, чтобы только он мог его раскодировать, при условии, что канал прослушивается.
- Как умножать числа быстрее, чем школьным методом
в столбик
. - Как предобработать
Войну и мир
так, чтобы потом иметь возможность почти мгновенно ответить на вопрос, сколько раз в тексте встречается заданное слово. - Как динамическое программирование используется в геномике.
- Как двоичное дерево поиска может самобалансироваться в процессе добавления, удаления и даже поиска элемента.
- Когда имеет смысл действовать жадно.
- Как быстро найти кратчайший путь в графе.
- Как подкидывание монетки может помочь алгоритму работать быстрее.
- Как найти пару ближайших точек на плоскости, не проверяя при этом все пары точек.
- Почему за решение некоторых алгоритмических задач обещан миллион долларов.
В 2013 году лекции курса записываться не будут, по ссылке можно найти лекции 2011 года и смотреть их.
Литература:
- S. Dasgupta, C. Papadimitriou, U. Vazirani. Algorithms. McGraw-Hill. 2006.
- А. Х. Шень. Программирование: теоремы и задачи. Издательство МЦНМО. 2007.
- М. А. Бабенко, М. В. Левин. Введение в теорию алгоритмов и структур данных. Издательство МЦНМО. 2012.
- Т. Кормен, Ч. Лейзерсон, И. Ривест, К. Штайн. Алгоритмы: построение и анализ.
Преподаватели
Список лекций
Вычисление чисел Фибоначчи: экспоненциальный рекурсивный алгоритм, полиномиальный алгоритм, более детальный анализ (арифметические и битовые операции), визуализация. Время работы алгоритма, O-символика. Скорость роста функций: логарифм, полином, экспонента.
Элементарная арифметика: сложение, умножение, деление. Арифметика сравнений: сложение, умножение, возведение в степень, алгоритм Евклида для нахождения наибольшего общего делителя, расширенный алгоритм Евклида, нахождение обратного по модулю.
Проверка чисел на простоту. Генерация случайных простых чисел. Криптография: схемы с закрытым ключом, RSA, цифровая подпись.
Стек с поддержанием максимума; моделирование очереди с помощью двух стеков; задаче о нахождении минимумов во всех окнах массива; расширяющийся массив и амортизационный анализ; универсальное хеширование.
Основные идеи метода; алгоритм Карацубы: умножение $n$-битовых чисел за $O(n^{1.6})$; основная теорема о рекуррентных соотношениях; бинарный поиск; алгоритм Штрассена умножения матриц; сортировка слиянием.
Нижняя оценка $\Omega(n\log n)$ на время работы сортировки сравнениями. Быстрая сортировка: анализ среднего времени работы, анализ глубины рекурсии, элиминация хвостовой рекурсии, IntroSort, массивы с малым количеством различных элементов, QuickSort3.
Сортировка подсчётом, устойчивость. Цифровая сортировка. Сортировка вычёрпыванием. Сравнения различных сортировок: визуализация 1, визуализация 2.
Графы и способы их представления, способы использования графов. Поиск в глубину в неориентированных графах, выделение компонент связности. Поиск в глубину в ориентированных графах (визуализация): ориентированные ациклические графы, топологическая сортировка вершин — с помощью поиска в глубину (визуализация) и с помощью массива входящих степеней вершин (визуализация), наличие стока и истока в ациклическом графе, выделение компонент сильной связности (визуализация).
Выделение компонент сильной связности. Нахождение кратчайших путей из одной вершины в невзвешенных графах, поиск в ширину (визуализация). Нахождение кратчайших путей из одной вершины в графах с положительными весами, алгоритм Дейкстры (визуализация), оценка времени работы при различных реализациях очереди с приоритетами (массивом, двоичной кучей, d-чной кучей).
Представление множеств с помощью деревьев, эвристика сжатия путей, верхняя оценка \(O(m\log^*n)\) на время работы \(m\) операций, визуализация.