Жұмыс бағдарламасы мамандықтың жұмыс оқу жоспары және 20 ж бекітілген элективті пәндер каталогы негізінде әзірленген





Грамматиканы беру үшін жиі Бэкус-Наур қарапайым формасы (БНҚФ) деп аталатын көрсетудің көрнекі формасын қолданады.



Мысал ретінде предикаттар тілінің қатаң анықтамасын береміз немесе басқаша айтқанда тілдің синтаксисін береміз.

		(1-ші ереже: ақиқат)
		(2-ші ереже: жалған)
		(3-ші ереже: идентификатор)
		(4-ші ереже: теріске шығару)
		(5- ші ереже: дизъюнкция)
		(6- ші ереже: шартты Немесе)
		(7- ші ереже: конъюнкция)
		(8- ші ереже: шарттыЖәне)
		(9- ші ереже: импликация)
	e	(10- ші ереже: эквиваленттілік)

Берілген грамматиканың жалғыз метасимволы болып табылады, ал



Берілген грамматикадағы шығарылатын тізбектің мысалын келтірейік:





2-сурет – _предикатының шығыс ағашы

- аталған теорияның барлық пайымдауларын дәлелдеуге немесе теріске шығаруға бола (толықтығы туралы мәселе);

- белгілі-бір пайымдауды дәлелдеуге немес теріске шығаруға болатындығы (қарама-қайшы еместігі туралы мәселе) және т.б.

Әрбір логикалық есептеу төмендегідей сипатталады:

- символдар жиынтығымен немес алфавитімен;

- алфавиттің негізінде мағыналы пайымдаулардың немесе формулалардың ережелерімен;

- аксиомалар жүйесі деп аталатын белгілі бір формулалар жиынтығымен;

- ережелер жиынтығымен.

Алфавит және формулалар жиынтығы есептеулер тілін құрайды, ал формулалардың жасалуы есептеулер синтаксисын құрайды.

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

Логикалық есептеуді анықтаудың аксиомасы және ережелері формулалар жиынтығынан дәлелденетін формулаларды немесе теоремаларды анықтауға мүмкіндік береді. Оларға шығару ережелері арқылы алынған аксиомалар мен теориялар жатады.

Алгебра предикаты σ сигнатурасының формуласы:

σ сигнатурасын σ = σ₁Uσ₂ бірігуі түрінде белгілейік, мұндағы σ₁ операциялар формулаларының жиынтығы, σ₂ М предикатының бос емес символдар жиынтығы. σ₀ ішкі жиыны арқылы σ₁ жиынының нуль-арлы операцияларын белгілейік. Ол М жиынының кез-келген ішкі жиыны болуы мүмкін. Формуланы анықтау барысында белгі ретінде әр түрлі әріптер қолданылуы мүмкін (индекспен болуы да мүмкін): σ₀ жиынында a, d, c; σ₁ жиынында f, φ, ψ; σ₂ жиынында p, q. Сонымен қатар, x, y, z, u, v әріптерімен белгіленген (индекспен болуы да мүмкін) М жиынынан алынған Х символдар жиынтығы,, v, ->, ┐, ,  логиклық операцияларының жиынтығы және қызметтік символдар, яғни жақшалар алынуы мүмкін. Осылайша, формуланы шығару алфавиті ретінде келесі жиын қолданылады:
Ҩ = σ U X U O
Операциялар мен предикаттарға нақты мысалдарда жалпыға бірдей белгілер+, , *, =, ≤ қолданылады.

5 Гомоморфизмдер мен изоморфизмдер

Изоморфизм – математикалық нысандардың (объектілердің) не нысандар жүйесінің арасындағы сәйкестікті (қатысты), кейбір жағдайда олардың құрылысының теңдігін де көрсететін негізгі ұғымдарының бірі. Математикада изоморфтық ұғымы нақты алгебралық жүйелерге (ең алдымен топқа) қолдануға байланысты қалыптасты. Кейін ол математикалық құрылымдардың кең класына (мысалы, сақина, өріс, т.б.) қолданыла бастады. Изоморфты жүйелердің қарапайым мысалы ретінде, қосу амалы (x=x₁+x₂), берілген барлық нақты сандар (R) жүйесі мен көбейту амалы (y=y₁·y₂), берілген оң сандар жүйесі (R+) қарастырылады. Осы екі жүйенің ішкі “құрылысы” бірдей болатындығын дәлелдеуге болады. Ол үшін, R-дің x санын R+-дің y=ax, (a>1) санына сәйкес қоя отырып, R жүйесін R+ жүйесіне бейнелеу жеткілікті. Сонда x=x₁+x₂ сандарының қосындысы, x₁ және x₂ сандарына сәйкес келетін және сандарының y=y₁·y₂ көбейтіндісіне сәйкес келеді. R+-дің R-ге кері бейнеленуінің түрі мынадай: x=log_ay·R+ сандар жүйесінің қосындысына қатысты кез келген сөйлемнен оған сәйкес келетін R+ сандар жүйесінің көбейтіндісіне қатысты сөйлемді шығарып алуға болады. Мысалы, егер R-дегі арифметикалық прогрессия мүшелерінің қосындысы (s_n=x₁+x₂+...+x_n) мына s_n= формуласымен өрнектелсе, онда R+-дегі геометриялық прогрессия мүшелерінің көбейтіндісі (pn=y1·y2...yn) мына: pn= формуласымен өрнектеледі. Бұл жерде, R жүйесінен R+ жүйесіне ауысу кезінде: R-дегі n-ге көбейту амалы R+-дегі n-ге дәрежелеу амалына, ал екіге бөлу амалы квадрат түбір табу амалына сәйкес келеді. Топологияда маңызды рөл атқаратын гомеоморфтық ұғымы изоморфтық ұғымының дербес бір түрі болып есептеледі. Ал алгебралық жүйенің өзіне-өзінің изоморфтығы (бір мәнді бейнеленуі) автоморфтық деп аталады. “Изоморфтық” термині математикаға 19 ғасырдың ортасында енді. Оның қазіргі анықтамасы неміс математигі Э. Нeтердің (1882 – 1935) еңбектерінде қалыптасты.

