ЕМЕС, ЖӘНЕ, НЕМЕСЕ ункцияларының ақиқаттық кестесі

Тарихи жағынан «алгоритм» термині ІХ ғасырда өмір сүрген шығыс математигі Мухаммед ибн Муса әл-Хорезми тегінен шыққан. Ол алғаш негізгі төрт арифметикалық амалдың ережесін құрастырған. Алдымен осы ережелер алгоритмдер деп аталып, кейіннен термин ары қарай дамуын ең алдымен математикада жалғастырды – алгоритм деп қандай-да бір бастапқы мәліметтер класына бірдей орындалатын есептеулер тәсілі атала бастады, мысалы, функцияның туындысын табу. Математикаға оқытудың маңызды міндеттерінің бірі жалпы есептеу алгоритмдерін меңгерту болып табылады. Басқаша айтқанда, егер мектеп оқушысын екі санды бағанмен көбейтуге үйретсе, бұл жерде оған тек сол екі санды көбейтуді ғана емес, жалпы кез-келген екі санды көбейтуге қолданылатын әмбебап тәсілді (алгоритмді) үйретуде дегенді білдіреді. Мұндай мысалдарды көптеп келтіруге болады. Тек математикада ғана емес – «алгоритм» термині жалпы қоданысқа ие болды. Осыған байланысты сұрақ туындайды: алгритмнің жалпы және нақты анықтамасын құруға болды ма («кез-келген алгоритм» ұғымы )? Мысалы осы анықтаманы пайдаланып, қандай-да бір нұсқаулар жиынтығы алгоритм бола алатындығын немесе бола алмайтындығын анықтауға бола ма? Егер дұрыс мағынада айтсақ, алгоритм дегеніміз – қандай-да бір класстың кез-келген есебін шешуді қамтамасыз ететін, нақты анықталған (бірмәнді), қарапайым (элементар) әрекеттер тізбегі. Бірақ бұл анықтаманы алгоритмнің қатаң анықтамасы ретінде қабылдауға болмайды. Себебі оның ішінде басқа анықталмаған ұғымдар қолданылған – бірмәнділік, қарапайымдылық және т.б. Бұл ұғымдарды алгоритмге тән жалпы қасиеттерді көрстеу арқылы жетілдіруге болады. Оларға төмендегі қасиеттер жатады:

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

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

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

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

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

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

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

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

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

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

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

«Кез-келген алгоритм» ұғымының нақты анықтамасын, яғни, алгоритмнің барлық ойға келетін түрлері жатқызылатын максималды жалпы анықтамасын құру қажеттілігі осылайша туындады. ХХ ғасырдың 20-шы жылдарында алгоритмнің нақты анықтамасын құру мәселесі маңызды математикалық мәселелердің біріне айналды. Бұл анықтама бір жағынан алгоритмнің интуитивті түсінігінің маңызына сәйкес келуі қажет болса, екінші жағынан формальды түрде қатаң болуы қажет болды. Осындай түсінікті құрастыру әрекеттері ХХ ғасырдың 30-шы жылдарында алгоритмдер теориясының өз алдына жеке ғылым болып қалыптасуына әкелді. Бұл ғылым математикалық логикамен бірге математиканың негізгі құралдарын – дәледеу тәсілдерін, аксиоматикалық теорияны құру тәсілдерін, математикалық процедуралардың қасиеттерін және т.б. қарастырады. 40-шы – 50-ші жылдарда есептеу техникасы мен оның функционалдануы мен қолданылуына байланысты ғылымдардың қарқынды дамуы кезінде осы ғылымдардың негізінде алгоритмдер теориясы жататыны анықталды, себебі компьютер алгоритмдер түрінде көрсетілетін процедураларды ғана жүзеге асыра алады. Кез-келген программа алгоритмнің орындаушы – компьютер «түсінетін» тілде жазылуы. Осылайша практикалық тұрғыдан алғанда да алгоритм ұғымын жетілдіру маңызды болып табылады.

