Компьютерные науки
Математика и логика

Комбинаторные алгоритмы для программистов

В программе изучаются методы решения задач дискретной математики в программировании. Рассматриваются генерация перестановок, сочетаний, обход графов, динамическое программирование и алгоритмы на строках.
Студентов 2157 Выпускников 102 Для специалистов
690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
Темы:
Алгоритмы и сложность, Математика
Объем
36 час.
Длительность
30 дней
Нагрузка в неделю
9 час.
Формат обучения
Дистанционно (самостоятельно)
Описание Учебная программа знакомит с эффективными методами перебора и оптимизации на дискретных структурах. Слушатели изучают алгоритмы поиска путей, нахождение подмножеств, решение задач о рюкзаке и коммивояжере, а также базовые принципы криптоанализа. Освоение материала базируется на реализации классических математических задач в коде, охватывая оценку алгоритмической сложности комбинаторных переборов и применение эвристик для сокращения пространства поиска. Учебная программа ориентирована на разработчиков алгоритмов, олимпиадных программистов и исследователей в области науки о данных.
Цели
  • Дать системное представление о классах комбинаторных алгоритмов.
  • Раскрыть принципы решения задач динамического программирования на графах.
  • Сформировать навыки генерации комбинаторных объектов и перебора вариантов.
Чему я научусь?
  • Реализовывать алгоритмы генерации перестановок и сочетаний в коде.
  • Применять динамическое программирование для оптимизации вычислений.
  • Анализировать и решать дискретные задачи оптимизации (рюкзак, маршрутизация).

Авторы

Костюкова Нина Ивановна
Костюкова Нина Ивановна
Кандидат технических наук, доцент кафедры "Программирование" механико-математического факультета Новосибирского государственного университета.
Чему я научусь?
  • Реализовывать алгоритмы генерации перестановок и сочетаний в коде.
  • Применять динамическое программирование для оптимизации вычислений.
  • Анализировать и решать дискретные задачи оптимизации (рюкзак, маршрутизация).

Учебный план

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

Какой документ я получу?

Сертификат

Выдаётся автоматически после успешного завершения программы.

Удостоверение о повышении квалификации

Выдается при наличии среднего специального или высшего образования (необходимые документы).

Стоимость программы

690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
^