Опубликована: 05.04.2011 | Уровень: для всех | Стоимость: 3000.00 руб. | Длительность: 14 дней
Курс начинается с азов комбинаторики и охватывает все основные алгоритмы, их анализ и реализацию на языках программирования, а так же рассматриваются алгоритмы на графах с точки зрения комбинаторных методов их реализации и анализа.
Курс описывает различные способы представлений конечных последовательностей и операций над ними; множества и мультимножества; производящие функции и рекуррентные соотношения; абстрактные структуры данных; алгоритмы рекуррентных соотношений; комбинаторные задачи теории информации; алгоритмы на абстрактных структурах данных; различные типы поисков (последовательный, логарифмический в статических и динамических таблицах, бинарный, по сбалансированным сильно ветвящимся деревьям); все виды сортировок (внутренняя, вставка, обменная сортировка, выбор, распределяющая сортировка, цифровая распределяющая сортировка, частичная сортировка-выбор, частичная сортировка-слияние); алгоритмы на графах Дейкстры и алгоритм Флойда. В конце курса приводится программная реализация на языках программирования Паскаль, Си, С++ классических комбинаторных алгоритмов.

План занятий

ЗанятиеЗаголовок <<Дата изучения
-
Лекция 1
28 минут
Комбинаторные вычисления
Введение. Проблема представления: коды, сохраняющие разности. Классы алгоритмов. Анализ алгоритмов. Программа.
-
Тест 1
9 минут
-
Лекция 2
32 минуты
Целые и последовательности (последовательное распределение)
Введение. Целые. Последовательности. Различные способы представлений конечных последовательностей (или начальных сегментов бесконечных последовательностей) и операции над ними.
-
Тест 2
9 минут
-
Лекция 3
23 минуты
Последовательности (связанное распределение, стеки и очереди)
Связанное распределение. Разновидности связанных списков. Стеки и очередь. Задачи. Программы.
-
Тест 3
9 минут
-
Лекция 4
23 минуты
Последовательности (деревья)
Деревья. Представления. Прохождения. Длина путей. Задача. Программа.
-
Тест 4
9 минут
-
Лекция 5
36 минут
Комбинаторика разбиений
Введение. Задачи. Разные статистики. Деревья и перестановки из n элементов. Число сочетаний Cmn. Задачи на разбиение чисел. Комбинаторные задачи теории информации.
-
Тест 5
9 минут
-
Лекция 6
34 минуты
Последовательности (множества и мультимножества)
Множества и мультимножества. Формула включений и исключений. Решето Эратосфена. Примеры программ.
-
Тест 6
9 минут
-
Лекция 7
42 минуты
Рекуррентные соотношения
Размещения без повторений. Перестановки. Сочетания. Рекуррентные соотношения. Другой метод доказательства. Процесс последовательных разбиений. Задача: "Затруднение мажордома".
-
Тест 7
9 минут
-
Лекция 8
34 минуты
Алгоритмы рекуррентных соотношений
Решение рекуррентных соотношений. Линейные рекуррентные соотношения с постоянными коэффициентами. Случай равных корней характеристического уравнения. Производящие функции.
-
Тест 8
9 минут
-
Лекция 9
30 минут
Комбинаторика и ряды
Введение. Деление многочленов. Алгебраические дроби и степенные ряды. Действия над степенными рядами.
-
Тест 9
9 минут
-
Лекция 10
26 минут
Производящие функции и рекуррентные соотношения
Применение степенных рядов для доказательства тождеств. Производящие функции. Бином Ньютона. Ряд Ньютона. Производящие функции и рекуррентные соотношения. О едином нелинейном рекуррентном соотношении.
-
Тест 10
9 минут
-
Лекция 11
24 минуты
Алгоритмы на абстрактных структурах данных
Введение. Стеки. Очереди. Связанные списки. Двоичные деревья.
-
Тест 11
9 минут
-
Лекция 12
51 минута
Что такое граф? Определения и примеры
Введение. Представления. Связность и расстояние. Остовные деревья. Клики. Изоморфизм. Планарность.
-
Тест 12
9 минут
-
Лекция 13
1 час 3 минуты
Поиск
Введение. Поиск и другие операции над таблицами. Последовательный поиск. Логарифмический поиск в статических таблицах. Бинарный поиск. Оптимальные деревья бинарного поиска. Логарифмический поиск в динамических таблицах. Сбалансированные сильно ветвящиеся деревья.
-
Тест 13
9 минут
-
Лекция 14
30 минут
Сортировка (часть 1)
Введение. Внутренняя сортировка. Вставка. Обменная сортировка.
-
Тест 14
9 минут
-
Лекция 15
34 минуты
Сортировка (часть 2)
Выбор. Распределяющая сортировка. Цифровая распределяющая сортировка. Внешняя сортировка. Частичная сортировка. Частичная сортировка (выбор). Частичная сортировка (слияние).
-
Тест 15
9 минут
-
Лекция 16
27 минут
Алгоритмы на графах
Поиск в глубину. Алгоритм Дейкстры нахождения кратчайшего пути. Алгоритм Флойда нахождения кратчайших путей между парами вершин. Программы.
-
Тест 16
9 минут
-
Лекция 17
46 минут
Калейдоскоп из комбинаторных алгоритмов
Автоматическое построение лабиринтов. Бинарное дерево. Задача о восьми ферзях. Сортировки. Задача о назначениях (задачи выбора). Ханойская башня.
-
Тест 17
9 минут
-
5 часов
-