Учебно-методический комплекс по дисциплине "Теория языков и автоматов" для специальностей 050602 "Информатика"

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ

КАЗАХСТАН

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

УНИВЕРСИТЕТ им. С. АМАНЖОЛОВА

Институт МАТЕМАТИКИ, ФИЗИКИ И ТЕХНИКИ
кафедра Математического моделирования и компьютерных технологий

УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС
по дисциплине "Теория языков и автоматов"

для специальностей 050602 "Информатика"

Усть-Каменогорск, 2005

Составитель Кадырова А.С., УМК обсужден на заседании

доцент кафедры МмиКТ кафедры МмиКТ;

Протокол №_

от “2”февраля_2005г.

УМК одобрен на заседании

метод. совета Института Ма-

тематики, физики и техники

Протокол № __

от “_3”_февраля 2005г.

УМК рекомендован к изданию

методическим отделом

от "___" _______2005г.

Учебно-методический комплекс предназначается для студентов специальности 050602 "Информатика", изучающих теоретические основы программирования в рамках дисциплины “Теория языков и автоматов ”, преподавателей, обеспечивающих учебный процесс по данной дисциплине. В нем представлены тематический план, график выдачи и сроки сдачи СРС, перечень тем рефератов, лабораторных работ, список литературы. Теоретический материал по каждой теме сопровождается заданиями для самостоятельной работы.

Учебно-методический комплекс по теории языков и автоматов для студентов по специальности 050602 "Информатика" / Сост. Кадырова А.С. – Усть-Каменогорск: Изд-во ВКГУ, 2005. – 34 с.

Восточно-Казахстанский государственный университет им. С. Аманжолова, 2005.

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

(Syllabus)

Общие сведения:
1. Название дисциплины __Теория языков и автоматов __
2. Кафедра_Математического моделирования и компьютерных технологий
3. Ф.И.О. преподавателя _Кадырова Айнагуль Сабеновна__
4. Контактная информация: тел., электронный адрес, время пребывания на кафедре 22-21-48 (р), mm_kt@mail.ru, понедельник, вторник , четверг, пятница 11.30.- 17.20.
5. Место проведения __ВКГУ, 8 корпус, 10, 26 ауд.__
6. Количество кредитов___3____
7. Выписка из учебного плана

Табл. 1

Курс	Семестр	Кредиты	Лекции	Семинары (лабраб)	СРСП	СРС	Всего	Форма контроля
1	1,2	3	30	15	45	45	135	Экзамен

Пререквизиты курса: для усвоения содержания курса необходимы знания из школьного курса основ информатики и ВТ, алгебры, геометрии. Студент иметь навыки работы на персональном компьютере.
Постреквезиты: знания и навыки по теории языков и автоматов могут быть использованы студентом при изучении разделов других дисциплин: алгоритмизация и языки программирования, языки программирования и методы трансляции, а так же при курсовом и дипломном проектировании.

Краткое описание курса:

2.1 Цель курса: предоставить знания по основам теории языков и формальных грамматик, теории автоматов, методам разработки трансляторов.

Задачи курса применительно специальности: после обучения студенты специальности 050602 "Информатика" должны будут:

знать характеристики основных типов языков, используемых в практике информационного поиска, управления, логики, анализа их особенностей и отличительных черт;
знать методы построения информационных языков по их грамматике;
уметь различать языки общего и специального назначения;
уметь различать автоматы;

для формирования теоретических основ программирования на любых трансляторах.

2.3 Содержание курса: подробно анализируется сходство и различия естественных и информационных языков и намечены пути построения информационных языков различных типов и их грамматик. Рассмотрены следующие вопросы:

основные понятия теории алгоритмов и теории формальных грамматик,
рекурсивные функции, примитивной рекурсии и минимизации,
описание машин Тьюринга, способы их представления, операции над машинами Тьюринга,
алгоритмически неразрешимые проблемы теории алгоритмов основные понятия формальных грамматик и языков,
классификация грамматик, стратегии грамматического разбора, а также эквивалентные преобразования КС-грамматик,
различные типы автоматов (конечные автоматы, автоматы с магазинной памятью, автоматы Мили и Мура) и их связь с грамматиками и языками;
различать трансляторы, имея навыки работы в них.

График выполнения и сдачи заданий по дисциплине содержит:

