Kodomo

Пользователь

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

Семестр 5. Введение в алгоритмы

Ведомость

Там есть ошибки (до сих пор).

Рекомендованная литература

Расписание

  1. Машина Тьюринга. Сложность алгоритма. Элементарные операции. Кэши и устройство современного компьютера. Параллелизация. Альтернативы сложности алгоритма для современных компьютеров.

    [ Презентация | Задание ]

  2. Битовые операции. Массив. Динамический массив. Амортизационная сложность. Рекурсия. Бинарный поиск. Модификации (поиск левого крайнего, правого крайнего, поиск участка равных значений)

    [ Презентация | Домашнее задание, условие | ejudge ]

  3. Сортированный массив. Сортировка вставками. Сортировка слиянием. Быстрая сортировка. Partition. Поиск k-й порядковой статистики. Рандомизированные алгоритмы.

    [ Презентация | ejudge ] Дедлайн по дз: 23:59 06.10.2020

  4. Сортировка подсчетом. Односвязный список. Двусвязный список. Стек. Очередь. [Стек с минимумом за O(1).] Циклический массив.

    [ Презентация | ejudge ] Дедлайн по дз: 23:59 17.10.2020

  5. Замена системной рекурсии стеком. Разбор формул при помощи стека - без приоритета и с приоритетом. Бинарные деревья. Бинарные деревья поиска. Рандомизированное дерево поиска.

    [ Презентация | Условия дз | ejudge ] Дедлайн по дз: 23:59 29.10.2020

  6. Сбалансированные деревья. Красно-черные деревья. Хэш-функция и требования к ней. Хэш-таблицы - закрытая и [открытая] адресация. Фильтр Блума.

    [ Презентация, деревья | Презентация, хэш-таблицы | Домашнее задание | ejudge ] Дедлайн по дз: 23:59 04.11.2020

  7. Контрольная работа 1.
  8. Поиск в строке. Наивный алгоритм. Алгоритм Рабина-Карпа. Префикс-функция. Кнут-Моррис-Пратт. Время работы алгоритма КМП.

    [ Презентация | Домашнее задание | ejudge ] Дедлайн по дз: 23:59 11.11.2020

  9. Конечные автоматы. [Построение суффикс функции за линейное время]. Недетерминированные автоматы.

    [ Презентация, автоматы ] [ ejudge ] Дедлайн по дз: 23:59 22.11.2020

  10. Нагруженное дерево. Ахо-Корасик. Суффиксные ссылки и хорошие суффиксные ссылки.

    [ Презентация, Ахо-Корасик, начало ] [ Презентация, Ахо-Корасик, продолжение ]

  11. Суффиксный массив. Суффиксный бор. Суффиксное дерево.

    [ Презентация ] [ Домашнее задание ] Дедлайн. по дз: 23:59 06.12.2020 [ ejudge ]

  12. Контрольная работа 2.
  13. Графы. Виды графов. Поиск в ширину, глубину, поиск связной компоненты.

    [ Презентация ]

  14. Взвешенные графы. Поиск кратчайшего пути. Динамическое программирование на DAG. Подсчет числа путей.

    [ Презентация ] [ Условия ДЗ ] [ ejudge ]

  15. Понятие жадного алгоритма. Алгоритм Дейкстры. Алгоритм Беллмана-Форда. Проверка графа на наличие циклов отрицательного веса. Сложность по Колмогорову. Кодирование. Код Хаффмана. [Лемпель-Зив. Лемпель-Зив-Велч. Сети и потоки в них]

    [ Презентация ] [ Условия ДЗ ] [ ejudge ]

  16. Контрольная работа 3.
  17. Неразрешимые задачи. P-задачи. NP-полные задачи. Доказательство NP-полноты. Метод ветвей и границ. [Методы приближенного решения задач. Точные алгоритмы, дающие решение, отличающееся от оптимального не более чем на множитель. Монте-Rарло алгоритмы. Генетические алгоритмы]