ОСӨЖ күнтізбелік - тақырыптық жоспары

№	ОСӨЖ бойынша тақырып және тапсырма	Сағат саны	Апта
	Тақырыбы: Программалау тілдері. Программалау тілдерінің деңгейлерін анықтау. Программалау тілдерін кезеңдерге бөлу. Өткізу формасы :Тренинг Тапсырмалар: 1. Жоғары дәрежелі программалау тілдері. 2. Төмен дәрежелі программалау тілдері. 3. Программалау тілдерінің деңгейлері. 4. Мәліметтер базасының программалау тілдері. 5. Интернеттің программалау тілдері. 6. Моделдеу тілдері.
	Тақырыбы:Алфавит түсінігін беру. Алфавит элементтерін жазу. Кәдімгі тіл және программалау тілдері алфавитінің ерекшеліктерін көрсету. Тапсырма:Төмендегі сұрақтарға конспект жазу 1. Алфавит мысалдары. 2. Алфавит түсінігі. 3. Кәдімгі тіл алфавиті 4. Программалау тілінің алфавиті.
	Тақырыбы: Программалау тілдерінің синтаксис, семантика және прагматикасы. Тапсырма:Төмендегі сұрақтарға конспект жазу 1. Жоғары дәрежелі программалау тілдерінің қасиеттері. 2. Төмен дәрежелі программалау тілдерінің қасиеттері. 3. Прагматика ұғымы. 4. Метатілдер.
	Тақырыбы:Грамматика классификациясы. Регулярлы (жүйелі) грамматикалар. Регулярлы емес грамматикалар. Тапсырмалар: 1. Формальды грамматикаға анықтама беру. Эквивалентті грамматикаға мысалдар қарастыру. Регулярлы және регулярлы емес грамматикаларға есептер шығару. 2. Практикалық жұмыстарды орындау. Мысал. - ережесімен берілген G1=({a,b}, {S,A,B},P,S) грамматикасы G2=({a,b}, {S,Y},P,S) 1) S As, 2) S a, 3) S b, 4) S bY, 5)Y b, 6)Y bY, 7)S грамматикасына эквивалент. Есептер шығару. 1. Р ережесімен G3=({a}, {S,N,Q,R}, P,S) грамматикасы берілген, S QNQ, 2) QN QR, 3) RN NNR қандай грамматикаға эквивалент екенің табу? 2. G0=({0,1},{S}, {S 0S1, S })- грамматикасына эквивалент грамматика құрыныз. Грамматика класстарын анықтаңыз. 3. Формальды грамматика көмегігі арқылы L={a2n/ n 1}- тілі регулярлы болатының дәлелденіз.
	Тақырыбы: Контексті грамматикаларды сипаттау. Хомский және Грейбахтың нормальды формасымен танысу. Тапсырмалар: 1. Контексті грамматиканың объектілерін жазу. 2. Контексті еркін грамматика мысалдарын жазу. Практикалық жұмыстарды орындау. Мысал.Aab жолы үшін грамматикада 1) S AB, 2) A aA, 3) A , 4) B Bb , 5) B - ережелері берілген, оның шешімі S 1 AB 2 aAB 2 aaAB 3 aaB 4 aabB 5 aab- сол жақты болып табылады, ал шешімі - S 1 AB 4 AbB 5 Ab 2 aAb 2 aaAb 3 aab оң жақты болады. Есеп шығару. 1. Контексті еркін грамматика келесі өнімдерден тұрсын: S AB, A SA/BB/bB, B B/aA/ . Бұл грамматикаға эквивалент S түрдегі ие - өнімнен тұратын жаңа контексті грамматика құру. 2. L(G2)={an bn cn / n 1}- тілін дәлелденіз,мұнда G2- контексті грамматика
	Тақырыбы: Жалпы түрдегі және Атрибутты грамматика. Грамматикаға мысалдар келтіру. Атрибутты және программалы грамматикаларды сипаттау. Программалы грамматиканың ерекшеліктерін анықтау. Тапсырмалар:Төмендегі сұрақтарға конспект жазу 1. Жалпы түрдегі грамматика. 2. Атрибутты грамматика. 3. Программалы грамматика.
	Тақырыбы:Алгоритм проблемалары. Бос орын проблемасы және тілдің эквивалент проблемалары. Тапсырмалар:Төмендегі сұрақтарға конспект жазу 1. Алгоритм проблемалары. 2. Бос орын проблемалары. 3. Эквивалент қатынасы. 4. Эквивалент класстары. 5. Эквивалент проблемасы.
	Тақырыбы: Автомат классификациялары. Автоматтар түрлерін қарастыру және мысал келтіру. Тапсырмалар:Төмендегі сұрақтарға конспект жазу 1.Автомат түсінігі. 2.Автомат принциптері. 3.Автомат түрлері.
	Тақырыбы: Шеткі автоматтар. Шеткі автоматтарды анықтау және түрлендіру. Тапсырмалар:Шеткі автомат мысалдарын қарастыру. Практикалық жұмыстарды орындау. Мысал. M1 = (Q, , q0, F) кестеде анықталған, мұнда оң жақ бөлігінде шеткі автоматтың формальды анықтамасы берілген және олардың командалары жазылған. Сол жақ бөлігінде өту кестесі (таблица перехода) берілген. А В С Q={A,B,C}; = {a,b} А В   А = { (A,a)=B, (B,b)=C, (C,a)=A, } B   С   Q0= A; F={A,C} Есептер шығару. 1. M=(Q, , q0, F ) берілген, мұнда Q={S0, S1, S2, S3, S4, S5, S6, S7, S8}, = {0,1}, q0= S0 , F= { S1, S2, S6, S7 } және кестеде өту функциясы берілген. Шеткі автоматтың мүмкін емес болатын шамаларын жою. S0 S1 S2 S3 S4 S5 S6 S7 S8 S1 S2 S2 S5 S5 S3 S8 S0 S3 S5 S7 S5 S7 S6 S1 S0 S1 S6 2.M=(Q, , q0, F ) берілген, мұнда Q= {A,B,C,D,E,F}, = {a,b,1}, q0= A, F= {E,F} және кестеде өту функциясы берілген. Шеткі автоматтың эквивалент шамаларын біріктіру. A B C D E F A B   D       B   C   C     F   E
	Тақырыбы: Тақырыбы:Магазин жадылы автоматтар түсінігімен танысу. Стек түсінігін беру. Тапсырмалар: Тапсырма 1:Төмендегі сұрақтарға конспект жазу 1. Магазин жадылы автоматтар анықтамасы. 2. Магазин жадылы автоматтардың әртүрлілігі. 3. Контексті грамматика және Магазин жадылы автоматтардың байланыстары. 4. Кеңейтілген Магазин жадылы автоматтарды құру. Тапсырма 2. Практикалық жұмыстарды орындау. Мысал. Магазин жадылы автомат берілген, M=(Q, , Г, q0, Z0) Мұнда Q={A}, = {( , )}, Г= {I,O}, q0= A, Z0=I; = { ( A, ( , I) = (A, OI); (A , ( , O)= (A, OO); (A,), O) = (A, ); (A, , I ) = (A, ) }. Есептер шығару. 1. Е аксиомасы бар магазин жадылы автомат қалай құрылады? E E+F/F , F (E)/i ережесімен VT ={+ , ( , ), I }, VN ={E,F} берілген. 2. К аксиомалы грамматикасында VT= {c,d,g,q}, VN= {X,Y,R} және 1) R Xc 2) R Yd 3) X q 4) X Qx 5) Y g 6) Y gY ережелері берілген. S(Xc) символ көпшелерін және R Xc ережесі үшін F(R) символ көпшелерін табыңыз.
	Тақырыбы: Детерминді және детерминді емес автоматтар мысалдарын қарастыру, ерекшеліктерін анықтау. Тапсырмалар: Тапсырма 1: Төмендегі сұрақтарға конспект жазу 1. Детерминді магазинді автоматтар. 2. Детерминді емес магазинді автоматтар. 3. Детерминді автоматтар және контексті тілдер. 4. Детерминді емес автоматтар және контексті еркін тілдер. Тапсырма 2. Практикалық жұмыстарды орындау. 1. L – детерминді тіл , ал R- регулярлы тіл болсын, онда L R детерминді тіл екенің дәлелденіз. 2. S Aa/ Abb a. A Ba/Sb b. B Bas/ 3. түрлі өнімі бар детерминді емес магазинді автоматты құрыныз. 4. Егер L T* - детерминді тіл болса, онда L=T*/L - да детерминді тіл болатының дәлелденіз.
	Тақырыбы: Тьюринг және Пост машиналарын есеп шығаруға қолдану. Мүмкіндіктерін көрсету. Тапсырмалар:Төмендегі тақырыптар бойынша конспект жасау: 1. Тьюринг машинасының құрылымы. 2. Пост машинасының құрылымы. 3. Пост машинасының мүмкіндіктері. 4. Тьюринг машинасының мүмкіндіктері. 5. Машина анықтамалары.
	Тақырыбы:Формальды тілдердің даму тарихымен танысу. Тапсырмалар: Тапсырма 1:Төмендегі тақырыптар бойынша конспект жасау: 1. Формальды тілдер алфавиті. 2. Формальды грамматика түсінігі. 3. Сентенциалды форма. Тапсырма 2. Практикалық жұмыстарды орындау. Мысал. А= { 1,2,3}, B= {1,4,8,9} берілсін. Онда = {(2,4), (3,9)} B- дағы А толық емес бірлік бейнеленуі болады. a A үшін b= формуласы тиісті болып табылады. Есе шығару 1. Егер A = {ab,c} және B= {c, ca }, {a,b,c,}* алфавитіндегі екі формальды тілдер болса, онда келесіні есептеніз: A B; A/B; A0/ B0; AB; BA; A2 B2. 2. Т- тоғай болсын. Тоғайдағы тамырдан қандай да бір түйінге дейін жол жалғыз екенің көрсету. ( индукция әдісін қолдану).
	Тақырыбы: Объектілі код оптимизациясымен танысу. Машина коды генераторының алгоритмін жазу. Тапсырмалар:Төмендегі тақырыптар бойынша конспект жасау: 1. Объектілі код анықтамасын беру. 2. Код генераторы. 3. Машина коды.
	Тақырыбы:Синтаксистік және семантикалық анализатор ерекшеліктерін қарастыру. Өсу және кему синтаксисті анализдің алгоритмін құру. Трансляция әдісі. Тапсырмалар:Төмендегі тақырыптар бойынша конспект жасау: 1. Трансляция мақсаты. 2. Трансляцияда есептің берілуі. 3. Лексикалық анализ мақсаты.
	Барлығы

Студенттердің өздік жұмыстарына әдістемелік нұсқаулар:

Мақсаты: Студенттерді өз бетінше жұмыс жасай білуге дағдыландыру, теориялық білімдерін бекіту, ойлау қабілеттерін дамыту, программа құра білуге машықтандыру.

Әдістемелік нұсқау: әр тақырып бойынша өздік жұмысты орындап отыру. Тапсырмалардың программасын құрып, компьютерде орындағаннан кейін, оны тестілеп нәтижесін оқытушыға көрсетіңіз.

Тапсырмаларды орындау барысында А.П.Соколов «Системы программирования» теория, методы, алгоритмы, М, 2004 г.; В.Дж.Рейуорд-Смит «Теория формальных языков»-М, Радио и связь, 1988 г.; Могилев А.В., Пак Н.И., Хеннер Е.К., «Информатика», М., Академия, 1999 г. әдебиет көздерін және Интернет материалдарын пайдаланыңыздар.