Рабочая программа дисциплины теория вычислительных процессов и структур для студентов специальности 35. 15. 00

Вид материала

Рабочая программа

Содержание 3. Объем дисциплины и виды учебной работы. 4. Содержание дисциплины. 4.1. Разделы дисциплины и виды занятий Конечные автоматы и регулярные грамматики Контекстно-свободные грамматики и магазинные автоматы Теория синтаксического анализа и трансляций Трансляторы и методы их разработки Способы описания синтаксиса языков Семантика языка Понятие проекции конструкции исходного языка Способы передачи информации о транслируемой программе между просмотрами транслятора Методы динамического распределения памяти Методы реализации синтаксического анализа Семантический анализ Теория схем программ Оптимизация программ Основные оптимизирующие преобразования Представление программы для кодогенерации Глубинное остовное дерево Свойство интервальной сводимости и его применение Свойство единственности каркаса ... Полное содержание

Подобный материал:

• Рабочая программа дисциплины «Теория автоматического управления» для студентов специальности, 126.16kb.
• Программа дисциплины дс-05 теория вычислительных устройств для студентов специальности, 72.9kb.
• Рабочая программа по Теория случайных процессов (наименование дисциплины) для специальности, 94.12kb.
• Рабочая программа по дисциплине «система государственного управления», 182.78kb.
• Рабочая программа дисциплины архитектура вычислительных систем и компьютерных сетей, 129.55kb.
• Рабочая учебная программа дисциплины "Организация строительных и монтажно-заготовительных, 259.66kb.
• Рабочая программа разработана в соответствии с государственными требованиями к минимуму, 189.13kb.
• Рабочая программа дисциплины основы отраслевых технологий Для студентов специальности, 158.32kb.
• Программа дисциплины опд. Ф. 05. Теория информационных процессов и систем для студентов, 255.07kb.
• Рабочая программа по дисциплине «Теория автоматического управления» для специальности, 649.7kb.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ


УТВЕРЖДАЮ

Декан факультета ВТ

д.т.н., профессор

___________ Шашков В.Д.

«___»____________ 2002 г.


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

ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ И СТРУКТУР

Для студентов специальности 35.15.00

МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ И АДМИНИСТРИРОВАНИЕ

ИНФОРМАЦИОННЫХ СИСТЕМ


Пенза, 2002 г.

Программу разработал М.Н. Селиверстов


Программа одобрена

на заседании каф. «Системы автоматизированного проектирования», протокол № ___от ___________ 2002 г.


Зав каф. «Системы автоматизированного проектирования»

д.т.н, профессор А.М. Бершадский


Согласовано

Председатель НМК ФВТ

д.т.н., профессор П.П. Макарычев


Программа разработана в соответствии со следующими документами:

• государственным образовательным стандартом минобразования РФ по специальности 35.15.00;
  
• рабочим учебным планом ПензГУ по специальности 35.15.00;
  
• примерной программой специальности «Математическое обеспечение и администрирование информационных систем».
  

1. Цель и задачи дисциплины


Целью дисциплины является приобретение обучаемым фундаментальных знаний в области теории вычислительных процессов и структур и выработка практических навыков применения этих знаний. Изучение основных положений теории вычислительных процессов и структур, их применения при создании трансляторов с различных языков программирования и разработке прикладных информационных систем.


2. Требования к уровню освоения содержания дисциплины

В результате изучения дисциплины студенты должны:

-  знать

- методы синтаксического анализа и трансляций;

- принципы построения трансляторов и методы их разработки;

- методы построения схем программ;

- методы оптимизации программ;

- методы верификации программ;

- модели вычислительных процессов;

- методы моделирования систем на основе сетей Петри.

• уметь

- использовать методы теории трансляций при создании трансляторов для языков программирования;

- моделировать сложные вычислительные процессы с помощью специализированных пакетов прикладных программ.


-  иметь опыт

- разработки трансляторов для языков программирования;

- использования инструментальных средств моделирования вычислительных процессов.

- иметь представление

- о теории вычислительных процессов и структур как о базовом предмете, отражающем основные концепции построения и функционирования вычислительных систем.

3. Объем дисциплины и виды учебной работы.