№	Виды работ	Цель и содержание задания	Рекомендуемая литература	Продолжительность выполнения	Баллы (согласно рейтинг-шкале)	Форма контроля	Сроки сдачи
1	2	3	4	5	6	7	8
1	Письменная работа (Тема №1, 2, 3, 4, 5, 6)	Умение творческий перерабатывать информацию при усвоении направлений теории языков, умение составлять словарь.	11, 19, 24, 16, 26, 29-31, 42	2-4 недели	2	Проверка	5 н., 10 н., 1, 2 трим
2	Реферат по темам 1-3 и по темам 7-8	Изучение научной и учебной литературы Развитие аналитических умений.	1-14, 29-31, 39, 42, 45	4 недели	2	Защита реферата	5 н., 1, 2 трим
3	Контрольная работа № 1, 2	Развитие монологической речи при описании грамматик языков для ЭВМ. Закрепление теоретического материала по классификации автоматов	11, 24, 29, 30	1 неделя	20	Проверка контрольной работы	15 н., 1 трим, 15 н., 2 трим.
4	Индивидуальное задание (Тема №7 , 8)	Закрепление нового материла при доказательстве примитивной рекурсивности заданной функции, применение практических знаний на практике		9 недель	10	Проверка задания	10 н., 1, 2 трим.

Список литературы

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

Абрамов С.А. Элементы анализа программ / С.А. Абрамов - М.: Наука, Гл. ред. физ.-мат. лит., 1986. - 128 с.
Аханов Кґкен. Грамматика теориясыныњ негіздері: Оќу ќ±ралы / К. Аханов.- Алматы: Санат, 1996.- 240 бет. Пер.: Основы теории грамматики(на каз. яз. ) .
Бурин Е.А. Введение в основы информатики и вычислительной техники / Е.А. Бурин - Алма-Ата, Мектеп, 1989. - С. 97-112.
Информатика / Под ред. П.П.Беленького. – Ростов на Дону: Феникс, 2003.
Козырев А.А. Информатика: учеб. для вузов/ А.А. Коызрев. - СПб: Изд-во Михайлов В.А., 2002. - 511 с.
Информатика. Базовый курс: учеб.пособие для технич.вузов/ Под ред.С.В.Симоновича.- 2-е изд.- СПб.:Питер, 2003.- 640 с.
Скэнлон Лео. ПЭВМ IBM PC и XT. Программирование на языке Ассемблера. Перевод И. В. Емелина. М. Радио связь, 1989-335 с.
Страуструп Б. Язык программирования Си / Б. Страуструп - М.: Радио и связь, 1991. – 352 с.
Керниган Б. Язык программирования Си / Б. Керниган. М.: Финансы и статистика, 1992. – 272 с.
Климова, Л. М. Pascal 7. 0: Практ. Программирование. Решение типовых задач: Учеб. пособие / Л. М. Климова.- М.: Кудиц Образ, 2000.- 528. с.- (Библиотека профессионала).
Языки программирования. /под ред. Ф. Женюи. - М. Мир, 1972. - 405с.
Фаронов, В. В. Delphi 5: Учеб. курс / В.В. Фаронов.- М.: Нолидж, 2001.- 608 с.: ил.
Архангельский А. Разработка прикладных программ для Windows в Delphi 5 / А. Архангельский - М., 1999.
Юров В. Assembler: [Учеб.] / В. Юров.- СПб.: Питер, 2001.- 624 с. + дискета: ил.
Фаронов, В.В. Delphi 5:Руководство программиста/ В.В. Фаронов; Рос. ассоц. издателей компьютерной лит.- М.:Нолидж,2001.-880 с.
Ивани А. Элементы теоретического программирования: Учеб.пособие для вузов / А. Ивани, Р.Л. Смелянский –М.: МГУ, 1985.

Дополнительная литература:

