Лекция Алгоритм және оларды бейнелеу жолдары Сұрақтар: Алгоритм, программа ұғымы. Алгоритм қасиеттері

• 1-2 лекция

• Алгоритм және оларды

• бейнелеу жолдары

• Сұрақтар:

• Алгоритм, программа ұғымы.
• Алгоритм қасиеттері
• Алгоритмнің өрнектелу жолдары
• Алгоритмдердің бірыңғай құрылымдары
• Сызықтық алгоритмдер
• Тармақталу алгоритмдері
• Циклдік алгоритмдер

• Алгоритм атауы атақты шығыс математигі абу Жафар Мұхаммед ибн Мұса әл-Хорезми (763-850 ж. ) есімінің латынша Algorіthmі (Алгорит-ми) болып жазылуынан шыққан. Ол санаудың ондық жүйесінде көпорынды сандармен ариф-метикалық амалдардың орындалу ережесін ұсынған. Бұл ережелер қосынды мен көбейтін-діні табуға арналған амалдарды орындауға қа-жетті тізбектен құрылған. Сол ереже осы күнге дейін қолданылып келеді.

• 1. Алгоритм, программа ұғымдары

• Алгоритм – берілген есептің шығару жолын реттелген амалдар тізбегі түріне келтіру.

• Алгоритмді орындаушының рөлін негізінен адам немесе компьютер, робот т. б. атқарады. Мысалы, y = (ax+b)(cx-d) функциясын есептеу төмендегі қарапайым іс-әрекеттерден тұрады:
• 1) а-ны х-ке көбейту, оны R1 деп белгілеу;
• 2) оған b-ны қосу, нәтижесін R2 деп белгілеу;
• 3) с-ны х-ке көбейту, оны R3 деп белгілеу;
• 4) одан d-ны алу, оны R4 деп белгілеу;
• 5) R2-ні R4-ке көбейту, оны y деп белгілеу.

• Алгоритмге күнделікті тұрмыстан алып бір мысал келтіре кетейік. Студент болу үшін алгоритмнің мынадай қадамдарын орындау керек.
• 1. Орта мектепті бітіріп, тест тапсыру.
• 2. Керекті құжаттарды тест нәтижесімен бірге белгілі бір жоғары оқу орнына (колледжге, институтқа) өткізу.
• 3. Конкурстан өту.

• Техникалық құрылғыларды дұрыс пайдалану үшін есептің шешу жолы, яғни орындалатын әрекеттердің тізбегі әрі түсінікті, әрі дәл болуы қажет.
• Берілген мәселенің шешу жолдарының түсініктілігін оның алгоритмінің түсініктілігі деп қарастырады. Алгоритмде алдыңғы әрекеттің нәтижесі келесі әрекетте пайдаланылады.
• Алға қойған мақсатқа жету немесе берілген есепті шешу бағытында атқарушыға біртіндеп қандай әрекеттер жасау қажеттігін әрі түсінікті, әрі дәл етіп көрсететін нұсқаулар тобын агоритм деп атайды.

• Төмендегі алгоритм анықтамаларын салыстырыңыздар:
• 1. Алгоритм - алғашқы берілген мәліметтерді пайдаланып нақты нәтижеге қол жеткізетін шекті командалар тізбегін орындауда атқарушыға түсінікті және нақты нұсқаулар.
• 2. Алгоритм дегеніміз - берілген мәндерді пайдаланып қажетті нәтижеге жетуді жүзеге асыратын әрекеттердің орындалу ережесі.
• 3. Алгоритм дегеніміз - алғашқы берілген мәліметтерді пайдаланып, қойылған мақсатқа жетуге немесе мәселені шешуге (есепті шығаруға) бағытталған әрекеттердің орындалуын жүзеге асыратын атқарушыға түсінікті және нақты нұсқаулар тізбегі.

• Алгоритмді компьютерде орындау үшін оны программа түрінде жазып шығу керек.
• Программа – алгоритмді машинаға түсінікті нұсқаулар тізімі ретінде жазу.
• Программа машинаға түсінікті командалардан тұрады. Осы командалар тізбегі орындалу барысында есептің нәтижесі шығады. Әрбір компьютер алдын ала жазылған программамен істейді.
• Программа дегеніміз – белгілі бір нәтиже алу үшін орындалатын командалдардың айқындалған тізбегі.
• Процессор программаның құрамындағы командаларды кезекпен орындап отырады. Командалар тізбегін программа деп қарастыруға болады.

