Алгоритмдер теориясының негізгі ұғымдары

Жұмыс түрі: Курстық жұмыс
Тегін: Антиплагиат
Көлемі: 29 бет
Таңдаулыға:

ОҢТҮСТІК ҚАЗАҚСТАН МЕМЛЕКЕТТІК ПЕДАГОГИКАЛЫҚ
УНИВЕРСИТЕТІ
Физика-математика факультеті
Информатика кафедрасы

КУРСТЫҚ ЖҰМЫС
Тақырыбы: Алгоритмдер теориясының негізгі ұғымдары
Пәні : Информатиканың теориялық негіздері
Мамандығы: Физика-информатика
Орындаған: Шорабек Ә.
Қабылдаған: т.ғ.к Қалдарова Б.
Комиссия мүшелері: Қалдарова Б.
Жамалова К.
Алиева А.

Шымкент 2019
Оңтүстік Қазақстан мемлекеттік педагогикалық университеті
Физика-математика факультеті
Физика-математика кафедрасы
БЕКІТЕМІН
Кафедрасының меңгерушісі
________ Сүлейменова Л.
(қолы) (аты-жөні)
___ ________ 20__ ж.
Студенттің курстық жұмысына берілетін
ТАПСЫРМА
Шорабек Әсел
1. Жұмыстың тақырыбы: Алгоритмдер теориясының негізгі ұғымдары
2. Жұмыстың аяқталу уақыты: 06.05.2019ж
3. Жұмысқа керек материалдар: ғылыми әдістемелік журналдар, оқулықтар, интернет.
4. Жұмыстың мазмұны (әдебиеттік және теориялық ізденісі, қорытынды):
Кіріспе

I Алгоритм. Алгоритмдер теориясының негізгі ұғымдары

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

III Алгоритмдердің тиімділігі мен күрделілігін талдау

IV Қорытынды

V Пайдаланылған әдебиеттер

5. Кестелік және графикалық материалдардың тізімі: 6
6. Әдебиеттер тізімі:
Мамаев Қ.С., Айдосов Ш.И., Серікбаев Н.Қ. Информатиканың теориялық негіздері. - Шымкент: Әлем, 2013. -200б.
Алферова З.А. Теория алгоритмов. -М.: Статистика, 1973.
Ахо А., Хопкрофт Д., Ульман Дж. Структуры данных и алгоритмы. -М.: Издательский дом "Вильямс", 2001.
Ахо А., Хопкрофт Дж. Ульман Дж. Построение и анализ вычислительных алгоритмов. -М: Мир,1979.
Вирт Н. Алгоритмы и структуры данных: Пер. с англ. -2-е изд., испр. -СПб.: Невский Диалект, 2001. -352 с., ил.
Дюсембаев А.Е. Информатика. Учебное пособие. -Алматы: Издательство ТОО "Dair", 2006. -145с.
Информатика: учебник. -3-е перераб. изд. под ред. проф. Н.В.Макаровой. -М.:Финансы и статистика, 2001. -768 с. ил.
Макконнелл Дж. Основы современных алгоритмов. -М.: Техно-сфера, 2004. -368с.
Макконнелл Дж. Анализ алгоритмов. Вводный курс. -М.:Тех-носфера, 2002. -304с.
Максимов Ю.А., Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. -М.:МИФИ, 1982.
Мину М. Математическое программирование. Теория и алго-ритмы. -М.:Наука,1990.
Носов В.А. Основы теории алгоритмов и анализа их сложности. Курс лекций. -М., 1992.
7. Тапсырманың берілген уақыты:
8. Курстық жұмыстың жетекшісі:_________ т.ғ.к Қалдарова Б.
9. Тапсырманы алған студент:____________Шорабек Ә. 128-16 оқу тобы

МАЗМҰНЫ

Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
6

I Алгоритм. Алгоритмдер теориясының негізгі ұғымдары ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .

7
1.1 Алгоритм түсінігі және оның негізгі қасиеттері. Алгоритм орындаушы. Алгоритмді ұсыну тәсілдері ... ... ... ... ... ... .. ... ... ... ...

7
1.2 Алгоритмдерге қойылатын негізгі талаптар. Алгоритмдік модельдер ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .

8
1.3 Алгоритмдi талдау және алгоритмді құру схемасы ... ... ... ... .
9
1.4 Марковтың нормаль алгоритмдері ... ... ... ... ... ... ... ... ... ... ... .
10
1.5 Алгоритмдер арқылы шешілмейтін есептер ... ... ... ... ... ... ... ... ..
14

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

15
2.1 ЭЕМ - ақпаратты өңдеудің әмбебап құралы ... ... ... ... ... ... ...
15
2.2 ЭЕМ-нің дискретті сипаттамасы ... ... ... ... ... ... ... ... ... ... ... ...
16
2.3 Тьюринг машинасы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .
17
2.4 Пост машинасы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
20
2.5 Шексіз регистрлі машина ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ...
22