Алферова З.В. Теория алгоритмов / З.В. Алферова - М.: Статистика, 1973.
Ахо А. Теория синтаксического анализа, перевода, компиляции. В 2 т. Т. 1, 2 / А. Ахо, Дж. Ульман - М.: Мир, 1980.
Болски М.И. Язык программирования Си / М.И. Болски. Справочник. - М.: Радио и связь, 1988.-230 с.
Брауэр В. Введение в теорию конечных автоматов. -М.: Радио и связь, 1987.
Бруно Б. Просто и ясно о Borland C++ / Б. Бруно. - М.: БИНОМ, 1994. – 356 с.
Гинзбург С. Математическая теория контекстно-свободных языков / С. Гинзбург - М.: Мир, 1970.
Гросс М. Теория формальных грамматик / М. Гросс, А. Лантен - М.: Мир, 1971.
Денисова П.И. Принципы моделирования языка / П.И. Денисова - М., 1965.
Комягин В.Б. Современный самоучитель работы на персональном компьютере / В.Б. Комягин, А.О. Коцюбинский - Москва: изд. Триумф, 1997.
Крючкова Е.Н. Теория алгоритмов / Е.Н. Крючкова - Барнаул; 1995.
Теория формальных языков и автоматов/ Е.Н. Крючкова - Барнаул; 1996.
Мелихов А.Н. Теория алгоритмов и формальных языков / А.Н. Мелихов, В.И. Кодачигов - Таганрог, 1983.
Кузнецов О.П. Дискретная математика для инженера / О.П. Кузнецов, Г.М. Адельсон-Вельский - М.: Энергоатомиздат, 1988.
Информатика/ Под ред. Н.В. Макаровой. — М.: Финансы и статистика, 1997
Язык программирования Си./Под ред. Васильева Б.М. - М.: Радио и связь, 1989.- 321 с.
Подбельский В.В. Язык Си++/ В.В. Подбельский. - М.: Финансы и статистика, 1990. – 560 с.
Потоцкий В.К. Работаем на языке Си / В.К. Потоцкий. - М.: Малип, 1992.- 120 с.
Рейуорд - Смит В. Дж. Теория формальных языков. Вводный курс / В. Дж. Рейуорд - Смит - М.: Мир, 1988.
Скэнлон Л. Персональные ЭВМ , IBM, РС и ХТ. Перевод с английского / Л. Скэнлон. –М. Радио и связь, 1989.
Саломаа А. Жемчужины теории формальных языков / А. Саломаа - М.: Мир, 1987.
Язык Си. Практикум для начинающих.- Усть-Каменогорск, ВКГУ, 1997. –34 с.
Вострикова З.П. Программирование на языке Бейсик для ЭВМ / З.П. Вострикова –М.: Машиностроение, 1993.
Успенский В.А. Теория алгоритмов: основные открытия и приложения/ В.А. Успенский - М.: Наука, 1987.
Касаткин В.Н. Информация. Алгоритмы. ЭВМ / В.Н. Касаткин. - М.: Радио и связь, 1986.
Роджерс Х. Теория рекурсивных функций и эффективная вычислимость / Х. Роджерс - М.: Мир, 1972.

Информации по оценке

Рейтинг-шкала

Форма контроля	Баллы
Текущий (лекции, лабораторные работы, письменные задания, реферат, мини-тест, коллоквиум)	30
Рубежный (контрольная работа, индивидуальные задания)	30
Итоговый (экзамен)	40
Всего:	100

3.8 Шкала и критерии оценивания различных видов работ на примере 3 кредита:

Лекция – 5 баллов=1 балл*5 лекций (3 аудиторные+2 СРСП).

Виды работы:

Посещение (0,5 балла)
Конспектирование (0,5 балла)

Итого: 1 балл*5 лекций = 5 балла

Лабораторное занятие – 20 баллов =5 баллов*4 лаб.раб.

Виды работы:

решение задачи без ошибок в срок (4 балла)
наличие полного отчета: формулировка задачи, формулы решения (0,5 балл)
устная защита решения задачи (0,5 балл)

Итого: 5 баллов*4 лаб.раб. =20 баллов

СРС –4 балла =2 балла*0 реферат+ 1 балл* 0 мини-тест + +2 балла * 2 письм.работ

Виды работы:

Выполнение письменных заданий без ошибок в срок (2 баллов),
Выполнение мини-теста без ошибок (1 балл)
Соответствие содержания реферата теме (1 балл)
Соблюдение требований к оформлению реферата (0,5 балла)
Устная защита реферата (0,5 балла)

Итого: 2 балла* 2 письм.работ + 2 балла*0 реферат +1 балл*0 мини-тест = 4 балла

4. СРСП - 1 балл = 1 балл* 1 коллоквиум.

Виды работы:

правильное выполнение коллоквиума за 1 академический час (1 балл)

Итого: 1 балл *1 коллоквиум = 1 балл

4. Рубежный контроль 30 баллов = 10 баллов*1 инд.зад+20 баллов * конт.раб.

Виды работы:

выполнение индивидуальных заданий без ошибок в срок (9 баллов),
соответствие содержания индивидуальных заданий теме (1 балл)
Выполнение контрольных без ошибок в срок (20 баллов)

Итого: 10 баллов*1 инд.зад+20 баллов * конт.раб. = 30 баллов

Итого по курсу за 3 кредит: 60 баллов

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

Рубежный контроль подразумевает самостоятельное выполнение и своевременный отчет индивидуальных заданий, правильное выполнение контрольных работ.

Требования к выполнению лабораторных и индивидуальных заданий:

задания должны сдаваться в срок, отчеты могут представлены в тетради или на листах формата А4;
содержание отчета составляет формулировку проблемы, формулы решения или описание.

Требования к рефератам:

содержание реферата должно соответствовать теме;
реферат может быть представлен в тетради или на листах формата А4 с соблюдением требований к оформлению.

4.Политика курса :

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

сдавать и защищать лабораторные работы и задания в рамках СРС в назначенные сроки;
обязательное присутствие студента на промежуточном и итоговом контроле.

Итоговая оценка по дисциплине в буквенных символах представляет собой сумму баллов по всем видам контроля.

Схема оценки знаний студентов по дисциплине

"Теория языков и автоматов"

№	Форма контроля	Трудоемкость дисциплины
		1 кредит	2 кредит	3 кредит
1	Текущий контроль	30	30	30
	А) посещение и конспект лекций	12	8	5
	Б) работа на лабораторных занятиях	5	15	20
	В) СРСП (коллоквиум)		1	1
	Г) СРС (реферат, письмен. Раб., мини-тест)	13	6	4
2	Рубежный контроль (инд. задания, контр.раб)	30	30	30
3	Итоговый контроль	40		40
4	Всего	100		100

2. УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ

ПО ДИСЦИПЛИНЕ
2.1 Тематический план курса

Всего 3 кредитов

№ п/п	Наименование темы	Лекции	Лабораторные	СРСП	СРС
1	Синтаксис, семантика и прагматика языков программирования.	3	-	2	10
2	Грамматики. Классификация граммаитик: регулярные грамматики, контекстно-свободные грамматики, контекстно-зависимые грамматики, грамматики общего вида.	8	-	5	10
3	Алгоритмические проблемы.	3	3	3	5
4	Классификация автоматов. Конечные автоматы, автоматы с магазинной памятью.	2	2	6	5
5	Двухсторонние автоматы, машины Тьюринга.	2	-	5	10
6	Детерминированные автоматы, автоматы фон Неймана.	2	-	5	-
7	Нечеткие грамматики, автоматы и языки.	2	-	2	-
8	Формализация семантики языков программирования.	2	-	2	-
9	Методы трансляции.	3	10	10	5
10	Лексический, синтаксический , семантический анализатор. Генератор объектного кода.	3	-	5	-
	Всего (часов)	30	15	45	45

2.2 Тезисы лекционных занятий

Тема 1: Синтаксис, семантика и прагматика языков программирования

План

Введение
Способы описания языков.
Синтаксис, семантика и прагматика языков программирования.
Типы трансляторов.
Способы описания языков программирования.

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

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

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

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

Перекодировщик - программа или программное устройство, переводящие программы, написанные на машинном языке одной ЭВМ в программы на машинном языке другой ЭВМ.

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

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

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

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

Дайте определение транслятора, компилятора, интерпретатора, эмулятора, макропроцессора.
Приведите пример задач синтаксиса, семантики на материале традиционного языка программирования

Основная литература: 1, 2, 3, 4, 11.

Дополнительная литература: 18,19, 40.

Тема 2: Грамматики. Классификация граммаитик

План

Классы грамматик
Грамматический разбор
Построение всех типов грамматик

Правила порождающих грамматик позволяют осуществлять преобразования строк. Ограничения же на виды правил позволяют выделить классы грамматик.

Грамматики типа 0 - это грамматики, на правила вывода которых нет ограничений. Грамматики типа 1, или контекcтные грамматики -это грамматики, все правила которых имеют следующий вид: хАу -> хjу, где A -> VN, x, y, j Î (VN È VT)+.

Грамматики типа 2 - это бесконтекстные, или контекстно-свободные грамматики (КС- грамматики). Правила вывода для этих грамматик имеют следующий вид: А ->j , где А ÎVN, j Î(VN È VT)*.

Грамматики типа 3 - это автоматные грамматики (леворкурсивные, праворекурсивные).

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

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

