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

Лекция 10

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

1. ЕОБ (111,259) конструкциясы. Кемшіліктері.

2. Кемелдендірілген конструкция.

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
6
5

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-к сандардыњ барлыќ парлары ‰шін, екілік азайту ќ±рылѓысы ‰шін тењдеулер енгіземіз. Физикалық машинаның абстрактілі ќ±рылѓымыздыњ д±рыс моделі екендігін тексеру ѓана ќалады.