Алгоритмнің негізгі түсінігі,алгоритмнің қасиеттері.

2.1-тақырып. Алгоритмнің негізгі түсінігі,алгоритмнің қасиеттері.

Жоспары:

  1. Алгоритм түсінігі және негізгі ұғымдар.
  2. Алгоритмнің қасиеттері.
  3. Программалау тілі.

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

орынды сандар мен арифметикалық амалдарды орындалу ережесін ұсынған. Бұл ережелер қосындыны мен көбейтіндіні табуға арналған амалдарды орындауға қажетті тізбектен құрылған. Сол ереже осы күнге дейін қолданылып келеді.

Әл — Хорезми көп орынды сандардың бәріне ортақ және барлық сандарға жарамды ереже ұсынған. Әл-Хореизмидің ұсынған тәсілін жақтаушыларды алгоритмдіктер деп, ал «алгоритм» ұғымын бірқатар қасиеттері бар ережелер жүйесі деп атайды.

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

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

  1. Алгоритмнің айқын, дәл өрнектеу қасиеті. Алгоритмде келтірілген барлық іс-әрекеттің мағынасы айқын, нақты анықталған болу керек. Есеп шығаруға керектің бәрі біржақты анықталуды және орындаушыға түсінікті әрі нақты болуы тиіс. Атқарушы алгоритм командаларын орындау кезінде ешқандай ойланбауы тиіс.
  2. Алгоритмнің үзіктілік қасиеті. Алгоритмнің үзік модульдерге бөлінуі, яғни үлкен алгоритмді бірнеше кішкене алгоритмдерге жіктеу мүмкін болуы керек. Бұл қасиет бойынша алгоритм аралық нәтиже беретіндей бірнеше ықшам бөліктерге, ал олар одан да кіші қадамдарға бөлінеді, яғни мәселелерді шешу процесінің тізбегі жеке — жеке әрекеттерге жіктеледі.
  3. Алгоритмнің нәтижелік қасиеті. Кез келген алгоритмнің нәтижесі болуы керек. Әрекеттердің шектеулі санынан кейін белгілі бір уақытта қорытынды нәтиже алуымыз қажет. Әрбір алгоритм белгілі бір бастапқы мәліметтерді пайдаланады және олар нәтиже алуға жеткізеді.

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

5.Алгоритмнің формалды орындалуы. Алгоритмді орындағанда орындаушы оның әр командасының мағынасын түсінуі де, түсінбеуіде мүмкін. Бірақ алгоритмнің әр командасы орындаушының нақты бір әрекетті орындауын талап етеді.

Алгоритмдеу дегеніміз — ол объект процестерін зерттеу жұмыстары қарастырылған есеп шешуінің алгоритмін құрастыру.

Программалау дегеніміз – ол құрастырылған алгоритмді ЭЕМ түсінетін тілге ауыстыру, яғни программалау тілдерінің бірінде программа құрастыру.

Программаны компьютерде өңдеу дегеніміз – ол құрастырылған программаны ЭЕМ–де, оның математикалық қамтамасыздандыруын пайдаланып, керекті жауапты есептеушіге ыңғайлы түрде шығарып алу.

Алгоритм мен программаға байланысты ЭЕМ-нің мынадай жұмыс ерекшеліктері болады:

1) есепті шығару жолы алгоритм түрінде өрнектелуі қажет;

2) алгоритм программаға айналдырылуы тиіс;

3) программа машина жадына енгізіліп, ретімен орындалуы керек.

Сонымен керекті нәтижені алу жолында ақпаратқа қолданылатын әрекеттердің орындалу ретін анықтайтын нұсқау – алгоритм болып есептеледі.

Квадрат теңдеудің түбірін табу ережесі, үшбұрыштың ауданын есептеу жолдары алгоритмдердің мысалдары болып табылады. Сонымен, алгоритм есептерді шығару тәсілі, яғни белгілі бір нәтижеге жету үшін қолданылатын амалдардың реттелген жиыны.

Алгоритмдерді ЭЕМ-де орындау үшін оларды алдын ала жазып алу керек, яғни ол белгілі бір заңдылықпен өрнектелуі тиіс. Жалпы алгоритмді өрнектеу түрлеріне:

1) табиғи тіл арқылы жазу;

2) белгілі бір терминдер – псевдокодтар арқылы жазу;

3) графика жолымен жазу;

4) алгоритмдік тілдермен жазу жолдарын жатқызуға болады.

ЭЕМ-де есеп шығару күрделі процесс болып есептеледі, ол төменгі кезеңдерден тұрады:

  1. Берілген есепті математикалық түрде өрнектеу, яғни есепті мәселе ретінде қоя білу.
  2. Есепті шығарудың ЭЕМ-ге ыңғайлы сандық тәсілдерін анықтау.
  3. Есепті шығару жолын алгоритм түрінде бейнелеу.
  4. Есепті ЭЕМ-де шығару программасын жасау және оның қателерін түзету.
  5. Есепке керекті мәліметтер дайындау.
  6. ЭЕМ-де есепті шығару және шыққан нәтижені іс жүзінде қолдану.

