МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
УТВЕРЖДАЮ Декан ФВТ _______________ Л. Р. Фионова «_____» ___________________ 2015 г. |
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Б1.1.26 ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ И СТРУКТУР
Направление 020303 «Математическое обеспечение и администрирование
информационных систем»
Профиль подготовки «Администрирование информационных систем»
Квалификация выпускника бакалавр
Форма обучения очная
Пенза, 2015
1. Цели освоения дисциплины
Целями освоения дисциплины является овладение студентами знаниями о проблемах и направлениях развития теории вычислительных процессов, и навыками использования инструментальных средств моделирования вычислительных процессов, проектирования и создания многопоточных приложений с использованием стандартных средств операционных систем.
2. Место дисциплины в структуре ОПОП бакалавриата
2.1. Дисциплина входит в базовую часть образовательной программы. Изучение данной дисциплины базируется на следующих курсах: «Информатика», «Программирование», «Операционные системы и оболочки», «Структуры и алгоритмы компьютерной обработки данных».
2.2. Минимальные требования к «входным» знаниям, необходимым для успешного усвоении данной дисциплины ‑ удовлетворительное усвоение программ по следующим разделам указанных выше дисциплин:
- «Информатика» в полном объеме;
- «Программирование» ‑ практика программирование на языке высокого уровня;
- «Операционные системы и оболочки» – работа в операционной системе Windows;
- «Структуры и алгоритмы компьютерной обработки данных» – основные понятия алгоритмов и структур данных, подходы к анализу их сложности.
3. Компетенции обучающегося, формируемые в результате освоения дисциплины
Процесс изучения дисциплины направлен на формирование элементов следующих компетенций в соответствии с ФГОС ВПО по данному направлению:
Коды компетенции | Наименование компетенции | Структурные элементы компетенции (в результате освоения дисциплины обучающийся должен знать, уметь, владеть) |
1 | 2 | 3 |
ОПК-10 | способностью использовать знания методов архитектуры, алгоритмов функционирования систем реального времени | знать: модели основных вычислительных процессов и структур, принципы и способы их технической реализации; уметь: моделировать сложные вычислительных процессов с помощью специализированных пакетов прикладных программ; владеть методами проектирования и создания многопоточных приложений с использованием стандартных средств операционных систем. |
ОПК-11 | готовностью использовать навыки выбора, проектирования, реализации, оценки качества и анализа эффективности программного обеспечения для решения задач в различных предметных областях | знать: проблемы и направления развития теории вычислительных процессов, способы их формального описания и верификации; уметь: использовать методы управления вычислительными процессами и их синхронизации; владеть: инструментальными средствами моделирования вычислительных процессов. |
ПК-3 | готовностью к разработке моделирующих алгоритмов и реализации их на базе языков и пакетов прикладных программ моделирования | знать: основные тенденции развития способов задания синтаксиса и семантики программ; уметь: протоколы взаимодействия объектов, методы анализа структур и процессов, методы оптимизации программ; владеть: инструментальными средствами моделирования вычислительных процессов. |
4. Структура и содержание дисциплины
4.1. Структура дисциплины
Общая трудоемкость дисциплины составляет 5 зачётных единиц, 180 часов.
№ п/п | Наименование разделов и тем дисциплины | Семестр | Недели семестра | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) | Формы текущего контроля успеваемости (по неделям семестра) | ||||||||||||||
Аудиторная работа | Самостоятельная работа | ||||||||||||||||||
Всего | Лекция | Практические занятия | Лабораторные занятия | Всего | Подготовка к аудиторным занятиям | Реферат, эссе и др. | Курсовая работа (проект) | Подготовка к экзамену | Собеседование | Коллоквиум | Проверка тестов | Проверка контрольн. работ | Проверка реферата | Проверка эссе и иных творческих работ | курсовая работа (проект) | ||||
1. | Раздел 1. Схемы программ | ||||||||||||||||||
1.1. | Тема 1.1. Вводная лекция | 2 | 3 | ||||||||||||||||
1.2. | Тема 1.2. Теория схем программ | 4 | 16 | ||||||||||||||||
1.3. | Тема 1.3. Семантическая теория программ | 4 | 12 | ||||||||||||||||
2. | Раздел 2. Вычислительные процессы | ||||||||||||||||||
2.1. | Тема 2.1. Параллельные взаимодействующие вычислительные процессы | 6 | 12 | 24 | |||||||||||||||
2.2. | Тема 2.2. Модели вычислительных процессов | 6 | 8 | 18 | |||||||||||||||
2.3. | Тема 2.3 Сети Петри | 6 | 8 | 12 | |||||||||||||||
2.4. | Тема 2.4. Проблема тупиков и методы борьбы с ними | 6 | 8 | 20 | |||||||||||||||
2.5. | Тема 2.5. Заключительная лекция | 2 | 3 | ||||||||||||||||
Подготовка к экзамену | |||||||||||||||||||
Общая трудоемкость, в часах | 36 | 36 | 108 | Промежуточная аттестация | |||||||||||||||
Форма | Семестр | ||||||||||||||||||
Экзамен | 6 | ||||||||||||||||||
4.2. Содержание дисциплины
4.2.1. Содержание лекционного курса
Раздел 1. Схемы программ
Тема 1.1. Вводная лекция
Цели и задачи курса и его место в подготовке специалиста. Роль теория вычислительных процессов и структур в инженерной деятельности.
Тема 1.2. Теория схем программ
Стандартные схемы: базис, операторы, граф. Интерпретация схемы, программа. Исполнение программы: допустимые цепочки, значение программы. Понятия эквивалентности, тотальности, пустоты, свободы. Корректные отношения эквивалентности.
Тема 1.3. Семантическая теория программ
Синтаксис и семантика программ. Оптимизация программ. Кодогенерация и ее связь с оптимизацией. Общее понятие об эквивалентных (или почти эквивалентных) преобразованиях программ. Историческая справка. Анализ программ как средство сбора контекстной информации. Общий план оптимизирующего компилятора. Основные оптимизирующие преобразования: константные вычисления, общие подвыражения, чистка циклов, удаление мертвого кода и т. д.
Раздел 2. Вычислительные процессы
Тема 2.1. Параллельные взаимодействующие вычислительные процессы
Взаимодействие процессов, асинхронные процессы. Синхронизация параллельных процессов. Проблема критических участков. Анализ подходов к решению проблемы. Алгоритм Деккера. Программная реализация взаимоисключений. Семафоры и мониторы: определение, назначение, реализация.
Тема 2.2. Модели вычислительных процессов
Историческая справка. Машина Тьюринга. Конечные автоматы. Модель графа распределения ресурсов. Сети Петри. Вычислительные схемы.
Тема 2.3. Сети Петри
Принципы построения: неформальное и формальное определение и способы представления сетей Петри и описание их подклассов. Алгоритмы поведения: дерево достижимости и анализ структурной ограниченности, сохраняемости, повторяемости сетей Петри; избыточные сети Петри и инварианты сетей Петри, алгоритм Тудика. Способы реализации.
Тема 2.4. Проблема тупиков и методы борьбы с ними
Понятие тупиковой ситуации при выполнении параллельных вычислительных процессов и потоков. Разделение ресурсов системы на два класса – повторно используемые (или системные) ресурсы и потребляемые (или расходуемые) ресурсы. Пример тупика на ресурсах типа CR и SR. Методы борьбы с тупиками. Предотвращение тупиков. Обнаружение тупиков. Выход из тупика.
Тема 2.5. Заключительная лекция
Перспективы развития теории вычислительных процессов и структур.
4.2.2. Перечень и содержание лабораторных занятий.
№ п/п | № темы | Наименование лабораторных работ | Кол. ч |
1 | 2.1 | Параллельные взаимодействующие процессы | 12 |
2 | 2.2 | Синхронизация процессов с помощью семафоров | 8 |
3 | 2.3 | Обмен данными между параллельными процессами | 8 |
4 | 2.4 | Сети Петри (моделирование процессов сетями Петри) | 8 |
5. Образовательные технологии
При реализации различных видов учебной работы используются интерактивные методы и технологии формирования необходимых компетенций: лекции с применением мультимедийных технологий; проведение лабораторных занятий в компьютерном классе. Данные методы сочетаются с внеаудиторной работой с целью формирования и развития профессиональных навыков студентов.
6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.
6.1. План самостоятельной работы студентов
№ нед. | Тема | Вид самостоятельной работы | Задание | Рекомендуемая литература | Количество |
Тема 1.1. Вводная лекция | Подготовка к аудиторным занятиям | Изучение основных понятий | Поисковые системы Internet, рекомендуемая литература | 3 | |
Тема 1.2. Теория схем программ | Подготовка к аудиторным занятиям | Изучение стандартных схем, понятий интерпретации схемы, программы, эквивалентности схем программ | Поисковые системы Internet, рекомендуемая литература | 16 | |
Тема 1.3. Семантическая теория программ | Подготовка к аудиторным занятиям | Изучение синтаксиса и семантики программ, оптимизации программ, общих понятий об эквивалентных преобразованиях программ | Поисковые системы Internet, рекомендуемая литература | 12 | |
Тема 2.1. Параллельные взаимодействующие вычислительные процессы | Подготовка к аудиторным занятиям | Изучение взаимодействие процессов, проблемы критических участков, алгоритма Деккера | Поисковые системы Internet, рекомендуемая литература | 24 | |
Тема 2.2. Модели вычислительных процессов | Подготовка к аудиторным занятиям | Изучение понятий конечных автоматов, модели графа распределения ресурсов | Поисковые системы Internet, рекомендуемая литература | 18 | |
Тема 2.3 Сети Петри | Подготовка к аудиторным занятиям | Изучение принципов построения и алгоритмов поведения сетей Петри | Поисковые системы Internet, рекомендуемая литература | 12 | |
Тема 2.4. Проблема тупиков и методы борьбы с ними | Подготовка к аудиторным занятиям | Изучение понятия тупиковой ситуации при выполнении параллельных вычислительных процессов, методов борьбы с тупиками | Поисковые системы Internet, рекомендуемая литература | 20 | |
Тема 2.5. Заключительная лекция | Подготовка к аудиторным занятиям | Изучение перспектив развития теории вычислительных процессов и структур | Поисковые системы Internet, рекомендуемая литература | 3 |
6.2. Методические указания по организации самостоятельной работы студентов
Планируются следующие виды самостоятельной работы (внеаудиторной):
- подготовка к лабораторным работам,
- оформление отчётов по лабораторным работам,
- работа с конспектом лекций и изучение рекомендованной литературы при подготовке к экзамену.
6.3. Материалы для проведения текущего и промежуточного контроля знаний студентов
Контроль освоения компетенций
№ п\п | Вид контроля | Контролируемые | Компетенции, компоненты которых контролируются |
1 | Текущий: собеседование при защите лаб. заданий. Промежуточный: зачет в форме теста, экзамен. | Раздел 1. Схемы программ | ОПК-10, 11; ПК-3 |
2 | Текущий: собеседование при защите лаб. заданий. Промежуточный: зачет в форме теста, экзамен. | Раздел 2. Вычислительные процессы | ОПК-10, 11; ПК-3 |
Контроль освоения компетенции выполняется:
- для компетенции (ОПК-10) – путем оценки способности студента к использованию знаний методов архитектуры, алгоритмов функционирования систем реального времени;
- для компетенции (ОПК-11) – путем оценки готовности студента к использованию навыков выбора, проектирования, реализации, оценки качества и анализа эффективности программного обеспечения для решения задач в различных предметных областях;
- для компетенции (ПК-3) – путем оценки готовности студента к разработке моделирующих алгоритмов и реализации их на базе языков и пакетов прикладных программ моделирования.
Примерный перечень вопросов и заданий к экзамену
1. Понятие вычислительного процесса. Основные состояния процесса. Создание и уничтожение процессов. Иерархия процессов.
2. Понятие потока. Создание и уничтожение потоков. Пример многопоточного приложения. Управление приоритетами потоков.
3. Организация взаимодействия вычислительных процессов. Синхронизация. Независимые и взаимодействующие процессы.
4. Средства синхронизации вычислительных процессов. Алгоритм Деккера.
5. Организация обмена данными между вычислительными процессами. Почтовые ящики (Mailslots). Преимущества использования «почтовых ящиков».
6. Организация обмена данными между вычислительными процессами. Конвейеры (Pipes).
7. Организация обмена данными между вычислительными процессами. Очереди сообщений. Отличия очереди сообщений от конвейера.
8. Синхронизация потоков одного процесса. Глобальные блокирующие переменные. Недостатки метода глобальных переменных.
9. Синхронизация потоков одного процесса. Использование специальных системных вызовов в Windows (EnterCriticalSection и LeaveCriticalSection).
10. Синхронизация потоков различных процессов. Понятие и принцип работы семафоров. Основные достоинства семафорных операций.
11. Синхронизация потоков различных процессов. Понятие и принцип работы мьютексов.
12. Задача «Читатели - Писатели».
13. Задача «Поставщик - Потребитель».
14. Понятие тупиковой ситуации (Deadlock). Системные и потребляемые ресурсы. Графический способ решения задачи предотвращения тупиков. Пример возникновения тупиковой ситуации.
15. Сети Петри. Основные определения.
16. Условия возникновения тупиковых ситуаций.
17. Основные направления и общие принципы борьбы с тупиками.
18. Понятие вычислительных схем. Граф потока данных и граф управления. Понятие детерминированности вычислительной схемы.
19. Синтаксическая и семантическая сторона программ. Группы стандартных программных примитивов. Понятие схемы программы.
20. Понятие и состав базиса схем. Типы вершин ориентированного графа структурной схемы программ. Основные свойства схем.
21. Информационные связи и сечения программы.
22. Понятие верификации программ.
7. Учебно-методическое и информационное обеспечение дисциплины
7.1. Основная литература:
1. Автоматное управление асинхронными процессами в ЭВМ и дискретных сис-темах / Под ред. . – М.: Наука, Гл. ред. ФМЛ, 1986. – 400 с.
2. Котов, Петри / . – М.: Наука, Гл. ред. ФМЛ, 1984. –160 с.
3. Кузнецов, математика для инженера / , -Вельский /2-е изд. – М.: Энергоатомиздат, 1988. – 480 с.
4. Кук, Д. Компьютерная математика / Д. Кук., Г. Бейз; Пер. с англ. – М.: Наука, Гл. ред. ФМЛ, 1990. – 384 с.
5. Минский, М. Вычисления и автоматы / М. Минский; Пер. с англ. – М.: Мир, 1971. – 368 с.
6. Питерсон, Дж. Теория сетей Петри и моделирование систем / Дж. Питерсон; Пер. с англ. – М.: Мир, 1984. – 264 с.
7. Хоар, Ч. Взаимодействующие последовательные процессы / Ч. Хоар; Пер. с англ. – М.: Мир, 1989. – 264 с.
7.2. Дополнительная литература:
1. Кнут, Д. Искусство программирования для ЭВМ, т.2 / Получисленные алго-ритмы / Д. Кнут; Пер. с англ. – М.: Мир, 1977. – 727 с.
2. Петровский, понятия мультимножеств / . – М.: Едиториал УРСС, 2002. – 80 с.
3. Шиханович, в современную математику / . – М.: Наука, Гл. ред. ФМЛ, 1965. – 378 с.
7.3. Программное обеспечение:
1. Операционная система Windows
2. Пакет моделирования сетей Петри
3. Microsoft Visual C++
8. Материально-техническое обеспечение дисциплины
При проведении лекционных занятий для ряда тем необходимо проекционное оборудование, сопряженное с компьютером.
Лабораторные занятия проводятся в компьютерном классе с применением интегрированной среды разработки приложений Microsoft Visual Studio.
Рабочая программа дисциплины «Теория вычислительных процессов и структур» составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций ПрООП по направлению подготовки 020303 «Математическое обеспечение и администрирование информационных систем».
Программу составил:
Доцент кафедры САПР
Настоящая программа не может быть воспроизведена ни в какой форме без предварительного письменного разрешения кафедры-разработчика программы.
Программа одобрена на заседании кафедры САПР
Протокол № ______от «____» ______________ 2015 года
Зав. кафедрой САПР
Программа одобрена методической комиссией ФВТ
Протокол № ______от «____» ______________ 2015 года
Председатель методической комиссии ФВТ
Сведения о переутверждении программы на очередной учебный год и регистрации изменений
Учебный год | Решение кафедры (№ протокола, дата, подпись зав. кафедрой) | Внесенные изменения | Номера листов (страниц) | ||
заменен- ных | новых | аннулиро-ванных | |||