Гомоморфизм (грек тілінен аударғанда ὁμός – тең, бірдей және μορφή – түр, форма) – бұл алгебралық жүйелер категориясындағы морфизм. Бұл негізгі операцияларды және негізгі қатынастарды сақтайтын А алгебралық жүйесінің бейнеленуі болып табылады.

сипаттамасы және топтарының гоморфизмі деп аталады, егер ол бір топтық операцияны басқа операциясына аударса.

Гоморфизм, изоморфизм және морфизм түсініктерін нақтылайтын біршама жалпы теориясы "Жиындар теориясы" атты кітабында Н. Бурбаки белгілі француз математиктер тобымен ұсынылған.

Анықтама:σ cигнатурасының ��₁=1,σ> және ��₂=2,σ> алгебралық жүйелері берілсін. Егер f: M_1⟶ M₂ бейнелеуі

1) g және h-m орынды алгебралық амалдары σ сигнатурасының m орынды F фукционалдық символының ��₁ және ��₂ алгебралық жүйелеріндегі сәйкес интерпретациялары болып, кез келген a₁,….,a_mϵ M₁ элементтері үшін f(g(a₁,….,a_m))=h(f(a₁),…..,f(a_m)) теңдігі орындалады.

2) Сәйкес M₁ және M₂ жиындарында анықталған P және S-n орынды қатынастары σ сигнатурасының қандай да бір n орынды R предикаттық символының ��₁ және ��₂ алгебралық жүйелеріндегі сәйкес интерпретациялары болса, кез келген a₁,….,a_mϵ M₁ элeменттері үшін қатынасы орындалғанда S(f(a₁),…..,f(a_n)) қатынасы да орындалады.

3) Егер a_k ϵ M₁ және b_k ϵ M₂ элементтері σ сигнатурасының c_k константа символының ��₁ және ��₂ алгебралық жүйелеріндегі сәйкес интерпретациялары болса, онда f(a_k)=b_k теңдігі орындалады. Шарттарын қанағаттандырса, онда f: M_1⟶ M₂ бейнелеуін ��₁ алгебралық жүйесінен ��₂ алгебралық жүйесі гомоморфизм деп аталады. M₁ жиынының f бойынша алғашқы бейнелері бар элементтер жиыны ��₁ алгебралық жүйесінің гомоморфрты бейнесі деп аталады. Ол элементтерден тұратын жиын σ сигнатурасының ��₂ алгебралық жүйесіне сәйкес интерпретациясы бойынша σ сигнатурасының алгебралық жүйесі болады. Бұл алгебралық жүйелер арасындағы гомомофризмді f: ��_{1 ⟶} ��₂ арқылы белгілейміз.

Егер f: ��_{1 ⟶} ��₂ гомоморфризм және f(M₁₎₌M₂ болса, мұндай гомоморфризм эпиморфизм деп аталады. Ал ��₂ алгебралық жүйесін ��₁ алгебралық жүйесінің эпиморфты бейнесі дейді.

Егер f: ��_{1 ⟶} ��₂ эпиморфизм және f өзара әрменді сәйкестік және екінші шарт екі жақты болса, оны ��₁ және ��₂ алгебралық жүйелерінің изоморфизмі деп аталады. Ал аралында изоморфизм болатын ��₁ және ��₂ алгебралық жүйелері изоморфты деп аталып, бұл жағдай ��₁=��₂ арқылы белгіленеді

Бұл анықтамалардан кез келген қатаң гомоморфизм ауқатты болып табылатыны анықталады.

Осы барлық түсініктердің дифференциалды меңгеру үшін келесілер бар болатынын көрсететін қарапайым мысалдарын өз бетінше құру болып табылады:

- биективті гомоморфизмдер, яғни, бірінші жүйенің негізгі жиынын изомоморфизмамдер болып табыламайтын екінші жүйенің негізгі жиынын бейнелейтін биективті гомоморфизмдер;

- не қатаң, не ауқатты болып табыламайтын гомоморфизмдер;

- ауқатты болып саналатын, бірақ қатаң емес гомоморфизмдер.

6 Формальды тілдердің синтаксистық құрамының алгебралық құрылымы

Логикалық есептеу белгілі бір формальды тілдің негізінде құрылады. Формальды тілдің құрылымы төменде келтірілген (А.Черч бойынша):

1) Тілде (алфавитте) қолданылатын біркелкі бөлінбейтін алғашқы символдар теріп жазылады;

2) Соңғы алғашқы символдардың тізбегі формулаға айналады (формулалар жиыны);