III Алгоритмдердің тиімділігі мен күрделілігін талдау ... ... ... ... ... ... ..

24
3.1 Алгоритмдердің күрделiгiн анықтау ... ... ... ... ... ... ... ... ... ... ...
24
3.2 Алгоритм бойынша программаның тиiмдiлiгiн
анықтау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .

26

IV Қорытынды ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...

28

V Пайдаланылған әдебиеттер ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ...

29

Кіріспе

Информатика ғылымының анықтау кезеңін ақпарат пен ақпараттық жүйелер қалыптастырады. Информатика ғылым ретінде ХХ ғасырдың 50-жылдарында пайда болды, алайда ақпаратқа деген ғылыми қызығушылықтар мен осы саладағы анықтау жұмыстары ілгерірек кезеңде жүргізіле бастаған. Бұл ғылым 1940 жылдардың аяғында қалыптасып, бағдарламалық басқару принциптерін зерттеуді қамтитын "Кибернетика" ғылымынан бастау алады. Өткен ғасырдың алғышқы жылдарында телефон, телеграф, радио сияқты байланыс құралдарының өмірге келуіне байланысты "Байланыстар теориясы" деп аталынатын ғылыми бағыт қалыптасты. Ол өз кезегінде кодтау теориясы мен ақпараттар теориясының пайда болуына негіз болды. Ақпараттар теориясы байланыс каналдары арқылы берілетін ақпаратты өлшеуге ықпал етті.
Әр түрлі ғылымның теориялық негізі зерттеудің математикалық әдістеріне негізделеді. Бұл информатика ғылымы үшін де тән құбылыс. Мұнда ақпаратты өңдеудің модельдерін құруда, реттеуде және қолдануда математикалық әдістер қолданылады. Ақпарат табиғаты жағынан дискретті болатындықтан мәтін таңбалар мен цифрлардың жиынтығынан тұратындығы белгілі. Осыған орай, информатика ғылымында дискреттік математиканың Математикалық логика деп аталынатын бөлімінің заңдылықтары кеңінен қолданылады.
Алгоритмдер теориясын толыққанды меңгермей жоғары білімді бағдарламашыны, информатика пәнінің мұғалімін қалыптастыру әрі дайындау мүмкін емес. Қазіргі ақпарат ғасырында ақпарат қорына иелік етіп, оны сақтау, өңдеу және тұтынушыларға жеткізу технологиясын игерудің үлкен мәні бар. Қазақстан Республикасында білім беруді дамытудың 2011-2020 жылдарға арналған мемлекеттік бағдарламасына сәйкес орта білім беру ұйымдарында электрондық оқыту жүйесінің қолданылу санын 2015 жылы 50%-ға, 2020 жылы 90%-ға көбейту жоспарланған. Осыған байланысты оқу үрдісінде компьютерлік техникалар мен оқыту жүйелерін пайдаланудың маңызы уақыт өте келе көбеюде. Болашақ информатика пәні мұғалімінің есептеу техникасының теориялық негіздерін игеруі міндетті.
Курстық жұмыста абстрактілі автоматтар, алгоритмдер теориясының негізгі ұғымдары, алгоритмдер тиімділігі мен күрделіліктерін талқылау сияқты информатиканың ілгері ұғымдары туралы теориялық мәліметтер берілген.

I Алгоритм ұғымы. Алгоритмдер теориясының негізгі ұғымдары

