Рабочая программа по курсу “Формальные языки и алгоритмы.” ( наименование дисциплины по учебному плану )




Скачать 129.54 Kb.
НазваниеРабочая программа по курсу “Формальные языки и алгоритмы.” ( наименование дисциплины по учебному плану )
Дата08.03.2013
Размер129.54 Kb.
ТипРабочая программа
Нижегородский государственный технический университет

Факультет_____ ИРИТ

( наименование факультета )


УТВЕРЖДАЮ:

Первый проректор

Кошелев О.С.

« » ________2009 г.


Р А Б О Ч А Я П Р О Г Р А М М А


по курсу “Формальные языки и алгоритмы.”

( наименование дисциплины по учебному плану )

Направление подготовки 510200 Прикладная математика и информатика


( шифр и наименование )

Направление специальности 010000 Естественнонаучные специальности

( шифр и наименование )

Специальность 010200 Прикладная математика и информатика

( шифр и наименование )

Кафедра “Прикладная математика “


( наименование )

Курс 2


Семестр 3


Общая трудоемкость дисциплины 153 ( час )

Аудиторные занятия 72 ( час )

Лекции 36 ( час ) Самостоятельная


работа 81 ( час )

Лабораторные

занятия 36 ( час )


Практические Экзамен 3 ( семестр )

занятия ( час )


Курсовой проект Зачет ( семестр )

( работа ) . ( час )


Расчетно-графические

Работы ( час )


Рабочая программа утверждена на заседании кафедры


« » ___________ 2009_ г.


Зав. кафедрой ________________ ___ Митяков С Н __

( подпись ) ( Ф.И.О.)

Председатель координационного научно-методического совета

по направлению подготовки 510200 Прикладная математика и информатика

( шифр, наименование )

Митяков С Н

( подпись ) ( Ф.И.О. )

« » 2009__ г.


Председатель НМС по блоку естественно-научных дисциплин

( шифр, наименование специальности )

Ершов Н.Ф.

( подпись ) ( Ф.И.О. )

« » 2009__ г.


ПОЯСНИТЕЛЬНАЯ ЗАПИСКА


Рабочая программа составлена на основании Государственного стандарта высшего профессионального образования по направлению подготовки бакалавра 510200 – Прикладная математика и информатика и направлению специальности дипломированного специалиста 010200 - Прикладная математика и информатика.

В курсе «Формальные языки и алгоритмы» рассматриваются основные аспекты теории формальных языков, существенные с точки зрения синтаксического анализа и перевода. Особое внимание уделяется вопросам построения конечных автоматов и изучению контекстно-свободных грамматик, как основной теоретической базе, необходимой для построения компиляторов. Направленность курса связана с последующем изучением теории перевода и компиляции, а так же практической реализации простейших моделей компиляторов..

В курсе существенно используются знания из курсов: Дискретная математика, Теория множеств, Методы программирования.


ОПИСАНИЕ СОДЕРЖАНИЯ ОСНОВНЫХ ТЕМ КУРСА


  1. Постановка проблемы.

Множественность языков общения с вычислительной машиной. Уровни их сложности. Понятие языкового процессора как программы для обработки входных языков. Трансляторы и интерпретаторы. Понятие перевода. Теория формальных языков как основа изучения процесса трансляции.

  1. Понятие формального языка. Способы его определения.

Алфавит как множество символов. Цепочки в алфавите. Операции над цепочками (итерация, обращение, конкатенация). Суффикс и префикс цепочки, длина цепочки. Определение языка как множества цепочек в алфавите. Операции над языками. Необходимость описания в общем случае бесконечного языка конечными средствами. Два основных механизма определения языков: механизм порождения (генераторы) и механизм распознавания.

  1. Генераторы и распознаватели.

Грамматики как наиболее важный класс генераторов языков. Понятие грамматики как математической системы, порождающей синтаксически правильные цепочки. Грамматики с ограничениями на правила. Иерархия Хомского. Понятие языка, порождаемого заданной грамматикой. Распознаватель как алгоритм, распознающий синтаксически правильные цепочки. Общая структура распознавателей, основные классы распознавателей. Понятие языка, определяемого распознавателем. Взаимное соответствие между грамматиками из иерархии Хомского и классами распознавателей.

  1. Конечные автоматы-распознаватели.

