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

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 Есепті шешу тиімді алгоритмдерін практикалық анализ негізінде ақпарат өңдеу облысында құрастыру және жетілдіру.