МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Саратовский государственный университет имени
Факультет компьютерных наук и информационных технологий
УТВЕРЖДАЮ
___________________________
"__" __________________20__ г.
Рабочая программа дисциплины
Теория вычислительных процессов и структур
Направление подготовки
010500 Математическое обеспечение и администрирование информационных систем
Профиль подготовки
Параллельное программирование
Квалификация (степень) выпускника
Бакалавр
Форма обучения
очная
Саратов,
2011 год
1. Цели освоения дисциплины
Целями освоения дисциплины Теория вычислительных процессов и структур являются:
определение общих форм, закономерностей, инструментальных средств теории вычислительных процессов и структур; развитие навыков использования основных понятий, таких как теория схем программ и модели вычислительных процессов при решении задач, связанных с программированием.
2.Место дисциплины в структуре ООП бакалавриата
Дисциплина «Теория вычислительных процессов и структур» относится к профессиональному циклу. Читается в 7 семестре. Является продолжением дисциплины «Теория формальных языков и трансляций», читаемой в 5 семестре. Для успешного усвоения материала данного курса, необходимы знания и умения полученные в ходе изучения следующих дисциплин: «Дискретная математика», «Структуры и алгоритмы компьютерной обработки данных», «Рекурсивно-логическое программирование», «Теория формальных языков и трансляций».
Для успешного освоения данного курса обучающийся должен
знать:
- основные этапы компьютерного решения функциональных и вычислительных задач;
- базовые структуры и алгоритмы компьютерной обработки данных;
- формальное понятие алгоритма;
- понятие формального языка и формальной грамматики;
- понятие синтаксического и семантического анализа;
- понятие графа, автомата и способов их задания;
уметь:
- разрабатывать алгоритмы решения практических задач;
- на примере модельного языка строить его грамматику и проводить синтаксический и семантический анализ цепочек языка;
- использовать графовые и автоматные модели для анализа;
быть готовым:
- к обучению и самообучению.
3 Компетенции обучающегося, формируемые в результате освоения дисциплины:
способность учиться (ОК 7);
владение основными методами, способами и средствами получения, хранения, переработки информации, имеет навыки работы с компьютером как средством управления информацией (ОК 12);
базовые знания в различных областях (ОК 13);
определение общих форм, закономерностей, инструментальных средств для данной дисциплины (ПК 1);
умение понять поставленную задачу (ПК 2);
умение формулировать результат (ПК 3);
умение грамотно пользоваться языком предметной области (ПК 7);
умение публично представить собственные и известные научные результаты (ПК 18);
В результате освоения дисциплины обучающийся должен:
знать: теорию схем программ, семантическую теорию программ, модели вычислительных процессов (модель графов распределения ресурсов, сети Петри, вычислительные схемы), закономерности и инструментальные средства теории схем программ и моделей вычислительных процессов;
уметь:
понимать, формулировать, представлять и решать конкретные задачи, связанные с программированием, в терминах теории вычислительных процессов и структур, грамотно пользоваться языком теории вычислительных процессов и структур;
владеть навыками:
практического использования методов теории вычислительных процессов и структур при решении задач на программирование.
4. Структура и содержание дисциплины
Общая трудоемкость дисциплины составляет 4 зачетных единицы 144 часа.
№ п/п | Раздел дисциплины | Семестр | Неделя семестра | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) Лек Пр Сам | Формы текущего контроля успеваемости (по неделям семестра) Формы промежуточной аттестации (по семестрам) | |||
1 | Теория схем программ | 7 | 1-4 | 8 | 4 | 14 | Контрольная работа 1 (на 9 неделе) | |
2 | Семантическая теория программ | 7 | 5-9 | 10 | 6 | 14 | Контрольная работа 1 (на 9 неделе) | |
3 | Модели вычислительных процессов | 7 | 10-14 | 10 | 4 | 14 | Контрольная работа 2 (на 18 неделе) | |
4 | Сети Петри | 7 | 15-18 | 8 | 4 | 12 | Контрольная работа 2 (на 18 неделе) | |
Промежуточная аттестация | Экзамен | |||||||
Итого | 36 | 18 | 54 |
| 36 |
I. Теория схем программ
Постановка задачи. Стандартные схемы: базис, графовая форма, линейная форма. Интерпретация схемы, программа. Главные свойства стандартных схем: эквивалентность, тотальность, пустота, свобода. Логико-термальная эквивалентность и ее корректность.
Двоичный двухголовочный автомат (ДДА): определение и свойства. Моделирование ДДА стандартной схемой. Неразрешимость проблем пустоты и эквивалентности стандартных схем. Частичная разрешимость проблемы тотальности. Неразрешимость проблемы свободы.
Логико-термальная (ЛТ) эквивалентность стандартных схем: мотивация, определение. Корректность ЛТ-эквивалентности. Разрешимость ЛТ-эквивалентности. Полная система ЛТ-эквивалентных преобразований.
II. Семантическая теория программ
Логическая спецификация программ.
Анализ корректности последовательных программ.
Аксиоматическая семантика последовательных программ.
Автоматизация верификации программ.
Доказательство корректности программ в проблемных областях.
Верификация недетерминированных и параллельных программ.
Языки спецификаций. Языки, специализированные по средствам (табличные, эквациональные, функциональные, диаграммные и сетевые, модуляризации и структуризаоснованные на крупных операциях). Языки, специализированные по области применения (управление, структуры данных, языки и трансляторы, базы данных и знаний, пакеты прикладных программы). Универсальные и расширяемые языки.
Денотационная, операционная и аксиоматическая семантики. Теория неподвижных точек. Семантика состояний. Абстрактные типы данных и сигнатурные графы.
Формальные методы спецификации программ. VDM (венский метод построения программ). Логико-алгебраические спецификации. Машины абстрактных состояний.
III. Модели вычислительных процессов
Модели вычислительных процессов: модель графов распределения ресурсов, сети Петри, вычислительные схемы.
Взаимодействие процессов, асинхронные процессы. Синхронизация параллельных процессов. Проблема критических участков. Анализ подходов к решению проблемы. Алгорифм Деккера. Программная реализация взаимоисключений: блокирование (spin lock).
Cемафоры и мониторы: определение, назначение, реализация.
Протоколы и интерфейсы: открытость разработки стандартов; уровневые протоколы; драйверы; средства оконного интерфейса.
Функциональное программирование. Лямбда-исчисление и язык Лисп. Нормальные алгорифмы Маркова и язык Рефал. Комбинаторная логика и язык Миранда. Логическое программирование. SLD-резолюция и язык Пролог.
IV. Сети Петри
Принципы построения: неформальное и формальное определение и способы представления сетей Петри и описание их подклассов.
Алгоритмы поведения: дерево достижимости и анализ структурной ограниченности, сохраняемости, повторяемости сетей Петри; избыточные сети Петри и инварианты сетей Петри, алгоритм Тудика.
Способы реализации.
Области применения: моделирование систем на основе сетей Петри и расширения сетей Петри.
Принципы и способы технической реализации моделей процессов и структур.
5. Образовательные технологии
При проведении занятий по данному курсу используются следующие активные и интерактивные формы: организация временных творческих коллективов при работе над учебным проектом, организация дискуссий и обсуждений спорных вопросов, использование метода мозгового штурма, организация конкурса проектов и задач, использование мультимедийных презентаций.
7. Учебно-методическое и информационное обеспечение дисциплины
а) основная литература:
1. , Пентус, теория формальных языков : М.: Интернет-Ун-т Информ. Технологий: БИНОМ. Лаб. знаний, 2006
2. Терехов, программирования :: М.: Интернет-Университет Информ. Технологий: БИНОМ. Лаб. знаний, 2007
б) дополнительная литература:
, , Гринченков основы разработки и реализации языков программирования: М.: КНОРУС, 2010
в) программное обеспечение и Интернет-ресурсы
Интернет-университет информационных технологий
www. intuit.ru
8. Материально-техническое обеспечение дисциплины
Лекционная аудитория с мультимедийным оборудованием с выходом в Интернет
Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и Примерной ООП ВПО по направлению «Математическое обеспечение и администрирование программных систем» и профилю подготовки «Параллельное программирование»
Автор доцент | ___________ |
|
Программа одобрена на заседании кафедры информатики и программирования от «14»февраля 2011 года, протокол
Заведующий кафедрой информатики и программирования, доцент | ___________ |
|
Декан факультета КНиИТ, доцент | ___________ |
|
