Файл қосу
Шекті автоматтар
|Қазақстан Республикасы білім және ғылым министрлігі |
|Семей қаласы ШӘКӘРІМ атындағы МЕМЛЕКЕТТІК УНИВЕРСИТЕТІ |
|3 деңгейдегі СМК құжаты |ПОӘК |ПОӘК |
| | |042.14.2.07.1.20.хх/01-2013 |
| | | |
| | | |
| | | |
|ПОӘК |03.09.2013ж | |
|Оқытушыға арналған |№..... басылым | |
|«Соңғы автоматтар және | | |
|формальдік тілдер теориясы» пәні| | |
|бойынша оқу жұмыс бағдарламасы | | |
«Соңғы автоматтар және формальдік тілдер теориясы»
ПӘНІН ОҚЫТУ-ӘДІСТЕМЕЛІК КЕШЕН
5В011100 - «Информатика» мамандығына арналған
СТУДЕНТТЕРГЕ АРНАЛҒАН ЖҰМЫС БАҒДАРЛАМАСЫ
Семей
2013
АЛҒЫ СӨЗ
1. ҚҰРАСТЫРЫЛДЫ
Құрастырған:_________ Семей қаласы Шәкәрім атындағы Мемлекеттік
университеті, Информатика кафедрасының аға оқытушысы Рысжанова А.С.
«___»__________ 2013ж.
2. ТАЛҚЫЛАНДЫ
2.1. Информатика кафедрасының отырысында талқыланды
Хаттама № 1 «11» қыркүйек 2013 ж.
Кафедра меңгерушісі _________________ Абишова А.А.
2.2. Физика-математика факультетінің әдістемелік Кеңесінің отырысында
талқыланды
Хаттама №1 «12» қыркүйек 2013 ж.
Әдістемелік кеңестің төрағасы __________ Батырова Қ.А.
3. БЕКІТІЛДІ
Университеттің оқыту-әдістемелік кеңесінің отырысында мақұлданып, баспаға
ұсынылды
Хаттама №1 «18» қыркүйек 2013 ж.
Оқыту әдістемелік кеңесінің төрағасы _____________ Г.К.Искакова
БІРІНШІІ РЕТ ЕНГІЗІЛДІ
МАЗМҰНЫ
|Жалпы жағдайлар | |
|Пәнді оқып үйренуге әдістемелік нұсқаулар | |
|Курс саясаты мен форматы | |
|Бағаларды қоюдағы саясат | |
|Пән мазмұны және сабақ түрлері бойынша сағаттардың бөлінуі | |
|СОӨЖ және СӨЖ мазмұндары | |
|Пән бойынша оқу үрдісінің күнтізбелік графигі | |
ЖАЛПЫ ЖАҒДАЙЛАР
1.1 Оқытушы және пән туралы қысқаша мағлұматтар
Оқытушының аты-жөні – Рысжанова А.С7, аға оқытушы
Кафедра – Информатика
Байланыс жүйелері – тел.36-01-50, №3 оқу корпусы, 102-кабинет
Пәннің өтілу орны – 205 аудитория
Пән атауы – Соңғы автоматтар және формальдік тілдер теориясы
Кредит саны -3
1.2 Жұмыстық –оқыту жоспарынан ақпарат (1-кесте).
1-кесте. Оқу жоспарынан ақпарат
|Курс |Семестр |Кредит |Дәріс |
|1 |2 |3 |4 |
| |Барлық 1 және 7 аптадағы аудиториялық |30 | |
| |сабақтарға қатысу | | |
|2 |Тапсырманы орындау |15 |ЗЖ |
|3 |Ауызша сұрау |15 |СОӨЖ |
|3 |Тапсырманы орындау |20 |ЗЖ |
|4 |Ауызша сұрау |30 |СӨЖ |
|4 |Тапсырманы орындау |20 |ЗЖ |
|5 |Тапсырманы орындау |20 |ЗЖ |
|6 |Ауызша сұрау |15 |СОӨЖ |
|6 |Тапсырманы орындау |15 |ЗЖ |
|7 |Тапсырманы орындау |15 |ЗЖ |
|7 |Ауызша сұрау |45 |СӨЖ |
|7 |Аралық бақылау 1 |60 |АБ |
|1 және 7 апта бойынша барлық балдар жиынтығы |300 | |
| |Барлық 8 және 15 аптадағы аудиториялық |30 | |
| |сабақтарға қатысу | | |
|8 |Тапсырманы орындау |10 |ЗЖ |
|9 |Тапсырманы орындау |10 |ЗЖ |
|9 |Ауызша сұрау |20 |СОӨЖ |
|10 |Тапсырманы орындау |10 |ЗЖ |
|10 |Ауызша сұрау |30 |СӨЖ |
|11 |Тапсырманы орындау |10 |ЗЖ |
|12 |Тапсырманы орындау |10 |ЗЖ |
|12 |Ауызша сұрау |20 |СОӨЖ |
|13 |Тапсырманы орындау |10 |ЗЖ |
|13 |Ауызша сұрау |45 |СӨЖ |
|14 |Тапсырманы орындау |10 |ЗЖ |
|15 |Тапсырманы орындау |10 |ЗЖ |
|15 |Аралық бақылау 2 |75 |АБ |
| 8 және 15 аптадағы қорытынды балл жиынтығы |300 | |
|Емтихан балы |400 | |
|Академиялық аралықтағы балдар қорытындысы |1000 | |
Мерей А. студенттің рейтингісін есептеу мысалы:
Бірінші рейтинг:
[pic]
Екінші рейтингті есептеу барысында [pic] нәтижесіне студенттің екінші
аралықтағы барлық ұпайларын қосу керек. Сонымен қатар Мерей А. студентке
зертханалық жұмыс тапсырмалары, машықтану сабағының тапсырмалары және СОӨЖ
үшін 9 балл қосылған, себебі ол оны бірінші аралықта орындамағандықтан.
Сонда Мерей А. екінші рейтингісі былайша анықталады:
[pic].
Егер студент денсаулығының нашарлауына немесе басқа да себепті
жағдайлар бойынша межелік бақылауды тапсыра алмаса және ол құжат бойынша
дәлелденсе, онда ол межелік бақылауды жеке тапсыруына болады.
Студент, пән бойынша қорытынды бақылауға жіберіледі, егер оның
рейтингілік ұпайы 50%. Тең немесе одан артық болса.
Кесте 3 - Бағалардың әріптік эквивалентпен, ұпайлармен және процентпен
шкаласы
|Әріп |Ұпайлардың цифрлық|Проценттік мазмұн |Дәстүрлі жүйедегі |
|жүйесі |эквиваленті | |баға |
|бойынша | | | |
|баға | | | |
|А |4,0 |95 – 100 |Өте жақсы |
|А– |3,67 |90 – 94 | |
|В+ |3,33 |85 – 89 | |
| | | |Жақсы |
|В |3,0 |80 – 84 | |
|В– |2,67 |75 – 79 | |
|С+ |2,33 |70 – 74 | |
| | | | |
| | | |Қанағаттанарлық |
|С |2,0 |65 – 69 | |
|С– |1,67 |60 – 64 | |
|D+ |1.33 |55 – 59 | |
|D |1,0 |50 – 54 | |
|F |0 |0 – 49 |қанағаттанарлықсыз |
|I |NA |- |аяқталмаған |
|P |- |өтті |Пәнді өтті |
5. Пән мазмұны және сағаттарды сабақ түрлері бойынша бөлу
Кесте 3 - Пән мазмұны және сағаттарды сабақ түрлері бойынша бөлу
|Тақырып атауы |Дәріс |Зертханал|ОСӨЖ |СӨЖ |Барлық|
| |сабақта|ық | | |саны |
| |ры |сабақтар | | | |
|1 |2 |3 |4 |5 |6 |
|Тілдер және грамматика. Алфавиттер, |2 | | | |2 |
|тізбектер және тілдер | | | | | |
|Программалау тілдерінің даму тарихы. |4 | | | |3 |
|Тілдерді өрнектеу. Синтаксис, семантика | | | | | |
|және программалау тілдерінің | | | | | |
|грамматикасы. Формализациялау | | | | | |
|проблемалары | | | | | |
|Формальді грамматика. Формальді |4 | | | |3 |
|грамматиканың негізгі түсінігі және | | | | | |
|классификациясы. Грамматикаларды | | | | | |
|классификациялау: регулярлық, | | | | | |
|контексті-бос, контексті-тәуелді, жалпы | | | | | |
|көріністегі, атрибутты, программалық. | | | | | |
|Хомскийдің формальдық тілдер иерархиясы. | | | | | |
|Шекті автоматтар. Детерминантты шекті |4 | | | |3 |
|автоматтар. Мур диаграммалары. Шекті | | | | | |
|автоматтардың эквиваленттілігі. Мур | | | | | |
|теоремасы. Мили и Мур автоматтары. Шекті | | | | | |
|автоматтардың алгебралық құрылымдық | | | | | |
|теоремасы. Шекті автоматтардың ішкі | | | | | |
|жағдайларын кодтау. | | | | | |
|Тақырып 1. Толық автоматтардың | |2 | | |2 |
|эквиваленттілігі. | | | | | |
|Мазмұны: Формальдық тілдер мен | | | | | |
|грамматиканың типтерін айқындау. | | | | | |
|«алфавит», «тізбек», «формальдік | | | | | |
|грамматика», «эквиваленттілік грамматика»| | | | | |
|түсінігін бекіту. Формальді тілдердің | | | | | |
|типін, грамматикалардың эквиваленттілігі | | | | | |
|мен бірмәнділігін Хомский классификациясы| | | | | |
|бойынша туынды грамматикалардың | | | | | |
|иерархиясын құруды дағдыландыру. | | | | | |
|Тақырып 2. Шекті айқындауыштар, берілген | |2 | | |2 |
|автоматты грамматика үшін шекті | | | | | |
|автоматтың ауысу графын құру және өңдеу | | | | | |
|Мазмұны: Шекті айқындауыштардың | | | | | |
|эквиваленттілігі және бір мәнділігін | | | | | |
|құру, тұрақты грамматика бойынша шекті | | | | | |
|автоматтарды құру, «детерминатты емес | | | | | |
|және детерминантты емес шекті автоматтар»| | | | | |
|ұғымын бекіту. | | | | | |
|Тақырып 3. Дербес автоматтар және олардың| |3 | | |2 |
|минимизациясы. | | | | | |
|Мазмұны: «Автоматтардың | | | | | |
|эквиваленттілігі», «минимальді шекті | | | | | |
|автомат» түсінігін енгізу, детерминантты | | | | | |
|шекті автоматтарды минимизациялауды | | | | | |
|дағдыландыруды қалыптастыру. | | | | | |
|Мәліметтер және типтері | | |2 | |2 |
|Трансляция әдістері | | |2 | |4 |
|Лексикалық талдау | | |2 | |2 |
|Синтаксистік талдау | | |3 | |4 |
|Тілдер және оларды өрнектеу | | | |15 |5 |
|Шекті автоматтар | | | |15 |15 |
|1-рейтинг қорытындысы |14 |7 |9 |30 |60 |
|Тьюринг машинасы |2 | | | |2 |
|Тьюринг машинасы, фон Нейман автоматы. | | | | | |
|Бір қалыпты өрнек бойынша детерминант | | | | | |
|емес шекті автомат құру. Детерминант емес| | | | | |
|шекті автомат бойынша детерминант автомат| | | | | |
|Лексикалық талдау |2 | | | |2 |
|Белгілерді оқу. Лексикалық анализдерді | | | | | |
|программалау. LEX лексикалық | | | | | |
|анализаторының құрылымы. | | | | | |
|Синтаксистік талдау |4 | | | |4 |
|Шығарылған синтаксистік талдау. LL(1) - | | | | | |
|грамматикасы. Рекурсивтік түсу. | | | | | |
|КС-грамматикасының бейнеленуі. Сол жақ | | | | | |
|рекурсияның жойылуы. Сол жақ | | | | | |
|факторизация. Енгізілген синтаксистік | | | | | |
|талдау. LL(1)-анализаторы. Синтаксистік | | | | | |
|талдаудың құру және қолдану кестесі. LR | | | | | |
|талдауының ерекшелігі және нұсқасы. | | | | | |
|Семантикалық талдау |4 | | | |4 |
|Тілдің контексті еркін емес қасиеттері. | | | | | |
|Символдар кестесінің ұйымдастыру. | | | | | |
|Идентификатордың кестесі. Орналастыру | | | | | |
|кестесі. Тізімді қойылым кестесі. | | | | | |
|Орналастыру функциясы. Ағаштар кестесі. | | | | | |
|Блоқтық құрылым. | | | | | |
|Жадының бөлінуі және код генерациясы |4 | | | |4 |
|Жады ұйымдастыру. Статикалық және | | | | | |
|динамикалық жады. Компиляцияның уақыт | | | | | |
|адресі. Уақытша жады. Кодтың генерациясы.| | | | | |
|Кодты құру. Үш адресті код. Р – коды. | | | | | |
|Байт – коды. Машиналық кодты құру. | | | | | |
|Нұсқаның таңдауы. Регистрлердің үлестіру.| | | | | |
|Объектті кодтың ықшамдылығы | | | | | |
|Тақырып 5. Магазинді жадылы автоматтар. | |2 | | |2 |
|Мазмұны: Магазинді жадылы автоматпен | | | | | |
|КТ-грамматикалардың эквиваленттілігі. | | | | | |
|Контексті-тәуелсіз грамматика бойынша | | | | | |
|магазинді жадылы автоматтарды құру. | | | | | |
|Тақырып 6. LL(1)- грамматикасы үшін | |3 | | |2 |
|рекурсивті түсу әдісімен синтаксисті | | | | | |
|талдау | | | | | |
|Мазмұны: LL(1) - грамматикасы үшін | | | | | |
|айқындауыштардың функционалдық | | | | | |
|модельдеуі. LL(1) - грамматикасының | | | | | |
|қажетті және жеткілікті шарттарын | | | | | |
|қолдану. LL(1)- грамматикасы үшін | | | | | |
|тізбектерді анықтау функционалдау. | | | | | |
|Тақырып 7. Төмен түсу әдісі бойынша | |3 | | |2 |
|КТ-тілдердің синтаксистік талдау | | | | | |
|Мазмұны: Жоғарыдан төмен синтаксистік | | | | | |
|талдауды автоматы жүзеге асыру, қарапайым| | | | | |
|көрсетілімді грамматика үшін анықтауыштың| | | | | |
|функционалдау моделін құру. L(A) және | | | | | |
|R(A) жиындарын құру, грамматика | | | | | |
|белгілерінің матрицаларын төмен түсу | | | | | |
|әдісі бойынша құру. | | | | | |
|Программаның аралық ұсынылуы | | |3 | |2 |
|Код генерациясы | | |3 | |2 |
|Компилятор кестелерінің ұйымы | | |3 | |2 |
|Семантикалық талдау | | |4,5 | |2 |
|Лексикалық талдау | | | |18 |2 |
|Синтаксистік және семантикалық талдау | | | |19,5 |4,5 |
|құру | | | | | |
|2-ші рейтинг қорытындысы |16 |8 |13,5 |37,5 |75 |
| |30 |15 |22,5 |67,5 |135 |
6. СОӨЖ және СӨЖ мазмұны
Кесте 4 – СОӨЖ және СӨЖ жоспарлары
Студенттердің оқытушымен өздік жұмысы (тапсырмаларды орындау және тапсыру)
| |Тақырыбы |Тапсырма мазмұны |Өткізу |Өткізу |Баға |
| | | |түрі |мерзімі |лау балы|
|1 |Мәліметтер және|Динамикалық және |Конспект |2 апта |5 |
| |типтері |статис-тикалық программалау | | | |
| | |тілдері. Атаулы және | | | |
| | |құрылымдық типтер | | | |
| | |эквиваленттілігі. | | | |
|2 |Мәліметтер және|Модульдер түсінігі. Суреттеу |Конспект |3 апта |5 |
| |типтері |және әрекеттер облысы. | | | |
|3 |Трансляция |Программалық қамсызданудың |Семинар |4 апта |5 |
| |әдістері |компилятор орыны. | | | |
|4 |Трансляция |Компилятор құрылымы. |Семинар |5 апта |5 |
| |әдістері | | | | |
|5 |Лексикалық |Регулярлық жиын және |Семинар |6 апта |5 |
| |талдау |регулярлық өрнек. | | | |
|6 |Лексикалық |Лексикалық анализаторды |Семинар |7 апта |5 |
| |талдау |программалау | | | |
|5 |Синтаксистік |1. Кестелік басқаруды |Семинар |8 апта |5 |
| |талдау |болжаушы талдау. | | | |
| | |2. LL(1)-грамматикасын және | | | |
| | |жоғары-төмен талдаудың | | | |
| | |алгоритмі | | | |
|6 |Программаның |1. Код генераторындағы |Конспект | 9 апта |5 |
| |аралық ұсынылуы|ақпараттың ұйымы. | | | |
| | |2. Аралықтың ұсыну деңгейі. | | | |
|7 |Код генерациясы|Айнымалылар трансляциясы |Семинар |11 апта |5 |
|8 |Код генерациясы|Трансляцияның логикалық өрнек|Семинар |12 апта |5 |
| | |ерекшелігі | | | |
|9 |Компилятор |1. Орналастырып қою |Семинар |13 апта |5 |
| |кестелерінің |функциялары | | | |
| |ұйымы |2. Блоктық құрылым орындалуы.| | | |
|10 |Семантикалық |1. Транслятордың прог-лық |Семинар |14 апта |5 |
| |талдау |орындалуы | | | |
| | |2. Жеке автоматтардың | | | |
| | |программалық орындалуы | | | |
СӨЖ тапсырмаларын орындау және өткізу графигі
Студенттің өзіндік жұмысы дәpicтiк материалдарды талқылау,
зертханалық сабақтарға дайындалу, өздік жұмыстарды қорғау, аралық бақылауға
дайындалу мен қатар, косымша материалдарды оқуды қамтиды. Ақпараттар көзі
ретінде студент оқулықтарды, оқу құралдарын, компьютерлер мен компьютерлік
технологиялар туралы мерзімдік басылымдарды, анықтамалық әдебиеттерді және
институт пен кафедра сайттарындағы оқу материалдарын және Интернет қорын
пайдаланады.
|№ |Тақырыбы |Тапсырма мазмұны |Өткізу |Балл |Тапсырманы |
| | | |түрі | |орындау |
| | | | | |уақыты |
| |Тілдер және |Алгоритмдік проблемалар: |реферат |30 |4 апта |
| |оларды |бос, идентификациялау, | | | |
| |өрнектеу |тілдердің эквиваленттілігі | | | |
| |Шекті |Шекті автоматтарды тізбектеп|коллокви|45 |7 апта |
| |автоматтар |және параллель жіктеу. Анық |ум | | |
| | |емес грамматикалар, |реферат | | |
| | |автоматтар және тілдер | | | |
| |Лексикалық |Лексикалық талдаудың |коллокви|30 |10 апта |
| |талдау |өңделуі. Лексикалық |ум | | |
| | |талдаумен синтаксистік және |реферат | | |
| | |семантикалық талдаулардың | | | |
| | |өзара әрекеттесуі | | | |
| |Синтаксистік| Синтаксистік талдау |реферат |45 |13 апта |
| |және |кестесін құру, және оларды | | | |
| |семантикалық|қолдану. Тізімдері бар | | | |
| |талдау құру |орналастыру кестесін құру. | | | |
СӨЖ үй тапсырмасы ретінде А4 форматтағы қағазға орындалып, оқытушыға
тапсырылады. СӨЖ программасы оқытушыға электронды түрде өткізіледі.
Өздік жұмысын бақылау келесі түрде болуы мүмкін:
– орындалған жұмыстың презентациясы;
– өзбетімен оқылған тақырыптың баяндамасы;
– оқытушының ауызша сұрауы;
– жазбаша түрде;
Ескерту: Жақсы бағада аттестация алу үшін СОӨЖ, СӨЖ тапсырмалары
аттестация уақытына дейін оқытушыға 1 апта бұрын тапсырылуы қажет.
7. ӘДЕБИЕТТЕР ТІЗІМІ
Негізгі әдебиеттер:
1. Ю.Г. Карпов. Теория автоматов. – СПБ.: Питер, 2002.
2. Ахо А., Дж.Ульм. Теория синтаксического анализа, перевода и компиляции.
М.: Мир, 1978. тт. 1,2.
3. Касьянов В. Н.. Лекции по теории формальных языков, автоматов и
сложности вычисле ий. — Новосибирск: НГУ, 1995.
4. Языки и автоматы. Сб. переводов. М.: Мир, 1975.
5. Ф.Льюис, Д.Розенкранц, Р. Стирнз. Теоретические основы проектирования
компиляторов. М.: Мир, 1979.
6. Э. Дейкстра. Дисциплина программирования. М. Мир: 1978.
7. Д. Брис. Наука программирования. М.: Мир. 1984.
8. Б. Дисков, Дж. Гатэг. Использование абстракций и спецификаций при
разработке программ. - М.: Наука, 1996.
Қосымша әдебиеттер:
1. Кнут Д.. Искусство программирования для ЭВМ. В 3 томах. - М., Мир,1976.
2. Кормен Т., Ч. Лейзерсон, Алгоритмы. Построение и анализ -М:
МЦНМО,1999.
3. А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислительных
алгоритмов - М: Мир, 1979.
4. Агафонов В.Н. Синтаксический анализ языков программирования. Уч.пособие,
Новосибирск, НГУ, 1981.
Пәндер
- Іс жүргізу
- Автоматтандыру, Техника
- Алғашқы әскери дайындық
- Астрономия
- Ауыл шаруашылығы
- Банк ісі
- Бизнесті бағалау
- Биология
- Бухгалтерлік іс
- Валеология
- Ветеринария
- География
- Геология, Геофизика, Геодезия
- Дін
- Ет, сүт, шарап өнімдері
- Жалпы тарих
- Жер кадастрі, Жылжымайтын мүлік
- Журналистика
- Информатика
- Кеден ісі
- Маркетинг
- Математика, Геометрия
- Медицина
- Мемлекеттік басқару
- Менеджмент
- Мұнай, Газ
- Мұрағат ісі
- Мәдениеттану
- ОБЖ (Основы безопасности жизнедеятельности)
- Педагогика
- Полиграфия
- Психология
- Салық
- Саясаттану
- Сақтандыру
- Сертификаттау, стандарттау
- Социология, Демография
- Спорт
- Статистика
- Тілтану, Филология
- Тарихи тұлғалар
- Тау-кен ісі
- Транспорт
- Туризм
- Физика
- Философия
- Халықаралық қатынастар
- Химия
- Экология, Қоршаған ортаны қорғау
- Экономика
- Экономикалық география
- Электротехника
- Қазақстан тарихы
- Қаржы
- Құрылыс
- Құқық, Криминалистика
- Әдебиет
- Өнер, музыка
- Өнеркәсіп, Өндіріс
Қазақ тілінде жазылған рефераттар, курстық жұмыстар, дипломдық жұмыстар бойынша біздің қор #1 болып табылады.
Ақпарат
Қосымша
Email: info@stud.kz