• Команда бір ғана қарапайым амалды орындау үшін берілген бұйрық ретінде беріледі.
• Командалар: арифметикалық немесе логикалық амал; ақпаратты тасымалдау командасы; беріл-ген сандарды салыстыру командасы; нәтижені экранға, қағазға басып шығару командасы; кел-есі командаларға көшу тәртібін орындау т.с.с.
• Компьютердің жұмысы программалық принцип-ке негізделген, яғни ол өзінің жадында сақтала-тын командалар тізбегін автоматты түрде орын-дау арқылы есеп шығарады.

• Компьютер берілген тапсырманы орындауға дайын тұрған техникалық аспап болғандықтан, әрбір тапсырманы түсінікті түрде қысқаша жаза білу қажет. Тапсырма жоғарыда айтылған жекеленген командалардан тұрады. Машинаға түсінікті түрде жазылған тапсырмаларды немесе командалар жиынын да программа деп атауға болады.
• Программа – арнайы мәтін арқылы компьютерге тапсырманың ретті кезегін хабарлайтын ережелер мен нұсқаулар тізбегі.

2. Алгоритм қасиеттері

• Алгоритмнің мәнін ашатын негізгі қасиеттерінен немесе оған қойылатын талаптардан қысқаша мағлұматтар келтірейік. Компьютерде орындалуға тиіс алгоритмдерге мынадай талаптар қойылады:
• 1) алгоритм анық, әрі дәл өрнектелуі тиіс – детерминділік қасиеті;
• 2) оның модульдік (бөлікке бөліну) қасиеті, яғни алгоритмді шағын бөліктерге бөлу мүмкіндігі болуы қажет;
• 3) алгоритм шектелген уақыттан соң нәтиже беруі тиіс, яғни алгоритм қадамдарының саны шексіз болмауы керек – нәтижелілік (шектеулілік) қасиеті;
• 4) бір типтегі (біртектес) есептерге жалпы бір ғана алгоритм қолданылуы тиіс – жалпылық қасиеті.

3. Алгоритмнің өрнектелу жолдары

• Алгоритмдерді компьютерде орындау үшін оларды алдын ала жазып алу керек, яғни ол белгілі бір заңдылықпен өрнектелуі тиіс. Жалпы алгоритмді өрнектеу түрлеріне:
• 1) табиғи тіл арқылы жазу;
• 2) белгілі бір түйінді сөздер – терминдер (псевдокодтар - жалған кодтар) арқылы қысқаша тізбекті түрде жазу, мұны қарапайым алгоритмдік тіл деп те айтады;
• 3) график жолымен (блок-схема арқылы) жазу;
• 4) программалау тілдерінде жазу жолдарын жатқызуға болады.

• Алгоритмді табиғи тілде өрнектеу компьютердерде қолданылмайды, өйткені онда дәлдік, нақтылық болмайды.
• Ал алгоритмді екінші көрсетілген жолмен өрнектеу қарапайым алгоритмдік тіл деп аталып кеңінен қолданылып жүр. Мұны олардың ағылшын тіліне негізделіп жасалған программалау тілдеріне жақындығымен түсіндіруге болады.
• Алгоритмдерді график жолымен жазу, онан кейін оны программалау тіліндегі программаға айналдыру істері мемлекеттік стандартпен бекітіліп ақпарат өңдеу жұмысында кеңінен қолданылып келеді.

• Іс-әрекеттің аты

• Блоктың түрі

• Атқаратын жұмысы

•  
•  
• Процесс
•  
•  

•  
• Математикалық өрнектерді есептеу

•  
• Бастау, аяқтау
•  
•  
•  
•  

•  
• Алгоритмдерді бастау, аяқтау

•  
• Қосалқы программа
•  
•  

• Қосалқы программаларға кiру және шығу

• y : = a+b

• басы

• Е15

• Алгоритмдерді график жолымен жазу

• Таңдау

