Алгоритмнің тиімділігі мен күрделілігі. Тьюринг, Пост абстрактілі машиналарымен жұмыс

МАЗМҰНЫ

Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 3

1 Алгоритм және Алгоритмдер теориясының негізгі ұғымдары ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...4
1.1 Алгоритм түсінігі және оның негізгі қасиеттері. Алгоритм
орындаушысы. Алгоритмді ұсыну тәсілдері ... ... ... ... ... ... ... ... ... ... ... ... 4
1.2 Алгоритмдерге қойылатын негізгі талаптар. Алгоритмдік модельдер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .5
1.3 Алгоритмдi талдау және алгоритмді құру схемасы ... ... ... ... ... ... 6
1.4 Марковтың нормаль алгоритмдері ... ... ... ... ... ... ... ... ... ... ... ... .7
1.5 Алгоритмдер арқылы шешілмейтін есептер ... ... ... ... ... ... ... ... ..11

2 Автомат . ақпараттық жүйенің негізгі элементі ретінде.
Абстрактілі автоматтар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 12
2.1 ЭЕМ . ақпаратты өңдеудің әмбебап құралы ... ... ... ... ... ... ... ... 12
2.2 ЭЕМ.нің дискретті сипаттамасы ... ... ... ... ... ... ... ... ... ... ... ... ... 12
2.3 Тьюринг машинасы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..14
2.4 Пост машинасы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 17
2.5 Шексіз регистрлі машина ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .19

3 Алгоритмдердің тиімділігі мен күрделілігін талдау ... ... ... ... ... ... ... ... ..21
3.1 Алгоритмнiң күрделiгiн анықтау ... ... ... ... ... ... ... ... ... ... ... ... ... ..21
3.2 Алгоритмнің О.күрделіліктері ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...25
3.3 Алгоритм бойынша программаның тиiмдiлiгiн
анықтау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .25
3.4 Күрделіліктің жоғарғы, төменгі және орташа бағалаулары ... ... ... 26

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

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

Кіріспе

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

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

1. Мамаев Қ.С., Айдосов Ш.И., Серікбаев Н.Қ. Информатиканың теориялық негіздері. –Шымкент: Әлем, 2013. -200б.
2. Алферова З.А. Теория алгоритмов. -М.: Статистика, 1973.
3. Ахо А., Хопкрофт Д., Ульман Дж. Структуры данных и алгоритмы. -М.: Издательский дом "Вильямс", 2001.
4. Ахо А., Хопкрофт Дж. Ульман Дж. Построение и анализ вычислительных алгоритмов. -М: Мир,1979.
5. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. -2-е изд., испр. -СПб.: Невский Диалект, 2001. -352 с., ил.
6. Дюсембаев А.Е. Информатика. Учебное пособие. -Алматы: Издательство ТОО "Dair", 2006. -145с.
7. Информатика: учебник. -3-е перераб. изд./ под ред. проф. Н.В.Макаровой. -М.:Финансы и статистика, 2001. -768 с. ил.
8. Макконнелл Дж. Основы современных алгоритмов. -М.: Техно-сфера, 2004. -368с.
9. Макконнелл Дж. Анализ алгоритмов. Вводный курс. -М.:Тех-носфера, 2002. -304с.
10. Максимов Ю.А., Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. -М.:МИФИ, 1982.
11. Мину М. Математическое программирование. Теория и алго-ритмы. -М.:Наука,1990.
12. Носов В.А. Основы теории алгоритмов и анализа их сложности. Курс лекций. -М., 1992.
13. Савельев А.Я. Основы информатики: учебник для вузов. -М.: изд-во МГТУ им. Н.Э. Баумана, 2001 -328 с, ил. (Сер. Информатика в техническом университете).
14. Советов Б.Я. Моделирование систем: учебник для вузов / Яковлев С.А. -М.: Высш.шк., 1998.
15. Соломатин Ю.М. Информационные семантические системы. -М.: Высшая школа, 1989. -127 с.
16. Стариченко Б.Е. Теоретические основы информатики: Учебное пособие для вузов. -2-е изд. перераб. и доп. -М.: Горячая линия-Телеком, 2003. -312 с., ил.
17. Успенский В.А. Машина Поста (Популярные лекции по математике). 2-е изд., испр. -М.: Наука, 1988. -96 с.

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

МАЗМҰНЫ

Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
3

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

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

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

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

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

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

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

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

25
3.4 Күрделіліктің жоғарғы, төменгі және орташа бағалаулары ... ... .
26

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

