авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 3 | 4 ||

«УДК 002; 004.3(075.8) МИНОБРНАУКИ РОССИИ ББК 32.81; 32.97я73 ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ ...»

-- [ Страница 5 ] --

2) построение множеств FIRST(1, A) и FOLLOW(1, A) для каждого нетерминального символа грамматики;

3) проверка необходимого и достаточного условия LL(1) для введенной КС грамматики;

4) моделирование функционирования распознавателя для LL(1)-грамматик.

Составить набор контрольных примеров для случаев:

а) введенная КС-грамматика не является LL(1)-грамматикой;

б) исходная КС-грамматика является LL(1)-грамматикой, но входная строка не принад лежит языку грамматики;

в) заданная КС-грамматика является LL(1)-грамматикой и введенная строка принадле жит языку грамматики.

Разбор цепочек показать с помощью таблицы, строки вывода и дерева вывода.

Вариантами индивидуальных заданий к практической работе № 6 являются выходные данные практической работы № 4.

2.2.7. Моделирование функционирования распознавателя для грамматик простого предшествования Задачами проведения настоящего занятия являются:

– закрепить понятие «грамматика простого предшествования»;

– сформировать умения и навыки построения множеств L(A) и R(A), матрицы предше ствования символов грамматики и распознавателя для грамматик простого предшествования методом «сдвиг-свертка».

Рис. Р6.1. Дерево вывода для цепочки (a + (b – a)) в грамматике G Основы теории Определение Р7.1. Приведенная КС-грамматика G ( VT, V N, P, S, ) называется граммати кой простого предшествования, если выполняются следующие условия.

1) Для каждой упорядоченной пары терминальных и нетерминальных символов выпол няется не более чем одно из трех отношений предшествования:

а) Bi = B j ( Bi, B j V), если и только если существует правило A x Bi B j y P, где x, y V*;

б) Bi B j ( Bi, B j V), если и только если существует правило A x Bi Dy P и вывод D *Bjz, где A, D V N, x, y, z V*;

в) Bi B j ( Bi, B j V), если и только если существует правило A x CBjy и вывод С *zBi или существует правило A xCDy P и вывод С *zBi и D *Bjw, где A, C, D V N, x, y, z, w V*.

2) Различные правила в грамматике имеют разные правые части.

Определение Р7.2. Отношения =,, называют отношениями простого предшество вания для символов грамматики.

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

Метод предшествования основан на том факте, что отношения между двумя соседними символами распознаваемой строки соответствуют трем следующим вариантам:

– Bi = Bi + 1, если символы Bi и Bi +1 принадлежат основе;

– Bi Bi + 1, если Bi +1 – крайний левый символ некоторой основы;

– Bi Bi + 1, если Bi – крайний правый символ некоторой основы.

Алгоритм Р7.1. Поиск основы сентенции грамматики Если грамматика является грамматикой простого предшествования, то для поиска ос новы каждой ее сентенции надо просматривать элементы сентенции слева направо и найти самую левую пару символов x j и x j +1, такую что x j x j +1. Окончанием основы сентенции будет x j. Далее просматривать элементы сентенции справа налево, начиная с символа x j до тех пор, пока не будет найдена самая правая пара символов xi +1 и xi, такая что xi 1 xi.

Заголовком основы будет символ xi. Таким образом, будет найдена основа сентенции, имеющая вид xi xi +1 … x j 1. x j. Схема поиска основы сентенции грамматики представлена на рис. Р7.1.

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

Определение Р7.3. Построение матрицы предшествования основано на двух вспомога тельных множествах, определяемых следующим образом:

– L(A) = {X | A *Xz}, A VN, X V, z V* – множество крайних левых символов относительно нетерминального символа А;

– R(A) = {X | A *zX}, A VN, X V, z V* – множество крайних правых символов относительно нетерминального символа А.

Определение Р7.4. Отношения предшествования можно определить с помощью вве денных множеств следующим образом:

– Bi = B j ( Bi, B j V), если и только если существует правило A x Bi B j y P, где A VN, x, y V*;