Алгоритм түсінігін жетілдіру алгоритмдік модельдер аясында жүргізіледі. Модель есепті шешу кезінде қолдануға болатын құралдар жиынтығын көрсетеді, яғни, элементар қадамдар тізімін, келесі қадамды анықтау тәсілін, т.б. Алгоритмдік модельдер теориялық және практикалық болуы мүмкін. Теориялық тұрғыдан алғанда модельдердің бір жағынан әмбебап болғаны, яғни, кез-келген алгоритмді сипаттауға мүмкіндік бергені, екінші жағынан неғұрлым қарапайым болғаны, яғни, есепті шешудің неғұрлым аз құралын пайдаланғаны ерекше қызығушылық тудырады. Қарапайымдылық талабы алгоритмнің нақты қажет элементтері мен қасиеттерін ерекшелеп, осы қасиеттер туралы жалпы тұжырымдарды дәлелдеуді қамтамасыз ету үшін маңызды. Практикалық және қолданбалы модельдерде программалаудың қолайлылығы мен есептеу тиімділігі маңыздырақ, сондықтан олардың құралдары – қарапайым қадамдар жиынтығы, т.б. - әлдеқайда көп және күрделірек, бұл теориялық анализді қиындатады.

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

Екінші бағыт машиналық математикамен бай»ланысты.

Алгоритм орындаушысы – алгоритмде көрсетілген әрекеттер тізімін орындауға қабілетті субъект немесе құрылғы. Әрбір орындаушыға әрекеттерді орындауға нұсқау – арнайы тілдер арқылы беріледі. Мұнда әрекеттерді көрсететін қызметші сөздер, сол сияқты оларды біріктіретін синтаксикалық ережелер, командалар жиынтығы орындаушының командалар жиынтығын (СКИ) құрайды.

Дискретті информацияны өңдеудегі қарапайым бір белгіні екіншісімен ауыстыру болып табылады. Бірақ қарапайым әрекеттер тізімін орындайтын абстрактілі және шынайы құрылғы жасауға болады. Орындаушыға арналған мұндай алгоритм құру барысында интегралданған командалар тізбегін көрсету жеткілікті, ал оларды шын қарапайым командалар тізбегіне түрлендіруді орындаушы өзі атқарады. Мұндай алгоритмдеудің «көпсатылылығы» компьютерді басқару барысында көп қолданылады.

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

Мнемониктерді машиналық командаларға аударуды – ассемблер программасы жүзеге асырады. Программист орындаушы ретінде осы тілмен жұмыс істейді. Қарапайым әрекеттерді біріктіретін командалар жоғары деңгейдегі программалау тілдерінде көрінеді. Мысалы, «Write» сөзін программа текстінде жазу жеткілікті. Ал транслятор оларды қарапайым қадамдарға айналдырады. Программистке қарағанда бұл жағдайда орындаушы программалау тілінің трансляторы есептеледі. Бұдан жоғары қарапайым интеграциялау деңгейлерін қолданбалы программалардан көреміз. Бұл жерде ақырғы пайдаланушыға қарағанда қолданбалы программа орындаушы болып тұр. Мұндау орындаушының командалар жүйесіне барлық басқару командалары кіреді, яғни меню, экрандық батырмалар және т.б. интерфейс элементтері.

Бір команданы орындау күрделі әрекеттердің тізімін орындауға әкеледі, мысалы текстің көп жолдарын туралау.

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

7.3 Алгоритм абстрактілі машина ретінде
7.3.1 Жалпы қырлары

Бөлікті рекурсиялы функциялар класының нақты сипаттамасы Черч тезисімен бірге алгоритм үғымын жетілдіру туралы есептің мүмкін шешімдерінің бірін береді. Бірақ, бұл шешім толықтай тура емес, себебі есептелінетін функция ұғымы алгоритм ұғымына қатысты екінші болып тұр. Алгоритм ұғымы анықтамасының өзін тікелей жетілдіріп алып, содан кейін оның көмегімен есептелінетін функциялар класын нақты анықтауға болмай ма деген сұрақ туындайды. Іздеудің мұндай бағыты басқа алгоритм модельдерінің класын құруға әкелді. Оның негізгі идеясы келесіден тұрады: алгоритмдік процесстер – бұл белгілі бір үлгі бойынша құрылған, осылайша жеке амалдарды адамның орындауын модельдейтін машиналар орындайтын процесстер. Мұндай машинаның қызмет етуі (функционирование) қандай-да бір алгоритмнің орындалуы болып табылады. Алгоритмнің қасиеттерінен мұндай машиналарға жалпы талаптарды құруға болады:

1. 
   олардың функционалдану сипаты дискретті болуы тиіс, яғни әрбіреуі алдыңғысы аяқталған соң ғана орындалатын жеке қадамдардан тұруы керек;
   
2. 
   әрекеттері детерминирленген болуы керек, яғни, қадамдар қатаң тәртіппен орындалады, ал олардың нәтижесі қадамның өзінде және алдыңғы қадамдардың нәтижесімен анықталады;
   
3. 
   жұмыс басталмас бұрын машинаға алгоритмнің анықталу облысынан бастапқы мәліметтер беріледі;
   
4. 
   машинаның шекті қадамдар санынан кейін нәтиже алынуы тиіс (немесе нәтиже ретінде нені есептеу керектігі жөнінде ақпарат);
   
5. 
   машина әмбебап болу керек, яғни оның көмегімен кез-келген алгоритмді орындауға болатындай болуы керек;
   

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

Айталық, алгоритмнің анықталу жүйесінен алынған берілгендер А алфавитінің көмегімен көрсетілсін және {a1…a n} белгілерінің шекті тізбегін құрсын – мұндай тізбек сөз деп аталады. Алгоритмді орындау нәтижесінде басқа В алфавитінде көрсетілген жаңа {b1…bm} сөзі құрылсын. Бір қарағанда мұндай түрлендіру кезінде элементар болып келесі амалдар (қадамдар) ерекшеленеді:

1. 
   ai бастапқы сөзінің бір белгісін В алфавитінен алынған bj белгісімен ауыстыру;
   
2. 
   бастапқы сөздің белгісін өшіру;
   
3. 
   бастапқы сөзге В алфавитінің белгісін қосу;
   

Абстрактілі машина ретіндегі алгоритм концепциясын (1936-1937 жылдары) ағылшын математигі Алан Тьюринг және оның американдық әріптесі Эмиль Пост бір уақытта дерлік ұсынды. Олардың маңыздылығының тағы бір себебі – олар тек 8-9 жылдан кейін пайда болған мәліметтерді өңдеуге арналған шынайы құрылғылардың (есептеуіш машиналардың) негізгі принциптік сипатын болжап білді.

Шындығында, Тьюрингтен айырмашылығы Пост «машина» терминін қолданбаған, өзінің моделін алгоритмдік жүйе деп атаған. Біз екі автордың да ойларының бір екенін айта отырып, әдебиеттерде көрсетілгендей Пост машинасы туралы айтамыз.

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

Шолынулы секцияның үстіндегі головканы «» таңбасымен, ал белгіні секцияның ішіндегі «М» таңбасымен белгілеуге шарттасайық. Бос секцияда ешқандай белгі болмайды. Бір тактіде (оны қадам деп те болады) головка бір секцияға оңға немесе солға жылжып, белгіні қоя немесе өшіре алады. Пост машинасының жұмысы берілген жеке командалардан құрылған программа бойынша машинаның бір қалпынан екіншісіне өтуінен тұрады. Әрбір команда келесі құрылымға ие: xKy, мұндағы х – орындалатын команданың нөмірі; K – орындалатын әрекет туралы нұсқау; у – келесі команданың (ізбасардың) нөмірі. Келесі кестеде 6 әрекеттен тұратын машинаның командалар жүйесі берліген:

• 
  командасы тек бос секцияда ғана орындалуы керек;
  
• 
  командасы тек толтырылған секцияға қолданыла алады;
  
• 
  Кез-келген (y) командасының ізбасарының номері міндетті түрде осы программада бар команданың номеріне сәйкес келуі керек.