3) Барлық формулалардың ішінен белгілі бір ережеге сәйкес дұрыс құрылған формулалар анықталады, олардың кейбіреулері аксиома болып табылады (аксиомалар жиыны);

4) Қорытынды ережелерді шығару реті анықталады, дұрыс құрылған формулалардың ішінен қорытынды ретінде дұрыс құрылған формула анықталады (қорытынды ережелер жиынтығы).

Құрылған формальды тіл тиімділік талаптарына сай болу керек:

- кез-келген таңбаның бастапқы таңбаның (алфавиттың) бірі болып табылатынын тиімді анықтайтын әдістің болуы;

- кез-келген формуланың (алфавиттың символдарынан құралған) дұрыс құрылғандығын тиімді анықтайтын әдістің болуы;

- кез-келген формуланың (алфавиттың символдарынан құралған) аксиома болатындығын тиімді анықтайтын әдістің болуы;

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

Формальды тілді қолданудың ережесі адам түсінетін тілде берілуі керек (мұндай тіл метатіл деп аталады).

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

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

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

Формальды тілдердің құрылу әдісін анықтау кезінде, оның синтаксистық ерекшеліктерін және мүмкіншіліктерін зерттеу барысында студенттер индуктивты анықтамалардың спецификасымен танысады.

Атап айтсақ, базалық есептеулердегі (пікірлер есептеулері және предикаттар есептеулері) сөздердің синтаксистық құрылымының индуктивтық анализы (сөздердің реттілігі) бізге береді:

- аталмыш сөздің формула екендігін анықтау алгоритмін;

- аталмыш формуланың ішкі формулаларын жазу алгоритмін;

- соңғы формулалар тізімінің қорытынды тізім екендігін анықтау алгоритмін.

Аталған алгоритмдерді және соған ұқсас алгоритмдерді синтаксистік тұрғыдан зерттеудің мақсаты есептеуді жүргізетін үрдістердің бар болуын анықтау. Дәл осы кезде синтаксистық конструкцияның алгоритмдық мәні түсіндіріледі.

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

Студенттер алгебраны оқу барысыныда классикалық алгоритмның кең ауқымымымен танысады: қалдықпен бөлу алгоритмы, Евклид алгоритмы, Эратосфен алгоритмы, натурал санын жай сандар көбейтіндісі арқылы жазу, сызықтық теңдеулер жүйесін шешуде Гаус әдісін қолдану, Штурм алгоритмы нақты коэффициенті бар көпмүшенің нақты түбірлерін табу, т.с.с. Алгоритмның есептеу үрдісінің таза механизм түрінде өтуі (6.1-сурет):

- алгоритм соңғы өлшемдері берілген нұсқаулар жиынтығы;

- нұсқаулықтарды қолдана білетін және есептеуді жүргізе алатын есептеуіш (әдетте адам);

- алгоритм шексіз класстың бір типті есептерін шығаруда қолданылады;

- есептеуші нұсқаулықтарды қадам ретімен дискретті уақытта жүргізеді;

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

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

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

«::=»– белгісі «мүмкін осымен алмастырылады», «|»– «және» деп оқылады.

Алфавиттың символдары көп жағдайда терминальды символдар немесе терминалдар деп аталады және өзгертілмей жазылады. Басқа символдар арқылы анықталатын тілдік конструкцияның атауын (терминальды емес символдар немесе терминал емес) жазу барысында бұрышты жақшаға алыны жазылады («< », « >»). Мысалы, БНФ жазылған <Бүтін> конструкциясын жазу ережесі төмендегідей болуы мүмкін:

<Бүтін>::= <Белгі><Белгісі жоқ бүтін>│<Белгісі жоқ бүтін>

< Белгісі жоқ бүтін >::= < Белгісі жоқ бүтін ><Сан>│<Сан>

< Сан >::= 0│1│2│3│4│5│6│7│8│9

< Белгі >::= +│-

<Белгісі жоқ бүтін> конструкциясының кұрамында шексіз сандар болатындай көрсету үшін сол жақты рекурсия ережесі қолданылады. Бұл ережені қолдану нәтижесінде кез-келген цифр саны бар нақты санды алуға мүмкіндік береді.

Синтаксистық диаграммалар конструкцияларды құру ережелерінің көрнекті түрінде береді. Мұндай диаграммаларда алфавит символдар блогы овал рамкаларда, конструкциялар атауы тік төртбұрыштарда, конструкцияны құру ережелері – ұшында бағыты бар сызықтармен белгіленеді. Егер сызық блокқа бағытталған болса, онда аталып отырған конструкцияға сәкес символ енгізілу керек. Сызықтың тармақталуы басқа жағдайларды бар екенін білдіреді.

6.2-сурет <Бүтін> конструкциясының алғашқы екі ережесінің синтаксистық диаграммасы берілген. Диаграммада көріп отырғанымыздай бүтін сан белгі арқылы немесе белгісіз жазылуы мүмкін және шексіз цифрлардан тұруы мүмкін. Н.Вирт синтаксистық конструкцияны бейнелеуде осы синтаксистық диаграмманы қолданды, сондықтан конструкцияның мазмұны ұзақ әрі нақыт болмаса біз синтаксистық диаграмманы қолданатын боламыз.