• Модификация

•  
• Есеп шығару жолын таңдау

•  
• Нәтижені баспаға (қағазға) шығару

• Құжат

• a > b?

• иә

• жоқ

• Цикл (қайталау) басы

• i : = 1,10,1

• x, y

•  
• Енгiзу,
• шығару

•  
• Мәліметтерді енгiзу, шығару
•  
•  
•  
•  
•  

• х енгізу

•  
• Түсініктеме беру

• Схеманы, формулаларды түсіндіру
•  
•  
•  
•  
•  

•  
• Қосалқы программа
•  
•  

• Қосалқы программаларға кiру және шығу

• Е15

• Алгоритмдерді график арқылы бейнелеу түсінік-ті, анық, көрнекті түр болып есептеледі. Тек ола-рды сызу көбірек еңбекті талап етеді. Графика-лық жолмен алгоритмдерді жазу үшін мемлекет-тік стандарт белгіленген, онда кез келген амал белгілі бір геометриялық фигурамен өрнектеледі. Ол фигуралар немесе блоктар амалдар немесе операциялар символы деп те аталады. Блоктар бағытталған сызықтармен байланысып, бірінен соң бірі орналасады.

• 4. Алгоритмдердің бірыңғай құрылымдары

• Кез келген алгоритмді (программаны) блоктар-дың өзара байланысуына қарай төмендегідей үш түрлі басқару құрылымын пайдалану арқы-лы жазып шығуға болатындығы дәлелденген:
• сызықтық құрылым немесе әрекеттер тізбегі;
• тармақты құрылым немесе шартты тексе-ру;
• қайталау немесе циклдік құрылым.

• Осындай негізгі (канондық) құрылымдардан тұра-тын алгоритмді регулярлық алгоритм (программа) деп атайды, олардың бір ғана кіру нүктесі мен бір ғана шығу нүктесі болады. Осы үшеуі құрылым-дық программалаудың негізгі конструкцияла-ры, яғни құраушылары болып саналады.
• Программадағы кез келген әрекетті (операторды) оның кіру нүктесі арқылы тауып орындауға болады (осы тәсілмен табылмайтын операторлар және шек-сіз циклдер болмауы тиіс). Мұндай алгоритмді – программаны басқару ісі жоғарыдан төмен қарай жүргізіледі. Түсініктеме мәтін (комментарий) қос-ылған осындай программалар оқуға және түсінуге жеңіл болып есептеледі.

• Оператор – тілдің қарапайым сөйлемі, ол белгілі бір әрекет немесе амал орындап, ; таңбасымен аяқталады.
• Сызықтық құрылым бірінен кейін бірі орындалып тізбектеле орналасқан бірне-ше операторлардан тұрады.
• Тармақты – шартқа байланысты екі оператордың бірінің орындалуы
• Цикл – операторлар бөлігінің бірнеше рет қайталана орындалуы.

• Төменде алгоритмдердің бірыңғай құрылым-дарының схемалық бейнеленуі көрсетілген

• Мұнда a және b-ның сандық мәндерін ЭЕМ-ге енгізіп (2-блок), содан кейін қосу ама-лын орындап, ақырында y-ті қағазға басып шығарып, жұм-ысты тоқтатамыз.
• y = a + b формуласы есептеу блогы (3-блок) арқылы өрнек-теледі. Ал нәтижені қағазға ба-су үшін көпбұрышты құжат алу блогын (4-блок) пайдала-нып, оның ішіне нәтиженің атауларын жазамыз.

• басы

• a, b-ны енгізу

• y : = a + b

• y

• соңы

• 1

• 2

• 3

• 4

• 5

• 5. Сызықтық алгоритм

6. Тармақталу алгоритмдері

• Тармақталу алгоритмінде арифметикалық теңсіздік (тең-дік) түрінде берілген логикалық шарт тексеріледі. P шар-тының мәні ақиқат (true) немесе жалған (false) бола ала-тын логикалық өрнек түрінде болады. Егер ол орындалса – ақиқат болса, онда алгоритм бір жолмен, ал орындал-маса – екінші жолмен жүзеге асырылады, яғни есепті шы-ғару жолы тармақталып екіге бөлініп кетеді.

