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

Алгоритмы и модели вычислений

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

Авторы

Фуругян Меран Габибуллаевич
Фуругян Меран Габибуллаевич
Кандидат физико-математических наук, заведующий сектором ВЦ РАН, доцент МФТИ, доцент МГУ.\n
Чему я научусь?
  • Оценивать вычислительную сложность алгоритмов.
  • Применять теорию NP-полноты к разработке приближенных алгоритмов.
  • Использовать методы решения переборных задач и планирования вычислений.

Учебный план

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

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

Сертификат

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

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

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

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

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