Алгоритмдер теориясы. Анықтамасы. Қасиеттері. Түрлері. Алгоритмді жазу әдістері. Алгоритм модельдері



1.БӨЛІМ. АЛГОРИТМДЕР ТЕОРИЯСЫНА КІРІСПЕ
1.дәріс: Алгоритмдер теориясы. Анықтамасы. Қасиеттері. Түрлері. Алгоритмді жазу әдістері. Алгоритм модельдері.
2.дәріс: Алгоритм ұғымын тереңдету, анықтау. Тьюринг машинасын программалау. Пост алгоритмдік машинасы алгоритм ұғымын дәлелдеуші.
3.дәріс: «Алгоритмдік шығарылмайтын есептер. Есептелетін функциялар»
5.дәріс: Іздеу алгоритмі. Реттеу немесе сұрыптау алгоритмі.
2.БӨЛІМ. АЛГОРИТМДЕР ЖӘНЕ ДЕРЕКТЕР СТРУКТУРАСЫ, АЛГОРИТМДЕГІ
ТИІМДІЛІК
7.дәріс: Деректердің жай структурасы
8.дәріс: Деректердің статикалық структурасы.
9.дәріс: Деректердің жартылай статикалық структурасы.
10.дәріс: Деректердің динамикалық структурасы.
11.дәріс: Деректердің сызықты емес структурасы
12.дәріс: Деректердің файлдық структурасы
13.дәріс: Программалаудың әдістері мен технологиясы
14.дәріс: Структуралы және модульдік программалаудың негізгі принциптері
Тақырып №15. «Есептеудегі тиімділік және алгоритмнің әсерлілігі»
Алгоритмдер теориясы – алгоритмдердің жалпы қасиеттері мен заңдылықтарын, олардың ұғымдарының формальды модельдерін оқытатын ғылым. Алгоритмдерді формализациялау негізінде олардың тиімділігі бойынша салыстыру, эквиваленттілікті тексеру, қолданылу облысын анықтау мүмкіндіктері бар.
1930 жылдары құрастырылған алгоритмдердің формальды модельдері (Пост, Тьюринг, Черч) 1950-жылдардағы Колмогоров және Марковтың модельдерімен тең, себебі бір модельде шешілетін кез келген проблемалар класы басқа да модельмен шешіледі. Қазіргі кезде алгоритмдер теориясы негізінде практикалық ұсыныстарды көптеген жобалау және программалық жүйелерді құрастыру облыстарында көруге болады.
Ең алғашқы интуитивті түсінікте бізге жеткен алгоритм – қойылған есепті шешетін ақырлы элементарлы тізбектелген әрекеттер, біздің эрамызға дейінгі 3-ғасырдағы Евклид ұсынған екі санның ең үлкен ортақ бөлгішін табу болды. Оны Евклид алгоритмі деп атады. 20-ғасырға дейін ұзақ уақыт бойы алгоритм сөзі Евклидтік алгоритм сөзімен тұрақты тіркесіп айтылатын. Басқа математикалық есептерді қадамдап шешуді сипаттау үшін «әдіс» сөзі қолданылды. Бастапқы алгоритмдер теориясының заманауи жұмысын неміс математигі Курт Гёдель (1931 жылы) жазды. Ол символикалық логиканың толықсыздығы туралы теорема жазды. Онда бірқатар математикалық проблемалардың әлдебір класқа жататын алгоритмдермен шешілмейтіндігі көрсетілді. 1936 жылы тәуелсіз түрде Алан Тьюрингтің, Алоиз Черчтің, Эмиль Посттың фундаментальды жұмыстары жасалды. Тьюринг машинасы, Пост машинасы және Черчтің лямбда-санақ машиналары пайда болды. Олар өздері ұсынған формальды жүйелермен алгоритмнің интуитивті ұғымдарын эквивалентті деп есептеді. Оның негізінде алгоритмдік тұрғыдан шешілмейтін проблема болмайтындығы дәлелденді.
1950-жылдары Колмогоров және Марков алгоритмдер теориясына көп үлес қосты. 1960-70-жылдары келесі бағыттар пайда болды:
o Алгоритмдердің классикалық теориясы (формальды тілдер терминдеріндегі есептің қойылымы, шешілетін есептер ұғымы, күрделі кластарды енгізу, 1965 жылы Эдмондс ашқан P=NP проблемалары, NP- толық есептер класының ашылуы және оның зерттелуі);
o Алгоритмдердің асимптотикалық анализі (алгоритмдердің күрделілігі және көлемділігі, алгоритмдерді бағалау шарты, рекурсивті алгоритмдерді асимптотикалық бағалау әдістері), Кнут, Ахо, Хопкрофт, Ульман, Карп жұмыстарында көрсетілді;
o Есептеуіш алгоритмдердің практикалық анализін (айқын көлемді еңбек функциясының алынуы, функцияның аралық анализі, алгоритмнің практикалық сапасын бағалау, рационалды алгоритмдерді таңдау әдістемесі) Д. Кнут «ЭЕМ үшін программалау өнері» жұмысында көрсетті.
1. Алгоритмдер теориясының мақсаты мен міндеті.
o «алгоритм» ұғымын формальдандыру және формальды алгоритмдік жүйелерді зерттеу;
o Бірқатар есептердің формальды түде алгоритмдік шешілмейтіндігін дәлелдеу;
o Есептердің классификациясы, күрделі кластарды анықтау және зерттеу;
o Алгоритмдер күрделілігін асимптотикалық анализдеу;
o Рекурсивті алгоритмдерді анализдеу және зерттеу;
o Алгоритмдерді салыстырып анализдеу мақсатында айқын көлемді еңбек функциясын алу;
o Алгоритмдердің сапасын салыстырмалы түрде бағалау шарттарын құрастыру.

