Комбинаторные алгоритмы для программистов: Информация
Автор: Нина Костюкова | Новосибирский Государственный Университет
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 34 студентам
Уровень:
Специалист
Длительность:
12:16:00
Студентов:
1942
Выпускников:
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 минут
Калейдоскоп из комбинаторных алгоритмов
Автоматическое построение лабиринтов. Бинарное дерево. Задача о
восьми ферзях. Сортировки. Задача о назначениях (задачи выбора).
Ханойская башня.
Оглавление
-