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

МАЗМҰНЫ

Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 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 с.
        
        МАЗМҰНЫ
Кіріспе.......................................................................................
3
1 Алгоритм және Алгоритмдер теориясының негізгі ұғымдары......................................................................................................
4
1.1 Алгоритм түсінігі және оның негізгі қасиеттері. Алгоритм орындаушысы. Алгоритмді ұсыну ... ... ... ... талаптар. Алгоритмдік модельдер.................................................................................................
5
1.3 Алгоритмдi талдау және алгоритмді құру ... ... ... ... ... ... ... есептер..................................
11
2 Автомат - ақпараттық жүйенің негізгі элементі ретінде. ... ... ЭЕМ - ... ... ... ... ... дискретті сипаттамасы...............................................
12
2.3 Тьюринг машинасы...................................................................
14
2.4 Пост машинасы..........................................................................
17
2.5 Шексіз регистрлі машина................................................................
19
3 Алгоритмдердің тиімділігі мен күрделілігін талдау..........................
21
3.1 Алгоритмнiң күрделiгiн ... ... ... ... ... ... тиiмдiлiгiн
анықтау.....................................................................................................
25
3.4 Күрделіліктің жоғарғы, төменгі және орташа бағалаулары.........
26
Қорытынды..................................................................................................
28
Пайдаланылған әдебиеттер.......................................................................
29
Кіріспе
Ақпарат пен ақпараттық жүйелер Информатика ... ... ... болып табылады. Информатика ғылым ретінде ХХ ғасырдың ортасына пайда болғанымен ақпаратқа деген ... ... мен осы ... ... одан ... ... ... бастаған. Бұл ғылым 1940 жылдардың аяғында қалыптасып, бағдарламалық басқару принциптерін зерттеуді қамтитын "Кибернетика" ... ... ... ... ... ... ... телеграф, радио сияқты байланыс құралдарының өмірге келуіне орай "Байланыстар теориясы" атты ғылыми бағыт қалыптасты. Ол өз ... ... ... мен ... ... ... болуына негіз болды. Ақпараттар теориясы байланыс каналдары арқылы берілетін ақпаратты ... ... ... ... ... ... теориялық негізі зерттеудің математика-лық әдістеріне негізделеді. Бұл информатика ... үшін де тән ... ... ақпаратты тасымалдауда, қолдануда және өңдеудің модельдерін құруда математикалық әдістер қолданылады. Ақпарат табиғаты жағынан дискретті болатындықтан ... ... мен ... жиынтығынан тұратындығы белгілі. Осыған орай, информатикада Дискреттік математиканың Математикалық логика атты ... ... ... ... ... теориясын толыққанды игермей сапалы білімді бағдарламашыны, информатика пәнінің мұғалімін даярлау мүмкін емес. ... ... ... ... ... иелік етіп, оны сақтау, өңдеу және тұтынушыларға жеткізу технологиясын игерудің үлкен мәні бар. "Қазақстан Республикасында ... ... ... ... ... ... мемлекеттік бағдарламасына" сай орта білім беру ұйымдарында электрондық ... ... ... ... 2015 жылы ... 2020 жылы 90%-ға арттыру жоспарланған. Осыған орай оқу үрдісінде компьютерлік техникалар мен оқыту жүйелерін ... ... күн ... ... артуда. Болашақ информатика пәні мұғалімінің есептеу техникасының ... ... ... ... ... жұмыста абстрактілі автоматтар, алгоритмдер теориясының негізгі ұғымдары, алгоритмдер ... мен ... ... ... ... іргелі ұғымдары жайлы теориялық мәліметтер берілген.
1 Алгоритм ұғымы. Алгоритмдер теориясының ... ... ... ... және оның негізгі қасиеттері. Алгоритм орындаушысы. Алгоритмді ұсыну тәсілдері
Алгоритм ұғымы көптеген жылдар бойы интуитивтi ұғым ... ... Тек ... ... ... математиктер Д.Гильберт, А.Черч, Э.Пост және А.Тьюрингтың еңбектер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 түс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 ғана ... ... ... ұяшықтар жиынтығынан тұрады. Сондықтан берілгендер мен жад көлемін есептеуге мүмкіндік бар.
* Алгоритм жекелеген ... ... ... ... ... құрайтын түрлі қадамдар саны шектеулі болады. Мысалы, ЭЕМ-нің ... ... ... қадамдарының тізбегі детерминирленген болады. Әрбір қадамнан кейін қай ... ... ... не ... ... ... ... Алгоритмнің нәтижелілігі. Қандай да бір шекті қадамнан кейін нәтиже алынады.
* Алгоритм жүзеге асыру механизмін сипаттайды. Алгоритм мен оны ... ... ... ... ... ... ... үшін келесі түрде беріледі: 1-талап - ЭЕМ-нің сандық табиғаты; 2-талап - ЭЕМ жады; 3-талап - ... ... - ... ... ... 5-6 ... - ЭЕМ-нің есептеуіш құрылғылары.
Алгоритмнің келесі мазмұнсыз ұғымдарын сұрақ түрінде беру қабылданған:
* Бастапқы ... ... ... бола ... ... ... ... шекті аралығын анықтауға бола ма?
* Жад көлемінің шекті аралығын анықтауға бола ма?
* Есептеу барысында ... ... ... бола ... сұрақтарға деп жауап беріледі. Себебі ЭЕМ үшін бұл ... ... ... ... есептеулермен айналысатын теорияда ешқандай шектеу болмайды. Сонымен алгоритм ұғымы берілгендер мен ... ... ... және онда ... ... ... қарапайым қадамдарын, алгоритмді жүзеге асыру механизмін анықтауды талап етеді. Алайда бұл ... ... өзге де ... ... ... етіледі. Сондықтан алгоритмдер теориясында нақты алгоритмдік модель ұғымы қолданылады. Бұл модель белгілі бір іс-әрекеттер ... ... ... ... ... ... үш түрі қолданылады:
1. Белгілі бір уақыт аралығында саны шектеулі ... ... ... ... ... Тьюринг машинасы.
2. Рекурсивтік функцияларға негізделген модель.
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 шешудің алгоритмiн құруда келесi схеманы қолданған жөн:
1. Есептiң қойылымын зерттеу.
2. Алгоритм әмбебап болуы үш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н ... ... назар аудару керек.
5. Алгоритмнiң дұрыс құрылғандығын тексеру. Алгоритм сипаттамасында кездескен қателердi жою.
6. ... ... ... ... құру қиын ... Оны дайындау барысында түрлi логикалық қателiктер жiберiлуi мүмкiн. Сондықтан алгоритмнiң дұрыстығына, оның ... ... көз ... үшiн ... есеп ... оны ... ... қажет. Әдетте осы мақсатта шешiмi белгiлi есептер (тестiк есептер) қолданылады. Мысалы, квадрат теңдеудi шешуге арналған алгоритмдi тексеруде 3 түрлi теңдеудi ... ... ... Әртүрлi нақты түбiрлi теңдеу.
2. Бiрдей нақты түбiрлi теңдеу.
3. Терiс дискриминантты теңдеу. Мұнда комплекстi түбiрлер анықталады не нақты сандар ... ... ... көрсетіледі.
1.4 Марковтың нормаль алгоритмдері
Марковтың нормаль алгоритмі (МНА) - алгоритм ұғымының формальды анықтамасын берудің ... ... бірі ... ... ... Бұл ... көрнекті кеңес математигі А.А.Марков (1903-1979жж.) 1940 жылдардың соңында енгізген. Марков алгоритмдері туралы сөз болғанда, оны ... деп атау ... ... ... мен ... ... жалпы тәсілдері алгоритмдік жүйе делінеді. Абстрактілік алфавиттегі сөздердің ... ... ... ... жүйе ... ... операторлар және қарапайым танып-білгіштер сияқты табиғаты екіжақты болатын объектілер енеді. ... ... деп ... ... ... ... ... тізбектей орындалуы нәтижесінде алгоритм-дік жүйедегі кез келген алгоритм жүзеге асырылады.
Қарапайым танып-білгіштер арқылы өңделетін ақпараттың ... ... да бір ... ... операторының орындау ретін бағдарланған граф арқылы беруге болады (бағдарланған граф - алгоритмнің граф-схемасы).
Алгоритмнің ... ... ... ... саны ... ... ... Төбелерді кейде тораптар (узлы) деп те атайды. Әрбір торапқа қандай да бір оператор не танып-білгіш сәйкестендіріледі. Тек кіріс, ... ... ... ... ... (1.1-сурет).
352107555245009994903619500
1.1-сурет
Оператор сәйкестендірілетін кіріс торабынан тек бір доға шығады. Ал танып-білгіш сәйкестендірілген тораптардан 2 доға шығады. Шығыс торабынан ешқандай доға ... ... ... ... ... саны түрліше болуы мүмкін.
Граф-схема арқылы анықталатын алгоритмнің жұмысы келесі түрде жүзеге асырылады: бастапқы сөз кіріс төбесіне енгізіліп, ... ... ... ... торапта шарт тексеріледі. Шарт қанағаттандырылған жағдайда сөз операторлық торапқа, керісінше жағдайда ... ... ... де ... ... төбесіндегі р сөзі схема тораптары арқылы түрлендіріліп, саны шекті ... ... ... ... жеткізілсе, онда алгоритм р сөзіне қолданылды деп есептелінеді. Р сөзі ... ... ... ... ... де граф-схеманың кіріс нүктесіндегі р сөзі шығыс төбесіне жетпей, қадамдардың саны шексіз өсіп кетсе, онда ... р ... ... деп есептеледі.
1.4.2 Нормаль алгоритмдер
Нормаль алгоримтдерде ... ... ... алмастыру операторы, ал қарапайым танып-білгіш ретінде кіріс танып-білгіші қолданылады. ... ... р1 ... ... да бір q ... ... енетіндігі-енбейтіндігі шартын тексереді.
Алмастыру операторы q сөзінің сол жағынан бастап, р1 сөзін р2 сөзімен алмастырады, яғни р1р2. ... abcabca ... ... bccb ... 2 ... ... acbacba ... береді:
abcabcaacbabcaacbacba.
Алгоритмнің орындалуы барысында алынатын р1,р2,..., рn сөздер тізбегі р1 сөзінен рn сөзіне жеткізетін дедуктивтік тізбек делінеді.
Кіріс танып-білгіші мен ... ... ... граф ... ... алгоритмдер жалпыланған нормаль алгоритмдер деп аталады. Мұнда әрбір алмастыру операторына сәйкес танып-білгіштен шығатын бір ғана доға ... ... bcba, bbaс ... ... ... ... нормаль алгоритмді қарастырайық (1.2-сурет). Бастапқы сөз bcbaab түрінде берілсін. Нәтижеде baaaac сөзі алынады:
bcbaabbcababbcaabbbaaabbbaaaac.
411480013716000Граф-схемалары келесі шарттарды қанағат-тандыратын ... ... ... ... ... ...
- Танып-білгішке сәйкестендірілген барлық тораптар нөмірлері бойынша 1 мен n ... ... ... ... сай ... ... ... алғашқы танып-білгішке қатысты торапта немесе шығыс торабында түйіседі. Алғашқы жағдайда алмастыру қарапайым алмастыру деп, екінші жағдайда нәтижелік алмастыру деп ... ... ... ... доға ... бірінші танып-білгішке жалғастырылады. ... ... ... ... ... р1р2 ... ал ... алмастырулар р1.р2 түрінде таңбаланады.
Сөзге ешқандай алмастыруды қолдану ... ... не ... да бір ... ... орындалған жағдайда алмастыруларды орындау тоқтатылады.
Алфавиті А={+,1} және алмастыру ... ... `1'.'1' ... ... нормаль алгоритмі жұмысын қарастырайық. Бастапқы сөз ... ... ... Алгоритмнің орындалу нәтижесі:
`11+11+1''1111+1''11111'.
Алгоритм жұмысы барысында бірліктер топтастырылады.
Нормализация принципі. ... да бір ... А ... ... ... кез келген алгоритмге осы алфавит бойынша эквивалентті нормаль алгоритм құруға болады.
42291004572000 ... ... А ... ... құрылған алгоритмге эквивалентті алгоритм құру мүмкін болмайды. Бірақ А алфавитіне жаңа әріптер ... ... ... ... нормаль алгоритм тұрғызуға болады (1.3-сурет).
Егер де N алгоритмі А алфавитінің кеңейтілуі арқылы құрылса, онда N алгоритмі А алфавитіне қатысты ... ... ... ... де А ... ... р сөзі үшін F(p)=N(p) орындалатындай N нормаль алго-ритмі табылса, онда А алфавитіне қатысты ... бір ... ... ... ... ... есептелінетін делінеді. ... {0,1} ... F(p)=pa ... ... ... ... ... {0,1,2} кеңейтілген алфавитінде 2002, 2112, 2.а, 2 схемалы N нормаль алгоритмі берілсін (мұндағы, - бос ... ... ... ... да бір 0110=p ... ... Бірінші қадам нәтижесі бойынша 20110. Әрбір келесі қадамда 2 символы бір орынға оңға қарай ... ... ... ... 01102 сөзі ... яғни ...
Дербес жағдайда . схемалы алгоритм F(p)=p функциясын, ал ... ... еш ... анықталмаған функция мәнін есептейді.
Нормализация принципі математикалық ... ... ... ... алгоритмдердің композициясы
Берілген алгоритмнен жаңа алгоритм құру үрдісі композиция делінеді.
1) Алгоритмнің суперпозициясы. А мен В алгоритмдерінің суперпозициясында А алгоритмінің ... сөзі В ... ... сөзі ... қарастырылады. Нәтижені C(p)=B(A(p)) арқылы өрнектеуге болады. Суперпозиция кез келген саны шекті алгоритмдер үшін орындалады.
2) Х ... А,В ... ... деп сол ... ... С алфавитін айтады. Мұнда А және В алгоритмдерінің анықталу облыстарының қиылысуындағы кез келген р сөзі A(p) және B(p) қатар орналасқан ... ... Ал ... ... үшін бұл ... анықталмаған.
Мысалы, X={a,b} алфавиті, A={abba}, B={baab} алгоритмдері және олардың анықталу облыстарының қиылысуында ... аba сөзі ... ... ... ... ... ... алынады.
3) Алгоритмнің тармақталуы А,В және С алгоритмдерінің ... ... ... ... D болсын. D алгоритмінің анықталу облысы А,В және С үш ... ... ... ... Осы ... ... кез ... р сөзі үшін егер де C(p)=e болса, онда ... және ... ... ... е - бос жол.
4) ... ... А, В ... композициясы арқылы өрнектеледі. Композиция нәтижесі С алгоритмі арқылы беріледі. Қандай да бір р ... ... C(p) ... сөзі В ... А алгоритмін бірнеше рет тізбектей қолдану арқылы алынады.
Мысалы, X={a,b} алфавиті, A={abba}, ... ... ... ... ... ... ... түрде алынады:
ababbbaabbbababbbaabbbababbbaaab.
1-4 композицияларды нормаль алгоритмдерге қолдануда нормаль алгоритмдер алынады. Кез келген алгоритмнің жұмысын орындай-тын универсал алгоритм құру есебінің маңызы ... ... ... ... ... ... ... - шешу алгоритмдері табылмайтын есептердің болатындығын зерттеуге мүмкіндік берді. Бірқатар есептердің кез келген есептеу ... ... ... шешілмейтіндігі дәлелденген.
f функциясы есептелетін функция делінеді, егер де осы функцияның анықталу облысындағы кез келген аргумент үшін функция ... ... ... ... табылса. Егер де мұндай машина табылмайтын болса, онда f функциясы есептелінбейтін функция делінеді.
f функциясының анықталу облысының ішкі ... ... үшін ... ... есептейтін Тьюринг машинасы бар болса да, f функциясы ... ... ... ... f ... ... нәтижесі "ақиқат" не "жалған" түріндегі логикалық өрнек болса, онда есеп берілген есептелетін функцияға қатысты шешілетін не шешілмейтін есеп деп ... Есеп ... ... кейбірі үшін шешілетін, ал келесі біреулері үшін шешілмейтін болғандықтан, бастапқы берілгендердің мүмкін мәндерін нақтылап көрсету керек.
Машина жұмысын тоқтату ... ... ... ... есепке жатады. Ол келесі түрде беріледі:
Тьюринг машинасына арналған ... ... ... уақыт өтуіне қарай программа жұмысының аяқталатындығын не шексіз жұмыс істейтіндігін ... ... ... проблемасының шешілмейтіндігін дәлелдеу өзге есептердің де оған келтірілетіндігімен маңызды. Мысалы, Тьюринг ... бос ... ... ... машина жұмысын тоқтатудың қарапайым есебіне келтіруге болады.
2 Автомат - ақпараттық жүйенің негізгі Элементі. Абстрактілі автоматтар
2.1 ЭЕМ - ... ... ... ... ... ... ... қиындығы түрліше есептерді шешуде анағұрлым күрделі амалдарды орындайтын "қара жәшік" ретінде ұғынылады. Ақпаратты түрлендіру, өңдеу үрдісіне талдау жасай ... ... ... ... ... ... келесі мәселелерге назар аударған жөн:
* Кез келген есептеуіш машинасы (үлкен немесе кіші ЭЕМ, ... ... ... автоматты түрде жұмыс істейді. ЭЕМ-дерді автомат ретінде келесі құрылымдық схемалар түрінде беруге болады (2.1, ... ... ... ... ... ... ... құрылғылар
Орындаушы құрылғылар
Қосымша құрылғылар
Орындаушы элементті арифме-тикалық-логикалық құрылғы (АЛҚ), жад, енгізу-шығару құрылғылары құрайды.
Автоматтың басқарушы элементі-нің қызметін автоматты жұмыс режимін қамтамасыз ... ... ... атқарады.
Қосымша құрылғыларға автоматтың жұмысын кеңейтіп, жақсартатын қосымша құралдар жатады.
914400201930 Жад
Арифметикалық-логикалық құрылғы
Енгізу /
шығару
Басқару ... ... ... ... ... құрылғысы
Перифериялық құрылғылар
Ақпарат
2.2-сурет. ЭЕМ-нің құрылымдық схемасы.
2.2 ЭЕМ-нің дискретті сипаттамасы
ЭЕМ - ... ... ... ... Бұл ... екі ... идеяны негіздейді. Біріншісі, ЭЕМ - цифрлық және ... ... ... ... ... Бұл ... енгізілетін ақпараттың (мәтіндік, графикалық, сандық және т.с.с.) ... да бір ... ... ... мен ... ... білдіреді. Сондықтан санау жүйесін таңдау компьютер құрастырушылар үшін ... ... ... ЭЕМ ... ... не оның жадында сақталатын арнайы программамен басқарылады.
Жад (есте ... - ... ... аралық және қорытынды нәтижелерді сақтауға арналған ЭЕМ-нің құрамдас бөлігі. Машина жадында оның жұмысын басқаратын программалар да сақталынады.
Жад ... мен ... ... жасау уақыты жадты сипаттайтын негізгі параметрлер болып табылады.
Жад сыйымдылығы - ... ... ... ... ... санын сипаттайды. Сөз деп ұзындығы шекті алфавит ... ... ... айтады. Сөзді сақтайтын жад бөлігі жад ұяшығы делінеді. Жад сыйымдылығын ондағы сөз не ... ... ... ... Жад ұяшығының ұзындығы битпен өлшенеді. Бір бит бір екілік разрядқа тең (не 1 байт = 8 бит). Жад ... ... не ... ... ... ақпараттарды орналастыра алады. ЭЕМ-нің ақпаратты өрнектеу әдісіне қарай формат сөзбен, екі еселі сөзбен немесе ... ... ... мүмкін.
Жадқа қаратпа жасау уақыты деп жадқа ақпаратты енгізу және одан шығару уақыттарының аралығын айтады. Ол ... ... ... үшін жұмсалған уақытпен сипатталады.
Есте сақтау құрылғыларын дайындау барысында физикалық элемент ретінде ... ... ... ... ... ... мен ... оптикалық есте сақтау элементтері және т.б. қолданылады.
Арифметикалық-логикалық құрылғы (АЛҚ) цифрлық ақпараттың негізгі түрлендірушісі ретінде қолданылады. АЛҚ - ... ... ... ақпараттарды өңдеуге қатысты арифметикалық және логикалық амалдарды орындайтын ЭЕМ-нің құрамдас бөлігі. Ол ... да бір ... ... сай ... ... ... ... сипатталады. Есептеу үрдісі жүргізілетін санау жүйесі АЛҚ-ның басты сипаттамасы болып табылады.
Қазіргі есептеу құрылғыларында процессор не микропроцессор негізгі орындаушы элементті ... ... ... АЛҚ, ... жад және ... ... ... негізінде құрастырылған есептеу техникалары микроЭЕМ деп аталады және оларда жадтың екі түрі қолданылады: RAM (Random-Access-Memory) ... ... жад және ROM ... ... жад. ... ... ... тілдердің трансляторын, қандай да бір мақсатта қолданылатын дайын программалар пакетін енгізіп қоюға болады. Бұлар ... ... ... ... ... ... және шығыс каналдарының, сондай-ақ ЭЕМ-нің сыртқы құрылғылармен әрекеттесу құралдары мен әдістерінің болуы ... ... оны ... дейінгі орындалатын іс-әрекеттер уақытын жылдамдатуға мүмкіндік береді.
2.3 Тьюринг машинасы
2.3.1 Тьюринг машинасы ... ... ... (ТМ) деп ... ... ... ... ғалымы Алан Тьюринг 1936 жылы ұсынды және бұл модельдің ЭЕМ пайда болуына үлкен маңызы болды. Тьюринг машинасы келесі ... ... сол және оң жақ ... ... ұяшықтарға бөлінген лента;
* символдарды оқитын және жазатын бастиек;
* лентаны жылжытатын механизм (лентатартқыш);
* ... ... Ол ... да бір шекті жиынтыққа тиісті q0,q1,...,qs дискреттiк ... ... ... ... ... ... жиынтық ішкі күйлер алфавиті делінеді, ал q0 ... күй ... ... ... ... ... әріптерін оқиды, өшіреді және жазады. Әрбір уақыт мезетінде лентаның әрбір ұяшығында А ... ... ... ... ... ішінде a0 әрпі - бос орын жиі ... ... ... ... лентаның қандай да бір ұяшығының үстінде орналасады. Ол ағымдық жұмыс ұяшығы деп ... ... ... ... ... ... үстіне орналасатындай етіп жылжытып отырады. Мұнда келесі жағдайлардың бірі орын алуы мүмкін:
а) бастиек лентаның сол жақ шетіне шығып ... Бұл - ... ... ... ... ... ... тоқтатылады. Мұнда жұмысты тоқтату туралы командалар орындалады.
2.3.2 ... ... ... сипаттамасы
Тьюринг машинасы жұмыс істеу реті Тьюринг машинасының кестесімен сипатталады. Бұл кесте 4 ... және саны ... ... ... ... құрайды. Әрбір жол qiajvijqij командасынан тұрады. Мұндағы 0is, 0jt және qij {q0,q1,...,qs}.
vij арқылы ... ... ... мен ... ... ... ... лентатартқыш механизм үшін l - лентаны солға, r - оңға ... s - ... ... ... ... ... Демек, vij - Тьюринг машинасы орындайтын іс-әрекет. Мұнда лента ұяшығына a0,a1,...,at алфавитінің символы енгізілуі, не бастиек ... не ... ... ... qij ... ... күйі болып табылады.
Тьюринг машинасы келесі ереже бойынша жұмыс істейді: егер Тьюринг машинасы qi күйінде болса, онда бастиек жұмыс ұяшығындағы aj ... ... ... ... ... ... жолы кестеде 1 рет қана кездессін.
Егер vij жұмыс алфавитінің әрпі болса, онда бастиек ... ... осы ... ... ...
Егер vij лентатартқыш механизмнің r не l командасының бірі ... онда ... ... оңға не ... жылжытылады.
Егер vij=s болса, онда машина жұмысы тоқтатылады.
Тьюринг машинасы жұмысын қандай да бір бастапқы конфигурацияға сай ... ... ... ... ... ... q0 ... күйінде болып, бастиек А алфавиті әріптерінің бірі енгізілген ... ... ... ... ... ... жұмыс алфавитінде неғұрлым түрлі символдар көп болса, соғұрлым лентада түрлі мәтіндік және сандық ақпараттар көбірек өрнектеледі. Ал Тьюринг ... ... ... арқылы әртүрлі күйлерге өтуі оның аралық нәтижелерді сақтау механизмін сипаттайды.
Тьюринг машинасының жұмыс істеу тәртібін анықтайтын кесте ... ... ... Ол ... ... орындалмайды, тек лентадағы қандай да бір мәтін символдарының түрленуін сипаттайды. Тьюринг ... ... ... ... схемасы деп, кейде Тьюринг машинасы деп аталады.
Осы кезге дейін түрлі алгоритмдер ... ... ... ... ... Бұл ... машиналары бір-бірінен командалары, ішкі және сыртқы алфавиттерімен ерекшеленеді. Кез келген Тьюринг машинасына арналған алгоритм-дерді орындайтын әмбебап Тьюринг машинасын да ... ... ... әрбір Тьюринг машинасының конфигурациясы мен программалары әмбебап Тьюринг машинасының сыртқы алфавитіне кодталады. ... ... ... ... мүмкін:
* Түрлі таңбалар түрлі кодтау топтарымен алмастырылуы тиіс. Әрбір символ тек бір ғана ... ... ... ... жазбалар жолдары жекелеген кодтау топтарына бірмәнді түрде жіктелуі тиіс.
* 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,..., qn+t} болатын T машинасын айтады. Мұнда T1,T2 ... ... ... ... бірі ... ... T =T1*T2.
Осылайша дәрежелеу амалы анықталады: n-ші дәрежелі T машинасы деп ... ... ... ... ... саны ... амалы тек бір ғана машинаға қолданылады және ... ... ... T1 ... ... күйді сипаттасын. r-ші күй таңдалып, машина схемасының алғашқы күйімен беттестіріледі. Нәтижеде алынған T1:T= T1 машинасы итерация ... ... ... ... ... стандартты жағдайы. Есепте-летін функция
Тьюринг машинасы үшін схемасы ... ... ... ... ... әрпі ... ... ерекшелейтіндігін көрсетеді. Тьюринг машинасы күйіне көшіп, ұяшықтағы ... ... оның ... ... ... ... кейін Х мәніне сай бастапқы ұяшықтан кейінгі не алдыңғы ұяшық таңдалынады. Егер де Х орнына команда ... онда ... ... өзі ... ... кейін Тьюринг машинасы және т.с.с. командаларды орындауға көшеді.
А және Q алфавиттеріндегі немесе АQ ... ... кез ... ... сөз ... ... машинасының k-ші конфигурациясы деп k-ші такт алдындағы ақпарат енгізілген лента күйін айтады. Мұнда ағымдық ұяшық пен машина күйі қоса көрсетіледі. ... ... ... мәлімет енгізілген ұяшық саны шекті болады да, қалғандары бос ... ... ... бос емес ... ... ... стандартты жағдайда қабылдайды, егер де
* барлық өзге ... бос ... ... сөзі ... ... оң жақ ... ерекшелеп тұрса.
Стандартты жағдай бастапқы (соңғы) делінеді, егер де сөзді стандартты жағдайда қабылдайтын ... ... ... ... ... тоқтату) күйінде болса.
Тьюринг машинасы сөзін сөзіне ... егер де ... ... жағдайдағы сөзі командалардың шекті саны орындалғаннан кейін сөзіне ауыстырылып, соңынан ... ... іске ... да бір алфавитінің сөздері жиынында мәндері де сол ... сөз ... ... ... ... ... араларында бір бос ұяшық қалдырылып, тізбектей жазылған, функцияның анықталу облысына енетін k сөзден тұратын кез ... ... осы ... ... ... ... ... түрлендіретін алфавитті Тьюринг машинасы берілсін. Бұл Тьюринг машинасы функциясының анықталу облысына кірмейтін кез келген k сөздер жиынтығы ... ... ... ... ... ... ... машинасын берілген функция мәнін есептейді деп атайды. Ал функцияның өзі Тьюринг машинасы бойынша есептелетін немесе жай ғана ... ... ...
Алгоритмдер теориясының негізгі гипотезасы (Черч тезисі) бойынша мәні қандай да бір алгоритммен есептелетін кез келген функция ... ... ... ... бұл ... ... сай Тьюринг машинасында жүзеге асырылады.
Алгоритм ұғымын формальдау (мысалы, Тьюринг машинасы) алгоритмдік тұрғыдан шешілмейтін бірқатар мәселелердің ... ... ... ... ... ... Бір ... есептерді шешудің біртұтас (әмбебап) тәсілінің болмауы олардың алгоритмдік тұрғыдан шешілмейтіндігін білдіреді. ... ... ... ... шешудің жекелеген дербес тәсілі табылуы мүмкін.
2.4 Пост машинасы
2.4.1 Пост машинасының құрылысы мен жұмыс принципі
1936 жылы американ ... Эмил Пост және ... ... ... ... бір мезгілде, бір-бірінен тыс өздерінің абстрактілі машиналарын ұсынды. Бұл абстрактілі машиналар өздеріне арналған ... ... ... ... дәлелдеуге мүмкіндік берді. Аталған машиналар бастапқы мәліметтерді енгізіп, программа орындалғаннан кейін ... ... ... ... ... ... ... Пост машинасының мүмкіндігі жоғары болғанымен Тьюринг машинасына қарағанда аз қолданыс тапқан. Пост машинасы арқылы ЭЕМ-де программа құрып үйренуге ... ... ... ... ... ұяшықтардың шексіз тізбегінен және бастиектен тұрады. Әр ұяшық бос болуы не "V" таңбасымен толтырылуы мүмкін.
Бастиек әрбір ... ... ... оңға не ... ... 1 ... ... Бос ұяшыққа бастиек "V" таңбасын енгізеді. Егер ұяшықта таңба болса, онда ол өшіріледі. Бастиек кейде ұяшықта таңбаның бар-жоқтығын тексереді. ... ... ... ... ... ... ... күйін білдіреді және машина жұмысы барысында өзгеріп отырады.
V
V
V
V
V
2.3-сурет. Пост ... ... ... nKm ... ... ... n команданың реттік нөмірі, K - бастиектің орындайтын іс-әрекеті, m - ... тиіс ... ... нөмірі.
2.4.2 Пост машинасы командалары
Пост машинасында команданың 6 түрі қолданылады:
* Бастиекті 1 ұяшыққа оңға жылжыту: n ... ... 1 ... солға жылжыту: n m.
V
V
V
V
V
V
* Бастиектің тұсындағы ұяшыққа таңбаны енгізу: n М m.
V
V
V
V
V
V
V
* Бастиектің тұсындағы ұяшықтан таңбаны жою: n С ... ... ... ... ... ... ... Егер таңба бар болса, онда басқару m1 командасына беріледі, керісінше жағдайда m2 командасы орындалады.
2781300753110 m2
00 m2
182880056197500 n
m1
n
m1
* Машинаны тоқтату: n Стоп m. ... ... бар ... ... таңба енгізуі немесе ұяшықтағы таңбаны жоюы апаттық жағдай делінеді.
Пост машинасы программасы деп ... ... ... бос емес командалар тізбегін айтады:
* n-ші орында n-ші нөмірлі команда сақталады;
* әрбір команданың нөмірі командалар тізімінің қандай да бір нөмірімен ... ... ... ... ... ... сай ... орындалу барысында тоқтатылу себептеріне айрықша назар аударылады:
* Стоп командасы бойынша программа жұмысын тоқтату. Осылайша программаны ... ... ... және оның ... ... Орындалмаған командаға сай машина жұмысының тоқтатылуы. Бұл жағдайда машина жұмысының тоқтатылуы нәтижесіз делінеді.
* Машина жұмысы уақытша тоқтатылмайды. Осы және ... ... ... ... ... ... ... үшін лентаның сол жағындағы бос ұяшықтың тұсындағы жағдайы бастиектің бастапқы жағдайы делінеді.
Пост ... ... ... ... ... ... ЭЕМ мен Пост машинасының ұқсастықтары:
* бос немесе толтырылған күйде болатын ақпарат ... ... ... (ұяшықтар биттер);
* әрбір қадамда тек бір ғана іс-әрекет ... ... ... ... санының болуы.
Екі машина да программа арқылы жұмыс істейді. Бірақ Пост машинасында ... ... ... да, ... ... Ал ... ... адрестері арқылы оқылады. ЭЕМ-де қолданылатын командалар жүйесі ... және ... ... Шексіз регистрлі машина
2.5.1. Шексіз регистрлі машина (ШРМ). Бастапқы конфигу-рация
Алгоритмге нақты ... ... беру ... ... Пост, Тьюринг, Марков және т.б. өзара ұқсас бірнеше анықтама ойлап тапқан. Кейінірек бұл анықтамалардың мәндес екендігі, олардың бір ғана ұғымды ... ... ... ... ... ... ... регистрлі машина (ШРМ) ұғымын қарастырамыз. ШРМ жұмысы нақты ЭЕМ жұмысына ұқсас.
Әр алгоритм бастапқы, аралық және нәтижелік ... ... ... ... ... ... үшін ШРМ-де берілгендер ретінде Z0 теріс емес бүтін сандарды қарастырамыз. Себебі мұнда барлық объектілер және оларға қолданылатын ... ... ... кодталады. Демек, оны натурал сандарға қолданылатын амалдар ретінде қарастыруға болады. Біз ШРМ орындайтын командаларды (), әр команда орындайтын іс-әрекетті ( ... ... ... ... ... ... ... танысамыз.
ШРМ қарапайым сипаттайтын атқарушы болып табылады. ... болу ... ... ... жад ... ... Шексіз регистрлі машинаның жады шектеусіз. Жад ұяшықтары регистрлер делініп, ... ... ... ... ... кез ... уақыт мезетінде қандай да бір бүтін оң сан енгізілуі мүмкін.
R1
R2

R4
...
r1
r2

r4
...
Саны ... ... ғана ... ... ... енгізіледі де, қалғандары нөлдермен толтырылады.
2.5.2. ШРМ командалары
Әрбір алгоритм жадтың тек шекті бөлігін ғана ... ШРМ төрт ... ... ... Z(n) ... айналдыру командасы; S(n) 1-ді қосу командасы; Т(m,n) адресті алмастыру командасы; J(m,n,q) шартты көшу командасы. Z(n), S(n), Т(m,n) ... ... ... ... таңбалануы
Команда бойынша ШРМ орындайтын
іс-әрекет
Z(n)
Rn:=0
S(n)
Rn:= Rn+1
Т(m,n)
Rm:=Rn
J(m,n,q)
Егер Rm=Rn ... q ... ... ... ... бастап, орындалатын бос емес командаларының тізбегі алгоритм деп аталады. Алгоритм командалары ШРМ-нің жад ... ... ... ... ... ... ... R1,R2,R3,...регистрлеріндегі r1,r2,r3,... сандар тізбегі бастапқы конфигурация деп ... да бір Р ... ... командалары тізбегінен тұрсын. ШРМ алдымен І1 командасын, содан кейін І2,І3,....т.с.с. командаларын J(m,n,q) түріндегі команда ... ... ...
ШРМ Р: І1,І2,..., Іs алгоритмін мүмкін болғанша орындайды. Есептеу үрдісі келесі команда жоқ ... ... ... Яғни ШРМ Ік ... ... ал одан ... ... Іv, мұндағы V>S. Бұл келесі екі жағдайдың бірімен ... егер Ік=Іs ... және Ік ... ... ...... соңғы командасы орындалса);
2)егер Ік= J(m,n,q), Rn=Rm және q>S болса;
3) егер Ік= J(m,n,q), RnRm және q=S ... Бұл ... ... Ік командасы орындалғаннан кейін есептеу үрдісін тоқтатты" делінеді. ... да бір ... ... қолданылған алгоритм нәтижесі деп соңғы конфигурациядағы R1 регистрінде ... r1 ... ... есептеу үрдісі ешқашан тоқтамайтын алгоритм кездеседі. Кез келген бастапқы конфигурация үшін төмендегі алгоритм жұмысы шексіз орындалады:
І1 S(1);
І2 J(1,1,1).
Егер де есептеу ... ... ... ... онда бұл ... ... конфигурацияға қолданылмайды делінеді.
3 Алгоритмдердің тиімділігі мен күрделілігін талдау
3.1 ... ... ... ... ... ... ... шешілмейтіндігін дәлелдеудің маңызы зор. Қандай да бір проблеманың шешілмейтіндігін дәлелдеуде үйлестіру ... ... ... жиі ... ... мәні ...
Берілген тұжырым бойынша Pr1 проблемасын шешу Pr2 про-блемасын ... ... ... егер Pr2 проблемасы Pr1 проблемасы арқылы шешілсе, онда Pr1-дің ... Pr2 ... ... шығады. Керісінше, Pr2-нің шешілгіш-тігінен Pr1 проблемасының шешілетіндігін аламыз.
Математикада алгоритмнiң күрделiлiгi ұғымын білудің мәнi зор. Мысалы, мәні 1000-нан аспайтын натурал санды ... табу ... ... ... тек "иә" ... "жоқ" деп ... ... сұрақтар қойылсын. Санды табудың алгоритмдерінiң бiрi төмендегiше: [1; 1000] ... ... ... ... Сан ... үрдіс жүргiзiле бередi. Мұнда ең көбі 999 ... ... ... ... ... басқаша құруға да болады.
* Алдымен ойланған санды 500-бен салыстырады.
* Егер ... сан ... ... ... онда ол 750-мен салыстырады және т.с.с. Осылайша 10 сұрақпен ғана шектелуге болады. Әр қадам ... ... ... саны екi ... азайып отырады. Мұнда алгоритмнiң күрделiлiгi ретiнде сұрақтар санын ... ... ... ... ... ... қарағанда 100 есе күрдел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лгендер ... ... ... есеп ... n ... онда жалпылаған есептi шешу алгоритмнiң күрделiлiгi осы n-ге қатысты функция ... ... ... Екi n ... санды баған бойынша көбейту керек болсын. Ол бiр ... ... n2 рет ... ... ... күрделiлiгi "*" амалы бойынша анықталатындықтан ол n2-на тең. Бұл - полиномдық алгоритмнiң мысалы болып табылады.
Математикада бiр ... ... ... ... ... мүмкiн. Сондықтан есептiң күрделiлiгi ретiнде оны шешу ... ең аз ... ... Практикада полиномдық алгоритмдер арқылы шешiлмейтiн есептер де кездеседі. Мысалы, Коммивояжер есебi.
Коммивояжер есебi. Жолдар ... ... саны n ... ... Әр жол үшiн жүру ... ... ... қалалар арқылы өтетiн, жол жүру ақысы ең төмен болатын бағытты (маршрутты) анықтау керек.
Алгоритмдi талдауда бағалаудың мәнi үлкен. ... ... ... ... ... компьютер мен пайдаланушының ресустарын ескеру керек. Мысалы, қажеттi жад көлемi мен ... ... ... ... ... ... ... программаның "әлсіз" бөлiктерiн, компьютер жадының пайдаланылмайтын аймақтарын анықтауға болады. Бiр ғана есептi шешудiң бiрнеше ... ... үшiн ... ... қажет. Нәтижеде анағұрлым жетiлдiрген алгоритмдi енгiзiп, ескiлерiн қолданыстан шығару керек.
P ... ... А ... ... ... осы ... бастапқы берiлгендерi бойынша қажеттi нәтижеге жеткiзетiн iс-әрекеттер тiзбегi ... ... Ал ... ... ... жетуге бағытталған командалар - операторлар тiзбегiнен тұрады.
Алгоритмдегi берiлгендер бiрқатар аралық ... ... Осы ... ... саны немесе iс-әрекеттер мен команда қиындықтарының қосындысы f(A,P) ... ... ... ... ... ... А алгоритмінiң уақытқа қатысты күрделiгi деп те атайды. Алгоритм есептер тобын шығару үшiн құрылады, ал қиындық әрбiр есептi (жекелеген) шешу үшiн ... ... ... ... ... ... тобын кластарға жiктейдi, әрбiр класта қиындықтар өзара салыстырылатындай болуы тиiс. Әдетте мұндай ... ... бiр не ... ... санды параметрлермен анықталынады. Мұнда қолданылатын берiлгендердiң құрылымына сай ... ... ... ... алынады.
n - есептiң өлшемi болсын. n - бүтiн сан, вектор не одан да күрделi ... ... ... ... - кез келген n өлшемдi есептi шешудің А алгоритміндегi орындалатын амалдардың ең көп саны ... ...
f ... f(A,P) / P есебi n өлшемдi}.
Кез келген n мәнi арқылы алгоритм күрделілігінің уақыттық бағасын ... ... ғана ... ... ... де ... болады.
Есептiң өлшемiн (көлемiн) кеңейтуге қатысты f(A,n) өзгерісі асимптотикалық уақыттық күрделілік делінеді.
Егер n ... ... f(A,n) өсу ... ... ... онда А алгоритмi - полиномдық алгоритм делiнедi. Ал, керiсiнше жағдайда, экспоненциалдық алгоритм болып табылады. ... ... ... бағасының критерийі үшiн қандай да бiр класты есептi шешудiң орташа уақытын алуға болады.
Анағұрлым көлемдi есептердi шешуде ... ... ... дұрыс. Көлемi шағын есептер үшiн қарапайым алгоритмдерi пайдалануға болады.
Қандай да бiр n өлшемді P есеб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р U ... үшiн ... мен ... құру ... ... Осы n өлшемдi есептер класы үшiн
H(U,n)=MIN{F(A,n) / A алгоритмi U класында анықталған}
ұғымын, ал ... ... үшiн ... / A ... U класында анықталған}
ұғымын енгiзуге болады.
Алгоритмдер класының эталоны ретiнде Тьюринг машинасы ақырлы автоматында ... ... ... есеп ... ... ... ... күрделi делiнедi, егер де бұл есептi полиномдық ... ... ... ... ... ... ... табылса.
Керiсiнше жағдайда, есептiң (есептер класының) күрделiлiгi NP-типтi немесе экспоненциалдық делiнедi.
Түрлi алгоритмдердi салыстыруда олардың ... ... ... ... ... (мысалы‚ уақыттық бағалау). Есептi шешу барысында пайдаланылатын жад көлемi (сыйымдылық сипаттамасы) де кез ... ... ... ... болып табылады.
Анағұрлым "қарапайым" алгоритмдер логарифмдiк не сызық-тық күрделiлікті алгоритмдер деп аталады. Ал "қиынырақ" алгоритмдерге күрделiлiгi экпоненциалдық функция ... ... ... ... ... ... күрделiгiн бағалау қиын жұмыс. Бұл мәселе математиканың Асимптотика атты арнайы бөлiмiнде қарастыры-лады. Мұнда келесi ... ... ... Егер де ... да бiр C тұрақтысы үшiн n>n0 жағдайында f(n)