– Bi B j ( Bi, B j V), если и только если существует правило A x Bi DyP и B j L(D), где A, D VN, x, y V*;

– Bi B j ( Bi, B j V), если и только если существует правило A xC Bi y и Bi R(C) или существует правило A xCDy P и Bi R(C), B j L(D), где A, C, D VN, x, y V*.

Матрицу предшествования дополняют символами н и к (начало и конец цепочки).

Для них определены следующие отношения предшествования:

– n X, X V, если X L(S);

– X, X V, если X R(S).

k Алгоритм Р7.2. Построение множеств L(A) и R(A) Шаг 1. Для каждого нетерминального символа А ищем все правила, содержание А в ле вой части. Во множество L(A) включаем самый левый символ из правой части правил, а во множество R(A) – самый крайний правый символ из правой части, т.е.

A VN : L0 (A) = {X | A Xy, X V, y V*}, R0(A) = {X | A yX, X V, y V*}.

Шаг 2. Для каждого нетерминального символа А: если множество L(A) содержит не терминальные символы грамматики А, A, …, то множество L(A) надо дополнить символа ми, входящими в соответствующие множества L(А), L(A) и т.д., … и не входящими в L(A).

Аналогичную операцию выполнить для множеств R(A), т.е.

A VN : Li (A) = Li 1 (A) Li 1 (B), B ( Li 1 (A) VN ), Ri (A) = Ri 1 (A) Ri 1 (B), B ( Ri 1 (A) VN ).

Шаг 3. Если на предыдущем шаге хотя бы одно множество L(A) или R(A) для некоторо го символа грамматики изменилось, то вернуться к шагу 2, иначе построение закончено. Т.е.

если существует A VN : Ri (A) Ri 1 (A) или Li (A) Li 1 (A), то положить i:= i + 1 и вер нуться к шагу 2, иначе построение закончено и R(A) = Ri (A) и L(A) = Li (A).

Алгоритм Р7.3. Функционирование распознавателя для грамматик простого предшествования Шаг 1. Поместить в верхушку стека символ n, считывающую головку – в начало входной цепочки символов.

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

– если самый верхний символ стека имеет меньшее или равное предшествование, чем очередной символ входной строки, то производим операцию «сдвиг» (перенос текущего символа из входной цепочки в стек и перемещение считывающей головки на один символ вправо);

– если самый верхний символ стека имеет большее предшествование, чем очередной символ входной строки, то выполняем операцию «свертка». Для этого находим на верхушке стека «основу» сентенции, т.е. все символы, имеющие равное предшествование или один символ на верхушке стека. Символы основы удаляем из стека, выбираем правило вывода грамматики, имеющее правую часть, совпадающую с основой, и помещаем в стек левую часть выбранного правила. Если такого правила вывода найти не удалось, то выдается сооб щение об ошибке, и разбор завершен неудачно;

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

– если в стеке остаются символы n S, а во входном буфере только символ, то k входная строка прочитана полностью, и алгоритм разбора завершен успешно.

Пример Р7.1. Дана грамматика G({a, (, )}, {S, R}, P, S), с правилами P:

1) S(R | a;

2) R Sa). Построить распознаватель для строки (((aa)a)a).

k Этап 1. Построим множества крайних левых и крайних правых символов L(A) и R(A) относительно всех нетерминальных символов грамматики (табл. Р7.1).

Таблица Р7. Построение множеств L(A) и R(A) для грамматики G Шаг Li ( A) Ri ( A) L0 ( S ) = {(, a} R0 ( S ) = {R, a} L0 ( R) = {S } R0 ( R) = {)} L1 ( S ) = {(, a} R1 ( S ) = {R, a, )} L1 ( R) = {S, (, a} R1 ( R) = {)} L2 ( S ) = {(, a} R2 ( S ) = {R, a, )} L2 ( R) = {S, (, a} R2 ( R) = {)} L( S ) = {(, a} R( S ) = {R, a, )} Результат L( R) = {S, (, a} R( R) = {)} Этап 2. На основе построенных множеств и правил вывода грамматики составим мат рицу предшествования символов (табл. Р7.2).