Вид учебной работы	Всего часов	Семестр
Общая трудоемкость дисциплины	149	5
Аудиторные занятия	137	5
Лекции	34	5
Практические занятия (ПЗ)	17	5
Семинары (С)	-	-
Лабораторные работы (ЛР)	34	5
Самостоятельная работа	-	-
Курсовой проект (работа)	52	5
Расчетно-графические работы	-	-
Реферат	-	-
Другие виды самостоятельной работы	-	-
Вид итогового контроля (зачет, экзамен)	9	зачет экзамен

4. Содержание дисциплины.

4.1. Разделы дисциплины и виды занятий

№ п/п	Раздел дисциплины	Объем в часах
		Лекции	Лаб.раб.
1	Теория формальных языков.	2	6
2	Теория синтаксического анализа и трансляций.	2	4
3	Трансляторы и методы их разработки.	8	12
4	Теория схем программ.	4
5	Оптимизация программ.	4	8
6	Семантическая теория программ.	2
7	Модели вычислительных процессов.	4	2
8	Сети Петри.	6	2

4.2. Содержание разделов дисциплины


Теория формальных языков


1. Языки и их представление: алфавиты и языки, представление языков.

2. Грамматики: мотивировка; формальное определение грамматики; язык, порождаемый грамматикой; классификация грамматик по Н.Хомскому; рекурсивность контекстно-зависимых грамматик; деревья вывода в контекстно-свободных грамматиках.

3. Конечные автоматы и регулярные грамматики: детерминированные и недетерминированные конечные автоматы и регулярные множества; эквивалентность конечных автоматов и грамматик типа 3; свойства языков типа 3; регулярные выражения, построение конечного автомата по регулярному выражению; минимизация числа состояний конечного автомата; алгоритмически разрешимые проблемы, касающиеся конечных автоматов.

4. Контекстно-свободные грамматики и магазинные автоматы: упрощение контекстно-свободных грамматик; нормальная форма Хомского; нормальная форма Грейбаха; разрешимость конечности КС-языков; -правила в контекстно-свободных грамматиках; специальные типы контекстно-свободных языков и грамматик. Нетерминированные и детерминированные магазинные автоматы; эквивалентность недерминированных магазинных автоматов и КС-грамматик.

5. Машины Тьюринга: проблема остановки, языки типа 0; универсальная машина Тьюринга; неразрешимость проблемы остановки; класс рекурсивных множеств; машины Тьюринга и грамматики типа 0.

6. Линейно ограниченные автоматы и контекстно-зависимые языки: эквивалентность линейно ограниченных автоматов и контекстно-зависимых грамматик; контекстно-зависимые языки – подкласс рекурсивных множеств.

Теория синтаксического анализа и трансляций

7. Трансляции, их представление и реализация: трансляции и трансляторы; схемы синтаксически-управляемой трансляции; магазинные преобразователи и синтаксически-управляемые трансляции; детерминированная генерация выхода трансляции по левостороннему анализу входа.

8. LL(k)-грамматики: определение и свойства.

9. LL(k)-трансляции: K-предсказывающие алгоритмы анализа; построение 1-предсказывающего алгоритма анализа по LL(1)-грамматике; анализ в LL(k)-грамматиках; тестирование LL(k)-грамматик; вычисление функции (); вычисление функции (A); К-предсказывающий алгоритм трансляции; непростые LL(k)-трансляции и магазинные процессоры; непростые LL(k)-трансляции и магазинные процессоры.

10. LR(k)-трансляции: Синтаксический анализ типа “снизу-вверх”; LR(k)-грамматики; LR(k)-анализатор; свойства LR(k)-грамматик; тестирование LR(k)-грамматик; канонические LR(k)-анализаторы; резюме свойств LR(k)-анализаторов; корректность LR(k)-анализаторов.

Трансляторы и методы их разработки

11. Компиляторы и интерпретаторы. Перевод и генерация кода. Роль перевода в процессе компиляции.

12. Типы компиляторов: прямой компилятор, кросс-транслятор, конвертер. Виртуальная машина. Пример виртуальной машины: Java-машина. Фазы компиляции. Внешний интерфейс (front-end) и внешний интерфейс (back-end).