Алфавиттың символдары арқылы синтаксис ережелеріне сәйкес әр түрлі конструкциялар құрылады. Оның ішінде ең қарапайым түрі <Идентификатор> конструкциясы (6.3-сурет). Бұл конструкция көптеген күрделі конструкцияларда бағдарлама объектілерінің (берілімдер өрісі, процедура, функция) атын көрсетуде қолданылады. Borland Pascal-да идентификатор латын алфавиті әріптері мен сандарының (астын сызу символын қоса) тізімі түрінде беріледі және міндетті түрде әріптен басталады, мысалы, аааа, Ы21, Parametral, _а т.с.с.

6.3-сурет – <Идентификатор> диаграммасының синтаксисы

7 Бағдарламалау тілдерінің семантикалық анализ технологиясы

Бағдарламалау тілінің семантикасы – машинаның еркін түрде берілген бағдарламаны қандай операциялар арқылы және қандай реттілікте орындау керектігін анықтауды білдіреді. Теориялық тұрғыдан формальды тіл дегеніміз белгілі бір шегі бар жолдар жиынтығы (7.1-сурет ).

Формальды тілдің семантикасын сипаттауда оның элементтерін қандай да бір модель түрінде көрсету керек, мүмкін басқа тілдің жолдары түрінде (7.2-сурет). Формальды тілдердің семантикасын сипаттау Г.Фрегенің композиция принципы негізінде жасалған, яғни жеке-жеке семантикалардың құрамы арқылы. Формальды тілдердің синтаксисы формальды грамматика арқылы беріледі.

Формальды тілдердің семантикасын сипаттауда көптеген модельдердің түрлері мен әдістері құрастырылған (7.1-кесте).

Семантикаларды сипаттаудағы аталған әдістердің барлығы белгілі бір типті бөліп қарастыру көзделген – мәндер категориясы (семантикалық категориялар, примитивтер), сол арқылы және соның негізінде белгілі бір семантикалық тілде одан да күрделі ұғым беріледі.

Программалау тілдерінің семантикасын сипаттауда үш әдіс кеңінен тараған:

1) Операциялық (абстрактілі машинаның бір күйден екінші күйге өтуі), мысалы, П.Лендин машинасы;

2) Аксиоматикалық (программаны құрайтын объектілер жиынтығы), мысалы, Хоардың аксиоматикалық әдісі мен Флойдтың индуктивты тұжырымдау әдісі;

3) Денотациялық (программаға қатысты абстракциялар функциясы), мысалы, Д.Скоттың семантикалық домендер теориясы.

Транслятор - қандай да бір программалау тілінде жазылған программалары объектілі тілде бейнеленген жұмыс істейтін программаға айналдыратын арнайы программа. Бұл анықтама трансляцияланатын программалардың барлық түрлеріне қатысты. Мұндай программалардың трансляциялау процесі бойынша өз ерекшелігі бар. Қазіргі уақытта трансляторлар негізгі 3 топқа бөлінеді:

- ассемблер;

- компилятор;

- интерпретатор.

Компилятор

Интерпретатор

Алгоритм ұғымын анықтауда негізгі үш бағытты қарастыруға болады.

Алгоритмнен тиімді есептеуге өтудің өзіндік артықшылығы бар. Себебі, алгоритмге қойылатын барлық талаптар есептелетін функциялардың жиынтығына да қойылады және есептелетін функциялар жиынтығы атауына ие болады.

Есептелетін функциялар классын келесідей көрсетуге болады. Алдымен қарапайым функциялар алынады:

- l(x) = x + 1 (жылжыту операторы),

- O(x) = 0 (нөлге айналдыру операторы),

- I_n^m(x₁, x₂,…, x_n) = x_m (жобалау операторы).

Барлық үш қарапайым функция барлық жерде анықталған және

интуитивты түрде есептеледі.

Тьюринг машинасының жұмысы.

Машинаның жұмысы ең алдымен төмендегілерді анықтау арқылы (бастапқы) жүзеге асырылыады:

- лентадағы сөздер, яғни, торға жазылған символдар тізбег (сөз тордағы осы символдарды солдан оңға қарай оқу арқылы алынады);

- басының орналасуы;

- машинаның ішкі күйі.

Осы үш шарттың жиынтығы (аталмыш жағдайда) конфигурация деп аталады. Әдетте бастапқы уақытта машинаның ішкі күйі q₁ жағдайында болады, ал машинаның басы лентаның оң немесе сол жағының бірінші клеткасында орналасы.

Лентаға берілген сөз q₁ жағдайында және машинаның басы бірінші сөздің басында берілген жағдайда алғашқы конфигурация деп аталады. Теріс жағдайда Тьюринг машинасы алғашқы конфигурацияға қолданылмайда деп есептеледі.

Басқаша айтқанда, бастапқы жағдайда конфигурация келесі түрде болады: торлардан құралған лентаның әрбір тор көзіне А алфавитінің симолдары орналасады, басы сол немесе оң жақтан бірінші торға орналасады және машина q₁ ішкі күйінде болады. Осы команданың орындалуы барысында алынған сөз бен басының орналасуы соңғы конфигурация деп аталады.

Рекурсия – программаның өзін-өзі шақыруы. Рекурсиялық процедураны қолданған программалар өзінің қарапайымдылығымен, көрнектілігімен және шағын мәтінімен ерекшеленеді. Рекурсиялы алгоритмдердің мұндай қасиеті рекурсиялы процедураның не істеу керек екендігін көрсетеді, ал рекурсиялы емес алгоритм қалай істеу керек екендігін көрсетеді.

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

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