2. Алгоритмдер теориясының нәтижелерін практикалық қолдану
Екі аспектіде қолданылады:
Теориялық аспект: қандай да бір есепті зерттеу кезінде алгоритмдер теориясының нәтижесі мына сұраққа жауап береді – бұл есеп алгоритмдік тұрғыдан шешілетін есеп пе, егер шешілетін есеп болса, бұл есептің NP– толық есептер класына жататындығын зерттеу. Егер оған жатса, онда үлкен көлемді бастапқы берілгендер үшін дәл шешім алуға көп уақыт шығынын есептеу керек.
Практикалық аспект: алгоритмдер теориясының әдістері мен әдістемелері (асимптотикалық және практикалық анализ) келесі сұрақтарды қарастырады:
o Берілген есепті шешуге арналған алгоритмдер жиынынан есепті қолдану ерекшелігін ескере отырып рационалдысын таңдау (бастапқы берілгендердің көлеміне шектеу қойылса, қосымша жадының көлеміне шектеу қойылса);
o Күрделі есептерді шешудің уақыттық бағалауын алу;
o Криптографиялық әдістер үшін маңызды болып саналатын әлдебір есептің белгілі бір уақыт аралығында шешілмейтіндігі туралы шынайы бағалау алу;
o Есепті шешу тиімді алгоритмдерін практикалық анализ негізінде ақпарат өңдеу облысында құрастыру және жетілдіру.

2-БӨЛІМ. ДӘРІС КЕШЕНІ

1-БӨЛІМ. АЛГОРИТМДЕР ТЕОРИЯСЫНА КІРІСПЕ
Глоссарий
Алгоритмдер теориясы – алгоритмдердің жалпы қасиеттері мен заңдылықтарын,
олардың ұғымдарының формальды модельдерін оқытатын ғылым
Алгоpитм — кез келген алғашқы мәліметтен ( берілген алгоритм үшін мүмкін
алғашқы мәліметтердің қандай да бір жиынтығынан) басталатын және осы
алғашқы мәліметпен толық анықталатын нәтиже алуға бағытталған алгортмдік
үрдісті беретін дәл нұсқаулар тізбегі
Алгоритмдік үрдіс – конструктивті объектілерді (сөз, сан, сөз жұбы, сан
жұбы, сөйлемдер және т.б.) дискретті қадаммен түрлендіру үрдісі.
Алгоритмнің негізгі қасиеттері: дискреттілік, түсініктілік, анықтылық,
нәтижелік, көпшілік.
Алгоритмді орындаушы — бұл алгоритммен тағайындалатын әрекеттерді орындай
алатын абстрактілі немесе нақты жүйе (техникалық, биологиялық немесе
биотехникалық).
Тьюринг машинасы – белгілі бір есептерді шығаруға арналған қатаң
математикалық құрылым, математикалық аппарат
Сөз - әлдебір алфавиттен алынған әріптердің кез келген тізбегі
Сөз ұзындығы - сөздегі әріптердің саны
Енгізілетін сөз - алгоритмде қолданылатын сөз
Шығарылатын сөз - алгоритмнің нәтижесі
Пост алгоритмдік машинасы - абстрактылы машина, бірнеше бірдей секцияларға
бөлінген, оқу-жазу инесі бар шексіз лентадан тұрады.
Есептелетін функция - әлдебір алгоритм көмегімен есептелетін функция
Іс жүзінде алгоритм – функцияны беру әдісі

