Дәрісханалық кешен

№1 дәріс

Тақырыбы: Кіріспе. Алгоритм түсінігі және алгоритмдеу.

Дәріс жоспары:

1. Алгоритмдеу негізі

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

3. Алгоритмдердің берілу түрі

Кілт сөздер: алгоритм,визуалды, интерпретатор,компилятор, ассемблер

Иллюстрациялық материал: слайдттар

“Алгоритм” сөзі 9-ғасырда пайда болды және ол математик Аль-Хорезми атымен байланысты, ол көпшелі сандардағы төрт арифметикалық амалдарының орындалу ережесін құрастырды. Қазіргі кезде алгоритм түсінігі -информатика ғылымының мықты түсініктерінің бірі.Бір жағынан алгоритм математика саласындағы алгоритмдер теориясын үйрететін негізгі пән (Марков[1]), ал екінші жағынан информатикада алгоритмдердің фармальды емес түсінігі бар және алгоритмизация жалпы жағдайда информатика әдісі ретінде қалыптасқан.Алгоритмдердің негізгі объектілері практикалық мамандықтың ғылымы және облыстары болып табылады (Холлюк [3], Ахо [2]).Алгоритмнің практикалық тапсырмаларды орындауға кең көлемде қолданылуы, ол тек ЭЕМ-ны қолдану кезінде ғана информатиканың бұл облысын жеке дисциплина ретінде қарастырады.

Алгоритмді орындаушы. Алгоритмді құрайтын жеке қадамдар операция деп аталады.Яғни әр операцияда бір әрекет орындалады, мысалы, қосу, сонымен қатар өзара байланысқан әрекеттер.Әрбір алгоритмнің ерекшелігі есепті жалпы түрде шешу және әр есепті шешуде нақты мәндермен әрекетті орындау мүмкіндігі (тек адамға ғана емес, сонымен қатар техникалық құралдармен орындау).Жай алгоритмдерді орындаушы адам болып табылады.Күрделі алгоритмдерді шешуді орындаушы ЭЕМ болып табылады және алгоритмді құру бұл есепті шешудің негізгі этапы, ол программалауды жалғастырушы әдіс.Программа есепті шешуді терең бөлшектеп және визуальды етеді.Алгоритмдердің қасиеттері:

1. Дәлдігі -орындаушы бір әрекетті орындап болған соң, ол келесі қандай әрекет орындау керектігін тура білу керек;

2. Дискерттілігі-келесі әдісті орындамай тұрып, алдындағы әдісті толық орындау керек;

3. Жалпылылығы- бір алгоритммен біртипті есептер шешіледі және бірнеше рет;

4. Т үсініктілілігі-алгоритм нақты орындаушы адам үшін құрылады және оған түсінікті болу керек.Бұл оның тексеруін және модификациясын қажатті кезде жеңілдетеді;

5. Нәтижелілігі-алгоритм әр кезде нәтижеге әкелу керек.Әрбір есепті шешу кезінде оны шешудіматематикалық тілде формулалар жүйесіне келтіреді, ал одан соң алгоритм тілінде белгілібір процес түрінде шешеді, онда алдындағы математикалық формулалар және орындалу шарты қолданылады.

Алгоритмнің берілуінің негізгі тәсілдері.

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

Есепті шығаруды жүзеге асыратын алгоритмнің бірнеше әдісі болады:графика көмегімен немесе мәтін түрінде, мәндер таблицасы түрінде.Графикалық әдістің мынадай қасиеттері бар, олар:есепті шешу процесінің түсініктілігі және визуальдығы. Графикалық әдіспен шығарылатын алгоритмдер визуальды алгоритм деген атқа ие болады.Мәтіндік алгоритм компактілі болып табылады және программалаудың реальды немесе абстрактілі тілінде ЭЕМ үшін программа түрінде болуы мүмкін.Таблицалық әдіс алгоритмді түсінікті көрсете алмайды, мысалы кейбір берілгендерді кіруден шығуға түрлендіреді.Таблицалық әдісі алгоритмдерді есептеудің өңделген алгоритмдердің функционерлеуінің дұрыстығын тексеруде қолданылады, белгілі бір кіру берілгендерінің тестік теру, яғни олар алгоритмнің орындалған нәтижесімен “трассировка кестелерінде” фиксирленеді.

Осылайша, алгоритмнің үш тәсілі бірін-бірі толықтыратын деп есептеуге болады. Проектілеу этапында ең тиімді тәсіл графикалық,алгоритмдерді тексеру этапында-таблицалық, ал қолданылу этапында -программа түріндегі текстік жазба.

Визуальды алгоритмдер.

Визуальды алгоритмдерді проектілеу кезінде арнайы графикалық блоктар деп аталатын элементтер қолданылады, олар графикалық блоктар деп аталады (2-сурет)

