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

Памятка для студентов по изучению дисциплины
" Теория автоматов и формальных языков"
направления «Программная инженерия»

Составила профессор кафедры ПМ Сучкова Л.И.
Содержание дисциплины

Изучение дисциплины «Теория автоматов и формальных языков» происходит в 6 семестре. Учебный план предусматривает 34 часа лекций, 17 часов лабораторных работ, 57 часов СРС, выполнение расчетного задания, зачет.
Теоретический материал содержит:
Модуль 1.
1. Основные понятия теории формальных языков и автоматов. Концепция порождения и распознавания (2 часа; [2,3]).
Алфавит. Формальные языки. Операции над языками. Порождающая грамматика. Понятие вывода. Классификация грамматик по Хомскому. Автоматные языки. Замкнутость класса автоматных языков. Лемма о разрастании для автоматных языков. Порождение цепочек автоматного языка. Синтез автоматной грамматики по заданному формальному языку.
2. Синтез автоматов-распознавателей (4 часа; [1,4]).
Конечные автоматы как распознающее описание автоматного языка. Способы задания автоматов. Синтез конечных автоматов. Операции над конечными автоматами. Алгоритмы построения объединения, произведения, итерации, усеченной итерации, конечных автоматов.
3. Преобразования автоматов-распознавателей (6 часов; [1,4]).
Детерминированные конечные автоматы. Преобразование автомата к детерминированной форме. Минимизация автомата. Синтез автомата для распознавания дополнения, пересечения автоматных языков. Регулярные выражения и их свойства. Регулярный язык. Теорема Клини. Связь между регулярными языками и конечными автоматами.

Модуль 2.
4. Контекстно-свободные языки и их порождение. (4 часа; [2,3]).
Основные свойства контекстно-свободных языков. Лемма о разрастании. Лемма Огдена. Алгебраическая замкнутость класса КС-языков. Пересечение и дополнение КС-языков. Пересечение КС-языка с автоматным языком.
5. Преобразование КС-грамматик. (6 часов; [2,3]).
Нормальные формы КС-языков. Деревья вывода. Однозначные КС-грамматики. Приведение КС-грамматики к нормальной форме. Удаление бесполезных нетерминалов. Удаление эпсилон-правил.
6. Распознавание КС-языков (4 часа; [2,3,4]).
Автоматы с магазинной памятью. Детерминированные автоматы с магазинной памятью. Применение МП-автомата для распознавания КС-языков. Алгоритмически неразрешимые проблемы в теории формальных языков.

Модуль 3.
7. Автоматы-преобразователи. (4 часа; [1,4,5,6]).
Автоматы Мили и Мура, их синтез. Эквивалентность автоматов Мили и Мура. Метод Ауфенкампа и Хона. Тестирование абстрактных автоматов.

8. Синтез структурных автоматов. (4 часа; [4,5,6,7,8,9]).
Понятие структурного синтеза. Теорема о структурной полноте. Общая схема структурного автомата. Типы элементарных автоматов памяти. Канонический метод структурного синтеза автомата.
График контроля
Таблица Д.1
Контрольное испытание
Время проведения
Вес в итоговом рейтинге

Лабораторная работа 1
Защита
2 неделя
0,05

Лабораторная работа 2
Защита
4 неделя
0,1

Лабораторная работа 3
Защита
6 неделя
0,1

Контрольный опрос 1
6 неделя
0,1

Лабораторная работа 4
Защита
8 неделя
0,1

Лабораторная работа 5
Защита
12 неделя
0,1

Контрольный опрос 2
13 неделя
0,1

Лабораторная работа 6
Защита
14 неделя
0,1

Контрольный опрос 3
16 неделя
0,1

Лабораторная работа 7
Защита
17 неделя
0,05

Расчетное задание
8-17 недели
0,1

Зачет
17 неделя
веса не имеет


