2024
2023
2022
2021
2020
2019
2018
2017
Алгоритмы (семинары)
[ Ведомость ]
(7 сен) Машина Тьюринга [ Задание | Метод Ньютона ]
(14 сен) Бинарный поиск, сортировка слиянием [ Задание ]
(21 сен) Быстрая сортировка. Сортировка подсчетом. Массив. Динамический массив. Список (односвязный и двусвязный). [ Задание ]
(28 сен) Стек. Очередь. Циклический массив. Разбор формул при помощи стека. Замена явной рекурсии работой со стеком. Нахождение минимума в стеке и в очереди. [ Задание ]
(5 окт) Бинарное дерево поиска. Красно-черные деревья. [ Задание | Визуализация красно-черного дерева ]
(12 окт) Контрольная работа №1.
(19 окт) Хеш-таблицы. Открытая и закрытая адресации. Кэши памяти, фильтр Блума. [ Задание ]
(26 окт) Задача поиска подстроки в строке. Префикс-функция. Амортизационный анализ. Метод бухгалтерского учета (метод предоплаты). Динамический массив. Алгоритм Кнута-Морриса-Пратта. Доказательство линейной асимптотики алгоритма. Алгоритм Рабина-Карпа. [ Задание ] [ Хорошая лекция про амортизационный анализ, slideshare ] [ Хорошая лекция про амортизационный анализ, standalone ] [ Амортизационный анализ на хабре:) ] [ Про КМП при помощи только алгоритма вычисления префикс-функции ]
(2 ноя) Конечные автоматы. Задание
(9 ноя) Ахо-Корасик. Суффиксные ссылки. Хорошие суффиксные ссылки. Задание
(16 ноя) Суффиксный бор. Суффиксное дерево. Поиск наибольшего общего подслова. Суффиксный массив. Построение суффиксного массива через суффиксное дерево. Задание Хорошие лекции про суффиксные деревья: Суффиксное дерево, Алгоритм Укконена, Неплохая презентация про суффиксные деревья, Исчерпывающий анализ суффиксного массива, Построение суффиксного массива за O(NlogN)
(23 ноя) Контрольная
(30 ноя, 7 дек, 14 дек) Графы. Обход в глубину и в ширину, поиск циклов, топологическая сортировка, динамическое программирование, алгоритм Дейкстры. Алгоритм Белмана-Форда. Задание
