#1 слайд
Алгоритмдік шешілмейтін есептер Алгоритмдік шешілмейтін есептер Аты-жөні www.company.co m

1 слайд

#2 слайд
Кіріспе Өздеріңіз білетіндей, мәңгілік қозғалтқышты құру мүмкін емес, өйткені бұл табиғатты қорғаудың әмбебап физикалық заңдарына қайшы келеді. Сол сияқты, математика мен информатикада жалпы шешімі жоқ есептер бар. Алгоритмдік Шешілмейтін есептер 2www.company.co m

2 слайд

#3 слайд
Алгоритм тек дискретті нысандармен жұмыс істейтіндіктен, кез — келген алгоритмдік есеп – бұл көптеген дискретті нысандарда (кіріс сөздерінде) берілген функция. 3www.company.co m

3 слайд

#4 слайд
Мысалы, шахмат позициясы бойынша дұрыс ойында кім жеңетінін анықтау қажет болсын — ақ, қара немесе тең ойын. Осы алгоритмге сәйкес функцияны құрайық. Ол үшін әр позицияны сәйкес алфавиттегі v сөзімен (символдық жолмен) кодтауға болатын кодтау әдісін таңдаңыз. Содан кейін берілген тапсырма осындай сөздердің жиынында берілген f(v) функциясына сәйкес келуі мүмкін: 4ақ жеңетін позиция коды, қара жеңетін позиция коды, жеребе болатын позиция коды, қате позиция коды.

4 слайд

#5 слайд
Егер тапсырмаға сәйкес функция есептелетін болса, онда тапсырма алгоритмдік шешілетін деп аталады — оны есептеу үшін алгоритм құруға болады. Егер есепте анықталған функция есептелмесе, онда оны шешудің алгоритмі жоқ. 5www.company.co m

5 слайд

#6 слайд
Алгоритмдік тұрғыдан шешілмейтін мәселе - есептелмейтін функцияға сәйкес келетін тапсырма. 6

6 слайд

#7 слайд
1900 жылы Париждегі Халықаралық математикалық конгресте атақты математик Дэвид Гильберт 23 шешілмеген математикалық есептерді тұжырымдады Қазір олардың көпшілігі толығымен немесе ішінара шешілді. 7

7 слайд

#8 слайд
Әйгілі «Гильберттің оныншы мәселесі» берілген алгебралық теңдеудің бүтін сандарда шешімі бар-жоғын анықтауға мүмкіндік беретін әдісті табуды талап етеді. Мысалы : х 2  + у 3  + 2 = 0 оның екі бүтін шешімі бар, (5; -3) және (- 5; -3). Қиындық көптеген белгісіз теңдеулер үшін есепті шешуге мүмкіндік беретін бірыңғай әдісті (алгоритмді) табу керек болды. 8

8 слайд

#9 слайд
ХХ ғасырдың басында мұндай алгоритм бар деген сенім болды, сондықтан оны табандылықпен іздеді. Алайда, 1970 жылы кеңестік математик Ю. В. Матиясевич бұл мәселені шешудің жалпы алгоритмі жоқ екенін дәлелдей алды. 9

9 слайд

#10 слайд
Неміс математигі Г. в. Лейбниц XVII ғасырда кез- келген математикалық тұжырымдардың дұрыстығын тексеру әдісін табуға тырысты. Өздеріңіз білетіндей, барлық дерлік математикалық теориялар аксиомаларды қолдануға негізделген (дәлелсіз қабылданған ережелер), олардан барлық басқа тұжырымдар (теоремалар) алынады. Тапсырма берілген аксиома жүйесі шеңберінде А формуласынан в формуласын шығаруға болатындығын анықтауға мүмкіндік беретін алгоритм жасау болды («шығаруды тану мәселесі»). 10

10 слайд

#11 слайд
Дегенмен, теореманың жеке сыныптарын компьютерде дәлелдеуге болады.1936 жылы американдық математик А. Черч бұл есептің жалпы түрінде алгоритмдік тұрғыдан шешілмейтіндігін дәлелдеді, сондықтан кез-келген теореманы дәлелдеуге жарамды әмбебап алгоритмді тұжырымдау мүмкін емес 11

11 слайд

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

12 слайд

#13 слайд
Кейбір жаңа мәселенің шешілмейтіндігін дәлелдеу үшін олар оны бұрыннан белгілі алгоритмдік шешілмейтін есептерге дейін азайтуға тырысады. Егер бұл сәтті болса, онда жаңа тапсырма алгоритмдік түрде шешілмейді. 13А мәселесі шешілмейді делік, егер біз в мәселесін шешу үшін алгоритм құра алсақ, онда оның көмегімен а мәселесін шешу алгоритмін құруға болады.

13 слайд

#14 слайд
Сондай — ақ, олардың алгоритмдік түрде шешілетіні немесе шешілмейтіні белгісіз мәселелер бар – шешім табылмады, бірақ алгоритмдік шешілмейтіндігі дәлелденбеді. Page 14 14

14 слайд

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

15 слайд

#16 слайд
Алгоритмдік шешілмейтін эквиваленттік мәселе дәлелденді: берілген екі алгоритм бойынша олардың кез келген жарамды бастапқы деректер үшін бірдей нәтиже беретінін анықтау. Сондықтан бағдарламаларды әзірлеуге қатысты көптеген маңызды мәселелерді шешуді толығымен автоматтандыру мүмкін емес. 16

16 слайд

#17 слайд
Мысалы: • Бағдарламаның берілген мәтінінен оның «не істейтінін» анықтаңыз; • Бағдарлама кез-келген жарамды бастапқы деректермен дұрыс жұмыс істейтінін анықтаңыз; • Қате жұмыс істейтін бағдарламада қатені табыңыз. Сондықтан бағдарламаны жөндеу кезінде түйсігі үлкен рөл атқарады. Көмектесіңіз (бірақ мәселені толығымен шешпеңіз!) қатені табудың стандартты әдістері: • Бағдарлама нәтижелерін қолмен санау нәтижелерімен салыстыру; • Қателердің пайда болу заңдылығын анықтау үшін әртүрлі бастапқы деректермен ағдарламамен эксперименттер; • Бағдарламаның бөліктерін уақытша өшіру (түсініктеме беру) және т. б. 17

17 слайд

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

18 слайд

#19 слайд
Назар аударғандарыңыз ға рахмет! Назар аударғандарыңыз ға рахмет! www.company.co m

19 слайд