13. Способы описания синтаксиса языков. Форма Бэкуса-Наура как наиболее распространенный способ описания синтаксиса. Расширенная форма Бэкуса-Наура. Графическое представление синтаксиса. Грамматика ван Вейнгаардена.

14. Семантика языка. Способы определения семантики: интерпретационная и трансляционная семантики, аксиоматическое определение семантики, определение семантики через расширение.

15. Понятие проекции конструкции исходного языка. Представление значений. Представление примитивных значений. Представление структурных значений, проблема выравнивания. Представление многомерных значений. Представление строковых значений. Представление процедурных значений. Представление объектов. Стандарты, определяющие системный интерфейс.

16. Способы передачи информации о транслируемой программе между просмотрами транслятора. Древовидные и табличные структуры данных. Возможные структуры таблиц: таблицы с прямым доступом, таблицы расстановки, функции расстановки. Разработка конкретной структуры таблиц.

17. Методы динамического распределения памяти. Уплотнение памяти. Типы памяти, используемые во время исполнения программы: стек, куча, пузырь. Проблемы образования “мусора”. Алгоритмы сборки мусора.

18. Способы передачи и представления информации о стандартной языковой обстановке.

19. Методы реализации лексического анализа. Детерминированные конечные автоматы. Обработка идентификаторов при лексическом анализе. Таблица идентификаторов, использование хеш-функций.

20. Методы реализации синтаксического анализа. Метод рекурсивного спуска для создания синтаксического анализатора. Метод “перенос/свертка”. Анализ снизу вверх (сдвиг-свертка). LR(1)-элементы. LR(1)-анализатор. Понятие о LALR(1)-анализе. Нейтрализация синтаксических ошибок.

21. Семантический анализ. Атрибутные грамматики. Вычисление атрибутов. L-атрибутные грамматики. Атрибуты типов, переменных и выражений.

22. Обработка описаний и идентификация. Использование таблицы символов.

23. Обработка обозначений типов и контроль типов. Таблица типов. Эквивалентность типов.

24. Оптимизация программы: константные вычисления, вычисление общих подвыражений, удаление недостижимого кода, устранение оператора goto. Оптимизации объектно-ориентированных языков.

25. Синтез и генерация кода. Проблемы распределения регистров и временных переменных.

Теория схем программ

26. Стандартные схемы: базис, операторы, граф.

27. Интерпретация схемы, программа. Исполнение программы: допустимые цепочки, значение программы.

28. Эквивалентность, тотальность, пустота, свобода. Корректные отношения эквивалентности.

29. Свободные интерпретации. Теоремы Лакхэма-Парка-Патерсона.

30. Двоичный двухголовочный автомат (ДДА): определение и свойства. Неразрешимость проблемы пустоты ДДА.

31. Моделирование ДДА стандартной схемой. Неразрешимость проблем пустоты и эквивалентности стандартных схем.

32. Частичная разрешимость проблемы тотальности.

33. Задача Поста и ее частичная разрешимость. Обратная задача Поста и ее неразрешимость.

34. Сведение проблемы свободы схемы к задаче пустоты системы Поста. Неразрешимость проблемы свободы.

35. Логико-термальная (ЛТ) эквивалентность стандартных схем: мотивация, определение. Корректность ЛТ-эквивалентности.

36. Разрешимость ЛТ-эквивалентности.

37. Полная система ЛТ-эквивалентных преобразований.

Оптимизация программ

38. Кодогенерация и ее связь с оптимизацией. Общее понятие об эквивалентных (или почти эквивалентных) преобразованиях программ. Историческая справка. Анализ программ как средство сбора контекстной информации. Общий план оптимизирующего компилятора.

39. Основные оптимизирующие преобразования: константные вычисления, общие подвыражения, чистка циклов, удаление мертвого кода и т.д.

40. Неформальная постановка. Классы входных языков и машинных архитектур. Основные задачи кодогенерации: представление данных, проекция конструкций, соглашения о связях, выбор команд (instruction selection), распределение ресурсов.

41. Представление программы для кодогенерации: таблица символов, абстрактное синтаксическое дерево, ориентированный ациклический граф (DAG), граф управления (CFG).