Рекурсияның тереңдігі деп рекурсиялы шақырулардың максимал санын айтады.

Кез-келген Rec рекурсиялы процедурасы белгілі бір S операторлар жиынтығынан және бір немесе бірнеше рекурсиялы операторлардан тұрады.

Шартсыз рекурсиялы процедуралар шексіз үрдіске әкеліп соғады, бұл мәселеге аса назар аударған жөн, себебі, процедураны шексіз өзін-өзі шақыру мүмкін емес.

Осылайша, рекурсиялы процедураларға келесідей талап қойылуы қажет – рекурсиялы процедураны шақыру белгілі бір шартқа негізделуі керек және де ол рекурсияның белгілі бір деңгейінде жалған болуы керек.

Егер шарт ақиқат болса, онда рекурсия жалғасады. Жалған болған жағдайда рекурсия тоқтатылады және шақырылған процедуралық үрдістер рет-ретімен қайтарылады. Рекурсиялы процедура үш түрлі формада болуы мүмкін:

1. 
   рекурсия шақырылмас бұрын әрекеттердің орындалу формасы (рекурсиялық ағында);
   

S;

if шарт then Rec; end;

2. 
   рекурсия шақырылғаннан кейінгі әрекеттердің орындалу формасы (рекурсиялы қайтарым);
   

if условие then Rec;

S; end;

3. 
   рекурсия шақырылғанына дейінгі және кейінгі әрекеттердің орындалу формасы;
   

S1;

Рекурсиялы процедуралардың барлық формалары практика жүзінде қолданыс тапқан. Көптеген есептер, оның ішінде факториалды есептеу, рекурсиялы процедураның орындалуына көңіл аудармайды. Алайда, программисттың өзінің процедураның және функцияның орындалуын қадағалауды қажет ететін есептер классы бар. Ондай есептер көбінесе тізім түрінде және ағаш тәріздес есептерде кездеседі.

Есепті модульды шығару кезінде оны блоктарға бөлу арқылы шығарылады, осы орайда абстракция модульдың мазмұнын белгілі бір тілде орындалуына дейін анықтайды. Программалаудың модульды әдістерінің түрлері 9.1-суретте көрсетілген.

Бағдарламалаудың модульді (объектіге-бағытталған және «жоғарыдан – төмен») әдісін жақсы меңгеру үшін математиканың негізін білуді қажет етеді. Бағдарламалаудың модульді әдісінің математикалық негізін анықтау мақсатында, оқылатын пәндер мен логика-алгебралық ұғымдарының, терминдерінің арасында тезаурус түрінде салыстыру жүргіздік (9.1 кесте).

1	2	3	4
Ақпаратты жасыру	Модульдің ішкі детальдерінің орындалуына сырттан қол жетімсіз ететін процесс	М жиынын бөлу	М жиынының тек біреуіне ғана тиесілі p ішкі жиыны
Инкапсуляция	Объектінің ішінде деректер мен операцияларды біріктіру арқылы ақпаратты жасыру әдісі	Класстың қасиеті	Эквиваленттіліктің әр түрлі класстары қиылыспайды
Тектілік	Алдыңғы анықталған класстың қасиетін қабылдап алатын класстар арасындағы қатынас	Изоморфты алгебралар	Алгебраның бір типті және изоморфты деп аталады, егер сәйкес биективті көрініс бар болса
Полиморфизм	Программаның орындалуы барысында базалық класстан келіп шығатын деректің атауын өзі тектес класстармен байланыстыру әдісі	Алгебралардың гомоморфизмы туралы теорема	Айталық, алгебраның бір типті алгебраға гомоморфты көрінісі болсын. Онда, үшін түріндегі көрініс бар болады.

Объектіге бағытталған бағдарламалаудың (ОБП) негізгі қасиеттері:

- берілімдер типі объектілер классы ұғымымен алмастырылады;

- объектілер жүйедегі атқаратын міндетіне қарай әрекет ете алады;

- объектілер жалпы ортада өзара әрекеттеседі.

Берілімдердің аксиоматикалық анықтамасы және осы типке жататын объектілермен орындалатын әрекеттер ОБП-ның негізгі артықшылығы болып табылады.

Белгілі функцияға алгоритм құру кезінде «жоғарыдан – төмен» модульды әдісі арқылы шешіледі.

«Жоғарыдан – төмен» әдісі есептің бөліктерінің тізбектей төмендеуі негізінде құралған (9.2-сурет).

9.2-сурет – «Жоғарыдан - төмен» әдісінің схемалық көрсетілімі

Осылайша бағдарлама барысында рекурсия сол бағдарламаның өзіне негізделген, бірақ қарапайым берілімдерді қолданатын көмекші бөлігі деп қарастыруға болады.

