Лекция 4 Тақырыбы: Программалау тілдерінің ролі

Лекция 4

Тақырыбы: Программалау тілдерінің ролі

1. 
   Формальді жазу
   
2. 
   Формальді жазу артықшылықтары
   
3. 
   Синтаксис, семантика ұғымдары
   

1. Өткен сабақта екі оң санның ең үлкен ортақ бөлінгішін есептейтін екі түрлі машинаның формальді емес бейнесін келтірдік. Физикалық тұрғыдан олар екі басқа, бірақ математикалық тұрғыдан бір-біріне ұқсас. Олардың ең үлкен ортақ бөлінгіші есептеу қабілеттілігін дәлелдеу бір-біріне сәйкес келеді. Өйткені олар бір ғана “ойын ережелерін” әр түрлі іске асырады. Бұл ойын ережелері “Евклид алгоритмі” деген атпен белгі алгоритмнің мәнін құрайды.

Өткен сабақта Евклид алгоритм; ауызша тілмен бейнеленді. Бірақ оны қолдану мүмкін болған есептеулер саны өте көп болғандықтан оны формальді түрде қарастыру керек. Яғни бұл алгоритмді қандай да бір ыңғайлы формальді жазу түріне өткізуіміз қажет.

2. Формальді жазу түрінің бір қатар артықшылықтары бар.

- Ол алгоритмдерді математикалық обьектер ретінде қарастыруға мүмкіндік береді, алгоритімнің формальді бейнесін негіз ретінде алып,мысалы формальді бейнелері жалпы құрылымдық қасиеттерге ие болған алгоритмдер классы туралы теорема дәлелдеуге мүмкіндік береді.

[Мысалы Паскаль программаларының жалпы құрылымы]

- Формальді жазба түрі алгоритмді сондай дәл бейнелеуге мүмкіндік береді, егер аргуметтер мәні берілсе (кірісі), онда сәйкес жауаптың (шығысы) қандай болуы керектігіне қатысты ешқандайкүмән болмайды. Формальді бейнеленген алгоритм мен аргуметтерін қабылдап алып, есептеу жүргізетін автомат одан әрі адамның қатысынсыз-ақ жауабын шығарады.

- Мұндай автоматты есептеуіштерге арналған алгоритмдер программа деп аталады. Программаны жазудың формальді әдістері программалау тілдері деп аталады. Тілдер деген терминнің қолданылуы табиғи тілдер үшін бұрыннан қолданылатын “грамматика”,”синтаксис”,”семантика” программалау тілдері үшін терминдерін де қарастыруға жағдай жасады. Бұл термин ұғымдары (грамматика анықтамасы арнайы сабақта беріледі) программалау тілдерінде былайша баяндалады:

3. Синтаксис-қайсы бір тілдің элементтерінің құрылуын анықтайтын ережелердің жиынтығы. Басқаша айтқанда берілген символдардың симантикалық мағынасы бар тізбегінің ережелер жиынтығы. Синтаксис қайсы бір тілдің ұғымдарын сипаттайтын ережелер арқылы беріледі. Ол ұғымдардың мысалы ретінде айнымалы, өрнек, оператор және процедураны алуға болады. Ұғымдардың тізбегі мен ережелері бойынша пайдалануы программаның синтаксистік дұрыс құрылымын анықтайды.

Семантикалық анализатор-

синтаксистік ережеге және берілген программалау тілінің семантикасына сай болуын тексеруді қамтамасыз ететін компилятор компоненті. Анализатор синтаксис пен семантиканы тексерумен айналысады. Олардың әрқайсысы белгілі бір мәселені шешетін бірнеше блоктан тұрады.

Лекция 5

Тақырыбы: Жағдайлар және олардың сипаттамалары.

1. 
   Жағдайлар кеңестігі
   
2. 
   Жағдайлар кеңестігінде теңдіктерді қолдану
   

1. Жағдайлар ұғымын түсіну үшін жүз жыл алдын пайда болған механикалық сумматорды қарастыралық. Есептің жауабын көрсететін терезесі болады, сол терезенің артында бірнеше қатар орналасқан дөңгелекшелер бар. Әр дөңгелекше 10 түрлі жағдайда болуы мүмкін, яғни 10 түрлі цифрды көрсетуі мүмкін.(мысалы 00000019 цифрларын көрсетіп тұрған сумматорға 4-і қоссақ онда 2 дөңгелекше қоятын өзгертіп 00000023 санын көрсетеді).