Поясним заполнение матрицы предшествования. В правиле грамматики S (R символ ( стоит слева от нетерминального символа R. Во множестве L(R) входят символы S, (, a. Ста вим знак в клетках матрицы, соответствующих этим символам, в строке для символа (.

В правиле грамматики R Sa) символ a стоит справа от нетерминального символа S.

Во множество R(S) входят символы R, a, ). Ставим знак в клетках матрицы, соответст вующих этим символам, в столбце для символа a.

В строке символа n ставим знак в клетках символов, входящих во множество L(S), т.е. символов (, a. В столбце символа ставим знак в клетках, входящих во множество k R(S), т.е. символов R, a, ).

В клетках, соответствующих строке символа S и столбцу символа a, ставим знак =, т.к.

существует правило R Sa), в котором эти символы стоят рядом. По тем же соображениям ставим знак = в клетках строки а и столбца ), а также строки ( и столбца R.

Таблица Р7. Матрица предшествования символов грамматики к Символы ( ) S R a =.

S..

R. =..

a (. =...

)..

н..

Шаг 3. Функционирование распознавателя для цепочки (((aa)a)a) показано в табл. Р7.3.

Таблица Р7. Алгоритм работы распознавателя цепочки (((aa)a)a) Шаг Стек Входной бу- Действие фер н (((аа)а)а) к 1 сдвиг н( ((аа)а)а) к 2 сдвиг н(( (аа)а)а) к 3 сдвиг н((( аа)а)а) к 4 сдвиг н(((а а)а)а) к свертка S а н(((S а)а)а) к 6 сдвиг н(((Sa )а)а) к 7 сдвиг н(((Sa) а)а) к свертка R Sa ) н(((R а)а) к свертка S ( R н((S а)а) к 10 сдвиг н((Sa )а) к 11 сдвиг н((Sa) а) к свертка R Sa ) н((R а) к свертка S ( R н(S а) к 14 сдвиг н(Sa )к 15 сдвиг н(Sa) к свертка R Sa) н(R к свертка S ( R нS к 18 строка принята Шаг 4. Получили следующую цепочку вывода:

S (R (Sa) ((Ra) ((Sa)a) (((Ra)a) (((Sa)a)a) (((aa)a)a).

Восходящее дерево вывода цепочки представлено на рис. Р7.2.

Рис. Р7.2. Дерево вывода для цепочки (((aa)a)a) в грамматике G Постановка задачи к практической работе № Разработать программное средство, автоматизирующее процесс разбора цепочек для грамматик простого предшествования. Программное средство должно выполнять следующие функции:

1) ввод произвольной грамматики;

2) построение множеств L(A) и R(A) для каждого нетерминального символа граммати ки;

3) формирование матрицы простого предшествования для введенной грамматики;

4) проверка условия простого предшествования для данной грамматики;

5) моделирование функционирования распознавателя для грамматик простого предше ствования.

Составить набор контрольных примеров для случаев:

а) введенная грамматика не является грамматикой простого предшествования;

б) исходная грамматика является грамматикой простого предшествования, но анализи руемая строка не принадлежит языку грамматики;

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

Разбор цепочек представить в виде таблицы, строки вывода и дерева вывода.

Вариантами индивидуального задания к практической работе № 7 являются выходные данные практической работы № 4.

3. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ 3.1. Перечень основной и дополнительной литературы 3.1.1. Основная литература:

1. Угрюмов, Е. П. Цифровая схемотехника [Текст] : учеб. пособие для вузов / Е. П. Уг рюмов. – 3-е изд., перераб. и доп.– СПб.: БХВ-Петербург, 2007.– 800 с.

2. Безуглов, Д. А. Цифровые устройства и микропроцессоры [Текст] / Д. А. Безуглов, И.

В. Калиенко. – Изд. 2-е. – Ростов н/Д: Феникс, 2008. – 468 с.

3. Лехин, С. Н. Схемотехника ЭВМ [Текст] / Н. С. Лехин. – СПб.: БХВ-Петербург, 2010. – 672 с.

