Лекция 2 Тақырыбы: Сөздер және абстракт тілдер

Лекция 2

Тақырыбы: Сөздер және абстракт тілдер

Осылайша құрылған сөздер жиынын ішінен дұрыс сөздерді (қандайда бір ереже бойынша дұрыс құрылған) анықтайтын формальді тіл қажет болады. Формальді тілдің өзіне тән грамматикасы болады. Грамматика формальді ережелердің шектелген жиынынан тұрады. Ал осы формальді ережелерге сәйкес құрылған барлық сөздер дұрыс сөздер болады.

Қазіргі таңда информатикада формальді тілдерді тудыратын бірнеше граматиканы беру әдістері жасалынған. Қарапайым әдістердің бірі (әрі көп жерде қолданылатын) Бэкустің нормаль формалары деп аталатын әдіс.

Мысал арқылы қарастыралық. Айталық 2-лік цифр (0,1) және үтірден тұратын х алфавиті берілсін. Осы алфавит арқылы барлық рационал теріс емес екілік сандардан (бүтін, бөлшек) тұратын тіл құру керек. Мұндай тіл құру үшін Бэкус әдісінде мынандай екі (мета ұғым) ұғым беріледі.

“Сол жақ” Оң жақта келтірілген форма мәндерінің кез-келгенімен анықталады. n деген сөйлемді ынғайлылық үшін : : = белгісімен береміз.

<бүтін сан>: : =<0><1><0> <бүтін сан><1> <бүтін сан>

<екілік сан>: :=<бүтін сан> <,> <бүтін сан>

Мұнда  - немесе деген мағынаны білдіреді.

Жоғарыдағы анықтамаларға сәйкес дұрыс сөздер, яғни 2-лік сандар деп төмендегілерді айтуға болады: 01, 0010, 00.
2. Автоматтандырылған информациялық жүйелер мәліметтермен жұмыс істейді. Бұл мәліметтерді әдетте берілгендер деп атайды, ал жүйелердің өзі - берілгендерді өңдеудің автоматтандырылған жүйелері деп аталады. Берілгендер бастапқы (кіретін) аралық және шығатын болып ажыратылады. Берілгендер жеке-жеке құраушыларға бөлінеді. Оларды элементар берілгендер деп, не берілгендер элементтері деп аталынады. Әр түрлі типтегі берілгендер элементтері қолданылады. Берілгендер типі (элементар) осы берілгендер қабылдай алатын мәндерге сәйкес анықталады.

Қазіргі уақытта информатикада көптеген әртүрлі элементар берілгендер типтерінің ішінен ең жиі қолданылатындары бүтін және нақты сандар, сөздер және бульдік деп аталатын шамалар.

ЭВМ–де сандар көріністерінің 2-түрі бар: екілік, екілік-ондық, екілік көрінісінде екілік санау жүйесі қолданылады. Бұл бүтін сандар үшін.

Ал нақты сандар жағдайында 2-түрлі көрініс формасы пайдаланылады: жылжымалы және жылжымайтын үтір арқылы.

Жылжымайтын үтір арқылы жазылған уақытта барлық нақты сандар үшін үтірдің қай жерде жазылатындығы анықталып алынады. Мысалы: үтір 3-пен 4 разряд аралығында қойылсын деп келісілсе онда 00001010 коды 00001,010=(1+0*2^-1 +1*2^-2 +1*2^-3)=1,25¹⁰*1+1/2²=1,25

Жылжымалы үтір арқылы жазылған сандар коды мына түрде беріледі х=а*2^b а саны (белгісі бар - +) – мантисса деп аталады, b- саны х санының мінездемесі деп аталады.

Буль типі тек 2 мәнді ғана қабылдай алатын берілгендерді анықтайды: ақиқат және жалған. Бульдік шамаларды кодтау үшін 2-лік алфавит қолданылады.