Әрдайым дөңгелекше өзінің жағдайларының тек бірінде ғана бола алады. Мұны басқаша айтқанда дөнгелекшеге 10 нүктеден тұратын жағдайлар кеңістігі сәйкес қойылады. Әрбір жағдай нүктемен байланыстырады, нүктелер жиналып кеңістікті құрайды. Дөңгелекшелі айнымалы кезінде қарастыруға болады. Демек, бір айнымалыдан тұратын жүйе әрдайым өзінің жағдайлар кеңістігі нүктелерінің бірінде болады. Жағдайлар кеңістігі жүйе еркіндігінің деңгейін белгілейді. (басқа еш қайда өте алмайды).

Енді бір дөңгелекшені емес, қатарынан орналасқан 8 дөңгелекше регистрді қарастырайық. Әр дөңгелекше 10 түрлі жағдайда болуы мүмкін болса, бір бүтін қарастырылатын регистр 100 000 000 түрлі мүмкін болған жағдайдың бірінде болады. Оның әрбір жағдайы терезеден көрсетілетін санмен (дәлірек, 8 цифрлы қатармен) белгіленеді.

Егер барлық дөңгелекшелердің жағдайлары берілсе, онда бір бүтін регистірдің жағдайы бір мәнмен анықталады;керісінше бір бүтін регистірдің жағдайы бойынша жеке дөңгелекшелер жағдайлары бір мәнді анықталады. Бұл жағдайда, бір бүтін регистірдің жағдайлар кеңістігін, жекелеген 8 дөңгелекшенің жағдайлар кеңістігінің “ декартың көбейтіндісі ” бойынша құрамыз. Бұл кеңістіктің жалпы нүктелер саны жекелеген кеңістіктердің нүктелерінің көбейтіндісіне тең. (Ал декарттық деп аталу себебі жазықтықтағы әрбір нүктеге х,у кординатасын сәйкес қою идеясын Декарт тапқан. Біздің жағдайда регистірдің әрбір жағдайына 8-дөңгелекше жағдайы сәйкес қойылады).
2. Декарттық көбейтінді ретінде құрылған жағдайлар кеңістігінің барлық нүктелері де керекті болуы міндетті емес. Мысалы жыл күндерін 2 айнымалы ай мен күннің декарттық көбейтіндісі ретінде қарастыруға болады. Ай айнымалысы 12 жағдайға не мәнге ие (қаңтардан желтоқсанға дейін ), ал күн айнымалысы (1-ден 31-ге дейінгі ) 31 мәнге ие. Бұл жағдайда 372 нүктеден тұратын жағдайлар кеңістігі құрылады.

Ал шындығында жылдардың ешқайсысы да 366 күннен аспайды. Мысалы (июнь,31) жұбы (нүктесі) артық. Біз оны (июль,1) жұбына тең деп айтуымызға болады. “ Мүмкін емес даталар” деген ұғым ендіріліп, (июнь,31) жұбына тыиым салуымыз мүмкін. Бұның салдарынан жүйеде кейбір қарама – қайшылық пайда болуы мүмкін.

Декарттық көбейтінді ретінде құрылған жағдайлар кеңістігіндей әрбір нүктені идентификациялай аламыз. (Атау бере аламыз) Мысала аналар мерекесі (март, 8) деп белгілеп, айта аламын.

Бірақ, мұны басқаша көрсетуге болады. (блогадаря Декарту) Аналар мерекесі төмендегі теңдеудің шешімімен анықталады.

( ай=март) ^ (күн=8)

Теңдеулерді қолданудың артықшылығы, оның барлық шешімдер жиынын сипаттауға (қасиетін көрсетуге ) мүмкіндік береді.

Бұл теңдеудің тек бір шешімі ғана бар, сондықтан жылдың бір күнін көрсету үшін қолдануымызға ыңғайлы емес.

Басқа мысал айлық берілетін күндерді мына теңдікпен сипаттауға болады.

(күн=25)

Шынында да,”(қаңтар,25), (ақпан,25), (наурыз,25)...” деп тізіп отырудан гөрі жоғарыдағыдай теңдікпен жазу ыңғайлы болады.

Жағдайлар жиынын сипаттайтын теңдеулерді қолданудың жеңілдігі, ыңғайылығы жағдайлар кеңістігінің құрылымына қаншалықты сәйкес келетіндігіне, яғни ендірілген координаталар жүйесіне сәйкес келуіне байланысты.

Мысалы жоғарыда келтірілген (ай,күн) координаталар жүйесінде (қаңтар,1) –күніне тура келген апта күніне мысалы сейсенбіге тағы қайсы күндер тура келетіндігін сипаттайтын теңдік құру ыңғайлы болмас еді.