10. Алгоритм ұғымы, қасиеттері , түрлері

Алгоритм –­­­ өңдеудің қарапайым орындалатын тактілерін қолдануға негізделген қандай да бір әдістің нақты және шекті (ақырлы) сипаттамасы. Алгоритм ­­­­– мүмкін болатын бастапқы деректер класына ортақ есептің шешімін табуға арналған нақты анықталған және орындалатын қарапайым операциялардың ақырлы тізбегінен тұратын, қандай да бір тілде жазылған ақырлы нұсқаулар.

Алгоритм қасиеттері:

1. Дискреттік қасиеті: Үрдісті жеке бөлінуі қажет. Әрбір келесі бұйрықты орындау үшін алдыңғы бұйрықты орындау қажет.

2. Түсініктілік қасиеті: алгоритмді құру үшін орындаушыға түсінікті болу керек, орындаушының бұйрықтар жүйесін орындау қажет.

3. Анықтық немесе детерминдік қасиеті: алгоритмді түсінікті болуымен қатар мағынасы әр түрлі бұйрықтардан тұрмауы қажет, алгоритм орындаушының еркіндігіне жол бермеуі қажет.

4. Нәтижелік қасиеті: Алгоритмнің құрамдарының саны шектеулі болу керек. Көпшілік және жалпылығы көптеген алгоритмдер тек қана бір есепті емес бір типті есептер кластарының шешімін табуға мүмкіндік береді.

Алгоритм түрлері:

1. Тармақталған: алгоритмдағы амалдар шартқа қарап, орындалады.

2. Сызықты: алгоритмнің амалдары бір бірінің артынан орындалады.

3. Циклді: алгоритмнің амалдары қайталанып тұрады.

11. Алгоритмдер теориясы дегеніміз не? Алгоритмдер теориясының шығу тарихы.

Алгоритмдер теориясы алгоритмдердің жалпы қасиеттері мен заңдылықтарын, оларды көрсетудің түрлі формальды модельдерін зерттейтін ғылым саласы. Алгоритм ұғымын формальдау арқылы алгоритмдерді тиімділігі бойынша салыстыруға, эквиваленттілігін тексеруге, қолдану салаларын анықтауға болады.

Алгоритмдер теориясының шығу тарихы:

Алгоритм ұғымы мен аксиомалық жүйе антика заманынан басталады (Евклид). Алайда алгоритмнің нақты математикалық анықтамасы әлі болған жоқ . XXғ басы Гильберт және оның мектебі арқылы осы ұғымды формализациялады. Кейнс пен оны Гедель жалғастырды және математикалық тұрғыдан кез-келген формуланы автоматты тексеруді құрды (1931).

Алгоритмдер теориясының дамуы алғаш формальды жүйелердің толықсыздығы туралы теораманы 1931 жылы К. Гёдельдің дәлелдеуінен басталды. Осы теоремаға қатысты көптеген математикалық проблемалардың алгоритмдік шешімі болмауы туралы жорамал алгоритм ұғымының стандартталуын қажет етті. Кейін алгоритм ұғымын стандарттау Тьринг, Черч, Пост т.б. жұмыстарында жалғастырылды. Бұлардың машиналары эквивалентті болды. Алгоритмнің сәтті стандарталған вариантын А.Марков «нормальді алгоритм» ұғымын енгізу арқылы жасады. Гёдель еңбектеріне негізделе отырып С. Клини алдыңғы аталғандарға эквивалентті рекурсивті функция ұғымын енгізді.

Алгоритмдер теориясына Д.Кнут, А.Ахо, Дж. Ульман да өз еңбектерін сіңірді.

12. Алгоритмдер теориясына кіріспе. Алгоритм ұғымы, анықтамасы.

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

1930-жылдары жасалған алгоритмдердің формальды модельдері (Пост, Тьюринг, Черч), 1950- жылдары жасалған Колмогоров пен Марковтың модельдері тең , өйткені олар бір біріне мына мағынада эквивалентті: бір модельде шешімі табылған проблемалардың кез келген класы, екінші модельде де шешімі болады.

Қазіргі кезде алгоритмдер теориясының негізінде алынған практикалық ұсыныстар программалық жүйелерді жасау мен жобалау саласында кеңінен қолданылуда.

Алгоритм ұғымы, анықтамасы:

Алгоритм –­­­ өңдеудің қарапайым орындалатын тактілерін қолдануға негізделген қандай да бір әдістің нақты және шекті (ақырлы) сипаттамасы. Алгоритм ­­­­– мүмкін болатын бастапқы деректер класына ортақ есептің шешімін табуға арналған нақты анықталған және орындалатын қарапайым операциялардың ақырлы тізбегінен тұратын, қандай да бір тілде жазылған ақырлы нұсқаулар. Кез келген алгоритм осы сөздің интуициялық мағынасында эквивалентті Тьюринг машинасымен көрсетіле алады