АЛГОРИТМДЕУДІ? НЕГІЗГІ ??ЫМДАРЫ
Жоспары.
І. Алгоритм ??ымы ж?не оны? ?асиеттері.
ІІ. Алгоритмдеу ж?не програмалау кезе?дері.
ІІІ. Алгоритмді сипаттау, к?рсету т?сілдері.
ІV. Шамалармен ж?мыс істеу алгоритмдері.
I. Алгоритм ??ымы ж?не оны? ?асиеттері
Адам мен компьютер арасында?ы тіл ?атысу, хабар алысу ?рекеттері тек алгоритм ар?ылы ?ана іске асырылады. Сонды?тан, есептеуді, ме?гергісі келген адам, алдымен, алгоритм с?зі мен сол ??ымны? м?н, ма?ынасын тере? білуі ?ажет.
Тарихтан: Алгоритм с?зі ?ылым?а Орта Азияны? к?не тарихынан м?лім М?хаммед ибн М?са ?л-Хорезми (783-850 ж. шамасы) деген ?йгілі математикті? есімі мен е?бегіне байланысты енген.
Хорезмдік М?хаммед М?са ?лы ?зіні? «?нді хисабы туралы кітап» деген е?бегінде кез келген N санды б?л к?нде ?нді-араб цифрлары деп атап ж?рген 0,1,2,.,9 т?ріндегі он белгілемер ар?ылы ?рнектеп жазу ережесін баяндайды. Сонымен ?атар, ол осылайша жазыл?ан сандар?а ?олданылатын амалдарды орындау ережелеріне то?талады.
Европа елдері XII-XIII ?асырларда М?хаммед ?л-Хорезмиді? аталмыш кітабы ар?ылы ал?аш танысады. М?хаммед кітабында?ы ?рбір ереже «?л-Хорезми айт?ан» (латынша: Dixit Algorizmi) деген кіріспе с?зден басталады. Кейін Европа халы?тары тілінде б?л алгоритм немесе алгорифм болып ?алыптас?ан. (Б?л дерек ?. Н?рс?лтанов – «Дискретті математикалы? логика» кітабынан алынды).
Алгоритм – дегеніміз ал?а ?ойыл?ан ма?сат?а жету немесе берілген есепті шешу ба?ытында орындаушы?а (адам?а, ЭЕМ – ? процессоры сия?ты автомат?а) біртіндеп ?андай ?рекеттер жасау керектігін т?сінікті т?рде ?рі д?л к?рсететін н?с?аулар тізбегі.
Алгоритмді орындаушы - ол, ай?ындал?ан ?рекеттер жиынын орындай алатын адам немесе автомат немесе робот.
Алгоритмні? командасы – ол, бір ?ана ?рекет жасау?а арнал?ан б?йры?.
Орындаушыны? командалар ж?йесі (ОКЖ) – ол, орындаушыны? ат?ара алатын барлы? командалар жиынты?ы.
Алгоритмні? формалды орындалуы – деп, орындаушы есепті? ма?насын білмеседе, дайын алгоритмні? командаларын б?лжытпай бірінен кейін бірін орындап, сол есепті? н?тижесін шы?ару.
Алгоритмні? ?асиеттері:
Алгоритмні? н?тижелілігі (шектілігі) – саны шектеулі реттелген н?с?ауларды орындап ая?та?анда тияна?ты бір н?тижеге жеткізуге тиіс.
Алгоритмні? жаппайлы?ы (бірдейлігі) – алгоритм а???ла бір есеп ?ана емес, сондай б?кіл бір есептер класында?ы кез келген есепті? шешімін табу?а жарамды болуы тиіс.
Алгоритмні? дискреттілігі – ?арастырылып отыр?ан информацияны ??деу процессі ретімен жазыл?ан тізбекті? жеке-жеке б?ліктерінен т?руы тиіс.
Алгоритмні? т?сініктілігі – орындаушы?а (адам, ЭЕМ) н?с?аулар ж?йесі ар?ылы жазыл?ан алгоритмді т?сініп, орындай алатын болуы керек.
Алгоритмні? аны?тылы?ы – алгоритмні? н?с?аулары бірм?нді т?сінік беруге тиіс. Алгоритмде орындалатын ?ажеттті ?рекеттер тізбегі орындаушы?а д?л к?рсетіліп жазылуы керек.
II. Алгоритмдеу ж?не програмалау кезе?дері
ЭЕМ–де информацияны ??деу процессінде тек алгоритм ??руды ?ана емес, информацияны? мазм?нын зерттеуден бастап, оны? ??деу ?орытындысын тап?ан?а дейін ?тетін барлы? кезе?дерді барынша ?ада?алап, бір кезе?де ?ате кетсе, оны д?рыстап отыру керек.
Б?л кезе?дер:
- Есепті? ?ойылымын, я?ни мазм?нын зерттеу.
- Есепті? шешу ?дісін та?дау ж?не математикалы? ?лгісін (моделін) жасау.
- ??деу алгоритмін дайындау.
- Программа ??ру.
- Программаны тестілеу ж?не ж?ндеу.
- ЭЕМ-де программаны орындау.
- Н?тижені талдау.
Мысалы: Квадрат те?деуді? т?бірлерін табу алгоритімін ??ру керек.
Бірінші кезе?: те?деуді? ax2 + bx + c = 0 формуласын жазамыз, м?нда?ы a, b. с – ал?аш?ы берілгендер, кез келген сандар, ж?не a ¹ 0. Н?тиже: те?деуді? т?бірлеріні? м?ндері – x1 ж?не x2 деп белгілейік.
Екінші кезе?: Квадрат те?деулерді шешу алгоритмі барлы? жа?дайды ескеруге тиіс.
Дискриминантты есептеуден бастайы?: D = b2- 4ас. Енді квадрат те?деуді? т?бірлеріні? саны дискриминантты? та?басына байланысты бол?анды?тан екі жа?дайды ?арастыру ?ажет:
Егер D<0 болса, онда на?ты т?бірлері жо?.
Егер D ³ 0 болса, онда екі на?ты т?бірлері болады, оларды есептеу формулалары:
Б?л кезе?де, D=0 бол?ан жа?дайында т?бірлері те? болатыны онша ма?ызды емес.
?шінші кезе?: ауызша есептеу алгоритімін ??райы?:
- На?ты a, b. с м?ндерін енгізу;
- D –дискриминантты? м?нін D = b2 — 4ас формуласы бойынша есептеу;
- Егер D<0 болса, онда онда т?бірлері жо?. Бітіру;
- Егер D ³ 0 болса, онда т?бірлерді? м?нін формулалар бойынша есептеу.
III. Алгоритмді сипаттау, к?рсету т?сілдері
Ауызша таби?и тілмен сипаттау т?сілі: – алгоритмде оындалатын ?рекеттер таби?и тілмен сипатталады. ?асиеті: жалпы ?атынасты?ы, сипаттауді кез келген д?режеде дискретті ?адамдар?а б?лу м?мкіндігі. Кемшілігі: бірм?нді т?сініктілігіні? кемуі, программа?а ауысу?а ?иынды?ы.
- Жасанды алгоритмдік-формулалы? тілде сипаттау т?сілі – ол, бір сала?а келтірілген, на?ты ережелер мен та?балау ж?йесі аны?тал?ан жасанды тілді ?олдану ар?ылы алгоритмді ??ру.
- Графикалы?, блок-схема т?рінде сипаттау т?сілі – ??рылымдан?ан схема тілін ?олдану. Есепті? шы?ару кезе?дері ?рекеттерге с?йкес графикалы? жеке блоктармен бейнеленеді. ?р ?ректті? ?зіні? графикалы? бейнесі белгіленген. Мысалы: т?ртб?рыш – есептеу ?рекеті, ромб – шартты тексеру, т.б.
Квадрат те?деуді шешу блок-схемасы:
Алгоритмдеуді? негізгі бас?ару ??рылымдары
Алгоритмдегі ?рекеттер ?зіні? жазылу ретіне с?йкес тізбектеліп немесе белгілі бір шарт?а байланысты тарма?талып ия ?айталанып орындалады. Я?ни, алгоритмдегі ?рекеттерді? орындалу т?ртібі белгілі бір н?с?аулар бойынша бас?арылады.
Осындай н?с?ауларды бас?ару ??рылымдары деп атайды. Бас?ару ??рылымдарыны? негізгі ?ш т?рі бар:
Тізбекті ??рылымды – алгоритмні? командалары ?зіліссіз тізбекпен, бірінен кейін бірі орындалады. ?детте формула бойынша есептеуді ?йымдастыру?а ?олданылады.
Тарма?талу ??рылымды – алгоритмде ?детте, логикалы? шартты тексеру блогы болады. Егер шарт орындалса, онда ерекеттер тізбегіні? бір тарма?ы орындалады, ?йтпесе екінші тарма?ы орындалады.
?айталау немесе циклды? ??рылымды – алгоритмде «цикл денесі» деп аталатын ?рекеттер тізбегі, белгілі бір шарт бойынша к?п рет ?айталанылады. Циклды? алгоритмдік ??рылымдарды? ?ш типі белгілі.
Олар: алды??ы шартты ?зірше циклы, кейінгі шартты Дейін циклы ж?не параметрлі циклдік ??рылым.
Схемада тізбекті ж?не тарма?талу ??рылымдарымен ?атар, алды??ы ж?не кейінгі шарттар бойынша циклды? алгоритмді ?ымдастыру схемалары к?рсетілген:
Мысалы: N! факториал м?нін есептеуді? ауызша алгортимі мен блок схемасын ??ру керек. N! функциясы I – ден N-ге дейінгі натурал сандарды? к?бейтіндісі: N! = 1*2*3*…*N; ! – белгісі факториал деп о?ылады.
Шешімі. Алгоритм Дейін циклдік ??рылымды ?олданып ?йымдастырыл?ан:
алг факториал { алг ?ызметші с?зі, аты}
о?у N { N м?нін компьютерге енгізу}
k := 1; r := 1 {k–санауыш, r–н?тиже; }
- r := r*k {r! есептеп, ?айта меншіктеу}
- k := k + 1 {?р цикл сайын 1-ге ?сіру}
- егер k<= n ?ту 3 {шартты тексеру}
- жазу “n!= ”, r {n!= r м?нін шы?ару}
- со?ы {есептеуді ая?тау}
Егер алгоритмде ?айталану саны алдын ала белгілі процессті ?йымдастыру ?ажет болса, онда параметрлі цикл ?олданылады. Ондай алгоритмде цикл параметріні? бастап?ы м?ні, со??ы м?ні ж?не ?адамы алдын ала ай?ын болады.
. Шамалармен ж?мыс жасау алгоритмдері
Шама — ол, ?зіні? аты, типі ж?не бар жеке информациялы? объект.
Я?ни, шамалар?а ал?аш?ы берілімдер (ал?аш?ы информациялар) ж?не н?тиже берілімдер (??дегеннен кейінгі информация) жатады. Б?л жа?дайда информацияны? хабары шаманы? есімі ретінде, ал информацияны? мазм?ны шаманы? м?ні ретінде ?арастырылады.
Шамалар, ?здеріні? есімдеріне м?ндер беру т?сіліне байланысты т?ра?ты шама ж?не айнымалы шама болып екіге б?лінеді.
Т?ра?ты шама (константа) алгоритмні? орындалу барысында ?з м?нін ?згертпейді. Т?ра?ты шама ?зіні? меншікті м?німен (мысалы 10, 3.5 сандары) немесе символикалы? атымен (p саны) белгіленеді.
Демек, т?ра?ты шама?а атау берген кезде оны? м?ні бірге аны?талады. М?німен бірге оны? типі де белгілі болады. Мысалы, 1, 3 ж?не 5 цифрларынан ??рыл?ан 135 тізбегін т?ра?ты шаманы? атауы деп ?арастырса?, онда б?л шаманы? м?ні "бір ж?з отыз бес" деген б?тін сан болады. Ал 3.5 тізбегі т?ра?ты шаманы? атауы, типі на?ты сан бол?аны.
Осылардан мынадай т?жырым шы?ады:
Т?ра?ты шаманы? есімі, м?ні ж?не типі ?згермейді, оларды? барлы?ы бір мезгілде аны?талады.
Айнымалы шамалар – алгоритмні? орындалу барысында, м?ндері ?згертетін шамалар.
Программалауда айнымалы ?те ма?ызды ??ым, негізгі объектісі болып табылады. Айнымалыны программалауда, информацияны? элементін са?тайтын, айнымалыны? атымен та?баша ілінген ж?шік деп елестетуге болады. Программа орындал?анда осы ж?шікті? м?ні ?згеріп отырады.
Айнымалы – ол, айма?, компьютер жадысыны? ?яшы?ы.
Программада ?олданылатын ?р бір айнымалыны? (?яшы?ты?) аты болу?а тиіс. Информатикада айнымалы шама?а атау беру ?шін идентификатор деген ??ымды пайдаланады.
Идентификатор (атау, біркелкілегіш) - ?ріптен басталатын ж?не ?ріптер мен цифрлардан ??рал?ан ?зынды?ы шектелген тізбекті айтады. Айнымалы шамалар символды? аттармен белгіленеді. (D, X, Y, S, V, NM, K1, т.с.с.).
Мысалдар:
1) D - идентификатор
2) XI - идентификатор
3) K12C - идентификатор
4) 1Y - идентификатор емес, себебі цифрдан басталып т?р.
5) M+N идентификатор емес, себебі ішінде арнаулы та?ба "+" бар.
6) (R - идентификатор емес, себебі арнаулы та?ба "(" –дан басталады.
Шаманы? м?ні ?зіні? типімен сипатталады.
Шаманы? типі – шаманы? ?абылдай алатын м?ндер жиынын ж?не осы шамамен орындау?а болатын ?рекеттер жиынын аны?тайды.
Шаманы? негізгі типтері: б?тін, на?ты, символды?, логикалы?.
?рнек – шамалармен жасалатын ?рекеттер тізбегін аны?тайтын жазба. ?рнекте константалар, айнымалылар, амалдарды? белілері, функциялар жазылады.
Мысалы: C+D; 8 * A-B; N + M- sin(X).
Меншіктеу командасы - алгоритмді орындаушыны? командасы, оны? орындалу н?тижесінде айнымалы жа?а м?н ?абылдайды. Команданы? форматы:
<айнымалыны? аты> := <?рнек>
Меншіктеу командасыны? орындалу т?ртібі: 1) алдымен команданы? о? жа?ында?ы ?рнек есептеледі; 2) одан кейін, шы??ан н?тиже айнымалы?а меншіктеледі.
?детте, айнымалы шаманы? м?ніні? типі ?згермеуі тиіс. Ал олай болма?ан жа?дайда, осы шаманы ??деу кезінде к?п, м?мкін болатын шешуі кате шы?атын, ?иынды?тар пайда болады. Сонды?тан, айнымалыны? типіне, ?рнекті? типі с?йкес келуі керек.
Ескерту: «меншіктеу» := белгісі, арнайы «те?» = белгісінен айырмашылы?ы болу ?шін енгізілген. Себебі, айнымалыны? ??ымына байланысты, «меншіктеу» ж?не «те?» дегеніміз бірдей н?рселер емес.
1 мысал. D айнымалысына 18 м?ні меншіктелсін. Мына D:= 2*D – 1 меншіктеу командасы орындал?аннан кейін D айнымалысы ?андай м?н ?абылдайды.
2 мысал. X ж?не Y айнымалыларыны? м?ндерін, ?осымша айнымалыны ?олданып ауыстыратын меншіктеу командалар тізбегін жазу керек.
Шешімі. Есепті шешу ?шін ?осымша Z айнымалысы керек. Ізсалу кестесінде X=3, Y=7 м?ндері ?шін алгоритмні? орындалуы к?рсетілген:
Алгоритмі
X
Y
Z
3
7
-
Z:= X
3
7
3
X:= Y
7
7
3
Y:= Z
7
3
3
3 мысал. X ж?не Y айнымалыларыны? м?ндерін ?осымша айнымалыны ?олданбай ауыстыратын меншіктеу командалар тізбегін жазу керек.
Шешімі. Ізсалу кестесінде есепті шешуге ба?ыттал?ан меншіктеу командалар тізбегі, X=3, Y=7 м?ндері ?шін алгоритмні? орындалуы к?рсетілген:
Алгоритмі
X
Y
3
7
X:= X-Y
-4
7
Y:= X+Y
-4
3
X:= Y-X
7
3