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