Черч тезисі алгоритмдік – есептелетін бөлшекті сандық функциялар класы
барлық бөлшекті рекурсивті функциялар класымен беттеседі.

Бөлшекті рекурсивті функция - есептелетін бөлшекті функция интуитивті
ұғымының ғылымы эквиваленті бола алады.

1-дәріс: Алгоритмдер теориясы. Анықтамасы. Қасиеттері. Түрлері. Алгоритмді
жазу әдістері. Алгоритм модельдері.

Дәріс мақсаты: Алгоритмдер теориясының анықтамаларын қарастыру, оның шығу
тарихына шолу жасау, алгоритмдер модельдерін қарастыру.
1. Алгоритмдер теориясының негізгі анықтамалары
2. Алгоритмдер теориясының шығу тарихы

Алгоритмдер теориясының мақсаты мен міндеті.

Алгоритмдер теориясының нәтижелерін практикалық қолдану

Алгоритмдер теориясы – алгоритмдердің жалпы қасиеттері мен заңдылықтарын,
олардың ұғымдарының формальды модельдерін оқытатын ғылым. Алгоритмдерді
формализациялау негізінде олардың тиімділігі бойынша салыстыру,
эквиваленттілікті тексеру, қолданылу облысын анықтау мүмкіндіктері бар.
1930 жылдары құрастырылған алгоритмдердің формальды модельдері (Пост,
Тьюринг, Черч) 1950-жылдардағы Колмогоров және Марковтың модельдерімен тең,
себебі бір модельде шешілетін кез келген проблемалар класы басқа да
модельмен шешіледі. Қазіргі кезде алгоритмдер теориясы негізінде
практикалық ұсыныстарды көптеген жобалау және программалық жүйелерді
құрастыру облыстарында көруге болады.
Ең алғашқы интуитивті түсінікте бізге жеткен алгоритм – қойылған есепті
шешетін ақырлы элементарлы тізбектелген әрекеттер, біздің эрамызға дейінгі
3-ғасырдағы Евклид ұсынған екі санның ең үлкен ортақ бөлгішін табу болды.
Оны Евклид алгоритмі деп атады. 20-ғасырға дейін ұзақ уақыт бойы алгоритм
сөзі Евклидтік алгоритм сөзімен тұрақты тіркесіп айтылатын. Басқа
математикалық есептерді қадамдап шешуді сипаттау үшін әдіс сөзі
қолданылды. Бастапқы алгоритмдер теориясының заманауи жұмысын неміс
математигі Курт Гёдель (1931 жылы) жазды. Ол символикалық логиканың
толықсыздығы туралы теорема жазды. Онда бірқатар математикалық
проблемалардың әлдебір класқа жататын алгоритмдермен шешілмейтіндігі
көрсетілді. 1936 жылы тәуелсіз түрде Алан Тьюрингтің, Алоиз Черчтің, Эмиль
Посттың фундаментальды жұмыстары жасалды. Тьюринг машинасы, Пост машинасы
және Черчтің лямбда-санақ машиналары пайда болды. Олар өздері ұсынған
формальды жүйелермен алгоритмнің интуитивті ұғымдарын эквивалентті деп
есептеді. Оның негізінде алгоритмдік тұрғыдан шешілмейтін проблема
болмайтындығы дәлелденді.
1950-жылдары Колмогоров және Марков алгоритмдер теориясына көп үлес қосты.
1960-70-жылдары келесі бағыттар пайда болды:
o Алгоритмдердің классикалық теориясы (формальды тілдер
терминдеріндегі есептің қойылымы, шешілетін есептер ұғымы,
күрделі кластарды енгізу, 1965 жылы Эдмондс ашқан P=NP
проблемалары, NP- толық есептер класының ашылуы және оның
зерттелуі);
o Алгоритмдердің асимптотикалық анализі (алгоритмдердің
күрделілігі және көлемділігі, алгоритмдерді бағалау шарты,
рекурсивті алгоритмдерді асимптотикалық бағалау әдістері), Кнут,
Ахо, Хопкрофт, Ульман, Карп жұмыстарында көрсетілді;
o Есептеуіш алгоритмдердің практикалық анализін (айқын көлемді
еңбек функциясының алынуы, функцияның аралық анализі,
алгоритмнің практикалық сапасын бағалау, рационалды
алгоритмдерді таңдау әдістемесі) Д. Кнут ЭЕМ үшін программалау
өнері жұмысында көрсетті.