ЭЕМ бір қарапайым не логикалық операцияны ғана орындай алатын етіп құрылғандықтан ақпаратты өңдеу үшін машинаға берілетін командалар (бұйрықтар) берілетін нұсқаулар тізбегінен тұруы тиіс.

Мысалы:

a=10.3, b=5.4 және h=6 мәндерін пайдаланып, ЭЕМ-де трапеция ауданын есептеу керек болсын (a, b – табандары, h – биіктігі).

Мұндағы өңделетін ақпарат үлгісі – трапеция ауданы. Өңдеу алгоритмі: оны есептеу формуласы – B=(a+b)*h/2. Алгоритмдік тілді пайдаланатын символдар: * — көбейту таңбасы, / — бөлу таңбасы, ** — не “ –

дәрежелеу таңбасы, := — меншіктеу белгісі, . – нүкте. Бұл нақты санның бөлшек бөлігін бүтін бөлігінен ажырату үшін пайдаланылады. Осы формула бойынша трапецияның ауданын есептеуге арналған қарапайым нұсқаулар тізбегін мынандай түрде жазуға болады:

  1. 10.3-ті а деп, 5.4-ті b деп, 6-ны h деп белгілеу (a:=10.3; b:=5.4; h:=6);
  2. a-ны b-ға қосып, r1 деп белгілеу (r1:=a+b);
  3. r1-ді h-қа көбейтіп, r2 деп белгілеу (r2:=r1*h);
  4. r2-ні 2-ге бөліп, B деп белгілеу (B:=r2/2).

Осы сияқты жеке қадамдардан тұратын нұсқаулар тізбегі алгоритм деп аталатыны орта оқу орындарының информатика пәнінен белгілі. Жалпы алға қойылған мақсатқа жету үшін немесе берілген есепті шешу бағытында арнайы ережелер бойынша орындаушыға (адамға, не компьютерге) жинақты түрде берілген нұсқаулар тізбегі алгоритм деп аталады.

Құрылған алгоритмде 3 түрлі берілгендер кездеседі:

  1. бастапқы берілгендер (10.3, 5.4, 6)
  2. аралық берілгендер. Жоғары алгоритмдерде олар 2-ші және 3-ші нұсқауларды орындаудан соң шыққан нәтижелер.
  3. ол – 4-ші (қорытынды) нұсқауды орындаудан шыққан мән.

Жалпы, берілгендер — информатикадағынегізгіұғымдардыңбірі. Өңдеуүшіндайындалып, ЭЕМ-геенгізілетін, машинадакодталғантүрдепайдаболғанжәнешығарылатынақпараттардыңбәрідеберілгендердепаталады.

Бақылау сұрақтары:

  1. Алгоритм түсінігі және негізгі ұғымдарын ата.
  2. Алгоритмнің қасиеттеріне мысал келтір.
  3. Программалау тілі деген не?
  4. Жалпы алгоритмді өрнектеу түрлері.

2.2-тақырып.Алгоритмдерді құрастыру әдістері.

Жоспары:

  1. Алгоритмнің жазу әдістері.
  2. Алгоритмнің түрлері.
  3. Сызықтық алгоритмнің жазу әдістері.
  4. Тармақтық алгоритмнің жазу әдістері.
  5. Циклдік алгоритмніңжазу әдістері.

Алгоритмдерді жазу әдістері. Алгоритмдегі жарлықтардың, нұсқаулардың берілу түріне қарай алгоритмді жазу әдістерін ажыратуға болады. Орындаушының өзіне тән біліміне байланысты арнайы таңбалар, сөздер, іс-қимылдар, схемалар арқылы алгоритмдерді жазудың тәсілдерін ұйымдастыруға болады.

Программалау тілінде жазылған программа түрінде.

Орындаушы –адам болатын жағдайда алгоритм көбінесе сөзбен жазылады. Сөзбенжазылғаналгоритмдер, ретпен орналасқан сөйлемдерден (нұсқаулардан) тұрады. Сонымен бірге алгоритмдер арнайы таңбалар, блок-схемалар, формулалар, кесте түрінде, ноталар (сазгерлер үшін) арқылы жаылады.

Программалау тілінде алгоритм блок-схема арқылы өрнектеледі. Олар геометриялық фигуралар арқылы бейнеленеді.

Алгоритмдерді өрнектеудің көп тараған түрі – оны график арқылы бейнелеу. Графикалық жолмен алгоритмдерді жазу үшін мемлекеттік стандарт белгіленген, онда кез келген амал белгілі бір геометриялық фигурамен өрнектеледі. Ол фигуралар немесе блоктар амалдар символы деп те аталады. Жиі қолданылатын амалдар, яғни мәліметтерді ЭЕМ-ге енгізу, формуламен есептеу, шарттардың орындалуын тексеру, нәтижені қағазға басу символдары 2.2.1-суретте көрсетілген. Осы суреттегі көрсетілген блоктардан алгоритм схемалары құрастырылады. Кейде алгоритмдер схемасын оның блок-схемасы деп те атайды.

Іс әрекеттің аты Блоктың пішімі Оның атқаратын жұмысы

Процесс

Таңдау

Модификация

Құжат

Енгізу, шығару

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

Қосалқы

программа

Түсініктеме жоқ иә Математикалық өрнектерді есептеу Есеп шығару жолын таңдау Цикл (қайталау) басы Нәтижені шығару, қағазға басып алу Мәліметтерді енгізу (шығару) Алгоритмдерді бастау, аяқтау Қосалқы программаларға кіру және шығу Схеманы, формулаларды түсіндіру

2.2.1-сурет. Блок-схемалар. шарт

Сонымен алгоритм блоктармен немесе геометриялық көпбұрыштармен өрнектеледі. Әр блоктың ішінде орындалатыніс-әрекеттің

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

2.2.2-сурет. Алгоритмнің схемасы

(2-блок), содан кейін қосу амалын орындап, ақарында у-ті қағазға басып шығарып, жұмысты тоқтататыз. Осы алгоритмнің схемасы 2.2.2-суретте көрсетілген.

Мысал:

Сызықтық теңдеуді шешу алгоритмінің блок-схемасын құрайық.

иә жоқ

иә жоқ

2.2.3-сурет. Сызықтық теңдеуді шешу алгоритмінің блок-схемасы басы a, b енгізу у=a+b у соңы басы a¹0 y:=”шешімі бар” b=0 x:=b/a y:=”x-кез келген сан” y:=”шешімі жоқ” соңы

Есептеу әдістерінің негізгі түрлері: сызықтық

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

Сызықтыққұрылым.Қарапайымалгоритмдікқұрылымоперацияныңсызықтықжүруретіболыптабылады. Мұндайалгоритмдікқұрылымныңпрограммалықжүзегеасуынсызықтықпрограммадепатайық. Сызықтықалгоритмжәнесызықтықпрограммақарапайымесептердішешугеарналған. Ондабірнешемүмкінальтернативтердіңішінентаңдауыжәнеқандайдабіроперациялардыңциклдікқайталануықарастырылмаған.

Сызықтық құрылымды алгоритм немесе қарапайым сызықтық алгоритм іс-әрекеттердің орындалу ретіне қарай тізбектеле орналасқан блоктардан тұрады. Амалдардың бұлай бірінен соң бірі реттеліп орындалу тәртібін табиғи атқарылу дейді.

Мысалы:

Төменде көрсетілген Z функциясының сандық мәнін есептеп шығару алгоритмін жасау керек болсынZ=ax2+b+cos(ax2+b)- (ax2+b).

Бұлфункцияныңмәнінтабуүшіналдыменжақшадатұрған (ax2+b) көпмүшелігін жеке есептеп алу қажет, себебі ол тізбек үш рет есептеліп оған машина уақытты көп кетіреді. Сонымен, қарастырылған алгоритм қарапайым сызықтық алгоритмнің (2.2.3-сурет) мысалы болып табылады.

Мұндағы 2-блок – a, b, x мәндерінпернелерденпрограммағаенгізублогы, 3-блок t-ның, ал 4-блок Z функциясының мәндерін есептейді. 5-блок x айнымалысының және Z функциясының нәтижесін қағазға басып шығарады.

1.3-сурет. Қарапайым сызықтық алгоритм

Есептеу әдістерінің негізгі түрлері: тармақтық басы a, b, x енгізу t=ax2+b x, z соңы z=t+cost-tgt

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

Паскаль тілінде тармақталудың негізгі алгоритмдік құрылымының жүзеге асыратын екі операторы бар. Олар шартты оператор және таңдау операторы.

Шартты оператор «Иә» немесе «Жоқ» деп жауап беруге болатын белгілі бір логикалық шартты тексереді. Егер оның нәтижесі ақиқат, яғни құптарлық болса, онда бір программалық тармақ орындалады. Тексеру нәтижесі жалған болған жағдайда, программаның басқа бір тармағы жүзеге асырылады.

Таңдау операторы (case) бірнеше операторлардың ішінен таңдау жолымен көп тарамды тармақталуды ұйымдастырады. Тармақталу берілген шартты тексеруден басталады, шарт мәндері таңдап алынған типтердің бірі болатын бүтін, символдық, логикалық өрнек түрінде жазылады. Бұл өрнек оператор орындалар кезде белгілі бір мәнге ие болуы тиіс. Сол мән оған байланысты орындалатын оператордың белгісі рөлін атқарады. Егер өрнектің есептелген мәні көрсетілген мәннің біріне сәйкес келсе, сол қатардағы оператор орындалады.

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

y=Öx +x, егер х³0

Öx2+1, егер х >0

жоқ иә

2.2.4-сурет. Тармақтық алгоритмінің блок-схемасы

Мұнда х айнымалысының таңбасына (оң, теріс) байланысты не жоғары, не төменгі формуланы таңдап алып, сол арқылы у функциясының мәнін табамыз. 2-блоктың орындалу барысында х айнымалысына белгілі басы х енгізу х>=0 y=Öx +x y=Öx2+1 x,y соңы

бір мән беріледі де, ол мән енгізу операторлары арқылы программаға енгізілуі тиіс. Бұдан кейін енгізілген мәннің оң немесе теріс екендігі үшінші шартты тексеру блогы арқылы айқындалады. Шарттың «ақиқат» (иә) немесе «жалған» (жоқ) болуына байланысты тек 4- немесе 5-блоктардың бірі ғана орындалып, «таңдау» жүзеге асырылады. 6-блок енгізілген х айнымалысының және у функциясының сандық мәндерін экранға немесе қағазға басып шығарады.

2-мысал.ax2+bx+c=0 квадрат теңдеуін шешу алгоритмін қарастырайық. Мұнда егер дискриминант оң сан болса, онда теңдеудің нақты түбірлерін (х1, х2) табамыз. Ал, егер дискриминант теріс сан болса, онда теңдеудің комплекс түбірлерін х1,2=a±ib бөлек тармақ арқылы есептеп шығарып, a және b сандарын қағазға, не экранға басып алуымыз қажет. Сонымен, алгоритмді құру жолын математикалық түрде төмендегіше жазуға болады:

x1, 2=(-b±Öb2-4ac)/(2a), егер b2-4ac³0,

a=-b/(2a); b=±Ö4ac-b2)/(2a), егер b2-4ac<0.

Бұл алгоритмде негізгі тексерілетін шарт – дискриминанттың таңбасы. Енді осы квадрат теңдеуді шешу алгоритмін схема түрінде өрнектейік (2.2.5-сурет).

2.2.5-сурет. Квадрат теңдеуді шешу алгоритмін схема

Есептеуәдістерініңнегізгітүрлері: циклдік

Алгоритмдік құрылымның ең маңыздысының бірі цикл болып табылады. Цикл операторлардың қайталануын көрсетеді. Мәліметтерді өңдеумен немесе есептеумен байланысты программада циклді қайталанатын іс-әрекеттерді жиі орындауға тура келеді.

Математикада, экономикада көптеген есептерді шығару кезеңінде бір теңдеуді пайдаланып, ондағы айнымалының өзгеруіне байланысты оны бірнеше рет қайталап есептеуге тура келетін сәттер де жиі кездеседі. Осындай қайталап орындалатын есептеу процесінің белгілі бір бөліктерін цикл деп атайды. Осы бірнеше рет қайталанатын бөлігі бар алгоритмдер тобы циклдік алгоритмдерге жатады. Циклдер қайталану санының алдын ала белгілі және белгісіз болуына байланысты екі топқа бөлінеді. Қайталану сандары алдын ала белгілі болып келетін циклдер тобы арифметикалық цикл болып есептеледі, ал орындалу саны белгісіз циклдер – қадамдық цикл болып аталады.

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

Алгоритм схемасын салуды және программаны жазуды жеңілдету үшін цикл алгоритмдері ықшамдалған түрде «модификатор» немесе «цикл басы» блогын пайдалану арқылы жазылады. Онда 2.2.6-суретте көрсетілген 3-ші, 6-шы, 7-блоктардың орнына «цикл басы» блогы орналасады. Ол алтыбұрыш тәрізді геометриялық фигурадан тұрады және оның міндетті түрде екі кіру және шығу сызығы болуға тиіс. Осы блокты пайдалану арқылы жоғарыда келтірілген 2.2.6-суретте көрсетілген түрде кескінделеді. Параметрдің алғашқы мәні оның қадамы dx оң сан болады. Керісінше, параметрдің алғашқы мәні оның соңғы мәнімен артық болса, онда қадам теріс сан болады.

Бақылау сұрақтары:

  1. Алгоритмнің жазу әдістері.
  2. Алгоритмнің түрлері ата.
  3. Сызықтық алгоритмнің жазу әдістеріне мысалы келтір.
  4. Тармақтық алгоритмнің жазу әдістеріне мысалы келтір.
  5. Циклдік алгоритмніңжазу әдістеріне мысалы келтір.