4. Учебно-методический комплекс по дисциплине «Схемотехника ЭВМ» для студ.

напр. 230100.62 «Информатика и вычислительная техника», 230200.62 «Информационные системы» / сост. В. И. Воловач. – Тольятти: Изд-во ПВГУС, 2010. – 464 с.

5. Бочаров, В. А. Основы логики [Текст] : учеб. для вузов по гуманит. и естественнона уч. спец. / В. А. Бочаров, В. И. Маркин ;

МГУ им. М. В. Ломоносова. – М. : ФОРУМ : ИН ФРА-М, 2007. – 333 с.

6. Игошин, В. И. Задачи и упражнения по математической логике и теории алгоритмов [Текст] : учеб. пособие для вузов по спец. «Математика» / В. И. Игошин. – 3-е изд., стер. – М.

: Академия, 2007. – 303 с.

7. Тимофеева, И. Л. Математическая логика. Курс лекций [Текст] : учеб. пособие для вузов по спец. «Математика» / И. Л. Тимофеева. – 2-е изд., перераб. – М. : Университет, 2007. – 304 с.

8. Антонова, О. А. Логика и теория аргументации [Текст] : учеб. пособие / О. А. Анто нова ;

С.-Петерб. ин-т внешнеэкон. связей, экономики и права, О-во «Знание» С.-Петерб. и Ленингр. обл. - СПб. : [ИВЭСЭП], 2008. – 95 с.

9. Акулов, О. А. Информатика: базовый курс [Текст] : учеб. для вузов, бакалавров, ма гистров по направл. "Информатика и вычисл. техника" / О. А. Акулов, Н. В. Медведев. – 5-е изд., испр. и доп. – М. : Омега-Л, 2008. – 574 с.

10. Судоплатов, С. В. Дискретная математика [Текст] : учеб. для вузов по техн. спец. / С. В. Судоплатов, Е. В. Овчинникова ;

М-во образования и науки РФ, Новосиб. гос. техн. ун т. – М. [и др.] : ИНФРА-М [и др.], 2007. – 256 с.

11. Лихтарников, Л. М. Математическая логика. Курс лекций. Задачник-практикум и решения [Текст] : учеб. пособие / Л. М. Лихтарников, Т. Г. Сукачева. – Изд. 3-е, испр. – СПб.

: Лань, 2008. – 276 с.

12. Алгоритмы. Построение и анализ [Текст] / Т. Кормен [и др.] ;

[пер. с англ. И. В.

Красикова, Н. А. Ореховой, В. Н. Романова ;

под ред. И. В. Красикова]. – 2-е изд. – М. :

Вильямс, 2010. – 1296 с.

13. Воловач, В. И. Учебные материалы по дисциплине «Схемотехника ЭВМ». [Элек тронный ресурс]. – http://www.tolgas.ru/university/cathedra/elservice/downloads.

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

14. Новиков, Ф. А. Дискретная математика для программистов [Текст] : учебник / Ф. А.

Новиков. – СПб. : Питер, 2002. – 304 с.

15. Карпов, Ю. Г. Теория автоматов [Текст] : учеб. для вузов / Ю. Г. Карпов. – СПб. :

Питер, 2002. – 224 с.

16. Алексенко, А. Г. Основы микросхемотехники [Текст] / А. Г. Алексенко. – 3-е изд., перераб. и доп. – М. : ЮНИМЕДИАСТАЙЛ, 2002. – 448 с.

17. Ерусалимский, Я. М. Дискретная математика [Текст] : Теория, задачи, приложения:

учеб. пособие / Я. М. Ерусалимский. – 5-е изд., перераб. и доп. – М. : Вузов. кн., 2002. – с.

18. Кук, Д. Компьютерная математика [Текст] / Д. Кук, Г. Бейз ;

пер. с англ. Г. М. Ко белькова. – М. : Наука, 1990. – 384 с.

19. Рузавин, Г. И. Логика и аргументация [Текст] : учеб. пособие для вузов / Г. И. Руза вин. – М. : Культура и спорт : ЮНИТИ, 1997. – 351 с.