Алгоритмдер теориясының мақсаты мен міндеті.

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

Алгоритмдер теориясының нәтижелерін практикалық қолдану

Екі аспектіде қолданылады:
Теориялық аспект: қандай да бір есепті зерттеу кезінде алгоритмдер
теориясының нәтижесі мына сұраққа жауап береді – бұл есеп алгоритмдік
тұрғыдан шешілетін есеп пе, егер шешілетін есеп болса, бұл есептің NP–
толық есептер класына жататындығын зерттеу. Егер оған жатса, онда үлкен
көлемді бастапқы берілгендер үшін дәл шешім алуға көп уақыт шығынын есептеу
керек.
Практикалық аспект: алгоритмдер теориясының әдістері мен әдістемелері
(асимптотикалық және практикалық анализ) келесі сұрақтарды қарастырады:
o Берілген есепті шешуге арналған алгоритмдер жиынынан есепті
қолдану ерекшелігін ескере отырып рационалдысын таңдау (бастапқы
берілгендердің көлеміне шектеу қойылса, қосымша жадының көлеміне
шектеу қойылса);
o Күрделі есептерді шешудің уақыттық бағалауын алу;
o Криптографиялық әдістер үшін маңызды болып саналатын әлдебір
есептің белгілі бір уақыт аралығында шешілмейтіндігі туралы
шынайы бағалау алу;
o Есепті шешу тиімді алгоритмдерін практикалық анализ негізінде
ақпарат өңдеу облысында құрастыру және жетілдіру.

Алгоритм ұғымын формальдандыру