Рекурсия екі түрлі жағдайда орындалуы мүмкін, біріншісі – рекурсиялы шақыру («күрделі» берілімдер жағдайы), екіншісі – рекурсиялы емес шақыру («қарапайым» берілімдер жағдайы.

Рекурсия және итерация. Рекурсиялы бағдарламаны кез-келген уақытта дәл сол есептеулерді орындайтын рекурсиялы емес бағдарламаға түрлендіруге болады және керісінше.

 Рекурсиялы бағдарламалардың құрылымы. Рекурсиялы есептеулердің формальды схемаларына келетін болсақ, онда кем дегенде екі шығару жолы беріледі. Бірінші жағдайда есептеуді жүргізу үшін рекурсиялы шақыру кезінде қарапайым берілімдерді қолданады. Екінші жағдайда берілімдердің қарапайымдылығы соншалықты рекурсияны қолданудың қажеті де болмайды.

Мысалы, факториалды анықтау мысал ретінде қарастыруға болады
 F(n) = {n*F(n-1), n> 1

{1, n = 1

{1, n = 1,2

{ a->c , n = 1

Рекуррентті өрнекті көп жағдайда рекурсиялы есептеудің күрделілігін анықтауда қолданады.

Мысалы, рекурсивті схема арқылы Фибоначчи сандарын анықтауда.
F(i) = F(i-1) + F(i-2), при N >= 1; F(0) = 0; F(1) = 1;
Бағдарла мәтіні шамамен төмендегідей болуы мүмкін.
Function F( n : integer ) : longint;
begin
   if n < 2 then F := n

else F := F(n-1) + F(n-2)

end;
Есептеу барысында F(N) мәнін қажет ететін рекурсиялы шақырудың санын келесі рекуррентті өрнекті шешу арқылы анықталады
T_N = T_N-1 + T_N-2, при N >= 1; T₀ = 1; T₁ = 1

T_N шамамен Ф^N тең, мұндағы Ф^N –орташа пропорция, яғни жоғарыда келтірілген бағдарлама экспоненциалды уақытты жұмсауды қажет етеді.

Мысал ретінде N элементтен тұратын Item типті a[1], . . . , a[N] массивіне сақталған максимал элементті анықтауды қарастырайық. Бұл есеп массивті бір рет қарапшығу арқылы шешіледі:

if a[i] > Max then Max:=a[i];

m:= (l+r)/2;

if (l = r)

then Max:= a[l]

else begin

u := Max (a, 1, m);

v := Max )a, m+1, r);

if (u > v) then Max:= u else Max:= v

end;

end;
Көп жағдайда «бөліп ал да басқар» әдісін итерациялы алгоритмдерге қарағанда тез шешуді жүргізгендіктен қолданылады. Бірақ бір маңызды кемшілігі де бар, бағдарламаны өзара тәуелсіз ішкі бағдарламаларға бөлінуі. Ішкі бағдарламалар тәуелсіз болған жағдайда есептеуге көп уақыт жұмсалады.

Аталған мәселені динамикалық бағдарламалау арқылы шешуге болады.

Статистикалық K[1..100] массивінде мәндерін сақтай отырып, біз есептеулердің қайталануын болдырмаймыз.

Төменде келтірілген бағдарлама F(N) - ды N - ғы пропорционал уақытта есептейді.
Function F(n: integer): longint;

Begin

then F := K[n]

else if n < 2

then F := n

else begin

t := F(n-1) + F(n-2)

K[n] := t;

F := t

Аталған класстар абстракциялар классы деп аталады, ал бөліктерге бөлу (класстар отбасы) – осы қатынасқа сәйкес фактор - жиыны болып табылады. Абстракцияның бұл принципі абстракцияның екі процессін көрсетеді: біріншіден, класстар теңдігі сияқты абстаркция ұғымын енгізу; екіншіден, сондай класстың объектісіне қатысты «абстракция» ұғымын енгізу.

Рекурсия арқылы есепті шығарудың критерийлері:

- рекурсиялы функция өз-өзін шақырады;

- әрбір рекурсивті шақыру сол сияқты есептің азайтылған түрін шығарады;

- базисты шарттарды тексеру рекурсия үдерісін тоқтатуға мүмкіндік береді;

- есептердің біреуі ғана базисты болып табылады.

Программалаудың рекурсиялы әдісі рекурсиялы функциялардың

теориясы туралы білімді қажет етеді. Программистердің бағдарламалау барысында рекурсиялы функциялардың қолданудағы мүмкіндіктер 9.2-кестеде келтірілген.

9.2-кесте – Бағдарламалауда рекурсиялы функциялардың рөлі

Рекурсиялы функциялар	Бағдарламалауда қалай қолданылады
Примитивті рекурсивты функциялар – қарапайым функцмяға рекурсияны қолду арқылы алынатын функциялар ( – нөлге тең функция, – келіп шығу функциясы, – аргументті таңдау функциясы)	Примитивті функциялар арифметикалық опреацияларды, шарттық операторды және арифметикалық циклды қолданатын программалық функцияларға сәйкес болады (итерация саны алдын ала белгілі шарттық оператор)
Жартылай рекурсивты функциялар дегеніміз – примитивті функцияны қолданатын функцияларды айтады. Кез-келген примивті рекурсивты функция жартылай рекурсиялы болып келеді, себебі, жартылай рекурсивті функцияны құрайтын операторлардың құрамына примитвті рекурсиялы функцияны ұйымдастыруға арналған операторлардан тұрады.	Егер программалау барысында итерация саны алдын ала белгісіз және шексіз болуы мүмкін while шарттық операторын қолданатын болсақ, онда жартылай рекурсивты функциялр класына өтетін боламыз Жартылай рекурсивты функциялар аргументтің кейбір мәндерінда анықталмауы мүмкін.
Ортақ рекурсиялы функциялар – барлық жерде анықталған жартылай рекурсивты функциялар	Примитивті рекурсивті функция барлық жерде анықталған сондықтан жалпы рекурсивті функция болып табылады.

Программалауда белгілі бір тілді жеткілікті түрде меңгеру төмендегідей білімді қажет етеді: (1) алгоритмді және берілімдер құрылымын; (2) программалау парадигмаларын; (3) тілдің синтаксисы мен оның операциялық және дедуктивті жүйесін; (4) программалау құралдарын жасау технологияларын; (5) программалаудың психологиялық аспектілерін.

Объектілі программалаудың принциптері

1. 
   Абстракциялау
   

Абстракция деңгейлері:

- өзін-зі ұстау абстракциясы;

- виртуалды машинаның абстракциясы;

- ерікті абстракция;

- бар болу абстракциясы.

Контрактімен орындалатын барлық перация сигнатурамен сипатталады, оған параметрлер типі мен қайтарылатын мәннің параметрі.

Инварианттың өзгеруі абстракциямен байласынты контрактыны бұзады. Егер алғышарт бұзылса – клиент, егер кейінгі шарт бұзылса – сервер кінәлі болады. Осындай жағдайда ерекше жағдайлар қарастырылады.

2. Қолжетімділікті шектеу (инкапсуляция)

Қолжетімдікті шектеу абстракциялар арасында кедергі орнатады. Осы принципке сәйкес интерфейс және іске асыру ұғымдары енгізіледі.

Іске асыру нәтижеге жету механизмін сипаттайды және абстракциялы бейнені көрсетеді.

Модульдік принципі әр түрлі деңгейде қолданылады. Бағдарламаны келесі құрамды бөліктерге бөлу:

Иерархияның екі түрі белгілі:

- Тектілік (класстар иерархиясы);

«Типі» байланыс сөзі қолданылады.

- агрегациялау(объектілер иерархиясы);

«Бар болу» байланыс сөзі қолданылады.

Стандартты тектіліктің екі түрі бар:

- таксономия (қасиеттердің тектелуі );

- партномия (бөліктердің тектелуі).

С++ стандартты тектелу осы екі типті біріктіреді.

Көп жағдайда келесі мәселе туындайды – екі класс арасында қатынасты қалай іске асыру.

Тектіліктің мақсаты:

1) специализация үшін (ішкі типтердің туындауы үшін);

2) спецификация үшін;

3) конструкциялау үшін. Базалық класста жаңадан құрылған класста орындалатын әрекеттер көрсетіледі (яғни жаңа класста базалық әрекетті орындау керек болса).