4. 
   Әр түрлі берілгендерді идентификациялау (атау беру) үшін идентификаторлар деп аталатын арнайы атаулар беріледі. Бұл айнымалы қабылдай алатын мәндер осы айнымалымен анықталып отырған элементар берілгендер типімен анықталады.
   

Айнымалы шамалар үшін оның атауы мен мәнін айыру талап етілсе, тұрақты деп аталатын шамалар үшін шама мәні оның атауы ретінде де қолданыла береді. Егер тұрақты шамаға атау (идентификатор) берілсе онда ол “константа” деп аталады және тұрақты мәннен өзге мән қабылдай алмайды.

Мысалы: 2,718 е=2,718.

Лекция 3

Таќырыбы: Орындау абстракциясы.

М±ндай класс элементтерініњ µзара айырмашылыќтарына кµњіл бµлмей, класќа жалпы берілген аныќтамаѓа с‰йене отырып, оныњ єрбір элементтеріне тиісті пікірлер айтуѓа болады. Б±л пікір ќарастыратын наќты есептеу ‰шін де д±рыс болады.

“Есептеу” сµзі ќандай маѓына білдіріп т±рѓанын айќындап кµрсету ‰шін есептеу ќолданбайтын “алу” конструкциясын ќарастырамыз ењ ‰лкен. Мысалы, 111 мен 259 сандарыныњ ортаќ бµлінгішін алу конструкциясы. Ол бір-бірініњ ‰стіне орналасќан картоннан жасалѓан 2 карточкадан т±рады. Жоѓары карточкада мынадай жазу бар. “ЕОБ(111,259)=?” конструкциядан жауап алу ‰шін жоѓары карточканы кµтеріп, тµменгі карточканыњ сол жаѓына ќоямыз, тµменгі карточкадан “37” жазуын оќимыз. ЕОБ(111,259)=37

Карточкалыќ конструкцияны ќолдану µте ќарапайым, б±л оныњ жаќсы жаѓы. Кемшілігі екеу. Бірі кішкене, бірі ‰лкен.

Кішкене кемшілігі мынада: бұл констукцияны шынында да 111 мен 259 сандарының ең үлкен ортақ бөлінгіш алу үшін паидалануға болғанымен, бұдан басқаға жарамай ды. Үлкен кемшілігі мынада конструкцияның тура жауап беретініне көз жеткізе алмаймыз, конструкцияны даяарлаушыға сенім білдірумен ғана шектемеиміз.

2. Кемшіліктердің кішкенесін жою үшін, х,у жазықтығындағы нүктелер кординаталары (тек бүтін) жазылған үлкен кардон қағазды қарастырыумызға болады.0 x<500, 0,y<500 Әрбір (х,у) нүктесі үшін ЕОБ (х,у) мәні келтірілген болсын. Сонда картон қағазыда барлығы 250000 (х,у) сандар пары үшін БОБ (х,у)-ң мәнін аламыз.

x	y	EOБ(х,у)
1	1	1
1	2	1
1	3	1
...	...	...
20	10	10
20	11	1
20	12	4
...	...	...

Демек, картон қағазға қарағанда әлдеқайда көп сандар үшін паидалануға болады.

Ал үлкен кемшілік жойылмаиды керісінше 250000-ке артады, яғни дайындаушысына шексіз сенім білдіруге тура келтіреді. Бұл кемшіліктіде жоқ қылатын басқа бір конструкцияны қарастыраиық. Жоғарыдағыдай картон қағазға х,у өсі сызылып олардың әрбір түйісетін түйін нүктелері келтірілген 0

1. 
   Вертикал сызықтар (х= константа теңдеуімен )
   
2. 
   Горизонтал сызықтар (у=константа теңдеумен )
   
3. 
   Диогоналдар (x+y= константа теңдеуімен )
   
4. 
   Жауап сызығы x=y теңдеуімен.
   

7

0 1 2 3 4 5 6 7 8