Алгоритм ұғымы информатиканың ақпарат сияқты негізгі ұғымдарының бірі болып
табылады.
Анықтама 1.1.
Алгоpитм — кез келген алғашқы мәліметтен ( берілген алгоритм үшін мүмкін
алғашқы мәліметтердің қандай да бір жиынтығынан) басталатын және осы
алғашқы мәліметпен толық анықталатын нәтиже алуға бағытталған алгортмдік
үрдісті беретін дәл нұсқаулар тізбегі.
Бұл - алгоритм ұғымының интуитивті сипатталуы болып табылады. Алгоритмдік
үрдіс – конструктивті объектілерді (сөз, сан, сөз жұбы, сан жұбы, сөйлемдер
және т.б.) дискретті қадаммен түрлендіру үрдісі.
Алгоритмнің негізгі қасиеттері: дискреттілік, түсініктілік, анықтылық,
нәтижелік, көпшілік.
Алгоритмді орындаушы — бұл алгоритммен тағайындалатын әрекеттерді орындай
алатын абстрактілі немесе нақты жүйе (техникалық, биологиялық немесе
биотехникалық).
Орындаушыны - орта, элементарлық әрекеттер, командалар жүйесі,
әрекеттерінің формальдығы сипаттайды. Информатикада әмбебап алгоритм
орындаушысы компьютер болып табылады.
Орындаушының командалар жүйесі – орындаушы орындай алатын барлық командалар
жиынтығы. Әрбір команда үшін қолдану шарттары берілуі (ортаның қандай
жағдайында команда орындалуы мүмкін) және команданың орындалу нәтижелері
жазылған болуы тиіс. Команданы шақырғаннан кейін орындаушы сәйкес
элементарлық әрекеттерді орындайды.
Орындаушы формальды түрде әрекет етеді, яғни есептің мазмұнына үңілмейді,
тек қана қажетті нәтиже алу үшін қатаң түрде әрекеттерді (командаларды)
орындайды. Енді алгоритм орындаушысы ұғымын қолдана отырып алгоритм ұғымын
анықтауға болады.
Алгоpитм — алдыға қойылған есептің шешіміне ақырлы қадаммен жету үшін
қажетті қимылдар тізбегінің орындаушыға түсінікті және дәл нұсқаулары.
Алгоритм іргелі ғылыми ұғым ретінде қатаң сипаттауды талап етеді, яғни
формальдауды. Алгоритм ұғымы формальдаудың келесі бағыттары белгілі:
– шекті және шексіз автоматтар теориясы (Пост, Тьюринг машиналары,
Марковтың қалыпты алгоритмдері және т.б.);
– есептелетін (рекурсивті) функциялар теориясы;
– Черчтің (-есептеуі (LISP бағдарламалау тілі).
Алгоритм ұғымын формальдаудың негізгі мақсаты: әртүрлі математикалық
есептердің алгоритмдік шешілу мәселелерін қарастыру, яғни есептің шешілуіне
әкеп соғатын алгоритм тұрғызуға бола ма деген сұраққа жауап беру.
D – есептің бастапқы берілгендерінің облысы (жиыны) болсын. R – мүмкін
нәтижелер жиыны болсын, онда алгоритм D -- R бейнелеуін орындайды. Бұл
бейнелеу толық емес болғандықтан, келесі ұғымдар қажет:
Алгоритм бөлікті алгоритм деп аталады, егер D облысынан алынған d үшін
ғана нәтиже алатын болсақ. Егер частичным алгоритмом, если мы получаем
результат только для некоторых d из D D облысынан алынған барлық d үшін
дұрыс нәтиже алынса, онда толық алгоритм деп аталады.
Алгоритмнің формальды анықтамалары өте көп. Олардың барлығының
дәлелдемелері бар.
Анықтама 1.2 (Колмогоров): Алгоритм – қандай да бір қадамдар санынан кейін
қойылған есептің шешіміне әкелетін, қатаң анықталған ережелерге сәйкес
орындалатын, кез келген есептеу жүйесі
Анықтама 1.3 (Марков): Алгоритм – өзгеретін бастапқы берілгендерден
нәтижелерге қарай жүретін есептеу процесін анықтайтын дәл сипаттама.

Өзін-өзі бақылау сұрақтары:
1. Алгоритмдер теориясының негізін қалаушы кім?
2. Алгоритмдер теориясының интуитивтілігі неде?
3. Колмогоровтың алгоритмдерге берген анықтамасы?
4. Марковтың алгоритмдерге берген анықтамасы?
5. Бөлікті алгоритм деген не?
6. Алгоритмнің негізгі қасиеттері
7. ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Ұқсас жұмыстар
АЛГОРИТМДЕР ТЕОРИЯСЫН ИНТЕЛЛЕКТУАЛДЫ ЖҮЙЕЛЕРДЕ ҚОЛДАНЫЛУЫНА ҚАТЫСТЫ ТЕРМИНДЕРГЕ ШОЛУ
Алгоритмнің күрделілігі - осы алгоритмді есептеу процесінде қолданылған элементарлы қадамдар саны
Алгоритмдер және деректер структурасы
Информатика пәнінен лекциялық сабақтардың тезистері
Алгоритм түрлері
Алгоритмдердің күрделілігі
Алгоритмдерді оқыту әдістемесі
Алгоритм және алгоритмдеу ұғымдары
«Компьютер көмегімен есеп шығару технологиясын математикалық білім сапасын жақсартуда пайдалану ерекшеліктері»
Ақпараттарды өңдеудің техникалық құралдары
Пәндер