Введение в теоретическую информатику для биологов и биоинформатиков

Список всех тем лекций

Лекция 1. Введение в алгоритмы. Машина Тьюринга. Типы данных..
Введение в предмет курса Понятие алгоритма Структура курса Учебные материалы, необходимые для курса Машина Тьюринга Задача на построение машины Тьюринга, выполняющей копирование данной последовательности знаков Примеры применения машины Тьюринга Понятие компьютера Суть работы алгоритма Булева алгебра Многомерное пространство {0,1} в степени n Двумерные функции "и" и "или" Одномерная функция "не" ("не" X & "не" Y) Примеры других булевых функций Теорема: Любая булева функция от n переменных может быть представлена в виде формулы, содержащей только "и", "или", "не". Основание индукции Типы данных

Лекция 2. Адреса элемента. Упорядоченные и неупорядоченные массивы.
Адрес элемента Свойства массива Скриптовые и компилируемые языки Понятие массива на примере телефонной книги Алгоритм поиска элемента в неупорядоченном массиве Псевдокод Анализ алгоритма Упорядоченный массив Операции сравнения Операция "больше" Алгоритм поиска элемента в упорядоченном массиве Соглашение о нумерации в массиве Анализ работы алгоритма поиска элемента n/2 Добавление в упорядоченном и неупорядоченном массиве Удаление в упорядоченном и неупорядоченном массиве Упорядочение массива

Лекция 3. Методы сортировки массивов.
Сортировка слиянием Время работы сортировки Алгоритм QSort Задача сортировки массивов Односвязный список

Лекция 4. Структуры данных.
Односвязные списки Двусвязный список Очередь Стэк Дерево Время выполнения операций в различных структурах данных Бинарное дерево поиска

Лекция 5. Бинарные и красно-черные деревья.
Вопрос: Как по номеру элемента добыть элемент, например, в дереве? Построение бинарного дерева поиска, элементами которого будут слова Ввод операции вращения Красно-черное дерево Добавление элемента в красно-черное дерево

Лекция 6. Удаление элемента из красно-черного дерева, хэш-таблицы, работа со строками.
Удаление элемента из бинарного дерева Время выполнения операций в различных структурах данных Хэш-таблица Работа со строками

Лекция 7. Работа со строками.
Алгоритм Раббина-Карпа Суффиксы и префиксы слов Алгоритм Кнута-Морриса-Пратта Препроцессинг Свойства SP Мат ожидание n не зависит от структуры, а дисперсия зависит

Лекция 8. Автоматы.
Конечный автомат Построение автомата для поиска паттерна Построение конечного автомата (в качестве текста паттерн) σ(xa) q = σ(x), тогда σ(xa)= σ ((префикса P длины q)a) φ(Тi)= σ(Ti) Регулярное выражение Недетерминированные конечные автоматы

Лекция 9. Автомат Ахо-Корасик.
Поиск многих образцов в тексте Новые понятия: уровень вершины, функция неудач, метка ребра Автомат Ахо-Корасик Алгоритм, где мы долго работаем с текстом, но образцы быстро прикладываются Система описания текста

Лекция 10. Сложность текста и системы описания текстов.
Колмогоровская сложность текста не хуже системы П2 Можем ли мы сделать из двух систем одну общую? Универсальный описатель Про количество слов сложности k Пример: азбука Морзе Код Хаффмана Алгоритм Лемпеля- Зива Алгоритм Лемпеля- Зива-Вельча

Лекция 11. Алгоритм Лемпеля- Зива-Вельча. Графы.
Алгоритм Лемпеля- Зива-Вельча Примеры Методы задания графов Обход графа в ширину

Лекция 12. Ориентированные графы.
Обход графа в глубину Циклы Задача Эйлера Примеры использования Топологическая сортировка ориентированного графа

Лекция 13. Поиск оптимального пути в графе. Часть 1.
Кластеризация Поиск оптимального пути в графе Орграф без циклов Полукольцо Слайдинг Маршрутизация автомобилей, маршрутизация пакетов в интернете

Лекция 14. Поиск оптимального пути в графе. Часть 2.
Поиск кратчайшего пути во взвешенном графе Релакс (расслабление вершины относительно другой вершины) Очередь с приоритетами Алгоритм Дейкстры Алгоритм Беллмана-Форда Величина потока Найти такой поток в сети, который максимизирует величину потока Поток через разрез

Лекция 15. Теорема Форда-Фалкерсона. Понятие о NP полных задачах.
Теорема Форда-Фалкерсона Примеры задач о максимальном потоке Алгоритмы сортировки массива Алгоритм распознает язык Сводимость языков Проверяющий алгоритм NP полная задача

Лекция 16. Сведение задач к NP полным. Стохастические методы.
Варианты сведения одной задачи к другой Докажем, что 3CNF является NP полной задачей CLIQUE в графе Задача о CLIQUE является NP полной Приближенные (стохастические) методы