Алгоритм түсінігі және оның негізгі қасиеттері. Алгоритм орындаушы. Алгоритмді ұсыну тәсілдері
Алгоритм термині әрі ұғымы көптеген жылдар бойы интуитивті болды. Тек ХХ-ғасырдың ортасында, яғни, 30-жылдары математик ғалымдар Д.Гильберт, А.Черч, Э.Пост және А.Тьюрингтың жазбаларында алгоритмдiк үрдісті анықтауға және рекурсивтi функция ұғымына негізделген алгоритмдердiң формальды анықтамалары көрсетілген. Кейіннен математика ғылымының жаңа бағыты - алгоритмдер теориясы қалыптасты. Ал ол есептеуiш техникасының дамуының теориялық негiзi ретінде есептелінді.
Алгоритм сөзi арифметикалық тәсілдерді атқаратын ережені тұжырымдаған ұлы математик Әл-Хорезмидiң ("Арифметикалық трактат" еңбегi, IX ғасыр) аты-жөнiнiң латынша algoritmi ретінде бұрмалауынан шыққан.
Дайындалған есептердi шығару кезеңінде және алға қойған мақсатқа жету жолында арнайы шарттар арқылы атқарушыға (адам‚ компьютер‚ робот‚ станок‚ бағдарламалау тiлi т.б.) жинақты түрде ұсынылған нұсқаулар қатары - алгоритм.
Алгоритм қасиеттері:
Алгоритмнiң үздiктiлiгi. Ақпаратты өңдеу үрдісі кезегімен жазылған бөлек-бөлек нұсқаулар қатарынан тұрады.
Алгоритмнiң анықтылығы. Айтарлықтай барлық атқарушы (пайдаланушы) алгоритмдерді орындайды әрі түсіндіре білуі қажет. Оған қоса түрлі мағыналы нұсқаулар енгізілмеуі қажет.
Алгоритмдердің қарастырып отырған ақпараттардың әр түрлі алғашқы ұсынылғандарының бірдей болуы.
Алгоритмнiң нәтижелiгi. Қорытындыда алгоритм нәтижелі келіп, нұсқаулар шамадан тыс көп болмауы қажет.
Алгоритмдердің маңызды қасиеттері: атқарушы мезгілінен алдын ала ұсынылған iс-әрекеттер қатарын орындаса болғаны, есептердi шешудің тәсілдерін меңгеруді мақсат етпейді. Сондықтан атқарушы ережедегі бұйрықтарға сүйеніп, алгоритмдердi механикалық түрде орындайды. Алгоритм қандай да жеке орындаушыға (атқарушыға) арнаулы бағытталады. Мысалы, адам, компьютер және т.б. құрылғылар үшiн. Сондықтан орындаушыға алгоритмдердің мағынасы ұғымды болып келуі қажет. Орындаушының түсiну арқылы атқаратын барлық командалары оның командалары процесін құрайды. Мысалы, компьютер үшiн команда процесі: санды қосу, салыстыру, көбейту, бөлу және азайтудан тұрады.
Алгоритмдік тіл - құрылымы нақтыланған, шарт процесі, дәл және бірдей жазылатын арнайы таңбалардан тұрады. Мұндағы таңбалар жиынтығы оның алфавиттерін, ал алгоритмдердi жазу ережелерi оның синтаксисін құрайды.
Ол математикалық белгілерді (функция символын, шаманы, әдіс таңбасын, сандарды, жақшаны) қамтамасыз етеді.
Ақпаратты өңдеу алгоритмi табиғи тілде, блок-схема арқылы, алгоритмдік тілде құрылады.
Табиғи тілдегі алгоритм, алгоритмдiк белгілер және күнде қолданылатын сөздерді қолданып, атқарылу қатары берілген жеке бағдарлар қатарынан тұрады.
Блок-схема арқылы берілген алгоритмдерде мемлекет тарапынан бекiтілген арнайы схемалар мен символдар қолданылады.

1.2 Алгоритмдерге қойылатын негізгі талаптар. Алгоритмдік модельдер
Әрбір алгоритм берілгендермен (бастапқы, аралық, нәтижелік) жұмыс істейді.
Берілгендер ұғымын анықтау үшін таңбалардың алфавиті (саны шекті) мен алгоритм құру ережесі беріледі. Саны шекті таңбадан тұратын сөз - қарапайым алгоритмдік берілгенге кіреді. Ал сөздегі таңбалар саны берілгендер көлемін анықтауға мүмкіндік береді. Формула да алгоритмдік объекті болып саналады. Мысалы, пікірлер мен предикаттар алгебрасының формуласы.
Берілгендерді сақтау үшін жад қажет. Жад дискретті, әрқайсысында 1 ғана таңба сақталынатын біртекті ұяшықтар жиынтығынан тұрады. Сондықтан берілгендер мен жад көлемін есептеу үшін мүмкіндік бар.
Алгоритм жекеленген қарапайым қадамдардан тұрады. Бірақ алгоритмді құрайтын түрлі қадамдар саны шектеулі болып келеді. Мысалы, ЭЕМ-нің командалар жүйесі.
Алгоритм қадамдарының тізбегі детерминирленген болып келеді. Әрбір қадамнан кейін қай қадамды атқару қажеттігі не алгоритмді аяқтау қажеттігі көрсетіледі.
Алгоритмнің нәтижелілігі. Қандай да бір шекті қадамнан кейін нәтиже орындалады.
Алгоритм жүзеге асыру механизмін көрсетеді. Алгоритм мен оны жүзеге асыру механизмінің қадамдары шектеулі.
ЭЕМ-дер үшін келесі 6 талап жасалады:
1.сандық табиғаты;
2.жады;
3.программа;
4.логикалық құрылымы;
5-6.есептеуіш құрылғылары.
Алгоритмнің келесі мазмұнсыз ұғымдарын сұрақ түрінде беру қабылданған:
Бастапқы берілгендердің өлшемдері шекті болады ма?
Қарапайым қадамдар санының шекті аралығын анықтауға бола ма?
Жад көлемінің шекті аралығын анықтауға болады ма?
Есептеу кезінде қадам санын шектеуге болады ма?
1-4 сұрақтарға жоқ деп жауап беріледі.Себебі ЭЕМ үшін бұл өлшемдер шектеулі. Бірақ алгоритмдік есептеумен шұғылданатын анықтамада ешқандай шектеулер болмайды. Сондықтан , алгоритм ұғымы берілгендер мен соларды өрнектеуді, жадты және жадта берілгендердің орналасқанын, алгоритмнің қарапайым қадамдарын, алгоритмді жүзеге асыру механизмін анықтауды қажет етеді. Қайткенмен бұл ұғымдарды анықтауда өзге де қосымша ұғымдар қажет етіледі. Сондықтан алгоритмдер анықтамасында нақты алгоритмдік модель ұғымы қолданылады. Бұл модель белгілі бір іс-әрекеттер шеңберінде әмбебап (универсал) болып келеді. Алгоритмдік модельдің үш түрі қолданылады:
1. Белгілі бір уақыт аралығында саны шектеулі әдістерді жүзеге асыра алатын детерминирленген құрылғы. Мысалы, Тьюринг машинасы.
2. Рекурсивтік функцияларға негізделген модель.
3. Марковтың нормаль алгоритмдеріне негізделген модель. Мұндай модель түрлі сөз бөліктерінен сөздер құрастыруға негізделген.