20. Зегет, В. Элементарная логика [Текст] / В. Зегет ;

под ред. и с предисл. Е. Б. Кузи ной ;

пер. И. М. Морозовой. – М. : Высш. шк., 1985. – 256 с.

21. Ивин, А. А. Практическая логика [Текст] : задачи и упр. / А. А. Ивин. – М. : Про свещение, 1996. – 128 с.

22. Афанасьев, А. Н. Формальные языки и грамматики [Текст] : учебное пособие / А. Н.

Афанасьев. – Ульяновск: УлГТУ, 1997. – 84 с.

23. Ахо, А. Компиляторы: принципы, технологии и инструменты [Текст] : / А. Ахо, Р.

Сети, Д. Ульман: пер. с англ. – М. : Изд. дом «Вильямс», 2001. – 768 с.

24. Братчиков, И. Л. Синтаксис языков программирования [Текст] / И. Л. Братчиков;

под ред. С. С. Лаврова. – М. : Наука, 1975. – 262 с.

25. Вайнгартен, Ф. Трансляция языков программирования [Текст] / Ф. Вайнгартен;

под ред. В. В. Мартынюка. – М.: Мир, 1977. – 192 с.

26. Вильямс, А. Системное программирование в Windows 2000 для профессионалов [Текст] / А. Вильямс. – СПб. : Питер, 2001. – 624 с.

27. Волкова, И. А. Формальные языки и грамматики. Элементы теории трансляции [Текст] / И. А. Волкова, Т. В. Руденко. – М. : Диалог-МГУ, 1999. – 62 с.

28. Гордеев, А. В. Системное программное обеспечение [Текст] / А. В. Гордеев, А. Ю.

Молчанов. – СПб: Питер, 2001. – 736 с.

29. Грис, Д. Конструирование компиляторов для цифровых вычислительных машин [Текст] / Д. Грис;

пер. с англ. – М.: Мир, 1975. – 544 с.

30. Дворянкин, А. И. Основы трансляции [Текст] : учебное пособие / А. И. Дворянкин.

– Волгоград: ВолгГТУ, 1999. – 80 с.

31. Жаков, В. И. Синтаксический анализ и генерация кода [Текст] / В. И. Жаков, В. В.

Коровинский, В. В. Фильчаков. – СПб. : ГААП, 1993. – 26 с.

32. Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программирование. Осно вы построения трансляторов. – СПб.: Корона принт, 2000. – 256с.

33. Льюис, Ф. Теоретические основы проектирования компиляторов [Текст] / Ф.

Льюис, Д. Розенкранц, Р. Стирнз. – М. : Мир, 1979. – 654 с.

33. Пантелеева, И. А. Методы трансляции [Текст] : конспект лекций. – Новосибирск:

Изд-во НГТУ, 1998. – Ч.2. – 51 с.

34. Пратт, Т. Языки программирования: разработка и реализация [Текст] / Т. Пратт, М.

Зелковиц;

под ред. А. Матросова. – СПб: Питер, 2002. – 688с.

35. Рейуорд-Смит В. Теория формальных языков. Вводный курс: Пер. с англ. – М.: Ра дио и связь, 1988. – 128 с.

36. Саломаа, А. Жемчужины теории формальных языков [Текст] / А. Саломаа. – М.:

Мир, 1986. – 160 с.

37. Серебряков, В. И. Лекции по конструированию компиляторов [Текст] / В. И. Сереб ряков. – М. : МГУ, 1997. – 171 с.

38. Соколов, А. П. Системы программирования: теория, методы, алгоритмы [Текст] :

учеб. пособие / А. П. Соколов. – М. : Финансы и статистика, 2004. – 320 с.

39. Федоров, В. В. Основы построения трансляторов [Текст] : учебное пособие / В. В.

Федоров. – Обнинск : ИАТЭ, 1995. – 105 с.

40. Хантер, Р. Проектирование и конструирование компиляторов [Текст] / Р. Хантер;

пер. с англ. – М. : Финансы и статистика, 1984. – 232 с.

41. Алгебраическая теория автоматов, языки и полугруппы [Текст] / Под ред. М. А.