42. Классические методы кодогенерации: атрибутирование, запрос-ответ.

43. Синтаксически-управляемая генерация кода. Семантически-управляемая генерация кода, атрибутные и аффиксные грамматики.

44. Разбор деревьев и динамическое программирование.

45. Определение управляющего графа программы, подграфа, достижимости, связности.

46. Отношение обязательного предшествования (предоминирования) и обязательной преемственности (постдоминирования). Строгое и непосредственное предшествование. Алгоритмы построения отношения обязательного предшествования.

47. Глубинное остовное дерево. Типы дуг по отношению к глубинному остовному дереву. Каркас, натуральный цикл. Прямая и обратная нумерации, их свойства. Выделение зон.

48. Свойство интервальной сводимости и его применение. Одновходовость, запрещенный подграф, обобщенная сводимость. Аранжировки. Аранжируемость, связь с отношением обязательного предшествования и сводимостью.

49. Свойство единственности каркаса. Доминирование сводимом графе и его каркасе. Разборность. Представления вершин и дуг при разборе. Разборность и сводимость. Тест на сводимость.

50. Классические задачи анализа потоков данных: reaching definitions, constant propagation, live variables. Неформальные решения.

51. Решеточная модель задачи анализа потоков данных. Потоковые функции и их неподвижные точки. Уравнения по всем путям, связь между их решениями и неподвижными точками.

52. Задача распределения регистров и ее особенности для различных машинных архитектур. Загрузка, выгрузка и пересылка. Связь других оптимизирующих преобразований с задачей распределения регистров.

53. Сведение задачи экономии памяти к задаче раскраске графов. Информационные маршруты, области действия и граф несовместимости.

54. Хроматическое число графа, его оценки. Классы графов с известными хроматическими числами.


Семантическая теория программ


55. Логическая спецификация программ.

56. Анализ корректности последовательных программ.

57. Аксиоматическая семантика последовательных программ.

58. Автоматизация верификации программ.

59. Доказательство корректности программ в проблемных областях.

60. Языки спецификаций. Языки, специализированные по средствам (табличные, эквациональные, функциональные, диаграммные и сетевые). Языки, специализированные по области применения (управление, структуры данных, языки и трансляторы, базы данных и знаний, пакеты прикладных программы). Универсальные и расширяемые языки.

62. Денотационная, операционная и аксиоматическая семантики. Теория неподвижных точек. Семантика состояний. Абстрактные типы данных и сигнатурные графы.

63. Формальные методы спецификации программ. VDM (венский метод построения программ). Логико-алгебраические спецификации. Машины абстрактных состояний.


Модели вычислительных процессов


64. Модели вычислительных процессов: Модель графов распределения ресурсов. Сети Петри. Вычислительные схемы.

65. Взаимодействие процессов, асинхронные процессы: Синхронизация параллельных процессов. Проблема критических участков. Анализ подходов к решению проблемы. Алгорифм Деккера. Программная реализация взаимоисключений: блокирование (spin lock). Семафоры и мониторы: определение, назначение, реализация.

66. Протоколы и интерфейсы: открытость разработки стандартов; уровневые протоколы; драйверы; средства оконного интерфейса.


Сети Петри


69. Принципы построения: неформальное и формальное определение
и способы представления сетей Петри и описание их подклассов.

70. Алгоритмы поведения: дерево достижимости и анализ структурной
ограниченности, сохраняемости, повторяемости сетей Петри; избыточные сети Петри и инварианты сетей Петри, алгоритм Тудика.

71. Способы реализации.

72. Области применения: моделирование систем на основе сетей Петри и расширения сетей Петри.

73. Принципы и способы технической реализации моделей процессов и структур.


5. Курсовое проектирование


5.1. Цель курсового проектирования.

Целью курсового проектирования является самостоятельное изучение студентом фундаментальных знаний в области теории вычислительных процессов и структур и выработка практических навыков применения этих знаний.

5.2. Типовое задание на курсовое проектирование.

Разработать транслятор для языка заданного в форме Бэкуса-Наура, состоящий из лексического и синтаксического анализатора, программы формирования постфиксной записи и генерации кода. В качестве инструмента создания использовать среду разработки Microsoft Visual C++ 6.0.