Литература и учебно-методические материалы:
а) основная литература:
1. Горбатов В.А., Горбатов А.В., Горбатова М.В. Теория автоматов. Учебник для студентов втузов. – Изд-во АСТ, Астрель, 2008. – 560 с. – 13 экз.
2. Пентус А.Е., Пентус М.Р. Математическая теория формальных языков. Учебное пособие [Текст]/А.Е.Пентус, М.Р. Пентус. – БИНОМ, 2006. – 247 с. – 13 экз.
3. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. – М.: Изд-во Вильямс, 2007. – 528 с. - 5 экз.
4. Сучкова Л.И. Абстрактный и структурный синтез автоматов. Учебное пособие. - Барнаул, АлтГТУ, 2009. – 162 с. – 25 экз.
б) дополнительная литература:
5. Нарышкин  Александр Кириллович.   Цифровые устройства и микропроцессоры: [учеб. пособие для вузов радиотехн. специальностей] /А. К. Нарышкин .-М.: Академия, 2006.-317 с. – 4 экз.
6. Карпов Ю. Г.   Теория автоматов: учеб. для вузов по направлению подготовки бакалавров "Информатика и вычисл. техника" и по специальности "Вычисл. машины, комплексы, системы и сети" направления подготовки дипломир. специалистов "Информатика и вычисл. техника" /Ю. Г. Карпов.-СПб.: Питер, 2002. - 206 с.: ил..-( Учебник для вузов ). – 11 экз.
в) программное обеспечение и Интернет-ресурсы:

[ Cкачайте файл, чтобы посмотреть ссылку ]
[ Cкачайте файл, чтобы посмотреть ссылку ]
[ Cкачайте файл, чтобы посмотреть ссылку ]
Обучающая программа automat.exe.

г) методические указания студентам:

Сучкова, Л.И. Лабораторный практикум по дисциплине «Теория автоматов и формальных языков» / Алт. гос. техн. ун-т им. И.И. Ползунова. – Барнаул: АлтГТУ, 2012.- Режим доступа [ Cкачайте файл, чтобы посмотреть ссылку ]

В результате изучения дисциплины студенты должны обладать знаниями, умениями и навыками, приведенными в таблице Д.2.
Код компетенции по ФГОС ВПО или ООП
Содержание компетенции (или ее части)
В результате изучения дисциплины
обучающиеся должны:



знать
уметь
владеть

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

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

ОК - 10
Готовность использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования
- методы доказательства теорем теории формальных языков и автоматов;
- применять методы математической индукции для доказательства теорем;
- способностью к моделированию обработки цепочек языка автоматами

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


Порядок вычисления рейтинга по дисциплине «Теория автоматов и формальных языков»

1 Шкала оценок и правила вычисления рейтинга
Успеваемость студента оценивается с помощью текущего рейтинга (во время аттестации), семестрового (после окончания семестра) и итогового рейтинга (после сессии). Во всех случаях рейтинг вычисляется по формуле:
13 EMBED Equation.DSMT4 1415,
где Ri – оценка за i-ю контрольную точку, pi – вес этой контрольной точки. Суммирование проводится по всем контрольным точкам с начала семестра до момента вычисления рейтинга.
Пусть студент получил следующие оценки. Выполнение и защита работы 1 – 80 баллов, работы 2 – 50 баллов, работы 3 -40 баллов, работы 4 – 0 баллов (не защищена), контрольный опрос 1 - 60 баллов. На 1-й аттестации (9 неделя) его рейтинг равен:
13 EMBED Equation.3 1415.
На 17 неделе аналогичным образом учитываются выполнение и защита лабораторных работ по темам 1-7, контрольных опросов 1-3.
Перед началом сессии вычисляется семестровый рейтинг по темам 1-7, контрольных опросов 1-3, расчетного задания и с учётом посещаемости студентом занятий.
13 EMBED Equation.3 1415
где R – текущий рейтинг на конец семестра, вычисленный по результатам контрольных точек, Бп – дополнительные баллы за посещаемость занятий определённые по следующей схеме


В зачётку выставляется оценка, соответствующая итоговому рейтингу. Итоговый рейтинг может быть повышен не более чем на 20 баллов при выполнении студентом теста итогового контроля при условии, что семестровый рейтинг студента превышает 30 баллов.










СТО АлтГТУ 13.62.1.1118-2012

13 PAGE \* MERGEFORMAT 14215








Root Entry

Приложенные файлы

  • doc 8475033
    Размер файла: 165 kB Загрузок: 0

Добавить комментарий