Правительство Российской Федерации
Санкт-Петербургский государственный университет
РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ
|
Распараллеливание вычислительных алгоритмов
Concurrency of Numerical Algorithms
Язык(и) обучения___________русский___________________________________
|
Трудоёмкость_2_зачётных единицы
Регистрационный номер рабочей программы________________
Санкт-Петербург
2014
Раздел 1. Характеристики, структура и содержание учебных занятий.
1.1. Цели и результаты учебных занятий.
Cформировать у слушателей общее представление о содержании, задачах и методах современной теории распараллеливание вычислительных алгоритмов как самостоятельной научной и инженерной дисциплины, о диапазоне и разнообразии ее типичных приложений.
Обеспечить формирование принципов системного, аналитического и алгоритмического принципов мышления и соответствующих навыков для работы в области распараллеливание вычислительных алгоритмов, необходимых для решения различных научных и практических задач, включая этапы постановки и решения задачи или проекта, отбора необходимых технических средств, обеспечения информационной безопасности программного обеспечения, а также формирование соответствующих компетенций, в том числе навыков работы в коллективе.
Поставленные цели достигаются путём решения следующих задач курса: изучение общих структур и подходов в предметных областей основных разделов распараллеливание вычислительных алгоритмов, ознакомление с методологиями и структурами данных соответствующих разделов распараллеливания вычислительных алгоритмов на примерах математических моделей и их приложений; развитие навыков самостоятельного решения практических задач.
1.2. Требования к подготовленности обучающегося к освоению содержания учебных занятий (пререквизиты).
Знание основ информатики, программирования и математики в пределах бакалаврской подготовки.
Дисциплина “Распараллеливание вычислительных алгоритмов” является базовым основным курсом в подготовке профессионального математика-программиста и служит основой для изучения других специальных математических дисциплин отделения прикладной математики и информатики.
1.3. Перечень активных и интерактивных форм учебных занятий
В процессе изучения дисциплины “Распараллеливание вычислительных алгоритмов” обучаемые приобретают следующие
знания
| -
сущности и значения информации в развитии общества, основных методов, способов и средств получения, хранения, переработки информации;
-
современных тенденций развития программного обеспечения широкого диапазона типов вычислительных систем, в том числе суперкомпьютерных комплексов;
-
современных методов анализа и синтеза сложных проектов и проектирования программных средств для решения современных задач в различных прикладных областях;
-
современных парадигм распараллеливания вычислительных алгоритмов, языков программирования и базовых алгоритмов для реализации сложных проектов;
-
принципов организации программных комплексов: СУБД, операционных систем, информационных систем; принципов взаимодействия их внутренних механизмов.
|
умения
| -
работать с компьютером как средством управления информацией, в том числе в глобальных компьютерных сетях;
-
соблюдать основные требования информационной безопасности, в том числе защиты государственной тайны;
-
реализовывать решения, направленные на поддержку социально значимых проектов, на повышение электронной грамотности населения, обеспечения общедоступности информационных услуг;
-
использовать в научной и познавательной деятельности,
а также в социальной сфере профессиональные навыки работы с информационными и компьютерными технологиями;
-
использовать нормативные правовые документы в своей деятельности, действовать в условиях гражданского общества;
-
критически переосмысливать свой опыт, адаптироваться к различным ситуациям, проявлять творческий подход, инициативу и настойчивость в достижении целей профессиональной деятельности;
-
делать анализ и грамотную оценку эффективности разрабатываемых алгоритмов.
|
навыки
| -
работы с информацией из различных источников, включая сетевые ресурсы сети Интернет, для решения профессиональных задач;
-
осуществления целенаправленного поиска информации о технологических достижениях в сети Интернет и из других источников;
-
применения в профессиональной деятельности современных языков программирования и языков баз данных, операционных систем, электронных библиотек и пакетов программ, сетевых технологий;
-
взаимодействия с коллегами, работы в коллективе.
|
Знать содержание дисциплины "Распараллеливание вычислительных алгоритмов", в частности, иметь базовые представления об элементах асимптотического анализа, об основной оценочной теореме, о сортирующих сетях, о вычислительных моделях, о распараллеливании матричных операций, о параллелизме при работе со списками, иметь представление о возможностях применения знаний, излагаемых в разделах курса в различных прикладных областях науки и техники.
Уметь формализовывать поставленные задачи и реализовывать сложные программные комплексы как с точки зрения грамотной профессиональной разработки различного рода проектов, так и с точки зрения управления психологическим климатом в процессе работы в коллективе разработчиков для достижения эффективного результата.
1.4 Перечень и объём активных и интерактивных форм учебных занятий:
В качестве основных интерактивных форм (общее количество 45 часов) предполагается чтение лекций.
Также предполагается, что самостоятельную работу (всего 15 часов) в предлагаемом курсе студенты выполняют с обязательным использованием компьютера.
Построение курса подразумевает постоянное акцентирование внимания студентов на профессиональном, этическом и социальном контексте формирования и использования изучаемых средств и методов параллельных алгоритмов.
Раздел 2. Организация, структура и содержание учебных занятий
Трудоёмкость, объёмы учебной работы и наполняемость групп обучающихся
|
Период обучения (модуль)
|
Контактная работа обучающегося с преподавателем
|
Самостоятельная работа
|
Объём активных и интерактивных форм учебных занятий
|
Трудоёмкость
|
лекции
|
семинары
|
консультации
|
практические занятия
|
лабораторные работы
|
контрольные работы
|
коллоквиумы
|
текущий контроль
|
промежуточная аттестация
|
итоговая аттестация
|
под руководством преподавателя
|
в присутствии преподавателя
|
сам. раб. с использованием методических материалов
|
текущий контроль (сам. раб.)
|
промежуточная аттестация (сам. раб.)
|
итоговая аттестация (сам. раб.)
|
ОСНОВНАЯ ТРАЕКТОРИЯ
|
очная форма обучения
|
Семестр 7
|
45
|
|
|
|
|
|
|
|
|
|
|
|
15
|
|
|
|
10
|
5
| 2.1.1. Основной курс.
Формы текущего контроля успеваемости, виды промежуточной и итоговой аттестации
|
Период обучения (модуль)
|
Формы текущего контроля
успеваемости
|
Виды промежуточной аттестации
|
Виды итоговой аттестации
(только для программ итоговой аттестации и дополнительных образовательных программ)
|
ОСНОВНАЯ ТРАЕКТОРИЯ
|
очная форма обучения
|
Семестр 7
|
|
экзамен
|
|
|
2.2. Структура и содержание учебных занятий
Базовый курс Основная траектория Очная форма обучения
Период обучения: Семестр 7
|
|
№ п.п.
|
Наименование темы (раздела, части)
|
Вид учебных занятий
|
Кол-во часов
|
1
|
Тема 1. Элементы асимптотического анализа
|
лекции
|
2
|
по методическим материалам
|
2
|
2
|
Тема 2. Основная оценочная теорема
|
лекции
|
2
|
по методическим материалам
|
2
|
3
|
Тема 3. Сортирующие сети.
|
лекции
|
3
|
по методическим материалам
|
2
|
4
|
Тема 4. Вычислительные модели и сети процессоров.
|
лекции
|
4
|
по методическим материалам
|
1
|
5
|
Тема 5. Распараллеливание матричных операций
|
лекции
|
3
|
по методическим материалам
|
2
|
6
|
Тема 6. Параллелизм при работе со списками
|
лекции
|
1
|
по методическим материалам
|
1
|
Тема 1. Элементы асимптотического анализа.
Пределы и асимптотики. Основные обозначения. Асимптотические отношения. О-символика. Правила работы с асимптотиками. Асимптотические последовательности. Асимптотические разложения. Линейные операции с асимптотическими разложениями. Другие действия с асимптотическими представлениями. Асимптотические ряды. О суммировании асимптотических рядов. Примеры
Тема 2. Основная оценочная теорема.
Индукция и рекурсия. Математическая индукция. Рекурсия и бинарный поиск. Слияние и сортировка слиянием. Основной метод оценки. Основная оценочная теорема.
Тема 3. Сортирующие сети.
Комбинационные схемы. Битонические последовательности. Битонический модуль объединения. Алгоритмы BitonicMerge, MergeSort, QuickSort. Битоническая сортировка. Программы и процедуры. Примеры.
Тема 4. Вычислительные модели и сети процессоров.
Вычислительные модели. Параллельная машина с произвольным доступом к памяти. Стоимость алгоритма. Память распределенная и разделяемая (общая). Сети процессоров: диаметр сети, пропускная способность, возможности средств ввода-вывода. Линейная сеть процессоров. Структура сети процессоров. Гусеничный алгоритм. Кольцевая сеть процессоров. Матричная сеть. Алгоритмы: Mesh Semigrop Algorithm, Mesh Broadcast Algorithm. Древовидно-матричная структура сети. Гиперкуб.
Тема 5. Распараллеливание матричных операций.
Умножение матриц Метод исключения Гаусса. Операции с N и с NxN процессорами Параллельные модели. Ошибки округления. Упражнения.
Тема 6. Параллелизм при работе со списками.
Параллельный префикс. Матричная сеть процессоров. Последовательность с максимальным значением суммы. Задача о нулях и единицах. Интервальная (сегментная) передача данных. Задача о доминирующих точках. Задачи о пересекающихся отрезках. Задача о покрытии. Переход по указателю. Ранжирование списка. Параллельный префикс в связном списке.
Лабораторный практикум
Учебным планом не предусмотрен.
Раздел 3. Обеспечение учебной дисциплины
3.1. Методическое обеспечение
3.1.1. Методические указания по освоению дисциплины
Успешное освоение дисциплины возможно благодаря посещению лекций, участию в обсуждении вопросов, подготовленных к занятию, самостоятельной работе, включающей в себя чтение специальной литературы по разделам темы, подготовка презентаций по тематике курса
3.1.2. Методическое обеспечение самостоятельной работы:
Самостоятельная работа студентов в рамках данной дисциплины является важным компонентом обучения, предусмотренным компетентностно-ориентированным учебным планом и рабочей программой учебной дисциплины.
Настоящей программой предусмотрены формы самостоятельной работы с использованием методических материалов.
Одна из форм самостоятельной работы – это подготовка презентаций и сообщений по тематике курса и источникам, указанным в обязательной, дополнительной литературе и интернет-источниках, указанных с данной программе.
3.1.3. Методика проведения текущего контроля успеваемости и промежуточной аттестации и критерии оценивания:
Общая аттестация складывается из следующих компонентов:
-
Итоги текущего контроля.
-
Результаты экзамена.
3.1.4. Методические материалы для проведения текущего контроля успеваемости и промежуточной аттестации (контрольно-измерительные материалы):
Примерный краткий перечень вопросов к экзамену.
-
Пределы и асимптотики. Основные обозначения.
-
Асимптотические отношения. О-символика.
-
Правила работы с асимптотиками. Асимптотические последовательности.
-
Асимптотические разложения. Линейные операции с асимптотическими разложениями.
-
Действия с асимптотическими представлениями. Асимптотические ряды. О суммировании асимптотических рядов. Примеры
-
Индукция и рекурсия. Математическая индукция.
-
Рекурсия и бинарный поиск. Слияние и сортировка слиянием.
-
Основной метод оценки. Основная оценочная теорема.
-
Комбинационные схемы. Битонические последовательности.
-
Битонический модуль объединения.
-
Алгоритмы BitonicMerge, MergeSort, QuickSort. Битоническая сортировка. Программы и процедуры. Примеры.
-
Вычислительные модели. Параллельная машина с произвольным доступом к памяти.
-
Стоимость алгоритма. Память распределенная и разделяемая (общая).
-
Сети процессоров: диаметр сети, пропускная способность, возможности средств ввода-вывода.
-
Линейная сеть процессоров. Структура сети процессоров.
-
Гусеничный алгоритм. Кольцевая сеть процессоров.
-
Матричная сеть процессоров. Алгоритмы: Mesh Semigrop Algorithm, Mesh Broadcast Algorithm.
-
Древовидно-матричная структура сети. Гиперкуб.
-
Распараллеливание умножения матриц Метод исключения Гаусса.
-
Операции с N и с NxN процессорами Параллельные модели.
-
Ошибки округления. Упражнения.
-
Параллельный префикс. Матричная сеть процессоров.
-
Последовательность с максимальным значением суммы.
-
Задача о нулях и единицах. Интервальная (сегментная) передача данных.
-
Задача о доминирующих точках. Задачи о пересекающихся отрезках.
-
Задача о покрытии. Переход по указателю.
-
Ранжирование списка. Параллельный префикс в связном списке.
3.1.5. Методические материалы для оценки обучающимися содержания и качества учебного процесса.
Для оценки содержания и качества учебного процесса может применяться анкетирование или опрос в соответствии с методикой и графиком, утверждаемым в установленном порядке.
3.2. Кадровое обеспечение
3.2.1. Образование и (или) квалификация штатных преподавателей и иных лиц, допущенных к проведению учебных занятий:
К чтению лекций привлекаются преподаватели, имеющие базовое образование и/или ученую степень соответствующую профилю преподаваемой дисциплины.
3.2.2. Обеспечение учебно-вспомогательным и (или) иным персоналом не требуется.
3.3. Материально-техническое обеспечение
3.3.1. Характеристика аудиторий (помещений, мест) для проведения занятий:
Стандартно оборудованные лекционные аудитории для проведения интерактивных лекций: видеопроектор, экран, др. оборудование.
3.3.2. Характеристика аудиторного оборудования, в том числе неспециализированного компьютерного оборудования и программного обеспечения общего пользования: Нет
3.3.3. Характеристика специализированного оборудования: Рабочие места преподавателя и студентов должны быть оснащены оборудованием не ниже: Pentium IV-800/ОЗУ-256 Мб / Video-32 Мб / Sound card – 16bit /Headphones / HDD 80 Гб / СD-ROM – 48x / Network adapter – 10/100/ Мбс / SVGA – 19”.
3.3.4. Характеристика специализированного программного обеспечения: При использовании электронных документов каждый обучающийся во время занятий и самостоятельной подготовки должен быть обеспечен рабочим местом в компьютерном классе с выходом в Интернет и корпоративную сеть факультета.
3.3.5. Перечень и объёмы требуемых расходных материалов:
Фломастеры цветные, губки, бумага формата А3 (для блокнота-доски), канцелярские товары в объеме, необходимом для организации и проведения занятий по заявкам преподавателей, подаваемым в установленные сроки, доступ преподавателя и студентов к в компьютерные классы.
3.4. Информационное обеспечение
3.4.1. Список обязательной литературы:
-
Р.Миллер, Л.Боксер. Последовательные и параллельные алгоритмы. Общий подход. М.,БИНОМ. 2013. - 406 с.
-
В. Г. Олифер, Н. А. Олифер. Сетевые операционные системы. Изд-во: Питер, 2007. - 539 с.
-
И.Г. Бурова, Ю.К. Демьянович, Т.О. Евдокимова, О.Н. Иванцова, И.Д. Мирошниченко Параллельные алгоритмы. Разработка и реализация. Учебное пособие. М., Национальный открытый университет Интуит-Бином. Лаборатория знаний. 2012, 343с.
3.4.2. Список дополнительной литературы
-
А. Эрдейи. Асимптотические разложения. М. Наука. 1962. 127 с.
-
В.В.Воеводин, Вл.В.Воеводин. Параллельные вычисления. Спб. 202. 608 с.
-
Г.Р.Эндрюс. Основы многопоточного, параллельного и распределенного программирования. М. 2003. 512 с.
3.4.3. Перечень иных информационных источников
-
http://parallel.ru Designing and building parallel programs
-
В. В. Корнеев, А. Ф. Гареев, С. В. Васютин, В. В. Райх. Базы данных. Интеллектуальная обработка информации. М.: Нолидж, 2003. – 400 с.
-
Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайню Алгоритмы. Построение и анализ. Изд. 2-е. Introduction To Algorithms.Изд-во: Вильямс, 2007 г., 1296 с.
-
Э. Дейкстра "Дисциплина программирования", М., Мир, 1978. 275 с.
Разработчик рабочей программы: д.ф.м.н., профессор мат-мех факультета СПбГУ Демьянович Юрий Казимирович, Yuri.Demjanovich@gmail.com, тел. 428-41-97.
Достарыңызбен бөлісу: |