Рабочая программа учебной дисциплины распараллеливание вычислительных алгоритмов Concurrency of Numerical Algorithms



Дата02.05.2016
өлшемі147.19 Kb.
түріРабочая программа
Правительство Российской Федерации

Санкт-Петербургский государственный университет


РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ

Распараллеливание вычислительных алгоритмов

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. Методические материалы для проведения текущего контроля успеваемости и промежуточной аттестации (контрольно-измерительные материалы):

Примерный краткий перечень вопросов к экзамену.

  1. Пределы и асимптотики. Основные обозначения.

  2. Асимптотические отношения. О-символика.

  3. Правила работы с асимптотиками. Асимптотические последовательности.

  4. Асимптотические разложения. Линейные операции с асимптотическими разложениями.

  5. Действия с асимптотическими представлениями. Асимптотические ряды. О суммировании асимптотических рядов. Примеры

  6. Индукция и рекурсия. Математическая индукция.

  7. Рекурсия и бинарный поиск. Слияние и сортировка слиянием.

  8. Основной метод оценки. Основная оценочная теорема.

  9. Комбинационные схемы. Битонические последовательности.

  10. Битонический модуль объединения.

  11. Алгоритмы BitonicMerge, MergeSort, QuickSort. Битоническая сортировка. Программы и процедуры. Примеры.

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

  13. Стоимость алгоритма. Память распределенная и разделяемая (общая).

  14. Сети процессоров: диаметр сети, пропускная способность, возможности средств ввода-вывода.

  15. Линейная сеть процессоров. Структура сети процессоров.

  16. Гусеничный алгоритм. Кольцевая сеть процессоров.

  17. Матричная сеть процессоров. Алгоритмы: Mesh Semigrop Algorithm, Mesh Broadcast Algorithm.

  18. Древовидно-матричная структура сети. Гиперкуб.

  19. Распараллеливание умножения матриц Метод исключения Гаусса.

  20. Операции с N и с NxN процессорами Параллельные модели.

  21. Ошибки округления. Упражнения.

  22. Параллельный префикс. Матричная сеть процессоров.

  23. Последовательность с максимальным значением суммы.

  24. Задача о нулях и единицах. Интервальная (сегментная) передача данных.

  25. Задача о доминирующих точках. Задачи о пересекающихся отрезках.

  26. Задача о покрытии. Переход по указателю.

  27. Ранжирование списка. Параллельный префикс в связном списке.

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. Список обязательной литературы:

  1. Р.Миллер, Л.Боксер. Последовательные и параллельные алгоритмы. Общий подход. М.,БИНОМ. 2013. - 406 с.

  2. В. Г. Олифер, Н. А. Олифер. Сетевые операционные системы. Изд-во: Питер, 2007. - 539 с. 

  3. И.Г. Бурова, Ю.К. Демьянович, Т.О. Евдокимова, О.Н. Иванцова, И.Д. Мирошниченко Параллельные алгоритмы. Разработка и реализация. Учебное пособие. М., Национальный открытый университет Интуит-Бином. Лаборатория знаний. 2012, 343с.


3.4.2. Список дополнительной литературы

  1. А. Эрдейи. Асимптотические разложения. М. Наука. 1962. 127 с.

  2. В.В.Воеводин, Вл.В.Воеводин. Параллельные вычисления. Спб. 202. 608 с.

  3. Г.Р.Эндрюс. Основы многопоточного, параллельного и распределенного программирования. М. 2003. 512 с.


3.4.3. Перечень иных информационных источников

  1. http://parallel.ru Designing and building parallel programs

  2. В. В. Корнеев, А. Ф. Гареев, С. В. Васютин, В. В. Райх. Базы данных. Интеллектуальная обработка информации. М.: Нолидж, 2003. – 400 с.

  3. Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайню Алгоритмы. Построение и анализ. Изд. 2-е. Introduction To Algorithms.Изд-во: Вильямс, 2007 г., 1296 с.

  4. Э. Дейкстра "Дисциплина программирования", М., Мир, 1978. 275 с.


Разработчик рабочей программы: д.ф.м.н., профессор мат-мех факультета СПбГУ Демьянович Юрий Казимирович, Yuri.Demjanovich@gmail.com, тел. 428-41-97.

Достарыңызбен бөлісу:


©netref.ru 2019
әкімшілігінің қараңыз

    Басты бет