Geum.ru

Наименование магистерской программы Методы анализа и синтеза проектных решений Направление подготовки

Вид материалаДокументы

Содержание


Теория графов”
Основные разделы курса
Совершенные структуры
Подобный материал:
1   2   3   4

"Дискретные экстремальные задачи


Цель дисциплины: изучение математических моделей и методов решения оптимизационных задач, возникающих при анализе и синтезе проектных решений. В целом материал курса ориентирован на ознакомление с базовыми математическими моделями, освоение численных методов решения классических экстремальных задач, а также знакомство с современными направлениями развития методов принятия решений.

Для достижения поставленной цели выделяются задачи курса:
  • Дать студентам представление об математических моделях и методах решения оптимизационных задач.
  • Помочь им в изучении общих методов решения дискретных экстремальных задач – метода отсечения, динамического программирования, методов ветвления и отсечения.
  • Научить правильно классифицировать конкретную прикладную задачу и выбирать наиболее подходящий метод её решения.


Дисциплина входит в число дисциплин по выбору студента общенаучного цикла образовательной программы магистра. Изучение данной дисциплины базируется на базовых знаниях поступающего в магистратуру.

Изучение дисциплины направлено на формирование следующих общекультурных компетенций ОК-1, ОК-2, ОК-4 и профессиональных компетенций ПК-1, ПК-5, ПК-6.

В результате изучения дисциплины студент должен:


Знать:
  • элементы теории сложности для анализа задач математического программирования;
  • общие методы решения дискретных экстремальных задач – метод отсечения, динамического программирования, методы ветвления и отсечения.
  • базовые понятия, основные определения теории дискретных экстремальных задач;
  • современные подходы к решению задач дискретной оптимизации.

Уметь:
  • уметь оценить перспективы и возможности различных методов в конкретной прикладной задаче.
  • выбирать подходящий метод решения задачи.

Владеть навыками:
  • решения дискретных экстремальных задач - методом отсечения, динамического программирования, методами ветвления и отсечения.



Основные разделы и темы курса:
  • Экстремальные задачи на графах. Нахождение паросочетаний максимальной мощности и максимального веса.
  • Полиномиальные методы вычисления максимального потока в сети.
  • Общие методы решения дискретных экстремальных задач. Методы отсечений. Целочисленные многогранные множества.
  • Полиномиальная сводимость и NP-трудные задачи. Теорема Кука. Примеры полиномиальных сводимостей и доказательство NP-полноты классических задач комбинаторной оптимизации.
  • Приближенные алгоритмы с оценками качества. Рандомизированные алгоритмы. Полиномиальные и вполне полиномиальные приближенные схемы.



Аннотация учебной программы дисциплины

“^ Теория графов”


Цель дисциплины: ознакомление с базовыми математическими моделями и освоение теоретических основ решения задач теории графов, а также знакомство с современным состоянием и перспективами развития этого бурно развивающегося математического направления. В целом материал курса ориентирован на изучение классических моделей и методов решения задач, допускающих интерпретацию в терминах теории графов.


Для достижения поставленной цели выделяются задачи курса:
  • Дать студентам представление о современном состоянии и перспективах развития этого бурно развивающегося математического направления; познакомить с базовыми математическими моделями теории графов.
  • Помочь им в освоение теоретических основ решения задач теории графов.
  • Научить правильно классифицировать конкретную прикладную задачу, уметь оценивать перспективы и возможности методов теории графов в конкретной прикладной задаче.



Дисциплина входит в число дисциплин по выбору студента общенаучного цикла образовательной программы магистра. Изучение данной дисциплины базируется на базовых знаниях поступающего в магистратуру.

Изучение дисциплины направлено на формирование следующих общекультурных компетенций ОК-1, ОК-2, ОК-4 и профессиональных компетенций ПК-1, ПК-5, ПК-6.

В результате изучения дисциплины студент должен:

Знать:
  • об областях применения теории графов и, в частности, о раскрасках графов, критериях связности, двудольности, отделимости, Эйлеровости и Гамильтоновости;
  • теоретические основы решения задач теории графов - базовые понятия, основные определения теории, математические модели;
  • современные подходы к решению задач c использованием теории графов;
  • знать критерии планарности, двудольности, к-связности, оценки хроматического числа.

Уметь:
  • уметь оценивать перспективы и возможности методов теории графов в конкретной прикладной задаче;
  • выбирать подходящие методы решения задач, допускающих интерпретацию в терминах теории графов.