Арбиба. – М. : Статистика, 1975. – 120 с.

42. Апериодические автоматы [Текст] / Под ред. В. И. Варшавского. – М.: Наука, 1976.

– 423 с.

43. Баранов, С. И. Синтез микропрограммных автоматов [Текст] / С. И. Баранов. – Л. :

Энергия, 1979. – 232 с.

44. Букреев, И. Н. Микроэлектронные схемы цифровых устройств [Текст] / И. Н. Бук реев и [др.]. – М. : Сов. радио, 1975. – 368 с.

45. Гилл, А. Линейные последовательностью машины [Текст] / А. Грил. – М. : Наука, 1974. – 288 с.

46. Гинзбург, С. Математическая теория контекстно-свободных языков [Текст] / С.

Гинзбург. – М. : Мир, 1970. – 328 с.

47. Гладкий, А. В. Формальные грамматики и языки [Текст] / А. В. Гладкий. – М. :

Наука, 1973. – 368 с.

48. Глушков, В. М. и др. Логическое проектирование дискретных устройств [Текст] / В.

М. Глушков и [др.]. – Киев: Наукова думка, 1987. – 264 с.

49. Глушков, В. М. Синтез цифровых автоматов [Текст] / В. М. Глушков. – М. :

Физматгиз, 1962. – 476 с.

50. Закревский, А. Д. Алгоритмы синтеза дискретных автоматов [Текст] / А. Д. Закрев ский. – М. : Наука, 1971. – 511 с.

51. Каган, Б. М. Электронные вычислительные машины и системы [Текст] / Б. М.

Каган. – М. : Энергоатомиздат, 1985. – 306 с.

52. Котов, В. Е. Сети Петри [Текст] / В. Е. Котов. – М. : Наука, 1984. – 158 с.

53. Кудрявцев, В. Б. Введение в теорию автоматов [Текст] / В. Б. Кудрявцев. – М. :

Наука, 1985. – 319 с.

54. Кузин, Л. Т. Основы кибернетики [Текст] / Л. Т. Кузин. Т. 2. – М. : Энергия, 1979. – 584 с.

55. Лазарев В. Г., Пийль Е. И. Синтез управляющих автоматов [Текст] / В. Г. Лазарев, Е. И. Пийль. – М. : Энергия, 1978. – 408 с.


56. Леснин, А. А. Сети Петри в моделировании и управлении [Текст] / А. А. Леснин и [др.]. – Л. : Наука, 1989. – 133 с.

57. Логическое проектирование БИС [Текст] / Под ред. В. А. Мищенко – М. : Радио и связь, 1984. – 311 с.

58. Мелихов, А. Н. Ориентированные графы и конечные автоматы [Текст]. – М. :

Наука, 1971. – 416 с.

59. Периодические автоматы [Текст] / Под ред. В. И. Варшавского. – М. : Наука, 1976. – 178 с.

60. Питерсон, Д. Теория сетей Петри и моделирование систем [Текст] / Д. Петерсон. – М. : Мир, 1984. – 264 с.

61. Поспелов, Д. А. Логические методы анализа и синтеза схем [Текст] / Д. А.

Поспелов. – М. : Энергия, 1974. – 368 с.

62. Рабинович, З. Л. Основы теории элементных структур ЭВМ / З. Л. Рабинович. – М. :

Радио и связь, 1982. – 279 с.

63. Савельев, А. Я. Прикладная теория цифровых автоматов [Текст], А. Я. Савельев. – М. : Высшая школа, 1987. – 272 с.

64. Чирков, М. К. Основы общей теории конечных автоматов [Текст]. – Л. : ЛГУ, 1975.

– 280 с.

65. Рузавин, Г. И. Основы логики и аргументации [Текст] : учеб. пособие для вузов по гуманит.-соц. спец. / Г. И. Рузавин. – М. : ЮНИТИ-ДАНА, 2007. – 320 с.

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

Практическое занятие включает в себя следующие этапы:

– защиту студентами предыдущей практической работы;

