2024
2023
2022
2021
2020
2019
2018
2016
Алгоритмы (семинары)
[ Ведомость ]
(6 сен) Машина Тьюринга [ Задание | ejudge]
(13 сен) Сложность алгоритма. Бинарный поиск. Рекурсия. Подсчет сложности алгоритма в простейших случаях
(20 сен) Сортировки. Односвязный список. Задание
(27 сен) Двусвязный список. Стек. Очередь. Циклический массив. Разбор формул при помощи стека. Замена явной рекурсии работой со стеком. Задание старый ejudge, возможно RIP новый ejudge
(4 окт) Бинарное дерево поиска. Красно-черные деревья. Задание ejudge
(11 окт) Хеш-таблицы. Открытая и закрытая адресации. Кэши памяти, фильтр Блума. Задание ejudge
(18 окт) Контрольная работа 1. форма для псевдокода
(25 окт) Задача поиска подстроки в строке. Префикс-функция. Амортизационный анализ. Метод бухгалтерского учета (метод предоплаты). Динамический массив. Алгоритм Кнута-Морриса-Пратта. Доказательство линейной асимптотики алгоритма. Алгоритм Рабина-Карпа.
(8 ноября) Связь конечных автоматов и КМП. Ахо-Корасик, начало. автоматы, вторая часть Ахо-Корасик, первая часть
(15 ноября) Связь Ахо-Корасик и КМП. Ахо-Корасик и хорошие суффиксные ссылки. Суффиксные деревья. Суффиксные массивы. Лемпель-Зив. Лемпель-Зив-Велч
(29 ноября, 6 декабря) Графы. Поиск в ширину и в глубину, топологическая сортировка. Поиск кратчайшего пути в графе: динамическое программирование, алгоритм Дейкстры, алгоритм Беллмана-Форда. Задание
13. Неразрешимые задачи. P, NP и NPC. Приближенные алгоритмы. Монте-Карло. Первая часть дз