Kodomo

User

Учебная страница курса биоинформатики,
год поступления 2017

Алгоритмы (семинары)

[ Ведомость ]



  1. (6 сен) Машина Тьюринга [ Задание | ejudge]

  2. (13 сен) Сложность алгоритма. Бинарный поиск. Рекурсия. Подсчет сложности алгоритма в простейших случаях

  3. (20 сен) Сортировки. Односвязный список. Задание

  4. (27 сен) Двусвязный список. Стек. Очередь. Циклический массив. Разбор формул при помощи стека. Замена явной рекурсии работой со стеком. Задание старый ejudge, возможно RIP новый ejudge

  5. (4 окт) Бинарное дерево поиска. Красно-черные деревья. Задание ejudge

  6. (11 окт) Хеш-таблицы. Открытая и закрытая адресации. Кэши памяти, фильтр Блума. Задание ejudge

  7. (18 окт) Контрольная работа 1. форма для псевдокода

  8. (25 окт) Задача поиска подстроки в строке. Префикс-функция. Амортизационный анализ. Метод бухгалтерского учета (метод предоплаты). Динамический массив. Алгоритм Кнута-Морриса-Пратта. Доказательство линейной асимптотики алгоритма. Алгоритм Рабина-Карпа.

Строки Амортизационный анализ

  1. (1 ноября) Конечные автоматы. Задание ejudge

  2. (8 ноября) Связь конечных автоматов и КМП. Ахо-Корасик, начало. автоматы, вторая часть Ахо-Корасик, первая часть

  3. (15 ноября) Связь Ахо-Корасик и КМП. Ахо-Корасик и хорошие суффиксные ссылки. Суффиксные деревья. Суффиксные массивы. Лемпель-Зив. Лемпель-Зив-Велч

Задание ejudge

  1. (29 ноября, 6 декабря) Графы. Поиск в ширину и в глубину, топологическая сортировка. Поиск кратчайшего пути в графе: динамическое программирование, алгоритм Дейкстры, алгоритм Беллмана-Форда. Задание

ejudge

13. Неразрешимые задачи. P, NP и NPC. Приближенные алгоритмы. Монте-Карло. Первая часть дз