Мысалы, тізімге негізіндегі жиын.

Тізім – private() спецификаторымен тектелетін базалық класс.

4) кеңейтілу үшін. Жаңа құрылатын класста қажетті

функциялар қосылады немесе интерфейс

кеңейтіледі.

Мысалы, жаңа класста жолдарға арналған интерфейс қосылады.

DEQUE – стек үшін базалық класс (LR екі ұшы бар кезек)

1) көшірілетін базалық класстың өрістері (мысалы үшін В класы);

2) әдістердің және конструкторлардың көшірілуі.

3.Типизация

Типизация – программалау тілінің алғашқы деңгейінің операцияларына класстардың өзара ауысуын шектеу.

Типизиция деңгейіне қарай программалау тілі үш түрге бөлінеді:

- қатаң типизацияланған (Pascal, Ada);

- қатаң емес типизацияланған (java, c++);

- типтелген емес (Smalltalk).

Типизация деңгейімен полиморфизмді жүзеге асыру мүмкіндігі байланысты. Қатаң типтелген тілдерге миноморфизм сәйкес. Басқалар үшін – полиморфизм.

Полиморфизм – әр түрлі класстар объектілерімен жұмыс істеуге бір атауды қолдану мүмкіндігі.

Полиморфизмнің екі түрі қарастырылған:

- қарапайым («класс» типті жалғыз параметр қолданылуы мүмкін);

- жиындық (бірнеше параметрді қолдана алады).

Объектіге бағытталан програмалаудағы негізгі параллельділік ол үдеріс пен объектінің арасындағы қатынас болып табылады.

Үдеріс – рет-ретімен орындалатын әрекетер тізбегі. Үдерістің төмендегідей түрлері бар:

- тізбектей – бір уақытта бір ғана үдеріс жүргізіледі;

- квазипараллельді – бір уақытта көп үрдістер болуы мүмкін, бірақ орындалатыны біреуі ғана.

- параллельді

ОБП тілдерінің параллельділікті қолданатындар келесі түрге бөлінеді:

- ортогональды – параллельділік құралдары объектілі қатысты емес. (мысалы, Smalltalk80, Concurrent C++).

- біртекті – объектілер параллелінің бір типті болуы.

Параллельділіктің басқа да түрлерінің болуы мүмкін.

Объектінің үдерісті құрылымы:

- статистикалық;

- жалғызүдерісті (мысалы, Actor);

- көпүдерісті ;

- квазипараллельді (мысалы, Hybrid);

- параллельді;

- динамикалық (мысалы, S80);

Параллель объектілердің өзара қатынасы және жүзеге асырылуы төмендегідей жүргізіледі:

- объектіні құру;

- белсендіру;

- синхрондау;

- хабарлама алмасу.

Синхрондау механизмдері:

- Хоар мониторлары – берілімдерді жіберу мүмкінідігін қамтамасыз ететін жоғары деңгейлі механизм;