Конечный распознаватель как основа теории автоматов. Общая схема конечного распознавателя, назначение его составляющих, формальное определение. Принцип работы, понятие такта и конфигурации. Полностью и неполностью определенные автоматы, способы их доопределения. Способы представления конечных распознавателей. Допустимые и недопустимые цепочки. Понятие конечно-автоматного языка. Концевые маркеры и проблема выхода из распознавания. Эвристический метод построения конечного распознавателя.

  1. Эквивалентность состояний.

Мотивировка. Различимые и неразличимые состояния. Различающая цепочка. Теорема об эквивалентности двух состояний (критерии эквивалентности). Метод поиска различающей цепочки как метод определения неэквивалентности двух состояний. Недостатки метода. Недостижимые состояния. Алгоритм поиска и исключения недостижимых состояний. Построение эквивалентного минимального автомата. Минимизация автомата методом последовательного построения классов эквивалентности.


  1. Эквивалентность распознавателей.

Эквивалентность автоматов как следствие понятия эквивалентности состояний. Теорема об эквивалентности двух автоматов. Поверка эквивалентности путем построения различающей цепочки. Другой подход к проблеме эквивалентности автоматов. Понятие прямого произведения двух автоматов. Теорема Мура об эквивалентности.


  1. Недетерминированные конечные автоматы – распознаватели.

Недетерминированный автомат как формализм для определения множества цепочек. Функция переходов недетерминированного распознавателя. Способы представления. Допустимые цепочки символов. Интерпретация процесса распознавания недетерминированным автоматом. Эвристический метод построения недетерминированного автомата. Алгоритм построения детерминированного автомата, эквивалентного (относительно языка) недетерминированному.



  1. Конечные автоматы и регулярные множества.

Регулярные множества и регулярные выражения. Регулярные языки. Теорема Стефена Клини об эквивалентности регулярных языков и конечно-автоматных языков. Построение автомата по заданному регулярному выражению. Нахождение регулярного выражения, определяемого заданным конечным автоматом. Лемма о разрастании регулярных множеств как критерий “регулярности языка”. Некоторые разрешимые проблемы, связанные с регулярными языками: проблема принадлежности цепочки языку, проблема пустоты данного языка, проблема эквивалентности языков. Соответствующие алгоритмы.


  1. Праволинейные грамматики.

Определение праволинейной грамматики. Языки, генерируемые праволинейными грамматиками. Свойства праволинейных языков. Теорема об эквивалентности регулярных множеств и праволинейных языков. Вывод об эквивалентности языков, определяемых праволинейными грамматиками, конечными автоматами и регулярными выражениями.


  1. Распознаватели с магазинной памятью (стековые автоматы)

Общая схема, формальное определение, понятие такта и конфигурации, способ представления. Алгоритм работы: операции над магазином, операции над состоянием, операции над входом. Понятие -такта. Процесс распознавания цепочек. Язык, определяемый стековым автоматом как множество допустимых цепочек. Пример распознавания множества стековым автоматом. Расширенный стековый распознаватель, расширенные операции над магазином. Детерминированные стековые распознаватели. Проблема зацикливающих конфигураций и способы ее решения.


  1. Контекстно-свободные грамматики.

Понятие вывода в грамматике. Деревья выводов (деревья разборов). Левовыводимые и правовыводимые цепочки. Преобразования КС-грамматик: исключение бесполезных и недостижимых нетерминалов. Проблема неоднозначности КС-грамматик, теорема о ее неразрешимости в общем случае. Частные приемы построения эквивалентной однозначной грамматики. Грамматика арифметических выражений. Соотношение КС-грамматик и праволинейных грамматик. Лемма Огдена о разрастании для КС-языков.


  1. Эквивалентность стековых распознавателей и контекстно-свободных грамматик.

