АЛГОРИТМНІҢ ПРАКТИКАЛЫҚ АСПЕКТІЛЕРІ. АВТОМАТТАР ТЕОРИЯСЫ

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Реферат
Тегін: Антиплагиат
Көлемі: 11 бет
Таңдаулыға:

Мазмұны:

Кіріспе 3
Негізгі бөлім 4Практикада алгоритмдерді құру 4Автоматтар теориясы 5Тьюринг машинасы 6Пост машинасы 9
Қорытынды 11
Пайдаланылған әдебиет 12

КІРІСПЕ

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

Адам жас кезiнен бастап күнделiктi өмiрде алгоритмдi меңгередi және орындайды. Яғни, алгоритм дегеніміз - жеке қадамдардан тұратын, формальды түрде жазылған реттелген нұсқаулар тізбегі. Алгоритм- бастапқы берілген мәліметтермен бір мәнде анықталатын нәтиже алу үшін қай амалды (жұмысты) қандай ретпен орындау қажеттігін белгілейтін есептерді (мәселелерді) шешу (математикалық есеп-қисаптар орындау, техникалық объектілерді жобалау, ғылыми-зерттеу жұмысын жүргізу т. б. ) тәсілдерінің дәл сипаттамасы. Алгоритм - математика мен кибернетиканың негізгі ұғымдарының бірі. Агоритмді орындау алгоритмдік процесс деп аталады.

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

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

ПРАКТИКАДА АЛГОРИТМДЕРДІ ҚҰРУ

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

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

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

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

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

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

Элементарлы әрекеттерді біріктіру командалары жоғары деңгейдегі программаларда пайда болды. Тіл трансляторы берілген команданы элеменарлы қадамдарға аударады.

Одан гөрі элементарлы командаларды интеграцилауды қолданьалы программалар орындайды. ОКЖ - і мәзір, перне, терезе т. б. интерфейсті басқару командаларынан тұрады.

Алгоритм абстрактілі машина іспеттес.

АВТОМАТТАР ТЕОРИЯСЫ

Автомат (гр. autoatas - өздігінен әрекет жасайтын) - ішкі механизм арқылы өздігінен жұмыс істейтін қондырғы; белгілі бір жұмыс процесін алдын ала белгіленген бағдарлама бойынша, адамның тікелей араласуынсыз, өздігінен атқаратын машина, құрылғы, тетік немесе олардың жиынтығы болып табылатын агрегаттар. Олар белгілі бір есептерді шешуге бағытталған болғандықтан, есептеуіш техника құбылысымен іспеттес. Автомат ұғымын дискреттік математика зерттейді, оның ішінде автоматтар теориясы математикалық модельдеу мен оның шешу жолдарын зерттеп анықтайды. Дискреттік математика - математиканың дискретті құрылымдардың қасиеттерін зерттейтін саласы. Мұндай құрылымдарға шектеулі топтар, шектеулі графтар, сондай-ақ, ақпаратты түрлендіргіш кейбір матемематикалық модельдер, шектеулі автоматтар, Тьюринг машинасы, т. б. жатады.

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

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

ТЬЮРИНГ МАШИНАСЫ

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

Тьюринг машинасымен жұмыс істеу үшін объектілер туралы ұғымдарға тоқталу қажет.

Әлдебір алфавиттен алынған әріптердің кез келген тізбегі осы алфавитте сөз деп аталады.

Сөздегі әріптердің саны сөз ұзындығы деп аталады. Әріптері жоқ сөзді бос сөз дейді. Олар « » немесе деп белгіленеді.

Әлемдегі барлық объектілерді әртүрлі алфавиттегі сөздер түрінде қарастыруға болады. Сондықтан алгоритмнің жұмыс істеу объектілері сөздер болып табылады.

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

Әрбір Тьюринг машинасында 2 бөлік бар:

Ұяшықтарға бөлінген екі жағынан да шексіз лента
Автомат - жазу/оқу инесі

Тьюринг тезисі : Кез келген алгоритм үшін сәйкес Тьюринг машинасын құруға болады.

Тьюринг машинасы деп жүйесін айтады. Мұндағы: А - шекті -жиын, Тьюринг машинасының алфавиті, - А алфавитінің бос сөзі, Q -Тьюринг машинасының жағдайын білдіретін шекті жиынның элементі, q ₁ - ТМ-ның бастапқы

жағдайы, q ₀ - МТ-ның тоқтау жағдайы, пассивті жағдай, Т-МТ-ның жылжу жиыны, - МТ-ның программасы.

Алгоритм (Тьюринг бойынша) - қойылған есепті шешуге келтірілетін Тьюринг машинасына құрылған программа.

Тьюринг машинасы мен тезисі болашақта да қолданылады, себебі кез келген проблема шешілмейді деп айтуға болмайды, шешілмейтін есеп болмауы керек, оны қандай да бір шешілетін түрге келтіру керек, соған орайластырылған алгоритм құрастыру керек.

Машинаның белгілі бір процесті орындауының өзі алгоритмдік процесс болып табылады. Сондықтан алгоритмге қойылатын талаптар мен қасиеттер оны орындайтын машинаға да қойылады:

Машинаның жұмысы дискретті, бірінен кейін бірі орындалатын жеке - жеке командалармен орындалуы керек.
Әрекеттер детерминделген, яғни қадамдар қатаң реттелген, ал олардың нәтижесі алдыңғы қадамда алынған нәтижелермен тікелей байланысты болуы керек.
Жұмыс алдында алғашқы берілгендер алгоритмнің анықталу облысынан алынуы керек.
Саны санаулы қадамдарды орындаудан соң нәтиже алынуы керек.
Машина универсалды, жан - жақты болуы керек, оның көмегімен кез - келген алгоритмді орындайтын болуы керек.

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

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

Ережелерінің ақырлы кез келген жүйесі.

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

Алгоритмді орындау барысында жаңа сөз құрылады { }, олар В алфавитін құрайды. Бұл алмастыруды жүргізу үшін келесі қадамдар орындалады:

Бастапқысөзінің бір сөзін В алфавитінентаңбасымен алмастыру.
Бастапқы сөздің таңбасын өшіру.
В алфавитінен бір таңбаны бастапқы сөзге қосу.

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

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

ПОСТ МАШИНАСЫ

Бұл машинаның Тьюрингтен айырмашылығы - ол өзінің теориясында «машина» емес «алгоритмдік жүйе» деген терминді қолданған.

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

Лента жағдайы процесс уақытында өзгермелі болды. Осы лента жағдайы мен оқу-жазу инесінің орны туралы ақпарат Пост машинасының жағдайын айқындайды.

Инені « », метка-белгі М болсын. Секция бос болса, ешбір белгі түспейді. Бір қадам жасағанда ине оңға немесе солға 1 қадам жылжып белгіні салады немесе өшіреді. Программадағы командаларға сәйкес машина 1 жағдайдан келесі жағдайға көшіп отырады.