Основная литература: 1, 6.

Дополнительная литература: 18, 23-26, 30, 31.

Тема 3: Алгоритмические проблемы

План

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

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

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

Развитие вычислительной техники поставило перед математической теорией алгоритмов новую задачу: стало необходимым классифицировать алгоритмы по различным признакам. Эквивалентность понятий "алгоритм" и "машина Тьюринга" позволила предположить, что поиски классификации алгоритмов окажутся связанными с поисками промежуточных моделей между моделями конечного автомата и машиной Тьюринга.

Основная литература: 1, 2, 3, 4, 5, 11.

Дополнительная литература: 17, 19, 30, 31.

Тема 4: Классификация автоматов

План

Понятие автомата. Способы описания автоматов.
Типы автоматов.
Связь с грамматиками и языками.

Автомат - это алгоритм, определяющий некоторое множество и, возможно, преобразующий его в другое множество. Неформальное описание автоматов выглядит следующим образом: автомат имеет входную ленту, управляющее устройство с конечной памятью для хранения номера состояния, а также может иметь вспомогательную (рабочую) и выходную ленты.

Входную ленту можно рассматривать как линейную последовательность ячеек, причем каждая ячейка может хранить один символ из некоторого конечного входного алфавита.

Лента автомата бесконечна, но занято на ней в каждый момент времени только конечное число ячеек. Граничные слева и справа от занятой области ячейки могут занимать специальные концевые маркеры. Маркер может стоять только на одном конце ленты или может отсутствовать вообще.

Входная головка в каждый момент времени читает (обозревает) одну ячейку входной ленты. За один такт работы автомата входная головка может сдвинуться на одну ячейку вправо или остаться на месте, при этом она выполняет только чтение, т.е. в ходе работы автомата символы в ячейках входной ленты не меняются.

Рабочая лента - это вспомогательное хранилище информации. Данные с нее могут читаться автоматом, могут и записываться на нее.

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

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

Существуют следующие типы автоматов:

1) машина Тьюринга (МТ);

2) линейно-ограниченный автомат (ЛОА);

3) автомат с магазинной памятью (МП-автомат);

4) конечный автомат (КА).

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

Основная литература: 4, 5

Дополнительная литература: 21, 30, 32.

Тема 5: Двухсторонние автоматы, машины Тьюринга

План

Описание машин Тьюринга
Способы представления машин Тьюринга
Операции над машинами Тьюринга

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

Описывая различные алгоритмы для машин Тьюринга, и доказывая реализуемость всевозможных композиций алгоритмов, Тьюринг убедительно показал разнообразие возможностей предложенной им конструкции, что позволило ему выступить со следующим тезисом: “Всякий алгоритм может быть реализован соответствующей машиной Тьюринга”.

Доказать тезис Тьюринга нельзя, так как в его формулировке не определено понятие “всякий алгоритм”. Его можно только обосновать, представляя различные алгоритмы в виде машин Тьюринга. Было доказано, что класс функций, вычислимых на этих машинах, совпадает с классом частично рекурсивных функций.

Машина Тьюринга представляет собой автомат, имеющий бесконечную в обе стороны ленту, считывающую головку и управляющее устройство. Управляющее устройство может находиться в одном из состояний, образующих конечное множество Q = {q0, q1, ..., qn}. Множество Q называют внутренним алфавитом машины Тьюринга.

Принципиальное отличие машины Тьюринга от вычислительных машин состоит в том, что ее запоминающее устройство представляет собой бесконечную ленту, из-за которой невозможна ее физическая реализация. Лента разделена на ячейки, в каждой из которых может быть записан один из символов конечного алфавита A = {a0, a1, . . . , am}, который

называют входным алфавитом машины Тьюринга. Во время функционирования машины Тьюринга может быть заполнено конечное число ячеек. Считывающая головка в каждый момент времени обозревает ячейку ленты, в зависимости от символа в этой ячейке и состояния управляющего устройства записывает в ячейку новый символ или оставляет его без изменения, сдвигается на ячейку влево или вправо или остается на месте. При этом управляющее устройство переходит в новое состояние или остается в старом. Среди состояний управляющего устройства выделены начальное состояние q0 и заключительное состояние qz.

Основная литература: 4, 5, 6

Дополнительная литература: 21, 30, 32.

Тема 6: Детерминированные автоматы, автоматы фон Неймана

План

