Лекция 13 Тақырыбы: Флойд әдісі бойынша программаның дұрыстығын дәлелдеу

Лекция 13

Тақырыбы: Флойд әдісі бойынша программаның дұрыстығын дәлелдеу

Сонымен талданатын Р программасы р₁,р₂,...,р_и программалық бірліктерінен тұрғызылған болсын, яғни, әрбір программалық бірлік р₁(t=1,n) меншіктеу операторы, тармақталу операторы, тармақталу операторы, қайталану операторы немесе, топталу операторы болады. Р программасының верификациялау шарты cν (Р,і_р,о_р) арқылы белгіленсін, яғни,

cν (Р,і_р,о_р)→(і_р(Х,)∩r_р1(х,у)|_р2 )&( r_р1(х,у) ∩ r_р2(х,у)_р2) &...&( r_рn-1(х,у) ∩о_р(X,y)
М±нда енгізу векторы Х(х₁,х₂), Х₁-бµліггіш, х₂-бµлгіш ; аралыќ векторы (у₁,у₂), у₁-аралыќ бµлінді, у₂-аралыќ ќалдыќ;

Шыѓару векторы Z=(z₁,z₂), z₁-бµлінді, z₂-ќалдыќ.

a,b жєне c-программаныњ т‰йін н‰ктелері, б±л н‰ктелерде келесі т±жырымдар ќ±рылады:

a: і_р (х₁,х₂)х₁ 0х₂ 0

b: r_p1(x₁,x₂,y₁,y₂)x₁=y₁*x₂+y₂y₂0

c: o_p(x_1,x₂,z₁,z₂)x₁=z₁*x₂+z₂z₂0x₂z₂

Верификациялау шарттарын ќ±ру жол операторларын кері баѓытта (ретте) ќарастыру нєтижесінде ж‰зеге асырылады.

Бірінші жол ‰шін:
І_р(х₁,х₂,) (х₁,х₂,у₁,у₂,)_у10,_у2х₁

Яѓни, х₁0х₂0х₁0*х₁+х₂х₁0

Екінші жол ‰шін:

r_p1(х₁,х₂,у₁,у₂,)(у₂х₂r_p2(х₁,х₂,у₁,у₂,)_у1у+1,_{у2у2-х2}

z₂₌y₂

x₁₌y₁x₂₊y₂  y₂ O (x₂y₂x₁₌y₁* x₂₊y₂  y₂  O  x₂  y₂) (3)

(1)- формуладан арифметикалық амалдардф орындап біткен соң мынадай x₁   x₂  o  x₁=x₁ x₁ o логикалық өрнек шығады, мұндағы x₁=x₁- 2h әр қашанда ақиқат (тавтология), сондықтан оны қысқартып тастап өрнектен мынадай X₁Ox₂Ox₁ O формула алуға болады.

(2)- формуладан арифметикалық амалдарды орындап біткен соң және (С) және С түріндегі формулалардың логикалық теңмәнділігін, сондай-ақ, конъюнкцияның коммутативтілігін ескере отырып,  түріндегі аксиоманы (мәні әрқашан ақиқат формуланы) алуға болады, яғни,
x₁=y₁* x₂+y₂ y₂x₂  y₂ O x₁=y₁ * x₂+y₂x₂

A B A

Енді алынған (1), (2) және (3) верификациялау шарттарының ақиқаттығын тексеру үшін мән орнату функциясы VAL-ң көмегімен х₁ және х₂ енгізу айнымалылары үшін нақты тестілік деректер алайық, мысалы, VAL (х_1, х₂) = (7,3) болсын. Сонда верификациялау шарттары бойынша айнымалылар үшін келесі мәндерді аламыз:

7=1*3+4 & 4O (43 Й 7=(1+1)* 3+4-3 & 43; (2)

7=2*3+1& 1 O  (317=2*3+1& 31) (3)

(1’’). (2’’)және (3’’) өрнектердің ақиқаттығы көрініп тұр, яғни, P программасын верификациялау шарты _сv (Р, і, о ) ақиқат болады, ол жоғарыдағы теорема V. 1 бойынша і_р {p}o_p-ң ақиқаттығын көрсетеді. Ендеше, біз қарастырған бүтін санды бүтін санға бөлуді орындайтын З программасы дербес дұрыс.

Лекция 14

Таќырыбы: Программалау тілдерініњ сипаттары

1. 
   Машиналық тіл. Жасанды тіл.
   
2. 
   Программаның орындалуы
   

1. Алгоритмніњ машиналыќ тілдегі бейнесі программа деп аталады. Ал программа жазуѓа арналѓан тілі программалау тілі дейді. Сондыќтан машиналыќ тілдердегі барлыќ б±йрыќтар мен н±сќаулар комьпютердіњ ќ±рамына кіретін функционалдыќ бµліктер арќылы орындалады. Машиналыќ тілдер комьпютерлердіњ алѓашќы интеллектуалдыќ (зерделік) дењгейін аныќтайды. Кейін неше т‰рлі программаларды комьпютердіњ жадына саќтай отырып, оныњ интеллектуалдыќ дењгейін кµтеруге болады.

Машиналыќ тіл де барлыќ б±йрыќтар мен н±сќаулар тек “0” мен “1”-ден т±ратын тізбектер арќылы арќылы бейнеленеді. Сондыќтан машиналыќ тіл де программаларды жазу адам ‰шін µте ќиын. Себебі бір жаѓынан барлыќ амалдар мен н±сќаулардыњ екілік бейнелерін (кодтарын) есте саќтау керек, екіншіден кез келген алгоритімді осы машиналыќ амалдар мен н±сќаулар арќылы µрнектеліп білу ќажет. Алѓашќы деркетер, нєтиже жєне олардыњ адрестері екілік сандар арќылы бері леді. Тармаќталу н±сќауын жазу ‰шін басќару беретін адресті ќолмен есептеу ќажет Сол сияќты т±рын істелмеген кµптеген ж±мыстарды басынан бастап ќайтадан жасау керек. М±ныњ бєрі бір ден кµзге кµрінбейтін еµптеген ќателер жіберуге соќтырады. Жазылѓан программалар оќуѓа жєне т‰сінуге ќолайсыз болѓандыќтан, олардыњ ішіндегі жіберілген ќателерді тауып т‰зету µте кµп уаќытты жєне жылдамдылыќты ќажет етеді. Сондыќтан адамдар µздерініњ ж±мыстарын жењілдету ‰шін программа жазуѓа ыњѓайлы басќа жасанды тілдер ойластыра бастады.
2. Жасанды тілі компюьтер µзініњ машиналыќ тіліне адамныњ ќатысуынсыз (автоматты т‰рде) аударатындай етіп жасайды. Аударуды программа орындайды. Ондай программаны аѓылшын тілінде “транслятор” (аудармашы) деп атайды, ал аудару процесін “трансляция” дейді. Сондыќтан программаны жасанды тіл де пайдаланып жазѓан кезде комьпютердіњ ж±мысы екі кезењнен т±рады.

1. 
   Жасанды тілден машиналыќ тілге трансляциялау;
   
2. 
   Машиналыќ тілдегі программаны орындау.
   

1.Компиляция єдісі-алдымен жасанды тілдегі программа т‰гелдей машиналыќ тілге аударылады, сонан кейін б±л программа басынан орындалады.

2.Интерпретация єдісі- жасанды тілдегі программаныњ єрбір єрекеті (н±сќауы немесе амалы) жеке алдын ала аударылмастан бірден машиналыќ тілде орындала бастайды.

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

Сонымен осындай жасанды тілдер де комьпютерге т‰сінікті болады, сондыќтан оларды да біз программалау тілдері дейміз.

Ќазіргі кезде комьпютердіњ кµмегімен єрт‰рлі есептерді шыѓаруѓа м‰мкіндік беретін сан алуан программалау тілдері бар. Єр тілдіњ кемшілігі де, жетістігі де бар. Мысалы, кейбір тілде программаны жазу оњай болѓанымен оны орындау µте кµп уаќытты талап етеді немесе жадыныњ кµп орнын алады.