– постановка задачи для выполнения практической работы, включая краткие теоретиче ские сведения по рассматриваемому вопросу, обсуждение методики выполнения работы;

– ответы на вопросы студентов;

– подготовка студентами бланков отчетов по выполняемой практической работе;

– осуществление допуска студентов к выполняемой практической работе посредством обсуждения теоретических вопросов по теме занятия;

– непосредственное выполнение практической работы;

– подведение итогов занятия.

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

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

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

По окончании изучения дисциплины проводится итоговый контроль – зачет.

3.3. Методические указания студентам по изучению дисциплины При изучении дисциплины «Алгоритмы построения функциональных структур» сту денты должны знать: основные понятия о цифровом автомате;

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

теорию дискретных структур;

логику высказываний;

булевы функции;

логику предикатов;

методы формальных, прямых доказательств и доказательств с контрпримерами, доказательства от противного;

множества и отношения;

формальные языки;

комбинаторику;

теорию графов и деревьев;

ме тоды анализа и оптимизации проектных решений, а также применение для их реализации методов моделирования.

Аудиторная самостоятельная работа включает:

– дополнительное самостоятельное решение заданий по предложенным темам;

– выполнение индивидуальных тестов.

Внеаудиторная самостоятельная работа включает:

– изучение отдельных вопросов дисциплины;

– подготовку отчетов по практическим занятиям;


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

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

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

3.4. Учебно-методическая карта дисциплины 1 семестр Используемые наглядные Занятия и методические пособия (номера) Применение ПЭВМ Формы контроля Номер недели Номер темы Наименование вопросов, Лабораторные Практические изучаемых на лекции Кон Представление информации логически 1 1 1-4 слайды Microsoft спект, ми сигналами;

последовательный и парал Power Point защита лельный импульсный и потенциальный ко для пре практи ды. Понятие о комбинационной схеме и зентации ческих цифровом автомате.

слайдов работ (использу ется при проведе нии всех лекцион ных заня тий) (+) Программ ные моде ли неде термини рованного и детерми нирован ного ко нечных автоматов (++) Использу ется брау зер Internet Explorer (+++) Автоматы Мили и автоматы Мура. Кон 2 1 слайды + Структурный конечный автомат. Комбина- спект, +++ ционные логические элементы. Функцио- защита нальная полнота при построении цифрового практи автомата. ческих работ Системы логических элементов. Тригге- Кон 3 2 слайды + ры;

синхронные и асинхронные триггеры. Т- спект, +++ триггер;

D-триггер;

JK-триггер. Регистры;

опрос прием информации в регистр в парафазном на лек коде;

передача слова из одного регистра в ции другой;

сдвигающий регистр.

Построение функциональных структур с использованием логических элементов и ти повых узлов.

Высказывание;

связки;

истинность;

тав- Кон 4 3 слайды + тология и противоречие;

эквивалентность спект, +++ пропозициональных форм;

законы де Мор- сооб гана;

щение Высказывание;

логические операции. Кон 5 4 слайды + Построение таблиц истинности. Функция, спект, +++ порождаемая пропозициональной формой;

тести построение формы, порождающей заданную рование функцию.

Основные понятия и определения фор- Кон 6 5 5-7 слайды, + мальной грамматики и языка. Классифика- спект, компь ++ ция формальных грамматик;

классификация защита ютер грамматик и языков по Хомскому;

соотно- практи +++ ные шения между типами грамматик;

соотноше- ческих модели ния между типами языков. работ Граф и его разновидности. Ориентиро- Кон 7 6 слайды + ванные / неориентированные графы, подгра- спект, +++ фы, степень вершины, теоремы о сумме сте- кон пеней и о количестве нечетных вершин в троль графе. ная ра бота Кон Общие сведения и определения. Логиче слайды + 8 спект, ские операции над предикатами. Высказыва +++ тести ния с кванторами;

квантор всеобщности;

рование квантор существования;

истинность;

отрица ние высказываний с кванторами. Численные кванторы. Понятие исчисления предикатов (понятие формальной аксиоматической тео рии;

логический вывод, аксиомы и правила вывода). Значение формулы логики предика тов.