Владеть навыками:
  • решения задач теории графов;
  • определять вычислительную сложность экстремальных задач на графах;
  • разработки оптимизационных алгоритмов на графах.


Основные разделы и темы курса:

  • Введение в теорию графов.
  • Ациклические графы и цикломатическое число.
  • Эйлеровы и Гамильтоновы графы.
  • Плоские графы.
  • Паросочетания и теория f-факторов
  • Симметрии графов.
  • Раскраски графов.
  • Потоковые алгоритмы на графах



Аннотация учебной программы дисциплины

" Математическое программирование"


Основной целью курса является ознакомление с базовыми математическими моделями и освоение численных методов решения классических экстремальных задач, а также знакомство с современными направлениями развития методов оптимизации. В целом материал курса ориентирован на умение правильно классифицировать конкретную прикладную задачу, выбирать наиболее подходящий метод решения и реализовывать его в виде алгоритма и программы.

Для достижения поставленной цели выделяются задачи курса:

Дать студентам представление об областях применения математического программирования и, в частности, дробно-линейного, квадратичного и выпуклого программирования.

Знать математические методы, являющиеся основой теории матричных игр, потоков в сетях, задач комплементарности.

Уметь оценить перспективы и возможности методов математического программирования в конкретной прикладной задаче.

Требуемые компетенции для изучения данной дисциплины отвечают ключевым компетенциям бакалавра, указанным в Федеральном государственном стандарте высшего профессионального образования по направлению подготовки 230100 Информатика и вычислительная техника (квалификация (степень) "Бакалавр").


Изучение дисциплины направлено на формирование следующих общекультурных и профессиональных компетенций:

ОК-1, ОК-2, ОК-4

ПК-1, ПК-5, ПК-6

В результате изучения дисциплины студент должен:

Знать:

- об областях применения математического программирования и, в частности, дробно-линейного, квадратичного и выпуклого программирования;

Уметь:

- оценить перспективы и возможности методов математического программирования в конкретной прикладной задаче;

Владеть:

- математическими методами, являющиеся основой теории матричных игр, потоков в сетях, задач комплементарности.


^ Основные разделы курса:

Двухкомпонентные задачи

Дробно-линейное программирование

Задачи комплементарности

Биматричные игры


Предполагается, что студенты самостоятельно будут работать с литературой. Оценки за контрольные недели выставляются по посещаемости. Итоговая оценка – оценка за экзамен.


Аннотация учебной программы дисциплины

" ^ Совершенные структуры "


Основной целью курса является ознакомление с дополнительными главами дискретной математики и теории кодирования.

Для достижения поставленной цели выделяются задачи курса:
    Дать студентам представление о дистанционно-регулярных графах, теории Рамсея, квазигруппах и эквидистантных кодах.
    Научить строить матрицы Адамара.

Ознакомить студентов с оценками числа совершенных кодов, свойствами конечных проективных геометрий.

Ознакомить с последними достижениями в области построения совершенных кодов, а также с современным состоянием и перспективами развития этого важного математического направления.

Требуемые компетенции для изучения данной дисциплины отвечают ключевым компетенциям бакалавра, указанным в Федеральном государственном стандарте высшего профессионального образования по направлению подготовки 230100 Информатика и вычислительная техника (квалификация (степень) "Бакалавр").


Изучение дисциплины направлено на формирование следующих общекультурных и профессиональных компетенций:

ОК-1, ОК-2, ОК-4

ПК-1, ПК-5, ПК-6

В результате изучения дисциплины студент должен:

Знать(иметь представление):

- о дистанционно-регулярных графах, теории Рамсея, квазигруппах и эквидистантных кодах о числе совершенных кодов, о свойствах конечных проективных геометрий.

Уметь:

- оценить перспективы и возможности методов теории кодирования в конкретной прикладной задаче.

Владеть:
    - методами теории кодирования для анализа конкретных прикладных задач.


Основные разделы курса:

Метрические пространства и дистанционно-регулярные графы.

Частично упорядоченные множества

Совершенные коды

Квазигруппы

Матрицы Адамара

Блок-схемы

Совершенные упаковки и разбиения

Частичное восстановление совершенных структур


Предполагается, что студенты самостоятельно будут работать с литературой. Оценки за контрольные недели выставляются по посещаемости. Итоговая оценка – оценка за экзамен.