тематического и программного обеспечения электронных вычислительных средств Распределение часов
Работа добавлена на сайт samzan.net:
Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Рыбинская государственная авиационная технологическая академия
им. П.А. Соловьева
«УТВЕРЖДАЮ»
Декан факультета РЭИ
Дворсон А.И.
(подпись) (фамилия и.о.)
РАБОЧАЯ ПРОГРАММА
По дисциплине «Теория вычислительных процессов и структур»
для направления 230100 - Информатика и вычислительная техника (бакалавры)
и специальности 230105 – программное обеспечение вычислительной техники и автоматизированных систем
Кафедра Математического и программного обеспечения
электронных вычислительных средств
Распределение часов
|
Форма обучения
|
очная
|
очно-заочная
|
заочная
|
|
Лекции
|
54
|
|
|
|
Практические занятия
|
|
|
|
|
Лабораторные занятия
|
18
|
|
|
|
Индивидуальные занятия
|
|
|
|
|
Самостоятельная работа
в т.ч. курсовая работа
|
28
|
|
|
|
Всего часов
|
100
|
|
|
|
Форма контроля (зач., экз.)
|
экз.
|
|
|
Программу составил______________________ Пинаев В.Н.
(подписи) (фамилии и.о.)
Рабочая программа рассмотрена на ___________________________________________________________________________
(заседании кафедры, методическом семинаре,
___________________________________________________________________________
заседании методической комиссии)
«__30_»_августа 2005г.
Заведующий кафедрой _______________________________________________________
(подпись) (фамилия и.о.)
Согласовано________________________________________________________________
(подпись) (фамилия и.о.)
Настоящая программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования и Учебными планами подготовки специалиста по специальности 230105 программное обеспечение вычислительной техники и автоматизированных систем и направлению 230100 Информатика и вычислительная техника (бакалавры).
ЦЕЛИ И ЗАДАЧИ ИЗУЧЕНИЯ ДИСЦИПЛИНЫ
Целью изучения дисциплины являются семантическая теория программ; методы формальной спецификации и верификации; модели вычислительных процессов; взаимодействие процессов; протоколы и интерфейсы; асинхронные процессы; сети Петри. Основная задача курса заключается в формировании у студентов теоретической базы в области теории асинхронных процессов для дальнейшего изучения специальных дисциплин учебного плана подготовки, связанных с новыми информационными и сетевыми технологиями на основе принципов параллельной и распределённой обработки информации.
В результате изучения дисциплины студенты должны:
- иметь представление:
- о проблемах и направлениях развития теории вычислительных процессов и структур, новых способах их формального описания и верификации;
- об основных тенденциях развития способов задания семантики программ, их формальной спецификации и верификации; о проблемах и направлениях развития системных программных средств;
- знать и уметь использовать:
- формальные модели основных вычислительных процессов и структур, протоколы взаимодействия объектов вычислительных структур, методы анализа структур и процессов;
- основные модели и методы теории формальных языков и формальных грамматик, принципы построения, алгоритмы функционирования трансляторов и компиляторов;
- основные классы схем программ и программных механизмов, используемых в языках программирования, основные процедуры оценки сравнительной мощности программных механизмов при конструировании языков программирования;
- основные классы моделей и методы моделирования, принципы построения моделей процессов, методы и средства формализации, алгоритмизации и реализации модели на ЭВМ;
- иметь опыт:
- применения различных формальных средств реализации моделей асинхронных процессов и систем взаимодействующих вычислительных процессов с целью анализа, расчетов и оптимизации разрабатываемых систем; использования метода системного моделирования при исследовании и проектировании программных систем;
- конструирования языков программирования и разработки и реализации трансляторов.
1. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
Введение. Предмет дисциплины, ее объем, содержание и связь с другими дисциплинами учебного плана. Роль дисциплины в подготовке специалистов в области разработки средств вычислительной техники, цели и задачи дисциплины. Обзор литературы по курсу.
- Модели вычислительных процессов. Элементы теории асинхронных процессов. Концепция процесса. Динамика поведения дискретных систем и асинхронные процессы. Основные определения. Глобальные свойства - параллельность, асинхронность, недетерминизм. Концептуальная модель времени. Физическое и событийное время. Мета-модели, порождающие асинхронные процессы. Определения, способы задания, свойства. Взаимодействие процессов.
- Модельные интерпретации – генерация объектных моделей. Методы структурирования состояний. Автоматные, сетевые и комбинационные объектные модели. Предметная интерпретация моделей.
- Формальные языки и грамматики. Универсальное множество цепочек над конечным алфавитом. Формальный язык как множество цепочек. Операции над языками. Определение формального языка и формальной грамматики. Классификация формальных языков и грамматик по порождающей способности. Теорема о распознаваемости языка, порождаемого неукорачивающей грамматикой.
- Контекстно-свободные грамматики (КС - грамматики). Дерево вывода в КС - грамматике. Однозначность КС - грамматик и языков. Эквивалентные преобразования КС - грамматик: устранение бесполезных символов, исключение из грамматики правил с пустой правой частью и правил с одинаковой правой частью, устранение цепных и леворекурсивных правил. Праволинейные и автоматные грамматики.
- Автоматные модели. Понятие распознающего автомата. Определение, функция доступа и функция преобразования памяти. Типы распознающих автоматов, языки реализуемые распознающими автоматами.
- Конечные автоматы. Определение, способы задания. Детерминированные и недетерминированные автоматы. Автоматные функции. Автоматное отображение. Автоматы Мили, Мура и примитивные автоматы. Автоматы без выходов. Языки, реализуемые конечными автоматами. Автоматные грамматики и конечные автоматы.
- Автоматы с магазинной памятью. (МП - автоматы). Расширенные МП - автоматы. Способы задания МП - автоматов. Детерминированные и недетерминированные МП - автоматы. Языки, допускаемые МП - автоматами. Эквивалентность МП - автоматов и КС - грамматик.
- Определение преобразователя. Конечный преобразователь. Регулярный перевод. Преобразователь с магазинной памятью.
- Основы построения трансляторов. Семантика языка программирования и перевод. Схемы синтаксически управляемого перевода. Транслирующие грамматики. Описание контекстно - зависимых свойств языка. Понятие атрибута. Синтезированные и унаследованные атрибуты. Атрибутные транслирующие грамматики и перевод. Дерево вывода в атрибутной транслирующей грамматике. Вычисление значений атрибутов.
- Лексический анализ. Задачи и структуры данных лексического анализатора. Построение диаграммы лексического анализатора. Включение семантики в диаграмму лексического анализатора. Реализация лексического анализатора.
- Методы синтаксического анализа языков. Нисходящие методы синтаксического анализа. LL(k) - грамматики. Алгоритм разбора для LL(1) - грамматик. Построение управляющих таблиц для LL(1) - грамматик. Метод рекурсивного спуска.
- Восходящие методы синтаксического анализа. LR(k) - грамматики. Алгоритм разбора для LR(к) - грамматик. Построение управляющих таблиц для LR(O) - грамматик.
- Грамматики предшествования. Простое, слабое, операторное предшествование.
- Модели вычислительных процессов. Основы специальной теории сетей - сети Петри. Целочисленное структурирование в абстрактных моделях асинхронных процессов. Сети Петри. Модельная и предметная интерпретация. Определение, способы задания сетей Петри. Структура сетей. Области применения, принципы построения, алгоритмы поведения, способы реализации.
- Маркированные сети. Понятие выполнения сети. Основные соглашения выполнения сети. Пространство состояний, множество и граф достижимости. Динамические свойства сетей. Структурные ограничения и подклассы сетей Петри. Анализ сетей. Понятие мощности моде лирования и разрешимости задач анализа сетей. Сводимость и эквивалентность задач. Проблема достижимости и живости сетей.
- Особенности использования сетей высокого уровня в качестве формальных средств моделирования операционных систем, трансляторов различных типов, баз данных, коммуникационных протоколов информационного обмена.
- Протоколы и интерфейсы. Взаимодействие объектов вычислительных структур. Понятие протокола. Типы взаимодействия объектов: один-один, один - всем, сложные топологии связей. Способы задания. Маркированные и сигнальные графы. Сигнальные сети Петри. Диаграммы изменений. Требования к протоколам. Особенности асинхронных протоколов. Анализ и верификация протоколов. Синтез протоколов.
- Введение в теорию схем программ. Предмет и основные направления исследований в области теоретического программирования. Вычислимость и разрешимость. Интуитивное и точное понятие алгоритма. Вычислимые функции. Машина Тьюринга. Разрешимые и перечислимые множества. Массовые алгоритмические проблемы. Семантическая теория программ; схемы программ, методы формальной спецификации и верификации.
- Конечные автоматы. Проблемы пустоты и эквивалентности односторонних одноголовочных автоматов. Многоленточные и многоголовочные автоматы. Пустота и эквивалентность двуголовочных автоматов.
- Стандартные схемы программ. Понятие стандартной схемы. Стандартные схемы в линейной и графовой формах. Интерпретация схем. Понятие программы. Основные свойства стандартных схем. Понятие свободной интерпретации.
- Перспективные направления исследований формальных средств моделирования вычислительных процессов и структур, систем параллельной и распределенной обработки информации. Исследования формальных методов анализа и синтеза систем взаимодействующих асинхронных процессов. Разработка инструментальных средств моделирования на основе сетей высокого уровня.
- Основные тенденции развития и совершенствования формальных методов описания синтаксиса и семантики языков программи рования, методов проектирования и реализации языковых процессоров. Магистральные направления развития теории программирования. Области применения методов теории программирования.
2. ПЕРЕЧЕНЬ ЛАБОРАТОРНЫХ РАБОТ
- Порождающие языки и грамматики.
- Конечные автоматы.
- МП-автоматы.
- Регулярные выражения.
- Методы нисходящего анализа.
- Методы восходящего анализа.
- Реализация сетей Петри.
- Исследование сетей Петри.
- Протоколы: анализ и верификация.
- Стандартные схемы программ.
3. ПЕРЕЧЕНЬ ТЕМ КУРСОВЫХ РАБОТ
Курсовая работа учебным планом специальности не предусмотрена.
Цель курсовой работы – формирование практических навыков работы с моделями дискретных структур и формальными методами их представления.
- Методы задания синтаксиса языков программирования.
- Методы задания семантики языков программирования.
- Таблично - управляемый лексический анализатор.
- Таблично - управляемый LL(1)-анализатор.
- Реализация компилятора учебного языка.
- Построение LR(1)-таблицы разбора и LR(1) анализатор.
- Задание сетей Петри, их моделирование и анализ.
- Реализация МП автомата.
4. СПИСОК ЛИТЕРАТУРЫ И ПЕРЕЧЕНЬ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
ОСНОВНОЙ
4.1. Котов В.Е. Сети Петри. – М.: Наука, 1984.
4.2. Хоар Ч. Взаимодействующие последовательные процессы. – М.: Мир, 1989.
4.3. Пинаев В.Н. Формальные методы описания языков программирования и построение трансляторов: Конспект лекций / РГАТА. – Рыбинск, 1995.
ДОПОЛНИТЕЛЬНЫЙ
4.4. Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир, 1985.
4.5. Хантер Р. Проектирование и конструирование компиляторов: – М.: Финансы и статистика, 1984.
4.6. Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции. – М.: Мир, 1978.
4.7. Минский М. Вычисления и автоматы / Пер. с англ. – М.: Мир, 1971. –368 с.
4.8. Питерсон Дж. Теория сетей Петри и моделирование систем/ Пер. с англ. – М.: Мир, 1984. –264 с.
4.9. Кнут Д. Искусство программирования для ЭВМ, т.2 / Получисленные алгоритмы / Пер. с англ. – М.: Мир, 1977. –727 с.
5. МЕТОДИЧЕСКИЕ УКАЗАНИЯ СТУДЕНТАМ ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ
Изучение дисциплины должно быть тесно увязано с практическим программированием. Для глубокого погружения в дисциплину необходимо закреплять теоретические знания проработкой задаваемых преподавателем упражнением, выполнением всех лабораторных работ. Обязательным условием является изучение современной литературы.
Для изучения сетей Петри рекомендуется составить демонстрационную программу, показывающую изменение разметки сети в процессе ее функционирования.
Практическое изучение формальных языков и грамматик, методов лексического, синтаксического и семантического разбора рекомендуется на примере какой-либо реализации. Так, например, за основу можно взять доступную в электронном виде реализацию языка программирования Pascal-S. Эта реализация, описанная в литературе, использует специально придуманный Виртом промежуточный язык, получивший название P-код.
6. СПИСОК ЭКЗАМЕНАЦИОННЫХ (ЗАЧЕТНЫХ) ВОПРОСОВ
- Динамика поведения дискретных систем и асинхронные процессы. Основные определения. Глобальные свойства - параллельность, асинхронность, недетерминизм.
- Автоматные, сетевые и комбинационные объектные модели.
- Формальные языки и грамматики.
- Классификация формальных языков и грамматик по порождающей способности.
- Теорема о распознаваемости языка, порождаемого неукорачивающей грамматикой.
- Контекстно-свободные грамматики (КС - грамматики). Дерево вывода в КС - грамматике.
- Эквивалентные преобразования КС - грамматик.
- Автоматные модели. Понятие распознающего автомата. Определение, функция доступа и функция преобразования памяти.
- Детерминированные и недетерминированные автоматы. Автоматные функции. Автоматное отображение.
- Автоматы Мили, Мура.
- Языки, реализуемые конечными автоматами. Автоматные грамматики и конечные автоматы.
- Автоматы с магазинной памятью. (МП - автоматы).
- Языки, допускаемые МП - автоматами. Эквивалентность МП - автоматов и КС - грамматик.
- Семантика языка программирования и перевод.
- Транслирующие грамматики.
- Атрибутные транслирующие грамматики и перевод.
- Дерево вывода в атрибутной транслирующей грамматике.
- Вычисление значений атрибутов.
- Задачи и структуры данных лексического анализатора. Построение диаграммы лексического анализатора.
- Включение семантики в диаграмму лексического анализатора. Реализация лексического анализатора.
- Нисходящие методы синтаксического анализа.
- LL(k) - грамматики. Алгоритм разбора для LL(1) - грамматик
- Восходящие методы синтаксического анализа.
- LR(k) - грамматики. Алгоритм разбора для LR(к) - грамматик.
- Построение управляющих таблиц для LR(1) - грамматик.
- Грамматики предшествования.
- Сети Петри. Определение, способы задания сетей Петри.
- Маркированные сети.
- Пространство состояний, множество и граф достижимости.
- Динамические свойства сетей. Структурные ограничения и подклассы сетей Петри.
- Анализ сетей. Сводимость и эквивалентность задач. Проблема достижимости и живости сетей.
- Протоколы и интерфейсы. Взаимодействие объектов вычислительных структур. Понятие протокола.
- Типы взаимодействия объектов: один-один, один - всем, сложные топологии связей. Способы задания. Маркированные и сигнальные графы.
- Особенности асинхронных протоколов. Анализ и верификация протоколов. Синтез протоколов.
- Стандартные схемы программ. Понятие стандартной схемы. Стандартные схемы в линейной и графовой формах.
- Интерпретация схем. Понятие программы. Основные свойства стандартных схем. Понятие свободной интерпретации.