- Дейкстр семафорлары – ресурстарға қол жеткізу құралдары;

- рандеву – негізгі міндеті есептерді синхрондау (Ada-да жүзеге асырылыған).

Хабаралмасу механизмдері:

- жадының ортақ бөлігі;

- хабарламаны жіберу және қабылдау (тепе-теңдік, бағытталған);

- процедураны алыстан шақыру («клиент-сервер» қағидасымен бағыну).

Тұрақтылық деңгейлері:

- өрнектің мәнін есептегендегі аралық нәтижелер (өрнек есептелу барысында ғана болады);

- локальды айнымалылар;

- глобальды айнымалылар;

- программаны сынақтау арасындағы объектілер;

- программа версиялары арасындағы объектілер;

- бағдарлама болмаған кездегі объектілер.

Верификация мен валидацияның негізгі міндеті бағдарламалық қамсызданудың сапасын қадағалау және оның қателерін табуға бағытталған. Мақсаты бір болғанымен тексеру барысында әдістерінде, ережелерінде айырмашылықтары бар.

Верификация жұмыс барысында жасалған артефакттардың бұған дейін жасалған немесе негізге алынған артефакттарға сәйкестігін және олардың ережелерге және стандарттарға сәйкестігін тексереді. Верификация стандарттың нормалары арасында сәйкестігін, ПО қатысты қойлатын талапқа сәйкестігін, жобалық шешілуі, бастапқы кодының, қолданылған құжаттардың сәйкестігін тексереді. Сонымен қатар қойылған талаптар, құжаттар және коды аталып отырған мемлекеттің нормалары мен стандарттарына сай екендігін тексереді.

1. Программаның спецификациясын құру үшін түрлі айнымалы болуы қажет: енгізу, программалық, шығару айнымалылары.

Енгізу айнымалылары алғашқы деректерді, программалық айнымалылары арқылы нәтижелерді, ал шығару айнымалылары соңғы нәтижелерді, беруге арналған. Осы айнымалылар сәйкес векторларды топатаса алады:

- мәндері алғашқы кезеңде белгілі болатын және программаны орындау кезінде өзгермейтін енгізу айнымалыларынан тұратын енгізу векторы. Х=( х_1, х_2,..., х_к );

- мәндері программаның орындалу барысында арлық жағдайда айқындалатын, программалық айнымалылардан тұратын орындалу векторы; Y= (y, y₂,…, y₁ );

- мәндері программаның соңғы жағдайында айқындалатын, шығару айнымалыларынан тұратын шығару векторы, Z=(z₁,z₂,…, z_m).

Программа Р үшін енгізу векторлары мәндерінің жиыны inp(p), орындалу векторлар мәндерінің жиыны ran (p), шығару векторлары мәдерінің жиыны out(p) арқылы белгіленеді. Осы жиында бос емес, яғни,
Inp(p)

Сәйкесінше, әр программалық бірлік р_t, tn, үшін бос емес жиын inp (p)6 out (p₁), белгілеуге болады.Мұнда,

Ip (p₁)=inp out(p_n) = out (p)

Сонымен қатар, үшін

Inp(p₁) ran (p), out(p₁) ran(p)

Егер осы векторлардыңмәнін анықтайтын функция val болса, онда:

Val (x) =,val (y) = , val (x)=,

Мұнда inp (p), out (p).

Енгізу векторының мәні туралы және Р програмасының бастапқы жағдайын анықтайтын і_р(х) тұжырымды алғышарт деп атайды яғни, і_р (х): inp (p) {0,1},

Мұнда 0- логикалық “жалған” мән, ал, 1- логикалық “ақиқат” мән.

Енгізу және шығару векторларының байланысы туралы және программаның аралық жағдайын анықтайтын r_p(x,y), t=2,n- 1

Тұжырымды аралықшарттар деп атайды, яғни,

R_p1(x,y): inp (p) {0,1}

Анықтама 1. Р программасы і_р (х) - те аяқталады дейді, егер кез- келген Х үшін і_р (х) ақиқат болса және Р программасын орындау оның соңғы жағдайына алып келетін болса, яғни, Р(Х) анықталған.

Анықтама 2. Р программасы і_р (х) анықталмаған дейді, егер Р программасында шексіз орындауды талап ететін қандай-да бір құрылым бар болса, яғни, Р(х) анықталмаған.

Анықтама 3. Р программасы і_р (х) мен о_р (Х,Z) - ке қатысты дербес дұрыс дейді, егер кез-келген Х үшін і_р (х) ақиқат болатындығынан және Р программасын орындау і_р (Х) – те аяқталатындығынан о_р (x,z)-ң ақиқаттығы шығатын болса.

Егер Р программасының і_р (х) мен о_р (Х,Z)-ке қатысты дербес дұрыстығын і_р {P} o_p деп белгілесек, онда ол формалды түрде былай анықтайды.

і_р {P} o_p[( і_р (х) &p(x)=z) o_p(x,z)] мұнда - анықтама бойынша деген таңба.

Анықтама 4. Р программасы і_р (х) мен о_р (Х,Z) – ке қатысты толық дұрыс дейді, егер кез- келген Х үшін і_р (х) ақиқат болатындығынан Р программасын орындау і_р (х)- те аяқталатындығы және о_р (Х,Z) –ң ақиқаттығы шықса.