28

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

29

Кіріспе

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

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

1.1 Алгоритм түсінігі және оның негізгі қасиеттері. Алгоритм орындаушысы. Алгоритмді ұсыну тәсілдері
Алгоритм ұғымы көптеген жылдар бойы интуитивтi ұғым болып келдi. Тек ХХ-ғасырдың 30-жылдарында көрнектi математиктер Д.Гильберт, А.Черч, Э.Пост және А.Тьюрингтың еңбектерiнде рекурсивтi функция ұғымына және алгоритмдiк үрдісті сипаттауға негiзделген алгоритмнiң формальды анықтамасы берiлдi. Соңынан математиканың жаңа саласы - Алгоритмдер теориясы қалыптасты. Ал ол есептеуiш техникасының дамуының теориялық негiзiн құрайды.
Алгоритм сөзi арифметикалық амалдарды орындау ережесiн тұжырымдаған ұлы математик Әл-Хорезмидiң ("Арифметикалық трактат" еңбегi, IX ғасыр) аты-жөнiнiң латынша algoritmi болып бұрмалауынан шыққан.
Алға қойған мақсатқа жетуде немесе берiлген есептi шешуде арнайы ережелер бойынша атқарушыға (адам‚ компьютер‚ робот‚ станок‚ программалау тiлдерi т.б.) жинақты түрде берiлген нұсқаулар тiзбегi алгоритм делiнедi.
Алгоритм қасиеттері:
1. Алгоритмнiң үздiктiлiгi (дискреттiлiгi). Ақпаратты өңдеу үрдісі ретiмен жазылған жеке-жеке нұсқаулар тiзбегiнен тұруы тиiс.
2. Алгоритмнiң түсiнiктiлiгi және анықтылығы. Кез келген атқарушы (орындаушы) алгортмдi түсiндiрiп, орындай алатын болуы керек. Сондай-ақ әртүрлi мағыналы нұсқаулар енгiзiлмеуi тиiс.
3. Алгоритмнiң қарастырып отырған ақпараттың кез келген алғашқы берiлгендерiне бiрдейлiгi.
4. Алгоритмнiң нәтижелiгi. Нұсқаулар шексiз көп болмай, қорытындыда оның нәтижесi болуы тиiс.
Алгоритмнiң маңызды қасиетi мынада: орындаушыдан есептi шешу әдiсi түсiну талап етiлмейдi, тек алдын-ала берiлген iс-әрекеттер тiзбегiн орындаса болғаны. Сондықтан орындаушы (атқарушы) ережедегі бұйрықтарға сүйенiп, алгоритмдi механикалық түрде орындайды. Алгоритм қандай да бiр орындаушыға (атқарушыға) арналып дайындалады. Мысалы, адам, компьютер және т.б. құрылғылар үшiн. Сондықтан алгоритмнiң сипаты орындаушы үшiн түсiнiктi болуы тиiс. Орындаушының түсiнiп, орындайтын барлық командалары оның командалары жүйес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. Әрбір алгоритм берілгендермен (бастапқы, аралық, нәтижелік) жұмыс істейді.
Берілгендер ұғымын анықтау үшін таңбалардың алфавиті (саны шекті) мен алгоритм құру ережесі беріледі. Саны шекті таңбадан тұратын сөз - қарапайым алгоритмдік берілгенге жатады. Ал сөздегі таңбалар саны берілгендер көлемін анықтауға мүмкіндік береді. Формулалар да алгоритмдік объектіге жатады. Мысалы, пікірлер мен предикаттар алгебрасының формулалары.
2. Берілгендерді сақтау үшін жад қажет. Жад дискретті, әрқайсысында 1 ғана таңба сақталынатын біртекті ұяшықтар жиынтығынан тұрады. Сондықтан берілгендер мен жад көлемін есептеуге мүмкіндік бар.
3. Алгоритм жекелеген қарапайым қадамдардан тұрады. Бірақ алгоритмді құрайтын түрлі қадамдар саны шектеулі болады. Мысалы, ЭЕМ-нің командалары жүйесі.
4. Алгоритм қадамдарының тізбегі детерминирленген болады. Әрбір қадамнан кейін қай қадамды орындау қажеттігі не алгоритмді аяқтау қажеттігі көрсетіледі.
5. Алгоритмнің нәтижелілігі. Қандай да бір шекті қадамнан кейін нәтиже алынады.
6. Алгоритм жүзеге асыру механизмін сипаттайды. Алгоритм мен оны жүзеге асыру механизмінің қадамдары шектеулі.
1-6 талаптар ЭЕМ-дер үшін келесі түрде беріледі: 1-талап - ЭЕМ-нің сандық табиғаты; 2-талап - ЭЕМ жады; 3-талап - программа; 4-талап - ЭЕМ-нің логикалық құрылымы; 5-6 талаптар - ЭЕМ-нің есептеуіш құрылғылары.
Алгоритмнің келесі мазмұнсыз ұғымдарын сұрақ түрінде беру қабылданған:
1. Бастапқы берілгендердің өлшемдері шекті бола ма?
2. Қарапайым қадамдар санының шекті аралығын анықтауға бола ма?
3. Жад көлемінің шекті аралығын анықтауға бола ма?
4. Есептеу барысында қадам санын шектеуге бола ма?
1-4 сұрақтарға жоқ деп жауап беріледі. Себебі ЭЕМ үшін бұл өлшемдер шектеулі. Бірақ алгоритмдік есептеулермен айналысатын теорияда ешқандай шектеу болмайды. Сонымен алгоритм ұғымы берілгендер мен оларды өрнектеуді, жадты және онда берілгендердің орналасуын, алгоритмнің қарапайым қадамдарын, алгоритмді жүзеге асыру механизмін анықтауды талап етеді. Алайда бұл ұғымдарды анықтауда өзге де қосымша ұғымдар қажет етіледі. Сондықтан алгоритмдер теориясында нақты алгоритмдік модель ұғымы қолданылады. Бұл модель белгілі бір іс-әрекеттер шеңберінде әмбебап (универсал) болады. Алгоритмдік модельдің үш түрі қолданылады:
1. Белгілі бір уақыт аралығында саны шектеулі амалдарды орындайтын детерминирленген құрылғы. Мысалы, Тьюринг машинасы.
2. Рекурсивтік функцияларға негізделген модель.
3. Марковтың нормаль алгоритмдеріне негізделген модель. Мұндай модель түрлі сөз бөліктерінен сөздер құрастыруға негізделген.

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

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

