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

Алгоритмы: построение и анализ

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

Авторы

Швед Даниил Андреевич
Швед Даниил Андреевич
Ассистент (МФТИ).
Чему я научусь?
  • Разрабатывать и анализировать жадные алгоритмы и алгоритмы на графах.
  • Решать задачи на поиск максимального потока и минимального покрывающего дерева.
  • Применять алгоритм Укконена и преобразование Фурье.

Учебный план

№ Занятия
Экзамен экстерном Внимание! Экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите подтвердить свои знания по данному курсу без его изучения или поверить свои знания по нему. Экзамен экстерном можно сдать только один раз. 90 мин
1 Жадный алгоритм Лекция посвящена задачам, решаемым жадным алгоритмом. Приводится задача выбора подмножества из множества точек трехмерного пространства, задача... Лекция посвящена задачам, решаемым жадным алгоритмом. Приводится задача выбора подмножества из множества точек трехмерного пространства, задача нахождения максимальной системы линейно-независимых строк матрицы, задача из теории графов. Рассказывается об алгоритме Крускала, о структуре непересекающихся множеств, о системе представителей, о матроидах. ещё
2 Задачи минимального покрывающего дерева и задачи с весовыми функциями Лекция посвящена нескольким задачам: задаче минимального покрывающего дерева, задаче с двумя весовыми функциями на одном графе,... Лекция посвящена нескольким задачам: задаче минимального покрывающего дерева, задаче с двумя весовыми функциями на одном графе, задаче с одной весовой функцией и двумя покрывающими деревьями. В лекции рассказывается также об алгоритме Крускала и алгоритме Прима. ещё
Задачи минимального покрывающего дерева и задачи с весовыми функциями тест для курса Алгоритмы: построение и анализ 60 мин
3 Максимальный поток Лекция посвящена вопросу максимального потока. В ней рассказывается о сети, о потоке, о величине потока, об... Лекция посвящена вопросу максимального потока. В ней рассказывается о сети, о потоке, о величине потока, об определении максимального потока. Также, приводятся алгоритмы Форда-Фалкерсона и Эдмондса-Карпа. Кроме этого, даются задачи, использующие максимальный поток (задача о максимальном паросочетании и о минимальном контролирующем множестве). ещё
4 Общие подходы к задачам программирования Лекция посвящена некоторым компьютерным играм и их программированию. Рассказывается также об общих подходах к задачам программирования,... Лекция посвящена некоторым компьютерным играм и их программированию. Рассказывается также об общих подходах к задачам программирования, об основных используемых тегах, об альфа-бета отсечении и его особенностях. ещё
5 Задача о минимальном контролирующем множестве вершин и венгерский алгоритм В лекции рассказывается о ходе решения задачи о минимальном контролирующем множестве вершин, а также о венгерском... В лекции рассказывается о ходе решения задачи о минимальном контролирующем множестве вершин, а также о венгерском методе, его сути и недостатках. Кроме этого рассматривается венгерский алгоритм, его общая схема и частные случаи. ещё
Задача о минимальном контролирующем множестве вершин и венгерский алгоритм тест для курса Алгоритмы: построение и анализ 60 мин
6 Метод проталкивания предпотока Лекция посвящена методу и алгоритму проталкивания предпотока. В ней рассказывается о предпотоке, излишках в вершинах, переполненных... Лекция посвящена методу и алгоритму проталкивания предпотока. В ней рассказывается о предпотоке, излишках в вершинах, переполненных вершинах, высотной функции и используемых операциях. Кроме этого, анализируются условия корректности работы метода, а также, приводятся замечания по операциям и по поводу остановки алгоритма. ещё
7 Метод проталкивания предпотока и поиск образца в строке В первой половине лекции заканчивается рассмотрение алгоритма проталкивания предпотока. Вторая половина лекции посвящена вопросу поиска подстрок... В первой половине лекции заканчивается рассмотрение алгоритма проталкивания предпотока. Вторая половина лекции посвящена вопросу поиска подстрок в тексте. Рассматривается алгоритм Кнута-Морриса-Пратта, дается понятие префикса, суффикса, префикс-функции, а также решается задача ее нахождения. ещё
Метод проталкивания предпотока и поиск образца в строке тест для курса Алгоритмы: построение и анализ 60 мин
8 Суффиксные деревья Лекция посвящена вопросам суффиксных деревьев. В ней рассказывается о конечном автомате, о суффиксных ссылках, о построении... Лекция посвящена вопросам суффиксных деревьев. В ней рассказывается о конечном автомате, о суффиксных ссылках, о построении бора, структур суффиксных деревьев и структур с суффиксными ссылками. ещё
9 Суффиксные деревья и алгоритм Укконена Лекция посвящена алгоритму Укконена. В ней еще раз напоминается, что такое суффиксный бор, суффиксное дерево, суффиксные... Лекция посвящена алгоритму Укконена. В ней еще раз напоминается, что такое суффиксный бор, суффиксное дерево, суффиксные ссылки, приводится алгоритм построения суффиксного бора, дается понятие конечной вершины и граничного пути. Рассматривается также, как построить суффиксное дерево, как выбрать явные и неявные вершины, дается понятие активной вершины. Кроме того, в лекции рассказывается о суффиксных массивах. ещё
Суффиксные деревья и алгоритм Укконена тест для курса Алгоритмы: построение и анализ 60 мин
10 Нейтральные и конечные игры Лекция посвящена вопросам создания алгоритма нейтральной конечной игры, суммы игр. В ней также рассказывается о цветных... Лекция посвящена вопросам создания алгоритма нейтральной конечной игры, суммы игр. В ней также рассказывается о цветных играх, о числах Конвея и их определении. ещё
11 Преобразование Фурье Лекция посвящена преобразованию Фурье. В ней рассказывается об интерполяционном многочлене Лагранжа, о геометрической интерпретации умножения, о... Лекция посвящена преобразованию Фурье. В ней рассказывается об интерполяционном многочлене Лагранжа, о геометрической интерпретации умножения, о формуле Эйлера, о прямом и обратном преобразованиях Фурье. ещё
Преобразование Фурье тест для курса Алгоритмы: построение и анализ 60 мин
Тренировочный экзамен Внимание! Тренировочный экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите проверить свои знания курса перед сдачей экзамена. Тренировочный экзамен можно сдавать сколько угодно один раз. 90 мин
Экзамен 60 мин

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

Сертификат

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

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

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

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

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