|
1. |
Название дисциплины |
Информационные технологии. |
|
2. |
Курс обучения, специальность |
3, 1-31 03 09 Компьютерная математика и системный анализ |
|
3. |
Семестр обучения |
6 |
|
4. |
Количество кредитов |
2 |
|
5. |
Ф.И.О. лектора |
Доцент Лаврова Ольга Анатольевна, к.ф.-м.н. |
|
6. |
Цели изучения дисциплины |
Формирование теоретических знаний и практических навыков решения задач выпуклого и линейного программирования. В результате изучения студент должен уметь — строить экстремальные задачи на выпуклых множествах конечномерного пространства при наличии ограничений в виде равенств и неравенств; — решать задачи линейного и выпуклого программирования с применением полиномиальных методов. |
|
7. |
Пререквизиты |
Математический анализ. Алгебра и теория чисел. Геометрия. Компьютерная математика. Методы оптимизации. Численные методы |
|
8. |
Содержание дисциплины |
1. Геометрия задач линейного программирования. Теорема о декомпозиции полиэдра. Связь внутреннего представления полиэдра с задачей линейного программирования. Характеристический конус. Политоп. Пространство линейности. Грань. Фасета. Минимальная грань. Вершина. Экстремальный луч. Экстремальная точка. Геометрическое описание симплекс-алгоритма. 2. Полиномиальные методы решения задач выпуклого программирования. Метод эллипсоидов. Алгоритм двоичного поиска для последовательности задач о разрешимости. Алгоритмическое представление выпуклого тела. Теоретическая сложность метода эллипсоидов. Метод внутренней точки. Внутреннее скалярное произведение. Конкордантная функция в качестве функции-барьера. Функция-барьер для полиэдрических множеств. Теоретическая сложность метода внутренней точки. |
|
9. |
Рекомендуемая литература |
1. Материалы к курсу «Einfürung in die Mathematische Optimierung», проф. Кайбель, Магдебургский университет, Германия 2013/14: видео-лекции на немецком языке, слайды к лекциям, практические задания. 2. Р. Рокафеллар, Выпуклый анализ: Пер. с англ. – М.: Мир, 1973. 3. A. Ruszcynski, Nonlinear Optimization. Princeton University Press, 2006. 4. A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1986. 5. А. Схрейвер, Теория линейного и целочисленного программирования: в 2-х т.: Пер. с англ. – М.: Мир, 1991. 6. J. Matousek, B. Gärtner, Using and Understanding Linear Programming, Springer, 2006. 7. V. Chvatal, Linear Programming, Freeman, 1983. 8. M. Grötschel, L. Lovàsz, A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer, 1988 |
|
10. |
Методы преподавания |
Лекции, практические занятия |
|
11. |
Язык обучения |
Русский, немецкий |
|
12. |
Условия (требования), текущий контроль |
Контрольные работы. Зачет по дисциплине проходит в устной форме |
|
13. |
Формат текущей аттестации |
Зачет |