Алгоритмизация нәтижесі, есептің шешімі болып алгоритмнің блок-схемасы табылады, ол бірнеше графикалық блок тізбегінен тұрады.

Алгоритмнің басталу блогы

Енгізу және шығару блогы

Орындау блогы

Шарт блогы, 2 шығу бағыты бар.

Алгоритмнің аяқталу блогы

Алгоритмдерде басқару компазиция, альтератива және итерация структураларының

қатысуына байланысты:сызықтық, тармақталған және циклдік алгоритмдер болады.

Алгоритмдер мен программалау принциптерінің жұмысы.

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

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

Интерпретатор — берілген программаның әрбір жолын (командасын) жеке-жеке аударып отырып орындайтын транслятор түрі.

Компилятор — бірден барлык программа мәтінін толық аударатып машина тіліндегі бір модуль түріне келтіреді де, сонан соң сол модульді компьютер жадына кайта жазып алып, оны тек тек біздің калауымыз бойынша орындайды.

Ассемблер — тек автокод түрінде, ягни ассемблер тілінде жазылған программаларды ғана машина тіліне аударады.

Қазіргі кездегі кең таралған программалау тілдері: Бейсик, Си, Дельфи, Паскаль т. б. болып табылады. Негізінде компьютердегі программаның орындалу жолы 1.3-суретте берілген сұлбаға сәйкес келеді.

Қазіргі кезде дүние жүзінде үш жүзге жуық алгоритмдік программалау тілі таралған. Олардың әрқайсысы белгілі бір мақсатта қолданылады. Мысалы, Фортран — ғылыми-техникалык (инженерлік) есеп шығаруда, Паскаль — өндірісте, оку-ағарту саласында, Бейсик — алғашқы үйренушілер үшін дербес компьютерде диалогтік режімде жұмыс атқаруға арналған.

АЛГОРИТМДІК ТІЛДҢ ЖАЛПЫ ЕРЕЖЕСІ.

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

Алгоритмнің бірінен кейін бірі орындалатын, белгілі бір нәтиже беретін бірнеше командасының тізбегін серия деп атайды.

алг алгоритмнің атауы (типтері көрсетілген шамалардың атаулары) арг А, В,D, X

нәт Ү, Д1, R2

басы алгоритм Командалары (серия) соны.

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

Айнымалы: = өрнек немесе у:= ах-Ъ

№2 дәріс

Тақырыбы:Алгоритм түсінігін формализациялау.

Дәріс жоспары:

1. Алгоритм түсінігін формализациялау

2. Пост машинасы

Кілт сөздер: тетік, визуалды,процес

Иллюстрациялық материал: слайдттар

Пост пен Тьюрингтің абстракті машиналардың программалар қасиеттер жайлы әртүрлі тұжырымдары дәлелдеуге арналған. Бұл машиналар бір-бірінен тәуелсіз, бір уақытта жылы америка математигі И.Пост және А.Тьюринг ойлап тапқан. Бұл машиналарда қандай да бір мәлімет мәлімет енгізіп программа орындалғаннан соң нәтижесін оқуға болады. Пост машинасы Тьгинг машинасына қарағанда қарапайым. Оның көмегімен ЭЕМ-ға программа құрудың алғашқы қадамдарын үйренуге болады.

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

Команда	Командаға дейін	Командадан кейінгі күй
Тетікті оңға қарай бір ұяшыққа жылжыту nm	__        √  √  √	__       √   √  √
Тетікті солға қарай бір ұяшыққа жылжыту n m	__    √  √    √ √ √	__    √ √    √  √ √
Тетік тұрған ұяшықтағы белгіні өшіреді n C m	__    √  √  √    √	__   √  √    √
Тетіктің бар жоқ екенін тексеру. Егер тетік жоқ болса m1 командасы, ал егер тетік бар болса m2 --m1 командасына өтеді n – --m2	__   √  √       √ √	__    √ √     √
Тоқтау командасы n стоп m	__    √  √  √	__    √  √  √
Тетік тұрған ұяшыққа белгіні қою nMm	__    √  √	__    √  √    √

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

1. Стоп командасымен тоқтау. Бұл тоқтау нәтижелі тоқтау алгоритмнін дұрыстығын көрсетеді.

2. Орындалмайтын командада тоқтау. Бұл тоқтау нәтижесіз тоқтау.

3. Машина тоқтамай жұмыс жасай жүреді. Нәтижесіз жағдай.

2,3 жағдайда алгоритм дұрыс емес деп табылады. Тетіктің алғашқы күйі деп ең шеткі сол жақ клетканың сол жағында орналасқанын айтамыз.

Мысалы, Тетіктің алғашқы күйі берілсін. Бос таспаға 2 белгіні қою керек: 1. тетік тұрған жерге 2. оның оң жағына

__

алғашқы күй 1 М 2

2  3

3 M 4

__ 4cтop 4

√

__

√

√