Построение левостороннего (нисходящего) стекового распознавателя по заданной КС-грамматике. Лемма об эквивалентности определяемого ими языка. Построение правостороннего (восходящего) расширенного стекового распознавателя по заданной КС-грамматике. Эквивалентность определяемого ими языка. Решение обратной задачи: построение КС-грамматики по заданному стековому распознавателю. Вывод о том, что стековые распознаватели и КС-грамматики определяют один и тот же язык.


  1. Другие классы грамматик и соответствующих им распознавателей (обзор).

Контекстно-зависимые грамматики и линейно ограниченные автоматы. Грамматики общего вида и машина Тьюринга.

РАСПРЕДЕЛЕНИЕ ЧАСОВ ЛЕКЦИОННЫХ


ЗАНЯТИЙ ПО ТЕМАМ


Наименование темы

Лекции

  1. Введение. Способы определения формальных языков

4

  1. Конечные автоматы-распознаватели.

8

  1. Регулярные множества и конечные распознаватели.

4

  1. Праволинейные грамматики.

4

  1. Стековые распознаватели.

6

  1. Контекстно-свободные грамматики.

6

  1. Другие классы распознавателей и грамматик (обзор).

2

Всего часов:

36



НАИМЕНОВАНИЕ ТЕМ ЛАБОРАТОРНЫХ ЗАНЯТИЙ


Проводятся бригадами 2-4 человека.

Допуск занятий осуществляется устным опросом.

Отчеты - по окончании лабораторных работ каждой рабочей группой.

Зачеты лабораторной работы опросом рабочей группы.




Тема (раздел) дисциплины

Тема (наименование) лабораторной работы

Лаб. работа

1

2

Конечные автоматы-распознаватели

6

2

4

Праволинейные грамматики

10

3

5

Стековые распознаватели

14

4

6

Контекстно-свободные грамматики

6







Всего:

36

ОРГАНИЗАЦИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ




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


Виды самостоятельной работы

Объем самостоятельной работы по рабочему плану (час)

1. Проработка лекционного материала (а так же дополнительных тем, указанных лектором)

25

2. Подготовка к практическим занятиям.

-

3. Подготовка к лабораторным занятиям.

25

4. Подготовка реферата по теме.

-

5. Выполнение курсовой работы (проекта)

-

6. Выполнение расчетно-графической работы.

-

7. Подготовка к текущему контролю (тестированию и т.д.)

10

8. Подготовка к промежуточному контролю.

10

9. Подготовка к экзамену (зачету).

11

Итого

81



Контрольные вопросы

        1. Трансляторы и интерпретаторы.

        2. Понятие перевода.

        3. Алфавит. Цепочки в алфавите

  1. Понятие языка.

  2. Операции над языками.

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

  4. Механизм генерации и распознавания языка.

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

  6. Понятие грамматики.

  7. Понятие конечного распознователя.

  8. Схема конечного автомата-распознователя.

  9. Понятие такта и конфигурации.

  10. Детерминированные и недетерменированые конечные автоматы.

  11. Допустимые и недопустимые цепочки.

  12. Понятие конечно-автоматного языка. Концевые маркеры.

  13. Автоматы с -тактами.

  14. Эквивалентные состояния.

  15. Различающая цепочка, методы её поиска.

  16. Эквивалентные автоматы.

  17. Теорема Мура об эквивалентности.

  18. Достижимые и недостижимые состояния.

  19. Понятие минимального автомата.

  20. Методы построения минимального автомата.

  21. Регулярные множества и регулярные выражения.

  22. Теорема Клини.

  23. Лемма о разрастании регулярных множеств.

  24. Распознаватели с магазинной памятью.

  25. Регулярные множества, выражения, языки.

  26. Понятие вывода в грамматике. Деревья выводов (деревья разборов).

30.Контекстно-зависимые грамматики и линейно ограниченные автоматы.

ЛИТЕРАТУРА




Автор, наименование

Изд-во

Год издания

Кол-во в библиотеке НГТУ

А. Основная

1

Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции, т.1

