Автор: Даниил Швед | Московский физико-технический институт
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
 
Уровень:
Профессионал
Длительность:
20:14:00
Студентов:
1584
Выпускников:
27
Качество курса:
5.00 | 4.67
Курс посвящён теории алгоритмов и элементам дискретной математики. Основная цель курса - научиться эффективно решать алгоритмические задачи, вооружиться фундаментальными идеями и методами, выработать системный подход к решению алгоритмических задач.
Курс знакомит с классическими методами и задачами теории алгоритмов, а также важнейшими современными задачами информатики. Курс ориентирован на математиков и программистов, студентов 1-5 курсов, предполагающих активно использовать компьютеры для решения прикладных или теоретических задач.
Специальности: Программист
 

План занятий

Занятие
Заголовок <<
Дата изучения
Лекция 1
1 час 28 минут
Жадный алгоритм
Лекция посвящена задачам, решаемым жадным алгоритмом. Приводится задача выбора подмножества из множества точек трехмерного пространства, задача нахождения максимальной системы линейно-независимых строк матрицы, задача из теории графов. Рассказывается об алгоритме Крускала, о структуре непересекающихся множеств, о системе представителей, о матроидах.
Оглавление
-
Лекция 2
1 час 23 минуты
Задачи минимального покрывающего дерева и задачи с весовыми функциями
Лекция посвящена нескольким задачам: задаче минимального покрывающего дерева, задаче с двумя весовыми функциями на одном графе, задаче с одной весовой функцией и двумя покрывающими деревьями. В лекции рассказывается также об алгоритме Крускала и алгоритме Прима.
Оглавление
-
Лекция 3
1 час 38 минут
Максимальный поток
Лекция посвящена вопросу максимального потока. В ней рассказывается о сети, о потоке, о величине потока, об определении максимального потока. Также, приводятся алгоритмы Форда-Фалкерсона и Эдмондса-Карпа. Кроме этого, даются задачи, использующие максимальный поток (задача о максимальном паросочетании и о минимальном контролирующем множестве).
Оглавление
-
Лекция 4
1 час 46 минут
Общие подходы к задачам программирования
Лекция посвящена некоторым компьютерным играм и их программированию. Рассказывается также об общих подходах к задачам программирования, об основных используемых тегах, об альфа-бета отсечении и его особенностях.
Оглавление
-
Лекция 5
1 час 35 минут
Задача о минимальном контролирующем множестве вершин и венгерский алгоритм
В лекции рассказывается о ходе решения задачи о минимальном контролирующем множестве вершин, а также о венгерском методе, его сути и недостатках. Кроме этого рассматривается венгерский алгоритм, его общая схема и частные случаи.
Оглавление
-
Лекция 6
1 час 30 минут
Метод проталкивания предпотока
Лекция посвящена методу и алгоритму проталкивания предпотока. В ней рассказывается о предпотоке, излишках в вершинах, переполненных вершинах, высотной функции и используемых операциях. Кроме этого, анализируются условия корректности работы метода, а также, приводятся замечания по операциям и по поводу остановки алгоритма.
Оглавление
-
Лекция 7
1 час 41 минута
Метод проталкивания предпотока и поиск образца в строке
В первой половине лекции заканчивается рассмотрение алгоритма проталкивания предпотока. Вторая половина лекции посвящена вопросу поиска подстрок в тексте. Рассматривается алгоритм Кнута-Морриса-Пратта, дается понятие префикса, суффикса, префикс-функции, а также решается задача ее нахождения.
Оглавление
-
Лекция 8
1 час 31 минута
Суффиксные деревья
Лекция посвящена вопросам суффиксных деревьев. В ней рассказывается о конечном автомате, о суффиксных ссылках, о построении бора, структур суффиксных деревьев и структур с суффиксными ссылками.
-
Лекция 9
1 час 40 минут
Суффиксные деревья и алгоритм Укконена
Лекция посвящена алгоритму Укконена. В ней еще раз напоминается, что такое суффиксный бор, суффиксное дерево, суффиксные ссылки, приводится алгоритм построения суффиксного бора, дается понятие конечной вершины и граничного пути. Рассматривается также, как построить суффиксное дерево, как выбрать явные и неявные вершины, дается понятие активной вершины. Кроме того, в лекции рассказывается о суффиксных массивах.
Оглавление
-
Лекция 10
1 час 34 минуты
Нейтральные и конечные игры
Лекция посвящена вопросам создания алгоритма нейтральной конечной игры, суммы игр. В ней также рассказывается о цветных играх, о числах Конвея и их определении.
Оглавление
-
Лекция 11
1 час 28 минут
Преобразование Фурье
Лекция посвящена преобразованию Фурье. В ней рассказывается об интерполяционном многочлене Лагранжа, о геометрической интерпретации умножения, о формуле Эйлера, о прямом и обратном преобразованиях Фурье.
Оглавление
-
1 час 40 минут
-
Владислав Нагорный
Владислав Нагорный

Подскажите, пожалуйста, планируете ли вы возобновление программ высшего образования? Если да, есть ли какие-то примерные сроки?

Спасибо!

Лариса Парфенова
Лариса Парфенова

1) Можно ли экстерном получить второе высшее образование "Программная инженерия" ?

2) Трудоустраиваете ли Вы выпускников?

3) Можно ли с Вашим дипломом поступить в аспирантуру?

 

Александр Качанов
Александр Качанов
Япония, Токио
Александр Хамухин
Александр Хамухин
Россия, Томск