Множество натуральных чисел;

конеч- Кон 9 8 слайды + ные и бесконечные множества. Мощность спект, +++ множества. Принадлежность, включение, сооб равенство, операции над множествами, тож- щение дества.

Определения, каркасы и свойства. Графы Кон 10 9 слайды + с весами. Алгоритм построения каркаса ми- спект, +++ нимального веса (алгоритм Kruskal’а). Би- опрос нарные деревья, полные бинарные деревья и на лек их свойства. Организация хранения упоря- ции доченных данных в виде бинарного дерева.

Основные понятия методов анализа и оп- Кон 11 10 слайды, + тимизации проектных решений. Методоло- спект, компь- +++ гия анализа проектных решений;

математи- итого ютер ческие модели. Методика проведения анали- вое тес ные за;

методика оптимизации;

адекватность ма- тирова модели тематической модели;

концептуальные мо- ние дели.

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

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

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

1. Операционная система Microsoft Windows.

2. Пакет Microsoft Office (MS Word, MS Excel, MS PowerPoint).

3. Программные модели недетерминированного и детерминированного конечных ав томатов..

4. Браузер Internet Explorer.

Использование программного обеспечения по видам занятий приведено в учебно методической карте дисциплины (разд. 3.4 настоящего УМКД).

3.7. Технологическая карта дисциплины Поволжский государственный университет сервиса Управление магистратуры и послевузовского образования Технологическая карта дисциплины «Алгоритмы построения функциональных структур», кафедра «Информационный и электронный сервис», преподаватель Воловач В.И., группа МИ-101, семестр 2 10-20 учебного года Зачет контрольных Количество Количество но баллов за Срок прохождения контрольных точек контроль экза № п/п точек мена Виды контрольных точек февраль март апрель май цион ная сессия 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 I Обязательные:

1.1 защита практических работ 7 4 + + + + + + + 1.2 посещение лекционных за- 11 2 + + + + + + + + + + + нятий 1.3 контрольная работа 1 10 + 1.4 промежуточное тестирова- 1 10 + ние 1.5 итоговое тестирование 1 15 + II Творческий рейтинг:

2.1 выполнение и презентация 1 15 + самостоятельной работы с элементами исследования 2.2 подготовка к участию в сту- 1 + денческой конференции 2.3 подготовка докладов, рефе- 1 + ратов, сообщений зачет Ат.

не Форма контроля 100 деля 1) При условии выполнения всех обязательных контрольных точек студент может получить 85 баллов.

2) Для получения более высокой оценки либо в случае неучастия по уважительной причине в одном из обязательных видов рейтингового контроля сту дент может повышать количество баллов за счет участия в творческом рейтинге.

3) Для всех контрольных точек указано максимальное количество баллов.

Подпись преподавателя _ В.И.Воловач Согласовано: Зав. кафедрой В.И.Воловач ПРИЛОЖЕНИЯ Приложение Образец оформления титульного листа практической работы МИНОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ "ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СЕРВИСА" Кафедра "Информационный и электронный сервис" Отчет по практической работе № по дисциплине "Алгоритмы построения функциональных структур" " Распознавание типов формальных языков и грамматик" Студент _ Группа Факультет_ Преподаватель _ Работа защищена _ Тольятти, Учебное издание УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС по дисциплине «Алгоритмы построения функциональных структур»

для студентов направления 230100. «Информатика и вычислительная техника»

Составители Воловач Владимир Иванович Шакурский Максим Викторович Издается в авторской редакции.

Подписано в печать с электронного оригинал-макета 02.11.2011.

Бумага офсетная. Печать трафаретная. Усл. печ. л. 10,0.

Тираж 500 экз. Заказ 379/01.

Издательско-полиграфический центр Поволжского государственного университета сервиса.

445677, г. Тольятти, ул. Гагарина, 4.

rio@tolgas.ru, тел. (8482) 222-650.

Электронную версию этого издания вы можете найти на сайте университета www.tolgas.ru в разделе специальности учебно-методическое обеспечение дисциплин.

3

Pages:     | 1 |   ...   | 3 | 4 ||
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.