М.: Мир

1978

3

2

Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов

М.:Мир

1979

8

3

Манфред Брой. Информатика

М.: Наука

1996

10

Б. Дополнительная

4

Яблонский С.В. Введение в дискретную математику

М.: Наука

1979

15

5

Кауфман В.Ш. Языки программирования. Концепции и принципы.

М.: Радио и связь

1970

15




Сайт для студентов www.kovriguineda.ucoz.ru


Н.Новгород

2009






Составил: Ковригин Д.А.




Похожие:

Рабочая программа по курсу “Формальные языки и алгоритмы.” ( наименование дисциплины по учебному плану ) iconРабочая программа по курсу “Дискретная математика” ( наименование дисциплины по учебному плану )
Целью данного курса является изучение фундаментальных свойств дискретных математических объектов, к которым относятся множества,...
Рабочая программа по курсу “Формальные языки и алгоритмы.” ( наименование дисциплины по учебному плану ) iconРабочая программа демография региона наименование дисциплины по учебному плану Код дисциплины по учебному плану дв. 1 Для студентов направления 080200. 62 «Менеджмент»
Цель курса – сформировать у студентов устойчивое целостное представление о закономерностях протекания демографических процессов в...
Рабочая программа по курсу “Формальные языки и алгоритмы.” ( наименование дисциплины по учебному плану ) iconРабочая программа Культура региона наименование дисциплины по учебному плану Код дисциплины по учебному плану в. 1 Для студентов направления 080200. 62 «Менеджмент»
Цель курса – сформировать у студентов устойчивое целостное представление о исторических и социально-культурных закономерностях развития...
Рабочая программа по курсу “Формальные языки и алгоритмы.” ( наименование дисциплины по учебному плану ) iconРабочая программа Социология наименование дисциплины по учебному плану Код дисциплины по учебному плану б. 5 Для студентов направления 080200. 62 «Менеджмент»
Цель – дать теоретическое и методологическое обоснование социологии, выявить основные особенности данной области социогуманитарного...
Рабочая программа по курсу “Формальные языки и алгоритмы.” ( наименование дисциплины по учебному плану ) iconРабочая программа математика наименование дисциплины по учебному плану Код дисциплины по учебному плану б. 1 Для студентов направления 080200 «Менеджмент»
В результате усвоения курса у студента должно сложиться целостное представление об основных этапах становления современной математики...
Рабочая программа по курсу “Формальные языки и алгоритмы.” ( наименование дисциплины по учебному плану ) iconРабочая программа учебной дисциплины
«Защита в чрезвычайных ситуациях» ( шифр и наименование специальности ( направления) по учебному плану )
Рабочая программа по курсу “Формальные языки и алгоритмы.” ( наименование дисциплины по учебному плану ) iconРабочая программа по курсу “Теория компиляции.” ( наименование дисциплины по учебному плану )
Рабочая программа составлена на основании Государственного стандарта высшего профессионального образования по направлению подготовки...
Рабочая программа по курсу “Формальные языки и алгоритмы.” ( наименование дисциплины по учебному плану ) iconРабочая программа дисциплины теория автоматов и формальных языков направление подготовки 010300. 62 «Фундаментальная информатика и информационные технологии»
Уметь: строить формальные грамматики, деревья вывода, распознающие автоматы; анализировать формальные языки
Рабочая программа по курсу “Формальные языки и алгоритмы.” ( наименование дисциплины по учебному плану ) iconРабочая программа дисциплины демография (указывается шифр и наименование дисциплины по учебному плану) Направление (специальность) подготовки 080400 «Управление персоналом»
России; об основных понятиях и закономерностях развития демографических процессов; о методах анализа и прогнозирования естественного...
Рабочая программа по курсу “Формальные языки и алгоритмы.” ( наименование дисциплины по учебному плану ) iconРабочая программа педагога бабановой Светланы Анатольевны, по учебному курсу «Физика»
Рабочая программа к учебному курсу «Физика» 9 класс А. В. Перышкин, Е. М. Гутник разработана в соответствии с
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница