3 Тақырып. Есептерді алгоритмдеу негіздері.
4 Лекция
4.1 Алгоритм анықтамасы. Алгоритмдерді бейнелеу тәсілдері.
Алгоритм анықтамасы. «Алгоритм» сөзі Абу Абдуллах Мухаммед ибн Муса аль-Хорезми ғалым есімінен туындылаған деп саналады.
Алғашқы тұжырымдама бойынша алгоритм –нәтижеге жету үшін, шектеулі уақытта белгілі бір есепті шешу үшін белгілі бір орындаушының амалдар тізбегін сипаттайтын дәл нұсқаулар жиынтығы. Компьютер жұмысындағы параллельділіктің дамуы бойынша “тізбегі” сөзін жалпылау “реті” сөзімен ауыстыра бастады. Ол алгоритмдің кейбір амалдары бірінен кейін бірі орындалуы, ал кейбіреулері тәуелсіз болуы мүмкіндігіне байланысты.
Алгоритм – ол белгілі бір орындаушының операторлар жиынынан алынған операторлар жүйесі. Ол алгоритмдік үрдістердің белгілі бір класын толығымен анықтайды. Ол үрдістер:
дискреттік;
детерминді;
потенциалды тұрғыда ақырғы;
белгілі бір конструктивті объекттерді түрлендіреді.
Алгоритмнің операторлары мен алгоритмдік үрдістің операциялары (элементарлы амалдар) арасында гомоморфты сәйкестік орын алады. Сондықтан алгоритмді алгоритмдік үрдістің моделі деп санауға болады.
Алгоритмге қойылатын жалпы талаптар:
детерминділік — анықтық. Уақыттың әр моментінде жұмыстың келесі қадамы жүйенің күйі арқылы бірмәнді түрде анықталады. Сонымен, бірдей бір бастапқы деректер үшін бірдей бір нәтиже (жауап) қайтарады. Сонымен қатар, ықтималдық алгоритмдер де бар. Оларда жұмыстың келесі қадамы жүйенің ағымдағы күйіне және генерацияланатын кездейсоқ санға тәуелді.
түсініктілік — алгоритм орындаушы үшін оған (орындаушыға) қол жетерлік, оның бұйрықтар жүйесіне кіретін бұйрықтарды ғана қамтуы тиіс.
аяқталулық (ақырғылық) — бастапқы деректер корректілі түрде берілгенде алгоритм саны шектеулі қадамдардан кейін жұмысын аяқтап, нәтижені беруі тиіс. Екінші жағынан, ықтималды алгоритм нәтижесін ешқашан бермеуі де мүмкін, бырақ оның ықтималдығы 0 ге тең.
Көпшілікке ортақшылық — алгоритм бастапқы деректердің түрлі жиынтықтарына қолданылуы тиіс.
Маңызды рөльді рекурсивтік алгоритмдер атқарады (кері қайтудың белгілі бір шартына жеткенше өзін өзі шақыратын алгоритмдер). Соңғы кездері белсенді түрде параллельдік алгоритмдер жетілдірілуде. Олар бір мезгілде бірнеше операцияларды орындауға қабілетті есептеуіш машиналарға арналған.
4.2 Алгоритмдердің блок-схемаларын безендіру ережелері.
Программалаудағы Блок-схема — бұйрықтарды, амалдарды, деректерді және с.с. белгілейтін стандартты графикалық элементтерді (тік төртбұрыштарды, ромб, трапециялар және с.с.) пайдаланып, программа немесе алгоритмдің графикалық бейнеленуі.
Блок-схемаларды орындау ережелерін анықтайды:
ГОСТ 19.701-90 (ИСО 5807-85) - Алгоритмдер, программалар, деректер және жүйелер схемалары. Шартты белгілеулері және орындау ережелері.
Сурет 4.1 – Алгоритмдердің блок-схемаларын графикалық бейнелеу мысалдары.
4.3 Алгоритм құрылымдарының түрлері.
Негізінде, алгоритмдердің сызықтық, тармақталу, параллель және циклдік құрылымдарын қарастырады.
Цикл — программалаудың жоғары деңгейлі тілдерінде нұсқаулар жиынтығын қайталап бірнеше рет орындау үшін арналған басқарушы құрылымның түрі. Сонымен қатар, басқа тәсілмен (мысалы, шарт бойынша өту арқылы) ұйымдастырылған кезкелген көп рет орындалатын нұсқаулар тізбегі болуы мүмкін.
Сурет 4.2 – Сызықты және тармақталу алгоритмдерінің блок-схема мысалдары
Көп рет орындалу үшін арналған нұсқаулар тізбегі, цикл тұлғасы деп аталады. Цикл тұлғасының бір рет орындалуы итерация деп аталады. Кезекті мәрте итерация орындалатындығын немесе цикл аяқталатындығын анықтайтын өрнек шығу шарты немесе цикл аяқталу шарты деп аталады (немесе оның ақихаттығының интерпретациялануына тәуелді– циклді аяқтау немесе жалғастыру қажеттілігі белгісі ретінде жалғастыру шарты деп аталады). Итерацияның ағымдағы нөмірін сақтайтын айнымалы цикл итерацияларын санауыш немесе жай цикл санауышы деп аталады. Циклдың санауышты қамтуы міндетті емес, санауыштың жалғыз болуы міндетті емес – циклден шығу шарты цикл ішінде өзгеретін бірнеше айнымалыларға тәуелді болуы мүмкін, немесе сыртқы шарттар арқылы анықталуы мүмкін (мысалы, белгілі бір уақыттың басталуына), соңғы жағдайда санауыш мүлдем қажет болмауы да мүмкін.
Кез келген циклды орындау цикл айнымалыларын бастапқы инициализациялауды, шығу шартын тексеруді, цикл тұлғасын орындауды және әр итерацияда цикл айнымалысын жаңартуды қамтиды. Сонымен қатар, программалау тілдерінің көбісі циклді мезгілден бұрын аяқтау, яғни шығу шартының ақихаттылығына тәуелсіз циклден шығу құралдарын ұсынады.
Цикл түрлері. Шартсыз циклдер
Кейде программаларда олардан шығу шарты программа логикасында көзделмеген циклдар пайдаланылады. Мұндай циклдарды шартсыз немесе аяқталмайтын циклдер деп атайды. Олардың типсіздігіне байланысты шексіз циклдерді құруға арналған арнайы синтасистік құралдары программалау тілдерінде көзделмеген, сондықтан ондай циклдарды кәдімгі (немесе шартты) циклдарды құруға арналған құрылымдар арқылы құрады. Шексіз қайталануды қамтамасыз ету үшін ондай циклде шартты тексеру жоқ (егер синтаксис рұқсат етсе, мысалы, Ада тілінің LOOP…END LOOP циклындағыдай) немесе тұрақты мәнбен алмастырылады (Паскальда while true do …).
Алдынғы шартты цикл – ол басында көрсетілген шарт ақиқат болып тұрғанша орындала беретін цикл. Бұл шарт цикл тұлғасын орындау алдында тексеріледі, сондықтан цикл тұлғасы бір де бір рет орындалмауы да мүмкін (егер шарт ең басынан жалған болса). Программалаудың процедуралық тілдерінің көбісінде ол while операторы арқылы жүзеге асырылады, сондықтан оның екінші аталуы while-цикл.
Кейінгі шартты цикл – ол шарты цикл тұлғасы орындалғаннан кейін тексерілетін цикл. Сондықтан, цикл тұлғасы әрдайым кемінде бір рет болса да орындалады. Паскаль тілінде бұл циклды repeat..until; операторы, С тілінде — do…while операторы жүзеге асырады.
а – алдыңғы шартты цикл, б – кейінгі шартты цикл
Сурет 4.3 – Циклдік алгоритмдерінің блок-схемалар мысалдары
Ортасынан шығу циклы – шартты циклдің ең ортақ формасы. Синтаксис тұрғысында мұндай цикл үш құрылыс арқылы ұйымдастырылады: цикл басы, цикл соңы және циклдан шығу бұйрықтары. Цикл басының құрылысы программадағы цикл тұлғасы басталатын нүктені таңбалайды, цикл соңының құрылысы – цикл тұлғасы аяқталатын нүктені. Түлғаның ішінде циклдан шығу бұйрығы болуы тиіс. Ол бұйрық оррындалған кезде цикл аяқталады да басқару цикл соңының құрылысынан кейінгі операторға беріледі. Әрине, цикл бір реттен көп орындалуы үшін шығу бұйрығы шартсыз емес, ал циклдан шығу шарты орындалған кезде ғана шақырылуы тиіс.
Жоғарыда қарастырылған циклдерге қарағанда циклдің мұндай түрінің принципиалды айырмашылығы цикл басынан кейін шығу бұйрығына дейін орналасқан цикл тұлғасының бөлігі әрдайым орындалады (циклдан шығу шарты бірінші итерацияның өзінде ақихат болған жағдайда да), ал шығу бұйрығынан кейін орналасқан цикл тұлғасының бөлігі соңғы итерацияда орындалмайды.
Ортасынан шығу циклы арқылы алдыңғы шартты циклді (шығу бұйрығын цикл тұлғасының басында орналастырып) және кейінгі шартты циклді (шығу бұйрығын цикл тұлғасының соңында орналастырып) оңай модельдеуге болады.
Программалау тілдердің бір қатары ортасынан шығу циклын ұйымдастыру үшін арнайы құрылыстарды қамтиды. Мысалы, Ада тілінде ол үшін LOOP…END LOOP құрылысы және EXIT немесе EXIT WHEN шығу бұйрықтары бар:
LOOP
... Цикл тұлғасының бөлігі
EXIT WHEN <шығу шарты>;
... Цикл тұлғасының бөлігі
IF <шығу шарты> THEN
EXIT;
END;
... Цикл тұлғасының бөлігі END LOOP:
Мұндағы цикл ішінде екі типтегі шығу бұйрықтарының саны кезкелген болуы мүмкін. Шығу бұйрықтардың өздері принципиалды тұрғыда ажыратылмайды, әдетте тек шығу шарты тексерілетін кезде EXIT WHEN қолданылады, ал жай EXIT-ті циклдан шығу күрделі шартты оператор нұсқаларының біреуінде іске асырылады.
Ұқсама құрылыстары көзделмеген тілдерде ортадан шығу циклін кезкелген шартты цикл және циклдан мерзімнен бұрын шығу операторы (С тіліндегі break сияқты) немесе шартсыз өту goto операторы арқылы модельдеуге болады.
Санауышы бар цикл – ол ішінде кейбір айнымалы өз мәнін берілген бастапқы мәннен соңғы мәнге дейін белгілі бір қадаммен өзгертетін және осы айнымалының әр мәні үшін цикл тұлғасы бір рет орындалатын цикл. Программалаудың процедуралық тілдерінің көбісінде мұндай цикл for операторы арқылы жүзеге асырылады. Ол операторда санауыш (цикл айнымалысы), өтулердің талап етілетін саны (немесе санауыштың шекті мәні) және, мүмкін, санауыш өзгеретін қадамы. Мысалы, Оберон-2 тілінде мұндай циклдың түрі:
FOR v := b TO e BY s DO
... цикл тұлғасы
END
(мұндағы v - санауыш, b – санауыштың бастапқы мәні, e - санауыштың шекті мәні, s - қадам).
Оның ішінде берілген айнымалы санауыш ретінде қолданылған айнымалының цикл аяқталғанынан кейінгі мәні туралы сұрақ бір мәнді емес. Мысалы, егер Паскаль тіліндегі программада келесі түрдегі құрылыс кездессе:
i := 100;
for i := 0 to 9 do begin
... цикл тұлғасы
end; k := i;
сұрақ пайда болады: нәтижеде k айнымалысына қандай мән меншіктеледі: 9, 10, 100, мүмкін басқа бір мән? Ал егер цикл мерзімнен бұрын аяқталса? Жауаптар соңғы итерациядан кейін санауыштың мәні артады ма және транслятор сол мәнді қосымша өзгертеді ма деген сұрақтарға тәуелді. Және бір сұрақ: егер циклдың ішінде санауышқа анық түрде жаңа мән меншіктелсе не болады? Түрлі программалау тілдер бұл мәселелерді әртүрлі шешеді. Кейбір тілдерде санауыштың тәртібі айқын регламенттелген. Ал басқаларында, мысалы Паскальда, тілдің стандарты санауыштың соңғы мәнін де, цикл ішінде оны айқын өзгерткенде пайда болатын салдарын да анықтамайды, бырақ ол санауышты айқын түрде өзгертпеуді және цикл аяқталғаннан кейін санауышты қайта инициализациялаусыз пайдаланбауды ұсынады. Бұл мәселе Ада тілінде жақсы шешілген: санауыш цикл тақырыбында сипатталған болып саналады да одан тыс орын алмайды. Егер санауыштың есімі программада қолданылған болса да циклдың ішінде санауыш ретінде жеке айнымалы пайдаланылады. Санауышқа мәндерді айқын түрде меншіктеу рұқсат етілмейді, оны тек цикл операторының ішкі механизмі ғана өзгерте алады. Нәтижеде келесі құрылыс:
i := 100;
for i in (0..9) loop
... цикл тұлғасы
end loop; k := i;
сырт көрінісі жоғарыда келтірілген Паскаль цикліне ұқсама бірмәнді түрде тұжырымдалады: k айнымалысына 100 деген мән меншіктеледі, себебі берілген циклдан тыс қолданылатын і айнымалының цикл ішінде құрылып және өзгеретін і санауышқа ешқандай қатынасы жоқ. Санауышты осылайша жекешелендірген ең ыңғйлы және қауіпсыз болып саналады: оны жеке сипаттау қажет емес және циклге қарағанда сыртқы айнымалыларды кездейсоқ түрде бұзып алуға байланысты кездейсоқ қателердің пайда болуының минималды ықтималдығы.
Санауышы бар циклды әрдайым шартты цикл сияқты жазуға болады. Ол үшін циклдың басында санауышқа бастапқы мән меншіктеледі, ал шығу шарты санауыштың соңғы мәнге жеткен кезі болып табылады, цикл тұлғасына санауышты берілген бір қадамға өзгертетін оператор қосылады. Бырақ санауышы бар циклдың арнайы операторлары тиімділеу трансляцияланады, себебі мұндай циклдың формализацияланған түрі циклдарды ұйымдастырудың арнайы процессорлық бұйрықтарын пайдалануға мүмкіндік береді.
Бір бірінің ішіне салынған циклдар
Цикл тұлғасының ішінде басқа циклды ұйымдастыру мүмкіндігі бар. Ондай цикл кірістірілген (ішіне салынған) цикл деп аталады. Кірістірілген цикл ішкі цикл деп, ал тұлғасының ішіне басқа цикл кірістірілген циклды сыртқы цикл деп атайды. Кірістірілген циклдың ішіне кірістірудің келесі деңгейін құрып және бір циклды кірістіруге болады, және с.с. Кірістіру деңгейлер саны әдетте шектелмеген.
Ішкі цикл орындалуларының толық саны ішкі және барлық сыртқы циклдардың иерациялар сандарының көбейтіндісінен аспайды. Мысалы, әрқайсысы 10 итерациядан болатын бір біріне салынған 3 циклды алсақ, сыртқы цикл үшін тұлғасы 10 рет, екінші деңгейдегі цикл 100 рет және ең ішкі цикл 1000 рет орындалады.
Коллекция бойынша цикл Кейбір тілдер (C#, Java, JavaScript, Perl, Python, PHP, LISP, Tcl және басқалар) объекттердің берілген коллекциясының барлық элементтері бойынша циклдарды орындауға мүмкіндік береді. Мұндай циклды анықтау үшін белгілі бір санауышты көрсету, циклдан шығу шартын беру қажет емес. Коллекцияны және оған коллекциядағы барлық объекттердің мәндері немесе оларға жасалған сілтемелері ретімен меншіктелетін айнымалыны берген жеткілікті. Ондай циклдер foreach, for…in және с.с. операторлар арқылы жүзеге асырылады.