Детерминированные автоматы.
Автоматы фон Неймана.

Множество называется регулярным, если существует конечный детерминированный автомат, распознающий его. Так как произвольному конечному автомату однозначно соответствует детерминированный конечный автомат, операции над конечными автоматами эквивалентны операциям над регулярными множествами, или регулярными языками. Известно, что для произвольного конечного автомата можно построить эквивалентный автомат без циклов в начальных и (или) конечных состояниях. Конечные автоматы Мура и Мили предложено использовать в программах общего назначения (не только для логического управления) сравнительно давно. При этом наиболее разработанным вопросом применения конечных автоматов является синтаксический анализ в различного рода трансляторах алгоритмических языков. В настоящее время интерес к использованию конечных автоматов в программировании возобновляется, например, в области логического управления и в объектно-ориентированном программировании .

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

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

Основная литература: 4, 5, 6

Дополнительная литература: 21.

Тема 7: Нечеткие грамматики, автоматы и языки

План

Нечеткие грамматики.
Связь между автоматами и языками.

Языки могут быть заданы двумя способами:

1) грамматиками (порождающее средство языка);

2) автоматами (распознающее средство языка).

Различным по сложности автоматам соответствуют разные типы языков. Типичным примером такого рода является модель конечного автомата. Эта модель позволяет описать многие процессы, заданные на конечных множествах и развивающиеся в счетном времени, что позволило создать для нее продуктивную теорию. Если в эту модель ввести бесконечность по какому- либо параметру, то это приводит к общему классу систем, например, к машинам Тьюринга.

Развитие вычислительной техники поставило перед математической теорией алгоритмов новую задачу: эквивалентность понятий "алгоритм" и "машина Тьюринга" позволила предположить, что поиски классификации алгоритмов окажутся связанными с поисками промежуточных моделей между моделями конечного автомата и машиной Тьюринга.

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

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

Основная литература: 4, 5.

Дополнительная литература: 21, 30, 31.

Тема 8. Формализация семантики языков программирования

План:

Понятие формализации.
Примеры формализации языков

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

Примеры формализации языков - теория формализованных языков.

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

Основатели А. Черч, Г. Фреге. При создании формализованный язык стремиться к полной однозначности и предельной точности символов.

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

Основная литература: 6.

Дополнительная литература: 25, 30, 31.

Тема 9: Методы трансляции

План

Структура компилятора
Представление данных.
Отображение структур данных.
Распределение памяти.

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

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

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

Основная литература: 6, 8, 11.

Дополнительная литература: 22, 23, 27.

Тема 10: Лексический анализатор. Синтаксический анализатор. Семантический анализатор. Генератор объектного кода

План

Лексический, синтаксический анализатор.
Семантический анализатор.
Генератор объектного кода

Синтаксический анализатор - компонента компилятора, осуществляющая проверку исходных операторов на соответствие синтаксическим правилам и семантике данного языка программирования. Несмотря на название, анализатор занимается проверкой и синтаксиса, и семантики.

Избыточность в тексте программы устраняется на этапе лексического анализа. Выделение отдельных операторов происходит при синтаксическом анализе, при этом не проверяется смысл оператора. Генерирование команд означает анализ каждого оператора программы и сгенерирование эквивалентной ему последовательность машинных команд. Фиксированная последовательность команд называется каркасом.

Основная литература: 5, 6, 16.

Дополнительная литература: 23, 33, 35.

2.4 Планы лабораторных занятий

Тема: Алгоритмы

Лабораторная работа №1 "Алгоритмы. Конечные машины с памятью"

Вопросы

Определение алгоритма
Требования к алгоритму
Способы его описания

Задание: Разработать словесные алгоритмы вычитания из некоторого числа А последовательности n чисел b1, b2, ..., bn:

алгоритм вычисления по формуле:

C=(...((A - b1) - b2) - ... - bn)

Методические рекомендации описаны в [3] с.43.

Основная литература: 1, 3, 5, 6.

Дополнительная литература: 29.

Тема: Автокоды

Лабораторная работа №2 "Автокоды. Assembler"

Вопросы

Что означает дословная трансляция ?
Назовите директивы языка программирования.

Задание: сложите двоичные числа 00010101 и 00001101

Методические рекомендации описаны в книге Абеля П. Язык Ассемблер для IBM PC и программирования . - М.: Высш. Школа, 1992. на стр. 4-32.

Основная литература: 7, 14.