1.3 Алгоритмдi талдау және алгоритмді құру схемасы
Қойылған мақсатқа, есептердiң бастапқы шарттары мен оны шығару тәсілдеріне және орындаушының жұмысына қарай алгоритм бірнеше түрлерге бөлiнедi.
Механикалық алгоритм қарастырылып жатқан нәтижеге жету мақсатында тек жалғыз ғана түрде анықталатын қайталамалы iс-әрекеттер қатарынан тұрады. Мысалы, машина двигателдерінің жұмыс істеу алгоритмi.
Ықтималдық (схоластикалық) алгоритм берілген есептерді әр түрлі тәсілдермен шығару үшін жағдай жасайды. Соңынан шешімнің ықтимал мәндері алынады. Мысалы, Тьюрингтiң ықтимал машинасына негізделіп жасалған алгоритмдер.
Эвристикалық алгоритмде нәтижеге жету мақсатында iс-әрекеттер қатары жалғыз жауапты анықталмайды. Бұларға қағидалар (инструкциялар) кіреді.
Эвристика грек тілінен аударғанда, iздеп табу, анықтау мағыналарын береді. Ол қойылған есептердi талдаудың белгiсiз қатарларын анықтайтын арнайы тәсілдерін қамтиды. Эвристика тура шешімі белгілі емес есепті талқылаудың құнды бағыттарын анықтайтын әдіс, шығармашылықпен ойлануды қарастырады.
Алгоритм ұғымы есептердi талқылау тәсілдері ұғымымен тығыз байланыста болып келеді. Алгоритм есептердi талқылап шығару мен оны практикалық қолдану тәсілін меңгеруден тұрады. Ол тәсілді анықтау шешімінде құрылады.
Алгоритмнiң бірнеше әдіс-тәсілде беріледі:
формула;
кесте;
сөз арқылы;
графиктiк түрде;
алгоритмдiк тілде;
программалау тiлінде.
Мысалы, программа - бағдарламалау тілі арқылы берілетін алгоритм.
Берiлген есептерді орындаудың алгоритмiн құруда келесі ережені қолданған жөн:
1. есептердің қойылымын анықтыу;
2.алгоритм әмбебап болуы үшiн бастапқы ұсынылғандардың типтерін анықтау;
3. шешімнің түрлерін анықтап, шашімнің түрлеріне белгі ендіру;
4.есептердi шығарудың тәсілдерін ойлап табу және белгiлi тәсілдердің біреуін қолдану;
5.алгоритмдердiң дұрыс құрылғандығын анықтау. Алгоритм белгісінде пайда болған қателіктерді жоққа шығару;
6.алгоритмдердi сынақтаудан өткiзу.
Алгоритм құру қиын мәселе. Оны орындау кезінде түрліше логикалық қателіктердің туындауы мүмкін. Сондықтан алгоритмдердiң дұрыстығына, оның көпшілікке арналғандығына көз жүгіртіп , оны сынақтау қажет. Әдетте осы мақсатта жауабы анық есептер (тест есептері) қолданылады. Мысалы, квадрат теңдеулерді шығаруға арналған алгоритмдердi анықтауда 3 түрлi теңдеулердi қарастыру қажет:
- кез келген нақты түбiрлi теңдеу;
- біркелкі нақты түбiрлi теңдеу;
- терiс дискриминантты теңдеу.
Мұнда комплекстi түбiр есептелінеді не нақты сандар жиынтығында түбiр табылмайтындығы көрсетіледі.

