Курс идет по четвергам в 18.30 в ИППИ.
Содержания лекций и домашние задания (по датам)
Конспект лекций и ДЗ А.Р.Рубинова
Экзаменационные билеты
Лекция 1 (части 1, 2, 3, 4), 8 октября 2015
Лекция 2, 15 октября 2015
Лекция 3, 22 октября 2015
Лекция 4, 29 октября 2015
Лекция 5, 5 ноября 2015
Лекция 6 (части 1, 2, 3), 12 ноября 2015
Лекция 7 (части 1, 2, 3 ) 19 ноября 2015
Лекция 8 (части 1, 2, 3, 4, 5, краткий обзор пройденного материала), 26 ноября 2015
Лекция 9 (трейлер, части 1, 2, 3, 4), 3 декабря
Лекция 10 (трейлер, части 1, 2 , 3 ), 10 декабря
Лекция 11 (части
1,
2)
Экзамен (тизер)Визуализация алгоритмовПрограмма
Введение. Алгоритмы в биоинформатике Задачи сравнения текстов, глобальное парное выравнивание. Редакторское расстояние с различными операциями и штрафами. Алгоритм Нидельмана-Вунша на графах и его сравнение с полным перебором. Понятие о динамическом программировании.
Вычислительные модели и трудоемкость алгоритмов Машина Тьюринга, конечный автомат, модели и история компьютера (ячейки, доступ к памяти, хранение программы). Примеры («рибосома»). Псевдокод.
Массовые и индивидуальной задачи, размер индивидуальной задачи (варианты: число параметров, суммарная длина их записи, сумма их численных значений). Оценки времени и памяти, О(х). Сильно-полиномиальные, полиномиальные и псевдо-полиномиальные алгоритмы.
Сортировка Пузырек и сортировка слиянием, их сравнение. «Разделяй и властвуй», рекурсия.
БыстрСорт, рандомизация, трудоемкость в среднем и худшем случаях.
Теорема об необходимости О(n*ln(n)) сравнений.
Сортировка вычерпыванием и поразрядная сортировка, области применения.
Структуры данных Упорядоченные массивы, стеки, очереди, двусвязные списки, древовидные структуры. Трудоемкость базовых операций (добавить, удалить, найти, min, найти предков, потомков, пересадить ветвь).
Сбалансированные деревья, типы структур (словари, кучи). Хеширование.
Задачи на текстах, поиск образцов Наивный алгоритм и алгоритм Рабина-Карпа.
Препроцессинг образцов и префикс-функции.
Алгоритм Кнута-Морриса-Пратта, алгоритм Ахо-Корасик.
Препроцессинг текстов. Суффиксные деревья и массивы.
Задачи на графах Графы и сети в биоинформатике. Основные понятия, типичные примеры и задачи.
Поиск в глубину. Топологическая сортировка ациклического графа, построение компонент связности и сильной связности.
Поиск в ширину. Кратчайшее стягивающее дерево, дерево кратчайших путей. Понятие «жадных алгоритмов».
Кратчайший путь, варианты реализации алгоритма Дейкстры (наивный, с использованием кучи и т.д.).
Родственные задачи об оптимальных путях (поиск путей между всеми парами вершин, поиск максимальных путей, наличие отрицательных ребер и контуров, оптимальные пути на ациклических графах).
Максимальный поток в сети. Варианты постановки задачи (один/много источников/стоков, двусторонние ограничения и ограничения по вершинам, ориентированная/неориентированная сеть) и их сводимость друг к другу.
Теорема Форда-Фалкерсона и алгоритм Эдмондса-Карпа. Приложения: паросочетания (Холл), вершинная и реберная К-связность.
Поток минимальной стоимости. Варианты постановки задачи (максимальная и фиксированная мощность, транспортная задача, задача о назначениях и т.п.) и их эквивалентность. Метод отрицательных контуров. Двойственность, метод потенциалов, его связь с методом отрицательных контуров.
Сложность задач Полиномиальные алгоритмы, полиномиальная сводимость задач. Сводимость оптимизационных задач к задачам на существование. Понятие о NP-полноте. Примеры NP-полных задач (коммивояжер, клика, вершинное покрытие, раскрой, ранец, разбиение), примеры их сведения друг к другу. Псевдо-полиномиальные алгоритмы динамического программирования для задач о ранце и раскрое. Понятие сложности текстов.
1