5.3. Этапы выполнения курсового проекта.

1) Анализ грамматики языка, заданного в форме Бэкуса-Наура.

2) Создание лексического анализатора.

3) Приведение грамматики языка к LL(1).

4) Разработка синтаксического анализатора на основе полученной LL(1) грамматики.

5) Разработка программы формирования постфиксной записи.

6) Реализация алгоритма генерации кода для программного эмулятора псевдопроцессора.

5.4. Состав курсового проекта.

1) Задание на курсовое проектирование.

2) пояснительная записка объемом 10-15 страниц.

3) Листинг программы (машинная распечатка)

4) Тестовые примеры и результаты работы транслятора

5) Графическая часть – синтаксический граф реализуемого языка.

6. Лабораторный практикум

№ п/п	№ раздела дисциплины	Наименование лабораторных работ	К-во
1	1	Разработка лексического анализатора	6
2	2, 3	Разработка синтаксического анализатора	8
3	3	Разработка программы генерации постфиксной записи	8
4	5	Разработка программы генерации и оптимизации кода	8
5	7, 8	Моделирование вычислительных процессов на основе сетей Петри	4

7. Учебно-методическое обеспечение дисциплины.

7.1. Рекомендуемая литература

а) основная литература:

1. 
   Агафонов В.Н. Спецификация программ: понятийные средства и их организация. Новосибирск, Наука, 1990.
   
2. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1. Синтаксический анализ. 612 с., т. 2. Компиляция. 487 с. М.: Мир: 1978.
   
3. Ф.Л.Бауэр, Г.Гооз. Информатика. Т. 1,2. М., Мир, 1990.
   
4. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975. 544 с.
   
5. Касьянов В.Н. Оптимизирующие преобразования программ. М., Наука, 1989.
   
6. Касьянов В.Н., Поттосин И. Методы трансляции. М., Наука, 1986.
   
7. Котов В.Е. Сети Петри. -М.: Наука,1984.
   
8. Котов В.Е., Сабельфельд В.Н. Теория схем программ. М., Наука, 1989.
   
9. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. М.: Мир, 1979. 654 с.
   
10. Непомнящий В.А., О.М.Рякин. Прикладные методы верификации программ. Под ред. А.П.Ершова. М.: Радио и связь, 1988. 256 с.
    
11. Пратт Т. Языки программирования: разработка и реализация. М.: Мир, 1979. 574 с.
    
12. А.Филд, П.Харрисон. Функциональное программирование. М., Мир, 1993.
    
13. Ч.Хоар. Взаимодействующие последовательные процессы. М., Мир, 1989.
    

б) дополнительная литература:

1. Братчиков И.Л. Синтаксис языков программирования. М.: Наука, 1975. 232 с.
   
2. Гинзбург С. Математическая теория контекстно-свободных языков. М.: Мир, 1970. 326 с.
   
3. Гладкий А.В. Формальные грамматики и языки. М.: Наука, 1973. 368 с.
   
4. Грис Д. Наука программирования. М.: Мир, 1984. 416 с.
   
5. Гросс М., Лантен А. Теория формальных грамматик. М.: Мир, 1971. 294 с.
   
6. Математическая логика в программировании. Сб. статей. М., Мир, 1991.
   
7. Рейуорд – Смит В. Дж. Теория формальных языков. Вводный курс. М.: Радио и связь, 1988. 129 с.
   
8. Хантер Р. Проектирование и конструирование компиляторов. М.: Финансы и статистика, 1984. 232 с.
   

8. Материально-техническое обеспечение дисциплины.

Лабораторные занятия и курсовое проектирование проводятся в компьютерном классе с применением интегрированной среды разработки приложений Microsoft Visual Studio 6.0.

9. Переутверждение программы на очередной учебный год.

Учебн. год	Учебн. группа	Решение кафедры № протокола	Решение выпускающей кафедры № протокола, дата, подпись зав. кафедрой	Лектор, разработчик программы	№ изменения

Примечание: Тексты изменений в рабочей программе прилагаются

Разработчик программы: Селиверстов М.Н.