Программа курса "Алгоритмы. Построение и анализ"

• Информация о курсе
• Задачи для практикума
• Рекомендуемые материалы

---

Содержание:

Основные понятия: алгоритм, рекурсия.

О-нотация и методы оценки времени работы алгоритмов. 5 методов вычисления чисел Фибонначи и их анализ. Точная оценка асимптотики времени работы алгоритма вычисления чисел Фибонначи с учетом времени на длинной арифметики.

Двоичный поиск (дихотомия)

Корень уравнения. Пристрелка аргументов монотонных функций. Задачи "Корень уравнения", "Провода" и "Книга". Задача реализации своей структуры данных "Множество" с быстрой проверкой свойства принадлежности. Использование шаблона set из библиотеки STL.

АТД "Стек" и "Очередь"

АТД "Стек". Задача определения правильности скобочного выражения с несколькими типами скобок. Задача "постфиксный калькулятор". Задача перевода выражения из постфиксной нотации в инфиксную за линейное время. Реализация очереди с помощью двух стеков.

Жадные алгоритмы

Задачи о заявках (максимизация числа удовлетворенных заявок и минимизация числа аудиторий). Задача про атлетов. Алгоритмы Крускала и Прима поиска минимального остовного дерева.

Динамическое программирование.

Использование памяти для хранения найденных решений. Рекурсия с запоминанием или динамическое программирование сверху. Вычисление треугольника Паскаля с помощью рекурсии с запоминанием --- каков выйгрыш во времени по сравнению с обычной рекурсией? Общая идея декомпозиции и кеширования ответов. Вычисления числа скобочных выражений как количества путей в графе.

Задача "Бюрократический барьер". Задача вычисления количества представлений натурального числа в виде суммы упорядоченного/неупорядоченного набора различных/любых натуральных слагаемых.

Геометрические задачи.

Выпуклая оболочка. Площадь многоугольника. Важные точки треугольника. Применение дихотомии при решении геометрических задач. Задача про сферы. Задача про систему линейных неравенств на плоскости. Задача про бассейн. Метод деления попалам, метод границ и метод сведения к простым задачам на основании теоремы Хелли.

Деревья поиска и Хэш-таблицы.

АТД "Ассоциативный массив". Структуры, позволяющие выполнять find, insert и delete за O(log N). Двоичное дерево поиска. Белансировка деревьев поиска. Использование шаблона map. Хэш-функция и разрешение коллизий. Двойное хэширование.

Графы (часть 1). Основные алгоритмы, задачи о кратчайших путях.

Основные алгоритмы на графах. Представление графов. Обходы графов. Поиск в глубину и в ширину. Подсчёт числа связных компонент. Сильная и слабая связность. Топологическая сортировка. Повторяем задачу про минимальные покрывающие деревья. Кратчайшие пути. Алгоритм Дейкстры. Алгоритм Флойда-Уоршала. Умножение матриц в арифметике {MIN, +}.

Графы (часть 2). Максимальный поток и задача о максимальном паросочетании.

Задача про домино. Задача про максимальное число свадеб (максимальное паросочетание в двудольном графе). Задача про максимальный поток. Общая идея последовательных локальных улучшений. Метод Форда-Фалкерсона. Алгоритм "проталкивания предпотока". Минимальное сечение. Примеры задач, которые сводятся к максимальному потоку.

Приближённые алгоритмы и NP-полные задачи.

Классы сложности P и NP. NP-полные задачи: SAT, задача коммиавяжера, минимальное покрытие множествами, ... Генетические алгоритмы. Универсальные и не очень универсальные "эвристики". Базис NP-программирования. Метасистемные переходы и выделение макро-объектов. Метод отжига. Метод масштабирования. Как распознать NP-сложную задачу?

Программирование стратегий для игр

Дерево ходов. Дебюты, Middlegame и эндшпили — три различных алгоритма игры. Эндшпили — динамическое программирование. Middlegame — альфа-бета отсечение. Улучшения альфа-бета отсечения: запоминание оценок, сортировка по эвристике в узлах дерева ходов, вариации с узким окном — SSS, MTD(f).

Теория информации

Понятие количества информации и формула энтропии. Задача определения количества бит в информационных сообщениях. Алгоритм сжатия данных Хафмана (Huffman). Идея Information Bottleneck в алгоритмах классификации и распознования.

-- ArtemVoroztsov - 25 Mar 2004

---