Бұдан соң фишка гипатенузаның 2-ші осіне қарай жылжиды. Осылайша фишканы жауап сызығына жеткенше жылжытамыз. Жауап сызығына тура келетін фишканың соңғы орны, яғни Х- координата (не У-координата) ізделінді нәтиже болып табылады.

Бұл машина бізге дұрыс нәтиже беретіндігіне қалай көз жеткіземіз.

Егер (х,у) жауап сызыѓында орналаспаѓан 249500 н‰ктелердіњ кез-келгені болса, [500 б±л жауап сызыѓындаѓы н‰ктелер] жєне (х^І,у^І)фишканыњ бір ќадамда жылжыѓан н‰ктесі болса,

онда жєне немесе

жєне болады.

ЕОБ (х,у)=ЕОБ (х^І,у^І) болатынын дєлелдеу ќиын емес. Ењ мањыздысы, бір мєрте келтірілген пікірді м‰мкін болѓан 249500 жаѓдай ‰шін ќолдануѓа болады. Б±дан бµлек х=у болатын  (х,у) н‰ктесі ‰шін (яѓни (х,у) жауап сызыѓында жатќан 600 н‰ктеніњ бірі) ЕОБ (х,у)=х болатынын дєлелдеу ќиын болмайды. Таѓыда б±л пікірді жауап сызыѓындаѓы 500 н‰кте ‰шін бірдей ќолдануѓа болады. ‡шіншіден, б±л да ќиындыќ тудырмайды,  бастапќы (х,у) орынан шекті ќадамдар саны шынында да фишканы жауап сызыѓына апаратынын кµрсетуіміз керек. М±ны да бастапќы 250 000 (х,у) орын ‰шін ќолдана аламыз.

‡ш ќарапайым пікірді н‰ктелер санына байланыссыз ќолдана беруге болады.

Егер (х,у) бастапќы орыннан басталѓан фишканыњ ойын барысындаѓы  орнын (х,у) арќылы белгілеп алсаќ, онда 1-теорема осы ойын барысында ЕОБ (х,у)=ЕОБ (х,у) ќатынасы д±рыс болатындыѓын білдіреді. Ал екінші теорема фишканыњ соњѓы орнына сєйкес келетін х-координатаны (У координатаны) талап етілген нєтиже ретінде ќарастыруѓа болатындыѓын кµрсетеді.

Ал 3-теорема м±ндай соњѓы орынныњ бар екендігін айтады.

Енді бізге тек дайындаушы келтірген параќта осьтер, к‰лтелер, жєне сызыќтар д±рыс келтірілгенін тексеру ѓана ќалады. (яѓни біз ќ±рѓан абстрактілі машинаныњ д±рыс моделі, копиясы болу керек).

Басќа бір машина картон параѓымен емес, 2 тоѓыз биттік регистрлер мен ж±мыс істеу м‰мкін. Єрбір регистр 0 ден 500ге дейінгі екілік санды саќтай алады. Бір регистрді х координатасыныњ мєні ‰шін, 2-н у координатасынан мєнін саќтау ‰шін пайдалану м‰мкін. Орын жылжыту б±л жерде бір регистірдіњ мєнімен 2-ші регистрдіњ мєнін алып тастауѓа сєйкес келеді. Алу амалын µзімізде орындауымызѓа болады, біраќ біз ‰шін машина орындап беретін болса, єлдеќайда жаќсы болар еді. Машинаныњ беретін жауабына сенім білдіру ‰шін, біз машинаныњ салыстыру жєне азайту амалдарын д±рыс орындап жатќанына кµз жеткізуіміз керек. Таѓы да барлыќ жаѓдайлар, яѓни n разряды 2-к сандардыњ барлыќ парлары ‰шін, екілік азайту ќ±рылѓысы ‰шін тењдеулер енгіземіз. Физикалық машинаның абстрактілі ќ±рылѓымыздыњ д±рыс моделі екендігін тексеру ѓана ќалады.