Алгоритм туралы мәлімет

Презентация қосу

Семей қаласының Шәкәрім атындағы мемлекеттік университеті
Физика – математика факультеті математика мамандығы

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

Орындаған:Асқарбек М.Б.
Тексерген:Рысжанова А.С.
Семей 2015 жыл
Жоспар:
*I.Кіріспе
*1)Алгоритмның анықтамасы
*II.Негізгі бөлім
*1)Алгоритм арқылы шешілмейтін есептер
*2) Алгоритм теориясы және алгоритмның күрделілік тұрғысынан
кластары
*3) Алгоритм түсінігінің функция түсінігімен байланысы.
*4)Алгоритмдік тіл
*III.Қорытынды
Анықтама 1. (Колмогоров): «Алгоритм – нақты ережелермен қатаң түрде
орындалатын, қандай да бір қадамдардан соң қойылған есептің шешіміне әкелетін
есептеулердің кез келген жүйесі»
Анықтама 2. (Марков): Алгоритм – өзгертілетін бастапқы деректерден ізделінді
нәтижеге әкелетін есептеу процесін анықтайтын нақты ереже. Б ұл анықтамалардан
алгоритмге қойылатын келесі ортақ талаптарды атап өтейік: алгоритм қарапайым
орындалатын саны шектеулі ережелерден тұруы тиіс, яғни жазбалардың шектеулі
болуы талабын қанағаттандыруы тиіс; алгоритм шектеулі қадамнан соң есепті
шешуі тиіс, яғни әрекеттердің шектеулі болу талабын қанағаттандыруы тиіс;
алгоритм барлық мүмкін болатын бастапқы деректер үшін біреу ғана болуы керек,
яғни әмбебаптық талабын қанағаттандыруы тиіс; алгоритм қойылған есептің
дұрыс шешімін табуы керек, яғни дұрыс болу талабын қанағаттандыруы тиіс.
Алгоритм атауы атақты араб математигі Әбу Жафар Мұхаммед ибн Мұса әл -
Хорезми ( 763 - 850 ж. ж) есімінің латынша Algorithmi (Алгоритми) болып
жазылуынан шыққан. Ол санаудың ондық жүйесінде көп орынды сандар мен
арифметикалық амалдардың орындалу ережесін ұсынған. Бұл ережелер қосынды
мен көбейтіндіні табуға арналған амалдарды орындауға қажетті тізбектен
құрылған. Сол ереже осы күнге дейін қолданылып келеді.Алгоритм -
орындаушының белгілі бір мақсатқа жетуі үшін орындалатын әрекеттер тізбегін
айтады. Кез - келген есепті қарапайым амалдарды тізбектей орындау арқылы
шығаруға болады. Алгоритімді компьютерде орындау үшін оны программа түрінде
жазып шығу керек.
Алгоритм кестесі
* Алгоритмдер арқылы шешілмейтін есептер
Алгоритм ұғымын формальдандыру – шешу
алгоритмдері табылмайтын есептердің
болатындығын зерттеуге мүмкіндік береді.Бірқатар
есептердің кез келген есептеу құрылғыларында
алгоритмдік тұрғыдан шешілмейтіндігі дәлелденген.
ʄ функциясы есептелетін функция делінеді, егер де
осы функцияның анықталу облысындағы кез келген
аргумент үшін функция мәнін есептейтін Тьюринг
машинасы табылса.Егер де мұндай машина
табылмайтын болса,онда ʄ функциясы есептелінбейтін
функция делінеді
* Егер ʄ функциясының есептеу нәтижесі «ақиқат« не «жалған«
түріндегі логикалық өрнек болса,онда есеп берілген есептелетін
функцияға қатысты шешілетін не шешілмейтін есеп деп
аталады.Есеп бастапқы берілгендердің кейбірі үшін шешілетін ,
ал келесі біреулері үшін шешілмейтін болғандықтан, бастапты
берілгендердің мүмкін мәндерін нақтылап көрсету керек.
Машина жұмысын тоқтату проблемасының шешілмейтіндігі
дәлелденген есепке жатады.Ол келесі түрде болады:
Тьюринг машинасына арналған программа сипаттамамсына
қарап, уақыт өтуіне қарай программа жұмысының
аяқталатындығын не шексіз жұмыс істейтіндігін анықтау ға
болады.
Тоқтату проблемасының шешілмейтіндігін дәлелдеу өзге
есептердің де оған келтірілетіндігімен мағызды.
Мысылы:Тьюринг машинасының бос жолда тоқтау
проблемасының машина жұмысын тоқтатудың қарапайым
есебіне келтіруге болады.
Қазіргі кезде алгоритмдер теориясы негізі 3 бағытта дамып
келеді:
*Алгоритмнің классикалық теориясы – есептерді формальды тілдер
терминдерімен беру (формулировка задач) проблемасын зерттеді. Есептерді
күрделілік кластары бойынша (P,NP, т.б) классификациясын жасайды,
есептердің шешімін табу ұғымын енгізді.
*Алгоритмдерді асимтотикалық талдау теориясы. Алгоритмнің , соның ішінде
рекурсивті алгоритмдердің, орындалуының уақытының немесе
ресурстарының асимтотикалық бағасын алудың тәсілін қарастырады.
Асимтотикалық талдау енгізілетін деректер к өлеміні ң өсуіне байланысты
алгоритмдердің ресурстарға (мыс: орындалу уақыты) қажеттілігін бағалау ға
мүмкіндік береді.
*Есептеу алгоритмдерін практикалық талдау теориясы. Тиімді алгоритмдерді
таңдау әдістемесін жасау, алгоритмдердің сапасын тексеруді ң практикалы қ
өлшемдерін іздеу, функцияларды интервалдық талдау, к үрделілікті ң на қты
функцияларын алу және т.б. сияқтарды есептерді шешумен шұғылданады.
* Алгоритмдер теориясында алынған нәтижелер екі аспектіде: теориялық және
практикалық аспектілерде қолданылады.
Теориялық аспект: Есептің алгоритмдік шешімі болатындығын немесе оны
шешудің нақты алгоритмі болмайтындығына есепті зерттеу нәтижесінде
алгоритмдер теориясының жауап беру мүмкіндігі теориялық аспектіге жатады.
Алгоритмдік шешімі болмайтын есептер Тьюринг машинасын тоқтату есебіне келтіріледі.
Ал алгоритмдік шешімі болатын есептер үшін олардың NP-толық есептер класына тиесілі
ме екендігі анықталады. Егер тиесілі болса, онда бастапқы деректері үлкен болатын
есептердің нақты шешімін алу үшін қанша уақыт кететінін анықтауға немесе оны
шешудің жылдам нақты алгоритмі болмайтындығын айтуға мүмкіндік береді.
Практикалық аспект: алгоритмдер теориясының, әсіресе асимптотикалық және
практикалық талдаудың әдістері мен әдістемелері келесі мүмкіндіктерді береді: Берілген
есепті шешуге арналған алгоритмдер жиынынан жасалатын программалық ж үйедегі
олардың ерекшелігін ескеретін тиімді алгоритмді таңдауға мүмкіндік береді. Күрделілік
функциясы арқылы күрделі есептерді шешудің уақыттық бағалауларын алады. Белгілі
уақыт ішінде қандай да бір есептің шешуі болмайтындығына шынайы баға беріледі.
Ақпаратты өңдеу саласындаың маңызды деген есептерін шешудің тиімді алгоримтмдерін
құру мен жетілдіру.
Мысалы: алгоритмді жүзеге асыратын программаның орындалу уақытына немесе
пайдаланатын минималды жад көлеміне шектеулер қойылғанда түрлі алгоритмдерден
таңдау жасалынады; қиындық функциясы арқылы күрделі есептерді шешу уақыты
анықталады; берілген уақыт ішінде есепті шешу мүмкін болмайтындығы шынайы
бағаланады. Бұл қазіргі кезде криптографиялық әдістер үшін, ақпаратты өңдеу
саласында практикалық жағынан маңызды есептерді шешудің тиімді алгоритмдерін жасау
мен жетілдіру үшін аса сұранысқа ие болып отыр.
* Алгоритмдер классификациясы. Күрделілілік тұрғысынан алгоритмдердің екі үлкен
класы бар.Олар:
қайталауы бар алгоритмдер және рекурсивті алгоритмдер.
Бір есепті көптеген алгоритммен шешуге болады. Олардың әрқайсысының
жұмысының тиімділігі әртүрлі сипаттаулармен сипатталады. Алгоритмді талдамас
бұрын ең алдымен берілген алгоритм есепті дұрыс шешетінін дәлелдеуіміз керек. Егер
есепті дұрыс шешпесе тиімділік мәселесінің мәні жоқ. Егер алгоритм қойылған
есепті шешсе, оның қаншалықты тиімді екенін қарастыруымыз керек. Сондықтан
оның тиімділігінін анықтау үшін алгоритмдерді талдауымыз қажет. Қайталау
алгоритмінің негізінде шартты өрнектер мен цикл жатыр; мұндай алгоритмдерді
талдауда циклдын ішінде қолданылатын операция саны мен цикл итерациясының
санын бағалау керек. Рекурсивтік алгоритмдер үлкен есепті фрагменттерге б өледі
және әрбір фрагменттерді жеке қолдануға мүмкінлік береді. Осындай алгоритмдерді
кейде «бөліп алда біле» алгоритмі деп айтайды және оларды қолдану өте тиімді болуы
мүмкін. Үлкен есептердікішіге бөлу жолымен шешу үрдісінде үлкен емес, қарапайым
және түсінікті алгоритм құрылады. Рекурсивті алгоритмді талдауда есепті бөлімге
бөлуге қажетті операцияның санын санау, ірбңр бөлімдегі алгоритмнің орындалуы
және есепті толық шешудегі әрбір бөлімнің нәтижесін біріктіру керек. Осы
ақпараттарды және неше бөлік екенінің саны, олардың өлшемінен алгоритмнің
күрделілігінің рекуррентік қатынасын шығарамыз. Алгоритмдерді әртүрлі белгілер
бойынша жіктеуге болады. Мысалы, жалпы комбинаторлық алгоритмдер, тағы
алгоритмдер, максимальды ағынды іздеу алгоритмдері, максимальды жұп сәйкестігін
іздеу алгоритмдері, іздеу алгоритмдері, Алгоритмы на строках, жолды іздеу
алгоритмдері, Бұтақтармен жұмыс алгоритмдері, сұрыптау алгоритмдері, сығу
алгоритмдері, үлестірілген жүйелер алгоритмдері, операциялық жүйелердегі
алгоритмдер, тиімділеу алгоритмдері және т.б.
* Алгоритмнің күрделілігін анықтау
Математикада алгоритмнің күрделілігі ұғымын білудің мәні зор. Егер
алгоритмде есптеу сериялары кездессе , онда алгоримнің күрделілігі ретінде
орындалатын амалдар алуға болады.Егер алгоритмде "*" мен "+" амалдары қатар
кездессе , онда алгоритм күрделілігі ретінде "*« амалының саны орындалады.Себебі,
бұл амал "+" амалына қарағанда анағұрлым көп уақытты талап етеді.
Big-O-бағалау алгоритмнің орындалу уақытының өлшемін (runtime) береді. Әдетте
алгоритмнің жақсы және нашар жағдайлар үшін есептеу тиімділіктері әртүрлі ,
сондықтан әр нақты жағдай үшін Big-О мәні есептеледі. Егер алгоритм реті —0(1) болса,
оның реті коллекциядағы элементтер санына тәуелсіз болады. Бұл алгоритм тұрақты
уақыт бірлігі ішінде орындалады, мысалы егер массив соңын көрсететін индекс сақталса,
массив элементіне мән меншіктеу реті 0(1) болады. Алгоритм О(п) сызықты (linear).
Оның күрделілігі тізім размеріне пропорционал. Реті log2n болатын алгоритмдер
логарифмдік (logarithmic) деп аталады. Мұндай күрделілік тізімдерді бірнеше рет ішкі
тізімдерге 1/2, 1/4, 1/8 етіп бөлгенде туындайды. Мысалы бинарлық бұтақтарда іздеу
алгоритмдерінің күрделілігі орташа және нашар жағдайлар үшін O(log2n) болады. Реті
О(п2) болатын алгоритмдер квадраттық (quadratic) деп аталады. Шағын n үшін ғана
практикада қолданылады. п екіге артқан сайын алгоритмнің орындалу уақыты 4-ке
артады. Реті О(n3) болатын алгоритмдер өте баяу орындалады, кубтық (cubic) уақытты
қажет етеді. п екіге артқан сайын алгоритмнің орындалу уақыты 8 есе артады. Оның
мысалына графтарға қолданылатын реті О(п3) болатын Уоршел алгоритмі жатады.
Күрделілігі О(2п) тең алгоритмде экспоненциальды күрделілік (exponential complexity)
болады. Өте баяу орындалатындықтан өте аз п үшін қолданылады.
Іс жүзінде алгоритм – функцияны беру әдісі. Ал функция таблица,
схема, формула түрінде берілуі мүмкін. Бірақ кейбір процестерде
бастапқы енгізілген немесе берілген деректер мен алынған нәтижедегі
деректер арасындағы байланысты ұйымдастыратын функцияны құру
қиын, күрделі.
1 – бағыт Рекурсивті функциялар – есептелетін функциялар ұғымымен
байланысты.
X және Y жиындары бар болсын. X жиынының кейбір элементтеріне Y
жиынының элементтері сәйкес келсе, онда Y – те X – тен бөлшекті
функция берілген дейді.
Y жиынында сәйкес элементтері бар және X элементтерден құралған
жиынның элементтер жиыны функцияның анықталу облысы деп
аталады.
X жиынында сәйкес элеметтері бар Y жиынының элементтер жиыны
функцияның мәндер облысы деп аталады.
Егер X –тен Y-тегі функцияның анықталу облысы X жиынымен
беттессе, онда ол функцияны барынша анықталған деп атайды.
Осы ұғымға және рекурсивті функцияға негізделіп алгоритмнің дәл
анықтамасын құруға болады.
Анықтама. Әлдебір алгоритм көмегімен есептелетін
функцияны есептелетін функция дейді. Кез – келген
берілген деректерді (үзілісті, дискретті) әлдебір санау
жүйесінде натурал сандармен кодтауға болады, онда
Олардың барлық алмастыруы есептеу
операцияларының тізбегіне келтіріледі, ал өңдеу
нәтижесі солайынша бүтін сан болып қалады. Кез
келген алгоритм берілген сандық функция үшін
бірдей, оның мәнін есептейді, ал оның элементарлы
қадамдары қарапайым арифметикалық және
логикалық операциялар болады. Мұндай
функциялар есептелетін функциялар деп аталады.
Алгоритмдік тіл – алгоритмдерді жазуға арналған
символдар мен сол символдардан тұратын
конструкцияларды құрастыру жəне түсіндіру
ережелерінің жиыны.
Алгоритмдерді бейнелеу тəсілдері. Алгоритмдерді
бейнелеудің негізгі тəсілдеріне оларды жазудың келесідей
түрлері жатады: • табиғи тіл сөздері арқылы; •
формулалық-сөздік тəсіл арқылы; • графикалық түрде
бейнелейтін блок-схемалар арқылы; • псевдокодтар
арқылы; • программалау тілі арқылы. Алгоритмдерді
табиғи тіл сөздері арқылы бейнелеуде – есептеу кезеңдері
мазмұны кез келген түрде табиғи тілде жазылады. Бірақ
бұл тəсілде алгоритм көрнекілігі жоқ жəнедəлдік, яғни
детерминділік қасиет, толық формальдау мүмкіндігі
сақталмайды, сол себепті ол сирек қолданылады.
Алгоритмдерді формулалық-сөздік тəсіл арқылы
бейнеленуі– тапсырманың математикалық символдар мен
өрнектердің жəне сөздердің араласуымен берілуі болып
табылады.Мысалы, үшбұрыш ауданын оның үш
қабырғасының ұзындығы арқылы есептеу алгоритмін
құру керек болсын делік.
1. үшбұрыштың жарты периметрін есептеу p=(a+b+c)/2
2. үшбұрыштың ауданын есептеу
3. нəтиже ретінде S мəнін шығарып, алгоритм жұмысын
аяқтау.
4. Бұл тəсілді пайдаланғанда, алгоритмді кез келген
деңгейде айқындап көрсетуге болады, бірақ формальды
түрде анық бейнелеу қиын. Алгоритмді графикалық
түрде блок-схемалар арқылы көрсету – оның
логикалық құрылымын графикалық түрде бейнелеу
болып саналады. Мұнда мəліметтерді өңдеудің əрбір
кезеңі атқарылатын операцияға сəйкес əр түрлі
геометриялық фигуралар (блоктар) түрінде көрсетіледі
Қолданылған ақпарат көздері:
1) Мозговой М.В. Классика программирования: Алгоритмы Языки
Автоматы Компиляторы. Практический подход – Наука и техника,
Санкт – Петербург 2006г.-320с.
2)Stud.kz. Группа сайтов
3)Трахтенберг Б.А. Алгоритмы и вычислимые автоматы.- М.,Сов.
Радио,1974.
4) uk.wikipedia.org/wiki/Алгоритм
5)stud.kz/referat/show/22484
Назарларыңызға
рахмет!!!

Ұқсас жұмыстар

Алгоритм құруға үйрету

Перевезти козу капустой

ЭЕМ-ң қызметі, құрамы және жіктелуі. IBM PC және басқа осы тәріздес дербес компьютерлер жұмысы жайында мәліметтер. Алгоритмдік тілдер туралы мәліметтер

Алгоритм командалары

Жұмбақ сан

Білім аукционы

IBM PC және басқа осы тәріздес дербес компьютерлер жұмысы жайында мәліметтер

Арнайы модельдер ақпараттық модель

Кездейсоқ айнымалы және тармақталған алгоритм

Компьютерлік вирустар және оған қарсы бағдарламалар

Пәндер