1.4 Марковтың нормаль алгоритмдері
Марковтың нормаль алгоритмі (МНА) - алгоритм ұғымының формальды анықтамасын берудің нақты тәсілдерінің бірі (Тьюринг машинасы сияқты). Бұл ұғымды көрнекті кеңес математигі А.А.Марков (1903-1979жж.) 1940 жылдардың соңында енгізген. Марков алгоритмдері жайлы сөз болғанда, оны алгорифм деп атаған.
1.4.1 Қарапайым операторлар мен танып-білгіштер
Алгоритмнің берілуінің толықтай тәсілдері алгоритмдік жүйе делінеді. Абстрактілік алфавиттегі сөздердің арасындағы сәйкессіздікке негізделген алгоритмдік жүйе құрамына қарапайым операторлар және қарапайым танып-білгіштер сияқты табиғаты екіжақты болып келетін объектілер енеді.
Қарапайым операторлар - қарапайым алфавиттік операторлар. Олардың тізбектей атқарылуы нәтижесінде алгоритмдік жүйедегі әр түрлі алгоритм орындалады.
Қарапайым танып-білгіштер арқылы өңделетін ақпараттың қасиеттері анықталады.
Қандай да бір алгоритмнің қарапайым операторының атқару ретін бағдарланған граф арқылы береді (бағдарланған граф - алгоритмнің граф-схемасы).
Алгоритмнің граф-схемасы бір-бірімен байланыстырылған төбелердің саны шекті жиынтығынан тұрады. Төбелерді жиі тораптар (узлы) деп атайды. Әрбір торапқа қандай да бір оператор не танып-білгіш сәйкестендіріледі. Тек кіріс, шығыс тораптары айрықша тораптарға жатқызылады (1.1-сурет).

1.1-сурет

Операторлар сәйкестендірілетін кіріс торабынан тек бір доға шығады. Ал танып-білгіш сәйкестендірілген тораптан 2 доға шығады. Шығыс торабынан ешқандай доға шықпайды. Граф-схема торабына енетін доғалар саны түрліше түрде келуі мүмкін.
Граф-схема арқылы анықталатын алгоритмнің жұмысы келесі түрде жүзеге асады: бастапқы сөз кіріс төбесіне енгізіліп, бағыттауыш бойымен жылжиды. Танып-білгіш торапта қағидасы тексеріледі. Қағиданы қанағаттандырылған жағдайда сөз операторлық торапқа, керісінше жағдайда танып-білгішке жіберіледі.
Егер де граф-схеманың кіріс төбесіндегі р сөзі схема тораптары арқылы түрлендіріліп, саны шекті қадамнан кейін шығыс төбесіне жеткізілсе, алгоритм р сөзіне қолданылды деп есептелінеді. Р сөзі алгоритмнің анықталу облысына кіреді.
Егер де граф-схеманың кіріс нүктесіндегі р сөзі шығыс төбесіне жете алмай, қадамдардың саны шексіз өсіп кетсе, сонда алгоритм р сөзіне қолданылмайды деп есептеледі.

1.4.2 Нормаль алгоритмдер
Нормаль алгоримтде қарапайым оператор ретінде ауыстыру операторы, ал қарапайым танып-білгіш ретінде кіріс танып-білгіші қолданылады.
Кіріс танып-білгіші р1 сөзінің қандай да бір q сөзінің құрамына енетіндігін-енбейтіндігін ережесін тексереді.
Ауыстыру операторы q сөзінің сол жағынан бастап, р1 сөзін р2 сөзімен алмастырады, яғни р1р2. Мысалы, abcabca сөзіне қолданылған bccb алмастыруы 2 қадамнан кейін acbacba сөзін береді:

abcabcaacbabcaacbacba.

Алгоритмнің атқарылуы кезінде алынатын р1,р2,..., рn сөздер тізбегі р1 сөзінен рn сөзіне жеткізетін дедуктивтік тізбек делінеді.
Кіріс танып-білгіші мен алмастыру операторлары арқылы граф түрінде берілген алгоритмдер жалпыланған нормаль алгоритмдер болып табылады. Мұнда әрбір алмастыру операторына сәйкес танып-білгіштен шығатын бір ғана доға сәйкестендіріледі.
Baab, bcba, bbaс алмастырулары арқылы берілген жалпыланған нормаль алгоритмді қарастырайық (1.2-сурет). Бастапқы сөз bcbaab түрінде берілсін. Нәтижеде baaaac сөзі алынады:

bcbaabbcababbcaabbbaaabbbaaaac.

Граф-схемалары келесі қағидасы қанағат-тандыратын жалпылама алгоритмдер нормаль алгоритмдер делінеді:
Танып-білгішке сәйкестендірілген барлық тораптар нөмірлері сәйкесінше 1 мен n арасында реттелінеді.
Алмастыру операторларына сәйкес тораптан шығатын доғалар алғашқы танып-білгішке қатысты торапта не шығыс торабында түйіседі. Алғашқы жағдайда алмастыру қарапайым алмастыру деп, екінші жағдайда нәтижелік алмастыру деп аталады. 1.2-сурет
Кіріс торабы доға арқылы бірінші танып-білгішке жалғастырылады.
Толық, нәтижелік өзгертулер р1.р2 түрінде, нормаль алгоритмде қарапайым өзгертулер р1р2 түрінде ал таңбаланады.
Сөзге ешқандай өзгертулерді қолдану мүмкін болмағанда не қандай да бір нәтижелік өзгертулер орындалған жағдайда өзгертулерді атқару тоқтатылады.
Алфавиті А={+,1} және алмастыру жүйесі `1+1''11', `1'.'1' болаып келетін А.А.Марков нормаль алгоритмі жұмысын қарастырайық. Бастапқы сөз `11+11+1' түрінде берілсін. Алгоритмнің атқарылу нәтижесі:
`11+11+1''1111+1''11111'.
Алгоритм жұмысы жағдайында бірліктер топ тобымен біріктіріледі.
Нормализация принципі. Қандай да бір шекті А алфавиті арқылы құрылған әр түрлі алгоритмдерге осы алфавит арқылы эквивалентті нормаль алгоритм құрастырады.
Көптеген жағдайда А алфавиті арқылы құрылған алгоритмдерге эквивалентті алгоритм құру мүмкін болмайды. Бірақ А алфавитіне жаңа әріптер қосып, кеңейту арқылы, қажетті нормаль алгоритм тұрғызуға мүмкіндік бар (1.3-сурет).
Егер де N алгоритмі А алфавитінің кеңейтілуі арқылы құрылса, сол кезде N алгоритмі А алфавитіне қатысты нормаль алгоритм делінеді.
Егер де А алфавитіндегі әрбір р сөзі үшін F(p)=N(p) атқарылатындай N нормаль алго-ритмі табылса, сол кезде А алфавитіне қатысты 1.3-сурет. F(p) бір орынды бөлікше сөздік функция нормаль есептелінетін делінеді.
Мысал. {0,1} алфавитінде F(p)=pa формуламен берілген сөздік функцияны қарастырайық. {0,1,2} кеңейтілген алфавитінде 2002, 2112, 2.а, 2 схемалы N нормаль алгоритмі берілсін (мұндағы, - бос орын).
{0,1} алфавитінің қандай да бір 0110=p сөзін алайық. Бірінші қадам нәтижесі арқылы 20110. Әрбір келесі қадамда 2 символы бір орынға оңға қарай жылжиды. Бесінші қадамнан кейін 01102 сөзіалынады да, яғни 0110а=ра атқарылады.
Қалыпты жағдайда . схемалы алгоритм F(p)=p функциясын, ал схемалы алгоритм ешжерде анықталмаған функция мәнін есептейді.
Нормализация принципі математикалық тұрғыдан дәлелденбейді.

1.4.3 Нормаль алгоритмдердің композициясы
Берілген алгоритмдермен жаңа алгоритм құру үрдісі композиция делінеді.
1) Алгоритмнің суперпозициясы. А мен В алгоритмдерінің суперпозициясында А алгоритмінің шығыс сөзі В алгоритмінің кіріс сөзі ретінде қарастырылады. Нәтижені C(p)=B(A(p)) арқылы өрнектеуге болады. Суперпозиция әр түрлі саны шекті алгоритм үшін атқарылады.
2) Х алфавитіндегі А,В алгоритмдерінің бірігуі деп сол алфавитке қатысты С алфавитін айтады. Мұнда А және В алгоритмдерінің анықталу облыстарының қиылысуындағы әр түрлі р сөзі A(p) және B(p) қатар орналасқан сөздеріне түрлендіріледі. Ал басқа сөздер үшін бұл алгоритм анықталмаған.
Мысалы, X={a,b} алфавиті, A={abba}, B={baab} алгоритмдері және олардың анықталу облыстарының қиылысуында жатқан аba сөзі берілсін. Нәтиже A(aba)=baa, B(aba)=aab, C(aba)=baaaab түрінде алынады.
3) Алгоритмнің тармақталуы А,В және С алгоритмдерінің композициясын құрайды. Композиция нәтижесі D делік. D алгоритмінің анықталу облысы А,В және С үш алгоритмінің анықталу облыстарымен беттеседі. Осы қиылысуда жатқан кез келген р сөзі үшін егер де C(p)=e бола алады деп қарастырсақ , демек D(p)=A(p) және D(p)=B(p) атқарылады. Мұндағы е - бос жол.
4) Итерация әдісі А, В алгоритмдерінің композициясы арқылы өрнектеледі. Композиция нәтижесі С алгоритмі арқылы беріледі. Қандай да бір р кіріс сөзінен C(p) шығыс сөзі В алгоритміне А алгоритмін бірнеше рет тізбектей қолдану арқылы алынады.
Мысалы, X={a,b} алфавиті, A={abba}, B={bbbaaab} алгоритмдері берілсін. Демек, C(ababb)=ab нәтижесі келесі түрде беріледі:

ababbbaabbbababbbaabbbababbbaaab.

1-4 композицияларды нормаль алгоритмге қолдануда нормаль алгоритмдер пайдаланылады. Әр түрлі алгоритмнің жұмысын атқаратын универсал алгоритм құру есебінің маңызы күшті.

1.5 Алгоритмдер арқылы шешілмейтін есептер
Алгоритм ұғымын формальдандыру - шығару алгоритмдері табылмайтын есептердің болатындығын анықтауға мүмкіндік берді. Бірқатар есептердің әр түрлі есептеу құрылғыларында алгоритмдік тұрғыдан шешілмейтіндігі дәлелденген.
F функциясы есептелетін функция делінеді, егер де осы функцияның анықталу облысындағы әр түрлі аргумент үшін функция мәнін есептейтін Тьюринг машинасы табылатын болса. Егер де мұндай машина табылмаса, сол кезде f функциясы есептелінбейтін функция делінеді.
F функциясының анықталу облысының ішкі жиынындағы аргументтер үшін функция мәнін есептейтін Тьюринг машинасы бар болса да, f функциясы есептелінбейтін функция делінеді.
Егер f функциясының есептеу нәтижесі "ақиқат" не "жалған" түріндегі логикалық өрнек болатын болса, онда есеп берілген есептелетін функцияға қатысты шешілетін не шешілмейтін есеп дейді. Есеп бастапқы берілгендердің кейбірі үшін шешілетін, ал келесі біреулері үшін шешілмейтін болғандықтан, бастапқы берілгендердің мүмкін мәндерін нақтылап көрсету қажет.
Машина жұмысын тоқтату проблемасының (мәселесінің) шешілмейтіндігі дәлелденген есепке кіреді. Ол келесі түрде беріледі:
Тьюринг машинасына арналған программа белгісіне қарап, уақыт өтуіне қарай программа жұмысының аяқталатындығын не шексіз жұмыс істейтіндігін анықтауға болады.
Тоқтату проблемасының шешілмейтіндігін дәлелдеу өзге есептердің де оған келтірілетіндігімен маңызды. Мысалы, Тьюринг машинасының бос жолда тоқтау мәселесін машина жұмысын тоқтатудың қарапайым есебіне келтіруге болады.

II Автомат - ақпараттық жүйенің негізгі Элементі. Абстрактілі автоматтар

2.1 ЭЕМ - ақпаратты өңдеудің әмбебап құралы
Қолданушы тұрғысынан қарағанда компьютер қиындығы түрліше есептерді шығаруда анағұрлым күрделі тәсілдерді атқаратын "қара жәшік" түрінде ұғынылады. Ақпаратты өңдеу, түрлендіру үрдісіне талдау жасап, "қара жәшіктің" құрылысын қарап өтейік. Бұл жерде келесі жағдайларға назар аударған жөн:
2.1. Әр түрлі есептеуіш машинасы (дербес компьютер, үлкен және кіші ЭЕМ, Супер-ЭЕМ) автоматты түрде жұмыс жасайды. ЭЕМ-дерді автомат ретінде келесі құрылымдық схемалар түрінде көрсетуге болады. (2.1, 2.2-суреттер):
.

Басқарушы құрылғылар
Орындаушы құрылғылар
Қосымша құрылғылар
Басқарушы құрылғылар
Орындаушы құрылғылар
Қосымша құрылғылар

Автомат

2.1-сурет

Автомат

2.1-сурет

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

Жад
Арифметикалық-логикалық құрылғы
Енгізу
шығару
Басқару құрылғысы
Перифериялық құрылғылар
Ақпарат
Жад
Арифметикалық-логикалық құрылғы
Енгізу
шығару
Басқару құрылғысы
Перифериялық құрылғылар
Ақпарат

2.2-сурет. ЭЕМ-нің құрылымдық схемасы.

2.2 ЭЕМ-нің дискретті сипаттамасы
ЭЕМ - бағдарламалық басқарылатын цифрлық автомат. Бұл тұжырым екі іргелі идеяға негізделген. Бірінші, ЭЕМ-цифрлық және дискретті ақпаратты түрлендіру және өңдеуге арналған автомат. Бұл ЭЕМ-ге енгізілетін ақпарат (мәтіндік, графикалық, сандық және т.с.с) цифрлар мен сандардың қандай да бір санақ жүйесінде түрлендірілгендігін білдіреді. Сондықтан есептеу жүйесін таңдау компьютер әзірлеушілері үшін маңызды мәселе болып табылады. Екіншіден, ЭЕМ өзіне енгізілетін немесе оның жадында сақталатын арнайы бағдарламамен басқарылады.
Жад (есте сақтау) - кіріс ақпаратын, аралық және қорытынды нәтижелерді сақтауға арналған ЭЕМ-нің құрамдас бөлігі. Машина жадында оның жұмысын басқаратын бағдарламалар да сақталынады.
Жад сыйымдылығы мен жадқа қаратпа орындау уақыты жадты анықтайтын негізгі параметрлер болып саналады.
Жадыны анықтайтын негізгі параметрлер жадтың сыйымдылығы және оның орындалу уақыты болып табылады.
Жад сыйымдылығы-жадқа қосылатын ақпарат сөздерінің санын анықтайды. Сөз алфавиттің шекті ұзындық белгілерінің реттелген тізбегі деп аталады. Сөзді сақтайтын жад бөлігі-жад ұяшығы. Жад сыйымдылығы сөз немесе ұяшық санымен көрсетілуі мүмкін. Жад ұяшығының ұзындығы битпен өлшенеді. Бір бит бір екілік разрядқа тең (немесе 1 байт = 8 бит). Жад ұяшығының ұзындығы немесе пішімі әр түрлі ақпаратты орналастырады. ЭЕМ-де ақпарат білдіру тәсіліне байланысты формат сөзбен, екі еселі сөзбен немесе жартылай сөзбен өлшенуі мүмкін.
Жадқа қаратпа атқару уақыты деп жадқа ақпаратты енгізу және одан шығару уақыттарының аралығын айтады. Ол жадқа сөзді топтастыру үшін жұмсалған уақытпен анықталады.
Есте сақтау құрылғыларын жасау кезінде физикалық элемент ретінде электрондық схемалар, ферромагнитті материалдар, магнитті ленталар мен дискілер, оптикалық жад элементтері және т.б. қолданылады.
Арифметикалық-логикалық құрылғы (АЛҚ) сандық ақпараттың негізгі түрлендіргіші ретінде қолданылады. АЛҚ - компьютер жадында сақталатын ақпаратты өңдеудің арифметикалық және логикалық әдістерін орындайтын ЭЕМ-нің құрамдас бөлігі. Ол қандай да бір уақыт бірлігіне сәйкес қарапайым амалды атқару жылдамдығымен анықталады. Есептеу үрдісі жүргізілетін санау жүйесі АЛҚ-ның негізгі белгісі болып саналады.
Қазіргі есептеуіш құрылғыларда процессор немесе микропроцессор негізгі атқарушы элементті құрайды. Олардың құрамына АТҚ, жедел басқару блогы және оперативтік жад кіреді.
Микропроцессор негізінде есептеу техникасы микроЭЕМ болып табылады және екі жады қолданылады: RAM (Random-Access-Memory), кездейсоқ пайдаланушы жады және ROM (Read-Only-Memory), тұрақты жады. Тұрақты жадқа алгоритмдік тілдердің трансляциясын, қандай да бір мақсат үшін пайдаланылатын дайын бағдарламалар пакетін енгізуге болады. Бұл микроэвм мүмкіндіктерін кеңейтуге ықпал етеді.
Кіріс және шығыс арналарының, сондай-ақ ЭЕМ-нің сыртқы құрылғылармен өзара іс-қимыл жасау құралдары мен әдістерінің болуы ақпаратты енгізуден оны шығаруға дейін орындалатын іс-қимыл уақытын жеделдетуге мүмкіндік береді.

2.3 Тьюринг машинасы
2.3.1 Тьюринг машинасы элементтері
Тьюринг машинасы (ТМ) деп аталатын алгоритмдік модель 1936 жылы британдық ғалым Алан Тьюрингпен ұсынылды және бұл модель ЭЕМ пайда болу үшін үлкен маңызға ие. Тьюринг машинасы келесі элементтерден тұрады:
оң және сол жақ бөліктері шектеусіз ұяшықтарға бөлінген лента;
символиканы жазатын және оқитын бастиек;
таспаны (лентаны) ауыстыру механизмі (лентатартқыш);
басқару құрылғысы. Ол ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.