Дополнительная литература: 32, 33, 35.

Тема: Интерпретатор

Лабораторная работа №3 "Процесс разработки и отладки программ в интерпретаторе"

Задание: Разработать программу сложения двух чисел, вводимых пользователем с клавиатуры с отображением результата в среде интерпретатора GW Basic.

Методические рекомендации описаны [34] стр.10-12, 14-15.

Основная литература: 5, 6, 11.

Дополнительная литература: 32, 33, 44.

Тема: Макропроцессор

Лабораторная работа №4 "Использование заставок для увеличения функциональных возможностей языка"

Вопросы

Дайте определение макропроцессору.
Назовите назначение библиотеки классов MFC

Задание: найти максимум из двух назначений

Методические рекомендации к лабораторной работе приводятся в учебном пособии Подбельского В.В. “Язык С++” на стр.274.

Основная литература: 8, 9

Дополнительная литература: 34-38, 42.

Тема: Компиляция программ

Лабораторная работа №5 " Компиляция программ "

Вопросы

Опишите структуры данных или классов.
Назовите языки высокого уровня программирования.
Назовите компоненты инструментальной среды языка высокого уровня программирования.

Задание: найти сумму двух чисел.

Методические рекомендации к лабораторной работе приводятся в учебном пособии Назарова С.В., Мельникова П.П. "Программирование на MS Visual Basic"- М.: Финансы и статистика, 2001 - на стр. 23-34.

Основная литература: 11, 16.

Дополнительная литература: 26, 33.

Тема: Трансляция на машинный язык программирования

Лабораторная работа №6 " Трансляция на машинный язык программирования"

Вопросы

Что означает объектный язык программирования ?
Назовите группы трансляторов.

Задание: создать приложение, позволяющее проверить, является ли число, введенное пользователем простым.

Методические рекомендации описаны в [13] на стр. 15-18.

Основная литература: 4, 12, 13, 15.

Дополнительная литература: 17, 35, 40.

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

Задания:

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

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

Форма проведения СРСП:

доработка лабораторных работ;
проверка письменных заданий, консультации по СРС;
проведение коллоквиума.

Планы лекционных и лабораторных занятий

Тема 1: Синтаксис, семантика и грамматики языков программирования

Лекционное занятие

Классификация языков для ЭВМ по синтаксическому семантическому признаку.

Рекомендуемая литература: 1,2, 3, 4, 11, 18,19, 40.

Тема 2: Классификация грамматик

Лекционное занятие

Виды грамматик.
Атрибутные грамматики.
Программные грамматики.

Рекомендуемая литература: 1, 6, 18, 23-26, 30, 31.

Тема 3: Алгоритмические проблемы

Лекционное занятие

1.Оперативная память ЭВМ. Чтение кода.

Рекомендуемая литература: 1, 3, 4, 5, 11, 17, 30, 31.

Лабораторное занятие

Полное описание алгоритма решения задачи

Методические рекомендации в [3] стр.33-89.

Тема 4: Классификация автоматов

Лекционное занятие

1.Физическая реализация операторов программы.

Рекомендуемая литература: 4, 5, 21, 30, 32.

Тема 5: Машины Тьюринга

Лекционное занятие

1.Машина Тьюринга. Недетерминированные автоматы.

Рекомендуемая литература: 4, 5, 6, 21, 0, 32.

Тема 6: Детерминированные автоматы

Лекционное занятие

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

Рекомендуемая литература: 4, 5, 6, 21.

Тема 7: Автоматы и языки

Лекционное занятие

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

Рекомендуемая литература: 4, 5, 21, 30, 31.

Тема 8: Формализация языков программирования

Лекционное занятие

Языки спецификаций.

Рекомендуемая литература: 25, 30, 31.

Лабораторное занятие

1. Макроподстановка средствами препроцессора

Методические рекомендации в [37] стр.33-89.

Тема 9: Методы трансляции

Лекционное занятие

Типы трансляторов.
Сходство анализаторов.

Рекомендуемая литература: 6, 8, 11, 22, 23, 27.

Лабораторное занятие

1.Специальные средства отладчика

Компиляция, сборка и выполнение программы
Особенности среды программирования интерпретатора
Составление программного кода

Методические рекомендации в [34] стр.33-89, [14] стр 6-19, [19] стр. 11-15.

2.6 Планы занятий в рамках самостоятельной работы студентов

следующая страница >>