| Россия |
Инспектор
Вы можете этот курс.
Опубликован: 08.11.2006 | Уровень: специалист | Доступ: платный | ВУЗ: Новосибирский Государственный Университет
Курс начинается с азов комбинаторики и охватывает все основные алгоритмы, их анализ и реализацию на языках программирования, а так же рассматриваются алгоритмы на графах с точки зрения комбинаторных методов их реализации и анализа.
Курс описывает различные способы представлений конечных последовательностей и операций над ними; множества и мультимножества; производящие функции и рекуррентные соотношения; абстрактные структуры данных; алгоритмы рекуррентных соотношений; комбинаторные задачи теории информации; алгоритмы на абстрактных структурах данных; различные типы поисков (последовательный, логарифмический в статических и динамических таблицах, бинарный, по сбалансированным сильно ветвящимся деревьям); все виды сортировок (внутренняя, вставка, обменная сортировка, выбор, распределяющая сортировка, цифровая распределяющая сортировка, частичная сортировка-выбор, частичная сортировка-слияние); алгоритмы на графах Дейкстры и алгоритм Флойда. В конце курса приводится программная реализация на языках программирования Паскаль, Си, С++ классических комбинаторных алгоритмов.
Дополнительные курсы |
План занятий
| Занятие | Заголовок << | Дата изучения |
|---|---|---|
| - | ||
Лекция 128 минут | Комбинаторные вычисления
Введение. Проблема представления: коды, сохраняющие разности. Классы
алгоритмов. Анализ алгоритмов. Программа.
Оглавление | - |
Тест 19 минут | - | |
Лекция 232 минуты | Целые и последовательности (последовательное распределение)
Введение. Целые. Последовательности. Различные способы представлений
конечных последовательностей (или начальных сегментов бесконечных
последовательностей) и операции над ними.
Оглавление | - |
Тест 29 минут | - | |
Лекция 323 минуты | Последовательности (связанное распределение, стеки и очереди)
Связанное распределение. Разновидности связанных списков. Стеки и
очередь. Задачи. Программы.
Оглавление | - |
Тест 39 минут | - | |
Лекция 423 минуты | Последовательности (деревья)
Деревья. Представления. Прохождения. Длина путей. Задача. Программа.
Оглавление | - |
Тест 49 минут | - | |
Лекция 536 минут | Комбинаторика разбиений
Введение. Задачи. Разные статистики. Деревья и перестановки из
n элементов. Число сочетаний Cmn. Задачи на разбиение чисел.
Комбинаторные задачи теории информации.
Оглавление | - |
Тест 59 минут | - | |
Лекция 634 минуты | Последовательности (множества и мультимножества)
Множества и мультимножества. Формула включений и исключений.
Решето Эратосфена. Примеры программ.
Оглавление | - |
Тест 69 минут | - | |
Лекция 742 минуты | Рекуррентные соотношения
Размещения без повторений. Перестановки. Сочетания. Рекуррентные
соотношения. Другой метод доказательства. Процесс последовательных
разбиений. Задача: "Затруднение мажордома".
Оглавление | - |
Тест 79 минут | - | |
Лекция 834 минуты | Алгоритмы рекуррентных соотношений
Решение рекуррентных соотношений. Линейные рекуррентные
соотношения с постоянными коэффициентами. Случай равных корней
характеристического уравнения. Производящие функции.
Оглавление | - |
Тест 89 минут | - | |
Лекция 930 минут | Комбинаторика и ряды
Введение. Деление многочленов. Алгебраические дроби и степенные
ряды. Действия над степенными рядами.
Оглавление | - |
Тест 99 минут | - | |
Лекция 1026 минут | Производящие функции и рекуррентные соотношения
Применение степенных рядов для доказательства тождеств. Производящие
функции. Бином Ньютона. Ряд Ньютона. Производящие функции и
рекуррентные соотношения. О едином нелинейном рекуррентном соотношении.
Оглавление | - |
Тест 109 минут | - | |
Лекция 1124 минуты | Алгоритмы на абстрактных структурах данных
Введение. Стеки. Очереди. Связанные списки. Двоичные деревья.
Оглавление | - |
Тест 119 минут | - | |
Лекция 1251 минута | Что такое граф? Определения и примеры
Введение. Представления. Связность и расстояние. Остовные деревья.
Клики. Изоморфизм. Планарность.
Оглавление | - |
Тест 129 минут | - | |
Лекция 131 час 3 минуты | Поиск
Введение. Поиск и другие операции над таблицами. Последовательный
поиск. Логарифмический поиск в статических таблицах. Бинарный поиск.
Оптимальные деревья бинарного поиска. Логарифмический поиск в
динамических таблицах. Сбалансированные сильно ветвящиеся деревья.
Оглавление | - |
Тест 139 минут | - | |
Лекция 1430 минут | Сортировка (часть 1)
Введение. Внутренняя сортировка. Вставка. Обменная сортировка.
Оглавление | - |
Тест 149 минут | - | |
Лекция 1534 минуты | Сортировка (часть 2)
Выбор. Распределяющая сортировка. Цифровая распределяющая
сортировка. Внешняя сортировка. Частичная сортировка. Частичная сортировка
(выбор). Частичная сортировка (слияние).
Оглавление | - |
Тест 159 минут | - | |
Лекция 1627 минут | Алгоритмы на графах
Поиск в глубину. Алгоритм Дейкстры нахождения кратчайшего пути.
Алгоритм Флойда нахождения кратчайших путей между парами вершин.
Программы.
Оглавление | - |
Тест 169 минут | - | |
Лекция 1746 минут | Калейдоскоп из комбинаторных алгоритмов
Автоматическое построение лабиринтов. Бинарное дерево. Задача о
восьми ферзях. Сортировки. Задача о назначениях (задачи выбора).
Ханойская башня.
Оглавление | - |
Тест 179 минут | - | |
5 часов | - |
