Параллельные вычисления и алгоритмы

Название дисциплины

Курс обучения, специальность

1-31 03 09 Компьютерная математика и системный анализ

Семестр обучения

Количество кредитов

Ф.И.О. лектора

Доцент Лаврова Ольга Анатольевна, к.ф.-м.н.

Цели изучения дисциплины

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

В результате изучения студент должен уметь

— строить экстремальные задачи на множествах конечномерного пространства;

— осуществлять анализ выпуклых множеств, выпуклых функций, задач выпуклого и линейного программирования;

— решать задачи оптимизации с помощью параллельных вычислений и алгоритмов

Пререквизиты

Компьютерная математика. Математический анализ. Методы программирования и информатика. Методы оптимизации. Численные методы

Содержание дисциплины

1. Теория выпуклых множеств. Теорема об отделимости точки от выпуклого множества. Теорема об отделимости выпуклых множеств. Симплициальный конус. Теорема Каратеодори. Полиэдрический конус. Лемма Фаркаша о разрешимости линейных неравенств

2. Критерий оптимальности для задач выпуклого программирования. Критерий оптимальности для дифференцируемой выпуклой функции на выпуклом множестве. Регулярная задача. Условие Куна-Таккера. Критерий оптимальности для не дифференцируемых функций

3. Классификация задач выпуклого и дискретного программирования.

4. Параллельные алгоритмы. Принципы построения параллельных алгоритмов и усовершенствования известных последовательных алгоритмов для многопоточного выполнения. Оценка эффективности алгоритмов в параллельных и распределённых вычислительных средах. Задачи оптимизации на графах.

Рекомендуемая литература

1. Материалы к курсу «Einfürung in die Mathematische Optimierung», проф. Кайбель, Магдебургский университет, Германия 2013/14: видео-лекции на немецком языке, слайды к лекциям, практические задания.

2. Р. Рокафеллар, Выпуклый анализ: Пер. с англ. – М.: Мир, 1973.

3. A. Ruszcynski, Nonlinear Optimization. Princeton University Press, 2006.

4. A. Gramma, A. Gupta, G. Karypis, V. Kumar Introduction to Parallel Computing, Addison Wesley, 2003.

5. Дорошенко А.Е Математические модели и методы организаций высокопроизводительных вычислений Киев: Наукова думка, 2000.

10.

Методы преподавания

Лекции, лабораторные занятия

11.

Язык обучения

Русский, немецкий

12.

Условия (требования), текущий контроль

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

Зачеты по дисциплине проходят в устной или письменной форме.

13.

Формат текущей аттестации

Зачет

1.	Название дисциплины	Параллельные вычисления и алгоритмы
2.	Курс обучения, специальность	3, 1-31 03 09 Компьютерная математика и системный анализ
3.	Семестр обучения	5
4.	Количество кредитов	3
5.	Ф.И.О. лектора	Доцент Лаврова Ольга Анатольевна, к.ф.-м.н.
6.	Цели изучения дисциплины	Формирование теоретических знаний для решения задач математического программирования и навыков построения параллельных алгоритмов для задач оптимизации. В результате изучения студент должен уметь — строить экстремальные задачи на множествах конечномерного пространства; — осуществлять анализ выпуклых множеств, выпуклых функций, задач выпуклого и линейного программирования; — решать задачи оптимизации с помощью параллельных вычислений и алгоритмов
7.	Пререквизиты	Компьютерная математика. Математический анализ. Методы программирования и информатика. Методы оптимизации. Численные методы
8.	Содержание дисциплины	1. Теория выпуклых множеств. Теорема об отделимости точки от выпуклого множества. Теорема об отделимости выпуклых множеств. Симплициальный конус. Теорема Каратеодори. Полиэдрический конус. Лемма Фаркаша о разрешимости линейных неравенств 2. Критерий оптимальности для задач выпуклого программирования. Критерий оптимальности для дифференцируемой выпуклой функции на выпуклом множестве. Регулярная задача. Условие Куна-Таккера. Критерий оптимальности для не дифференцируемых функций 3. Классификация задач выпуклого и дискретного программирования. 4. Параллельные алгоритмы. Принципы построения параллельных алгоритмов и усовершенствования известных последовательных алгоритмов для многопоточного выполнения. Оценка эффективности алгоритмов в параллельных и распределённых вычислительных средах. Задачи оптимизации на графах.
9.	Рекомендуемая литература	1. Материалы к курсу «Einfürung in die Mathematische Optimierung», проф. Кайбель, Магдебургский университет, Германия 2013/14: видео-лекции на немецком языке, слайды к лекциям, практические задания. 2. Р. Рокафеллар, Выпуклый анализ: Пер. с англ. – М.: Мир, 1973. 3. A. Ruszcynski, Nonlinear Optimization. Princeton University Press, 2006. 4. A. Gramma, A. Gupta, G. Karypis, V. Kumar Introduction to Parallel Computing, Addison Wesley, 2003. 5. Дорошенко А.Е Математические модели и методы организаций высокопроизводительных вычислений Киев: Наукова думка, 2000.
10.	Методы преподавания	Лекции, лабораторные занятия
11.	Язык обучения	Русский, немецкий
12.	Условия (требования), текущий контроль	Текущий контроль работы студента проходит в форме собеседования, контрольной работы в аудитории или над выполнением лабораторных работ в лаборатории и самостоятельно вне аудитории с предоставлением отчета по лабораторным работам с его устной защитой. Зачеты по дисциплине проходят в устной или письменной форме.
13.	Формат текущей аттестации	Зачет