2.1 ЭЕМ - ақпаратты өңдеудің әмбебап құралы
Пайдаланушы тұрғысынан алғанда компьютер қиындығы түрліше есептерді шешуде анағұрлым күрделі амалдарды орындайтын "қара жәшік" ретінде ұғынылады. Ақпаратты түрлендіру, өңдеу үрдісіне талдау жасай отырып, "қара жәшіктің" құрылысын қарастырайық. Мұнда келесі мәселелерге назар аударған жөн:
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 жылы ұсынды және бұл модельдің ЭЕМ пайда болуына үлкен маңызы болды. Тьюринг машинасы келесі элементтерден тұрады:
1) сол және оң жақ бөліктері шектеусіз ұяшықтарға бөлінген лента;
2) символдарды оқитын және жазатын бастиек;
3) лентаны жылжытатын механизм (лентатартқыш);
4) басқару құрылғысы. Ол қандай да бір шекті жиынтыққа тиісті q0,q1,...,qs дискреттiк күйлердiң бiрiнде болуы мүмкiн. Берiлген шектi жиынтық ішкі күйлер алфавиті делінеді, ал q0 бастапқы күй болып табылады.
Бастиек А={a0,a1,...,at} жұмыс афавитінің әріптерін оқиды, өшіреді және жазады. Әрбір уақыт мезетінде лентаның әрбір ұяшығында А жиынының әріптері сақтаулы болады. Олардың ішінде a0 әрпі - бос орын жиі кездеседі.
Әрбір уақыт мезетінде бастиек лентаның қандай да бір ұяшығының үстінде орналасады. Ол ағымдық жұмыс ұяшығы деп аталады. Лентатартқыш механизм бастиекті көрші ұяшықтың үстіне орналасатындай етіп жылжытып отырады. Мұнда келесі жағдайлардың бірі орын алуы мүмкін:
а) бастиек лентаның сол жақ шетіне шығып қалады. Бұл - апаттық жағдай болып табылады;
ә) машина жұмысы тоқтатылады. Мұнда жұмысты тоқтату туралы командалар орындалады.
2.3.2 Тьюринг машинасы жұмысының сипаттамасы
Тьюринг машинасы жұмыс істеу реті Тьюринг машинасының кестесімен сипатталады. Бұл кесте 4 бағаннан және саны (s+1)(t+1) жолдан тұратын матрицаны құрайды. Әрбір жол qiajvijqij командасынан тұрады. Мұндағы 0is, 0jt және qij {q0,q1,...,qs}.
vij арқылы {a0,a1,...,at} алфавиті элементтері мен лентатартқыш механизм командалары сипатталады: лентатартқыш механизм үшін l - лентаны солға, r - оңға жылжыту, s - машинаны тоқтату командалары болып табылады. Демек, vij - Тьюринг машинасы орындайтын іс-әрекет. Мұнда лента ұяшығына a0,a1,...,at алфавитінің символы енгізілуі, не бастиек жылжытылуы, не машина тоқтатылуы мүмкін. qij машинаның келесі күйі болып табылады.
Тьюринг машинасы келесі ереже бойынша жұмыс істейді: егер Тьюринг машинасы qi күйінде болса, онда бастиек жұмыс ұяшығындағы aj символын оқиды.
qiaj символдарынан басталатын qiajvijqij жолы кестеде 1 рет қана кездессін.
Егер vij жұмыс алфавитінің әрпі болса, онда бастиек ұяшықты тазалап, осы әріпті сонда енгізеді.
Егер vij лентатартқыш механизмнің r не l командасының бірі болса, онда лента сәйкесінше оңға не солға жылжытылады.
Егер vij=s болса, онда машина жұмысы тоқтатылады.
Тьюринг машинасы жұмысын қандай да бір бастапқы конфигурацияға сай бастайды. Бастапқы конфигурация бойынша Тьюринг машинасы q0 бастапқы күйінде болып, бастиек А алфавиті әріптерінің бірі енгізілген лента ұяшығының үстінде орналасады.
Тьюринг машинасының жұмыс алфавитінде неғұрлым түрлі символдар көп болса, соғұрлым лентада түрлі мәтіндік және сандық ақпараттар көбірек өрнектеледі. Ал Тьюринг машинасының басқару құрылғысы арқылы әртүрлі күйлерге өтуі оның аралық нәтижелерді сақтау механизмін сипаттайды.
Тьюринг машинасының жұмыс істеу тәртібін анықтайтын кесте программа болып табылмайды. Ол нұсқау тізбектей орындалмайды, тек лентадағы қандай да бір мәтін символдарының түрленуін сипаттайды. Тьюринг машинасы кестесі Тьюринг машинасы схемасы деп, кейде Тьюринг машинасы деп аталады.
Осы кезге дейін түрлі алгоритмдер түрлі Тьюринг машиналарында орындалып келді. Бұл Тьюринг машиналары бір-бірінен командалары, ішкі және сыртқы алфавиттерімен ерекшеленеді. Кез келген Тьюринг машинасына арналған алгоритм-дерді орындайтын әмбебап Тьюринг машинасын да құруға болады. Мұнда әрбір Тьюринг машинасының конфигурациясы мен программалары әмбебап Тьюринг машинасының сыртқы алфавитіне кодталады. Кодтау келесі түрде жүргізілуі мүмкін:
1. Түрлі таңбалар түрлі кодтау топтарымен алмастырылуы тиіс. Әрбір символ тек бір ғана кодтау тобымен алмастырылады.
2. Кодтық жазбалар жолдары жекелеген кодтау топтарына бірмәнді түрде жіктелуі тиіс.
3. l,r,s командаларына сай кодтау топтарын анықтауға мүмкіндік болуы тиіс.
Түрлі машиналардың құрылымдары мен күрделіліктерін бағалау өте маңызды. К.Шеннон осының өлшемі ретінде сыртқы алфавитінің символдары саны мен ішкі күйлерінің санын көбейтуді ұсынған. Аз күрделілікті әмбебап Тьюринг машинасын құрудың теориялық мәні зор.
2.3.3 Тьюринг машинасының композициялары
Тьюринг машинасының композициялары алдын-ала берілген қарапайым алгоритмдерден анағұрлым күрделі алгоритмдер құрастыруға мүмкіндік береді. Мұнда көбейту, дәрежелеу және итерациялау амалдарын орындауға болады.
A={a0, a1,..., am} ортақ алфавитті және Q1={q0, q1,..., qn}, Q2={q0, q1,...,qt} ішкі күйлі T1, T2 Тьюринг машиналары берілсін.
T1, T2 машиналарының композициясы (көбейтіндісі) деп сыртқы алфавиті A={a0, a1,..., am} және ішкі күйі Q1={q0, q1,...,qn,qn+1,..., ... жалғасы

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