Дискрет анал

8- мавзу. Алгоритмлар (4 соат)
1-маъруза машғулоти

1. 
   Алгоритм тушунчаси.
   

Математиканинг дастлабки ривожланиш поғаналаридаеқ унда соф механик харктерга эга бўлган маьлум бир схема ёрдамида олиб бориладиган хисоблаш жараёнлари пайдо бўла бошлади.
Бир турдаги бир хил мазмунга эга бўлган кўп масалалар бир хил усул(йўл қоида) ёрдамида ҳисоблана бошлади. Математикадаги бундай жараёнлар алгоритмлар деб атала бошлади.Шу ерда «бир турдаги масалалар “бир хил мазмунга эга бўлган масалалар” деган тушунчаларни бироз ёритиш эхтиёжи туғилади. Ҳар қандай математик масала унинг «шартлари» деб аталувчи миқдорларнинг бирор системаси ва унинг «ечими»(жавоби) деб аталувчи миқдорларнинг икинчи бир системасидан иборат бўлади. Математик масаланинг шартлари одатда берилган бўлиб унинг ечимини топиш талаб этилади. Бу ерда “миқдор” тушунчаси кенг мазмунда тушунилиши керак, сонлар, функциялар, матрицалар, жумлалар, формулалар, геометрик объектлар ва хоказолар миқдор тушунчасига мисол бўла олади.
Алгоритмнинг ишлаши жараёнида қандайдир вақт моментида (бошланғич моментдан бошқа) хосил қилинган миқдорлар системаси орқали бир қийматли аниқланади. Бу алгоритмнинг яна бир хусусияти унинг бир қийматли аниқланувчанлигини (бир қийматлилигини) кўрсатади.
Алгоритм бирор миқдорлар системасига қўлланилганда алгоритмик жараён қуйидаги учта йўлдан бориши мумкин.
1). Алгоритмнинг ишлаши жараёнида бир ҳолат иккинчи ҳолат билан алмашинавермасада бу жараён хеч қачон тугамайди.
2)алгоритмик жараённинг бирор қадамидан сўнг шундай холат юз берадики хосил бўлган обьект (ёки обьектлар системаси) га бевосита қайта ишлаш қонуни (қоидаси) ни қўллаб бўлмайди ва алгоритм хеч қандай натижа бермай ўз ишишни тўхтатади.
3).алгоритмик жараённинг бирор қадамидан сўнг охирги холат юз бериб ишдан тўхтайди.

2. 
   Тъюринг машинаси.
   

Тьюринг машинаси «абстракт» “хисобловчи” машинадир. “Абстракт” сўзи қўштирноқ ичига олинганининг сабаби шундаки Тьюринг машинаси муайян механик қурилма бўлмай балки хаёлий математик машинадир. “Идеаллаштирилган” бу машинанинг тузилиши шунчалик соддаки уни хозирги замон электрон хисоблаш машиналарига таққослаш катта хатога олиб келган бўлар эди. Шунга қарамасдан Тьюбринг машинасининг «хисоблаш» қобилияти шунчалик юқорики у ихтиёрий математик алгоритмни реализация қилиши мумкин. Тьюринг машинаси иккала томонга ихтиерий давом эттириш мумкин бўлган ва тенг катакча (ячейка)ларга бўлинган тасмадан хамда тасма бўйлаб харакат қиладиган коретка (хисобловчи қурилма ) дан иборатдир. Каретка ҳар бир вақт моментида фақат катакча қаршисида туради. Тьюринг машинасининг тасмаси каретка (ичи) дан ўтказилган деб ҳам хисоблаш мумкин.