• false

• true

• А

• В

• P ?

• IF  P  then  A  else  B;

• Бұл құрылым толымсыз (қысқаша) түрде болуы мүмкін, онда логикалық өрнектің мәні жалған болғанда ешқандай әрекет орындалмайды. Мұндай құрылым түрі төменде көрсетілген:

• false

• true

• А

• P ?

• IF  P  then  A;

• . . .

• . . .

• ...

• 1 - àìàë

• æîº

• 2 - àìàë

• 3 - àìàë

• ...

• è¸

• øàðò?

• 1 - àìàë

• æîº

• 2 - àìàë

• 3 - àìàë

• è¸

• øàðò?

• "Таңдау" алгоритмі "Аттап өту" алгоритмі

• Тармақталу алгоритмдері осы екі түрде кездеседі, олар "таңдау" және "аттап өту" мүмкіндіктерін іске асыруға көмектеседі.

• 1-мысал. Y функциясын төмендегі формула бойынша есептеу керек

• x,y

• x енгiзу

• басы

• 2

• x0

• 3

• 6

• 7

• 1

• è¸

• æîº

• ñî»û

• Тармақталу алгоритмі

• 4

• 5

7. Циклдік алгоритмдер

• Көптеген есептерді шығару кезеңінде бір теңдеуді пайдаланып, ондағы айнымалының өзгеруіне байла-нысты оны бірнеше рет қайталап есептеуге тура ке-летін сәттер де жиі кездеседі.
• Осындай қайталап орындалатын есептеу процесінің белгілі бір бөліктерін цикл деп атайды.
• Бірнеше рет қайталанатын бөлігі бар алгоритмдер тобы циклдік алгоритмдерге жатады. Циклдік алго-ритмдерді пайдалану оларды кейіннен программа-ларда цикл операторы түрінде қысқартып жазу мүм-кіндігін береді.

• false

• true

• А

• P

• цикл – әзірше

• While  P do  A ;
• Мұнда А әрекеті Р шарт мәні ақиқат болып тұрса, қай-талана береді. Сондықтан А әрекеті орындалуы кезінде Р-ға әсер ететін айнымалылар мәні өзгеруі тиіс. Бұлай бол-маған жағдайда шексіз цикл орын алады. Шарт мәні А әрекетіне дейін анықталады, сол себепті кейде А әрекеті бір де бір рет орындалмауы да мүмкін.

• цикл – дейін

• true

• А

• false

• P

• Repeat  A  until  P;
• цикл – дейін түріндегі қайталау кем дегенде бір рет орындалады, өйткені шарт А әрекетінен кейін тексеріледі. А әрекеті Р мәні ақиқат болған кезде орындалмайтын болады.
• Циклдер қайталану санының алдын ала белгілі және белгісіз болуына байланысты екі топқа бөлінеді. Қайталану сандары алдын ала белгілі болып келетін циклдер тобы арифметикалық цикл болып есептеледі, ал орындалу саны белгісіз циклдер – қадамдық (итерациялық) цикл болып аталады.

• Практикада белгілі бір айнымалының сандық мәні-не байланысты орындалатын арифметикалық цикл-дер жиі кездеседі. Мұнда арифметикалық прогрес-сияға ұқсас болып келетін циклдер ең қарапайым арифметикалық цикл болып табылады. Оны басқару қайталану кезеңінде прогрессияның заңына сәйкес тұрақты шамаға өзгеріп отыратын цикл параметрі-нің сандық мәнімен байланысты болуы тиіс.
• Цикл орындалуы алдында оның айнымалы аргу-менті – параметрі алғашқы мәнге ие болуы керек, сонан соң қайталау кезінде цикл параметрі белгілі бір шамаға (қадамға) өзгере отырып, ол алдын ала берілген ең соңғы мәнге дейін жетуі қажет.