Пән: Информатика
Жұмыс түрі: Курстық жұмыс
Көлемі: 29 бет
Бұл жұмыстың бағасы: 1 300 теңге









Ұқсас жұмыстар
Тақырыб Бет саны
«дағдарыстық күйлер және посттравмалық бұзылыстар »7 бет
Алгоритм және алгоритмнің қасиеттері3 бет
Алгоритмнің күрделілігін есептеуге қолдалынатын тәсілдер21 бет
Алгоритмнің қасиеттері5 бет
Алгоритмнің құрылымдық негіздері мен қолдану тәсілдері26 бет
Аудиторлық қызмет жөнiндегi заң. аудиттiң концепциялары мен постулаттары7 бет
Аудиттің жалпы постулаттары6 бет
Аудиттің постулаттары, стандарттары және нормалары. ХАС сәйкес аудитті жоспарлау32 бет
Бақытжан Майтанов. Қазіргі қазақ поэзиясы және постмодернизм7 бет
Блоксхема алгоритмнің графикалық өңделуі.9 бет


Исходниктер
Пәндер
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить


Зарабатывайте вместе с нами

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Сіз үшін аптасына 5 күн жұмыс істейміз.
Жұмыс уақыты 09:00 - 18:00

Мы работаем для Вас 5 дней в неделю.
Время работы 09:00 - 18:00

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь