«Информатиканың теориялық негіздері»
Дәріс №11. Тақырыбы: Алгоритм және оның қасиеттері
жүктеу/скачать 363.46 Kb.
|
| Дәріс №11. Тақырыбы: Алгоритм және оның қасиеттері
ЭЕМ-ді пайдалану істерін қарастырмас бұрын оның жұмысымен тығыз байланысты алгоритм, программа ұғымдарын білуіміз қажет. Әрбір ЭЕМ алдын ала берілген алгоритммен, яғни жоспармен жұмыс істейді. Алгоритмді заңдылық, реттелген амалдар жиыны, кезекпен орындалатын операциялар тізімі деп ұғынған жөн. Бұл ұғым қазіргі кезде кеңінен қолданылып жүр. Оның көптеген анықтамалары да бар. Соның бірін келтіре кетейік. Алгоритм – берілген есептің шығару жолын реттелген амалдар тізбегі түріне келтіру. Кез келген есепті қарапайым амалдарды тізбектей орындау арқылы шығаруға болады. Алгоритмді ЭЕМ-де орындау үшін оны программа түрінде жазып шығу керек. Программа – алгоритмді машинаға түсінікті нұсқаулар тізімі ретінде жазу. Программа машинаға түсінікті командалардан тұрады. Осы командалар тізбегі орындалу барысында есептің нәтижесі шығады. Әрбір ЭЕМ алдын ала жазылған программамен істейді. Программа дегеніміз – белгілі бір нәтиже алу үшін орындалатын амалдардың айқындалған тізбегі. Процессор программаның құрамындағы командаларды кезекпен орындап отырады. Командалар тізбегін программа деп қарастыруға болады. Команда бір ғана қарапайым амалды орындау үшін берілген бұйрық ретінде беріледі. Командалар: арифметикалық немесе логикалық амал; ақпаратты тасымалдау командасы; берілген сандарды салыстыру командасы; келесі командаларға көшу тәртібін орындау т.с.с. ЭЕМ-нің жұмысы программалық принципке негізделген, яғни ол өзінің жадында сақталатын командалар тізбегін автоматты түрде орындау арқылы есеп шығарады. Кез келген ЭЕМ жадында берілген мәліметтермен қоса оны қандай жолмен, қандай нұсқауларды орындағанда шығатынын көрсететін программаны сақтайды. ЭЕМ берілген тапсырманы орындауға дайын тұрған техникалық аспап болғандықтан әрбір тапсырманы түсінікті түрде қысқаша жаза білу қажет. Тапсырма жоғарыда айтылған жекеленген командалардан тұрады. Машинаға түсінікті түрде жазылған тапсырмаларды немесе командалар жиынын да программа деп атауға болады. Программа – белгілі бір нәтиже алу үшін орындалатын амалдардың тізбегі. Ол реттелген командалар тізбегінен тұрады. Программа - арнайы текст арқылы ЭЕМ-ге тапсырманың ретті кезегін хабарлайды. Алгоритм қасиеттері Алгоритм ұғымының мәнін ашатын негізгі қасиеттерінен немесе оған қойылатын талаптардан қысқаша мағлұматтар келтірейік. ЭЕМ-де орындалуға тиіс алгоритмдерге мынадай талаптар қойылады: 1) анық әрі дәл өрнектелуі тиіс; 2) алгоритм шектелген уақыттан соң нәтиже беруі тиіс, яғни алгоритм қадамдарының саны шексіз болмауы керек; 3) бір тектес есептерге жалпы бір ғана алгоритм қолданылуы тиіс; 4) модулдік (бөлік), яғни алгоритмді кішкене бөліктерге бөлу мүмкін- дігі болуы қажет. Алгоритмдерді ЭЕМ-де орындау үшін оларды алдын ала жазып алу керек, яғни ол белгілі бір заңдылықпен өрнектелуі тиіс. Жалпы алгоритмді өрнектеу түрлеріне: 1) табиғи тіл арқылы жазу; 2) белгілі бір терминдер – псевдокодтар арқылы жазу; 3) графика жолымен жазу; 4) алгоритмдік тілдермен жазу жолдарын жатқызуға болады. Алгоритм мен программаға байланысты ЭЕМ-нің мынадай жұмыс ерекшеліктері болады: 1) есепті шығару жолы алгоритм түрінде өрнектелуі қажет; 2) алгоритм программаға айналдырылуы тиіс; 3) программа машина жадына енгізіліп, ретімен орындалуы керек. Сонымен, керекті нәтижені алу жолында ақпаратқа қолданылатын әре-кеттердің орындалу ретін анықтайтын нұсқау – алгоритм болып есептеледі. Марков алгоритмін алгоритм ұғымын, арнайы форманы қолданып жазу арқылы нақтылау деп санауға болады. Марковтық нормалды алгоритмі реттелген ауыстырылымдар формуласының жиынтығы деп қарастыруға болады. Атақты орыс математигі Андрей Андреевич Марков (1903 -1979) нормалды алгорифм деген атпен алгоритм ұғымының формальды түрін берді. Ол сөздермен, демек әріптердің сызықтық тізбегімен, жұмыс жасайтын алгоритмді қарастырған. Бұл теорияның негізгі ұғымы – алмастыру ұғымы. Алмастыру екі бөліктен тұрады: сол жақ және оң жақ. Алмастыру А алфавитінің сөзіне келесі ереже бойынша қолданылады: Сөздің ішінен алмастырудың сол жақ бөлігімен сәйкес келетін ішкі сөз ізделеді. Егер мұндай ішкі сөз бар болса, онда оның орнына алмастырудың оң жақ бөлігі жазылады. Егер ішкі сөз табылмаса, онда алмастыруды бұл сөзге қолдануға болмайды. Бар ауыстырылымдардыі біреуін бір рет қолдану арқылы А алфавитінің бір сөзінен екінші сөзі алынатын болса, онда мұндай сөздер сыбайлас сөздер деп аталады. Егер В, В1, В2,…,С тізбегінің әрбір екі көршілес сөздері сыбайлас сөздер болса, онда А алфавитінің В және С сөздерінің арасында дедуктивті байланыс бар деп есептелінеді. Егер В және С сөздері эквивалентті болса, онда В сөзінен С сөзіне және С сөзінен В сөзіне дедуктивті байланыс құрастыруға болады. Алмастыру формулаларының оң және сол жақ бөліктері бос болуы мүмкін. Марков алгоритмін жазу үшін бос орындарды арнайы белгілеудің қажеті жоқ. Сонымен, егер А алфавиті және ауыстырулар жүйесі берілген болса, нормалды Марков алгоритмі берілген деп саналады. Ауыстырулар жүйесі кез келген К сөзіне келесі ереже бойынша қолдануға болады: алдымен бірінші ауыстырылым қарастырылады, егер бұл ауыстырылымның сол жақ бөлігі К сөзіне кіретін болса, онда К сөзінің табылған ішкі сөзін ауыстырылымның оң жағымен алмастырамыз. Нәтижесінде К1 сөзін аламыз. Енді К1 сөзі бастапқы сөз болып саналады. Бірінші ауыстырылым қарастырамыз, егер бұл ауыстырылымды қолдануға болмайтын болса келесі ауыстырылымды қарастырамыз, т.с.с. Ауыстыру процессі екі жағдайда тоқталуы мүмкін: ең соңғы ауыстырылым қолданылғанда; ешбір ауыстырылым қолдануға келмейді. 1 мысал. Алфавит: {а, b, с, d, е}. Ауыстырылымдар: ас - са; abac - abace; ad - da; eca - ae; be - cb; eda - be; bd - db; edb - be. Егер abcde және acbde сөдерін алатын болсақ, бұл сөздер өзара сыбайлас (be – cb ауыстырылымы) сөздер болады. Ал abcde - cadbe сөздерін алатын болсақ, бұл сөздер – эквиваленті. жүктеу/скачать 363.46 Kb. Достарыңызбен бөлісу:
|