Марковтың нормальды алгоритмі

Қазақстан Республикасының Білім және ғылым министрлігі

Семей қаласының Шәкәрім атындағы Мемлекеттік университеті

Жаратылыстану - математика ғылымдар факультеті

СӨЖ №1

Орындаған: Бекбосунова Мариям Т- 311

Тексерген: Рысжанова Айжан Сайлаухановна

Семей 2015 жыл

Жоспар:

Тьюринг машинасы. Тьюринг тезисі және оның негіздемесі.

Марковтың нормальды алгоритмі.

Нормальдау принциптері және оның негіздемесі.

Тьюринг машинасының композициясы.

Информатиканың негізгі ұғымдарының бірі болып алгоритм ұғымы саналады.

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

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

Алан Тьюринг

Алан Мэтисон Тьюринг (23. 06. 1912 - 07. 06. 1954) - информатиканың дамуына үлкен үлес қосқан ағылшын математигі, логигі, криптографы. Ұлы Отан соғысы кезінде Алан Тьюринг Блетчли-паркта орналасқан Үкіметтік Байланыс Орталығында қызмет атқарды. Тьюринг Жапония, Германия және Италия секілді нацисттік елдер мен олардың жақтаушыларың құпия жазбаларын, шартты белгілерінің мағынасын ашумен айналысқан. Ол Германияның әскери-теңіз флотының хабарламаларының криптоанализіне жауапты Hut 8 тобын басқарды. Тьюринг криптоанализдің бірқатар тәсілдерін ойлап тапты. Соның ішінде, неміс шифраторы Enigma-ның құпия жазбаларын шешуді мақсат ететін Bombe базасы ойлап табылды.

Тьюринг машинасының құрылымы

3 бөліктен тұрады: лентадан, оқитын-жазатын бөлшектен және логикалық құрылғыдан.

Марковтың нормальды алгоритмдері.

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

Өздеріне арналған программалардың қасиеттері туралы әртүрлі тұжырымдауды дәлелдеуге арналған абстракты ( яғни шын емес, тек қиялда ғана бар) Пост пен Тьюринг машиналарын американдық математик Эмил Пост пен ағылшын математигі Аллан Тьюринг бірінен-бірі тәуелсіз (және іс жүзінде бір уақытта) 1936 ж. ұсынды. Бұл машиналар бастапқы мәліметтерді “енгізіп”, программалар орындалғаннан соң нәтижені оқуға мүмкіндік беретін, толығымен анықталған әмбебап орындаушылар болып табылады. Пост машинасы аса танымал емес, бірақ Тьюринг машинасына қарағанда әлдеқайда қарапайым.

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

Кодтаудың өзі былай орындалуға тиіс: а) әртүрлі таңбалар әртүрлі кодтық топтармен алмастырылуы қажет, бірақ бір таңба қай жерде кездескеніне қарамай, бір ғана кодтық топпен жаппай ауыстырылуы қажет; б) кодтық жазба жолдары жеке кодтық топтарға бірмәнді бөлшектенуге тиіс с) А, П, С командаларына сәйкес кодтық топтарды тану, сыртқы әріппеге және іш күйлеріне сәйкес кодтық топтарды ажырату

Қорытынды:

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

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