• Алгоритмнің орындалу барысында цикл параметрі, мысалы, х өзінің ең алғашқы х0 мәнінен ең соңғы хk мәніне дейін тұрақты шамаға (dx) өзгеріп отырады. Осының нәтижесінде х мынадай мәндерді қабыл-дайды: x0, x0+dx, x0+2dx, ..., x0+(n-1)dx, xk, мұндағы n – циклдің қайталану саны, ол былай анықталады:
• мұнда [...] – өрнектің бүтін бөлігі алынатынын көр-сетеді. n әрқашанда бүтін сан болуы тиіс, егер ол аралас сан болса, онда оның бөлшегі алынып тас-талады, өйткені циклдің қайталану саны бүтін натуралдық сан болуы тиіс.

• Арифметикалық цикл үшін y=f(x) функциясының есеп-телу жолы алгоритм ретінде суретте көрсетілген. Мұндағы 3-ші, 4-ші, 7-блоктар циклді ұйымдастыру үшін қажет. Олар цикл параметрінің алға-шқы мәнін, өзгеру қадамын белгілеп және оның ең соңғы мәніне жеткен-жетпегенін тек-середі. Ал 5- және 6-блоктар бірнеше рет қайталанып цикл-дің өзін құрайды. 4-блок шартты тексеріп қайталану процесін ұйымдастырады.

• Қарапайым циклдік алгоритм

• x, y

• ñî»û

• y:=f(x)

• басы

• x0,xê,dx

• x:=x0

• õxk

• жоқ

• иә

• 8

• 2

• 5

• x:=x+dx

• 6

• 7

• 4

• 1

• 3

• Алгоритм салуды және прог-рамманы жазуды жеңілдету үшін цикл алгоритмдерін "модификатор" немесе "цикл басы" блогын пайдалану арқылы жазылады. Онда алд-ыңғы көрсетілген 3-ші, 4-ші, 7-блоктардың орнына "цикл басы" блогы орналасады. Ол алтыбұрышты фигурадан тұрады және оның міндетті түрде екі кіру және екі шығу сызығы болуға тиіс.

• Модификаторлы циклдік алгоритм

• y= f (x)

• x,y

• ñî»û

• áàñû

• x0,xê,dx åíãiçó

• x=x0,xk,dx

• 2

• 4

• 6

• 5

• 3

• 1

• Қадамдық циклдер. Циклді орындаудың алдында, оның қайталану саны белгісіз болған жағдайда қадамдық циклдер пайдаланылады. Мұнда циклді жазу үшін тек қана "шартты тексеру" блогын қолдану қажет, ол циклді аяқтау үшін белгілі бір шартты тексереді. Қадамдық циклдердің схемасын сызғанда модификаторды (алтыбұрышты) қолдана алмаймыз, себебі алдын ала циклдің неше рет қайталанатыны бізге белгісіз. Енді осындай циклдер жұмысына мысал келтірейік.

• 3-мысал. функциясының
• мәндерін k = 1, 2, 3, ... және Z 0.0001-ден артық болған жағдай-да есептейік, мұндағы 0  х  1. Бұл мысалда алдын ала цикл не-ше рет қайталанатынын айта ал-маймыз, өйткені бізде тек k пар-аметрінің алғашқы мәні мен қа-дамы ғана белгілі. Сонымен қа-тар Z функциясы-ның 0.0001-ден артық болуы циклді қайта-лау шарты болып есептеледі (Z > 0.001). Суретте осы есептің алгоритм схемасы көрсетілген.

• k, z

• соңы

• басы

• x-ті енгізу

• z>10-4

• жоқ

• иә

• 8

• 2

• k=k+1

• 5

• 6

• 1

• 7

• 4

• k = 1

• 3

• z=

• Қадамдық цикл алгоритмі

• Таңдау – case ауыстырғыш (көп тармақты) құрылы-мы программалауды жеңілдететін мүмкіндік болып табылады. Таңдау құрылымы бірнеше мүмкіндіктер-дің біреуін ғана орындау кезінде өте қолайлы.

• А

• В

• P

• Y

• Z

• . . .

• Р мәніне байланысты А, В, …, Z әрекеттерінің бірі орындалады да, сонан кейін келесі құрылымдар атқарылады.
• Программа жұмысын басқару операторларын программаның басқарушы конструкциясы деп атайды. Олар:
• ·       құрама операторлар;
• ·       таңдау операторлары;
• ·       цикл операторлары;
• ·  көшу операторы
• болып бөлінеді.

• Тыңдағандарыңызға

• рахмет!