1. Алгоритм тушунчаси ва унинг характерли хусусиятлари. Ечилувчи ва саналувчи тўпламлар

25 – М а ъ р у з а


РЕЖА:


1.Алгоритм тушунчаси ва унинг характерли
хусусиятлари.
2.Ечилувчи ва саналувчи тўпламлар.
3.Алгоритм тушунчасига аниқлик киритиш.


Таянч иборалар:


Алгоритм тушунчаси. Ечувчи процедура. Ечилиш муаммоси. Алгоритмнинг интиутив таърифи. Ал-горитмнинг характерли хусусиятлари. Алгоритм-
нинг дискретлиги. Алгоритмнинг аниқланувчанли-
ги. Алгоритм қадамларининг элементарлиги. Ал-горитмнинг оммавийлиги.  Алгоритмнинг натижа-вийлиги. –Ечилувчи тўплам. Эффектив саналувчи тўплам. Пост теоремаси. Ечилувчи тўплам билан эффектив саналувчи тўпламлар ўртасидаги муноса-батлар. – Диофант тенгламаси. Ферманинг “буюк теорема”си. Ю.Матиясевич ва Г.Чудновскийлар на-тижалари. Уч асосий йўналиш. Эффектив ҳисоб-ланувчи функция.  - аниқланувчи функциялар. Умумрекурсив функция.  А.Чёрч ва С.Клинилар натижалари.  Чёрч тезиси.  К.Гёдел натижалари. Тьюринг тезиси. Тьюринг бўйича ҳисобланувчи функциялар. Тьюринг машиналари. Э.Пост натижалари. Нормал алгоритмлар.


1.Алгоритм тушунчаси ва унинг
характерли хусусиятлари

Математиканинг асосий тушунчаларидан бири алгоритм (алгорифм) тушунчасидир.

«Алгоритм» сўзи IX-асрда ижод этган буюк математик ватандошимиз Абу Абдулло Муҳаммад ибн Мусо ал-Хоразмий номининг лотинча Algorithmi тарзида бузиб ёзилишидан келиб чиққан.
Ҳар бири «ҳа» ёки «йўқ» деган жавоб талаб этувчи айрим саноқли-чексиз математик ёки мантиқий масалалар синфини кўрайлик.
Чекли сон қадамда ушбу синфдаги ҳар қандай саволга биз жавоб бера оладиган жараёнлик (процедура) мавжудми?
Агар шундай процедура мавжуд бўлса, у ҳолда у берилган саволлар синфи учун ечувчи процедура ёки ечувчи алгоритм (алгорифм) деб айтилади. Ечувчи процедурани излаш муаммосига бу синф учун ечилиш муаммоси деб айтилади.
Формал системалар учун ечилиш муаммосини кун тартибига биринчи қўйган олимлардан Шрёдер (1895), Лёвенгейм (1915) ва Гильбертларни (1918) кўрсатиш мумкин.
Масалан, қуйидагилар ечувчи алгоритмларга мисол бўла олади:
1.Сонлар устида арифметик амалларни бажариш қоидалари.
2.Квадрат илдиз чиқариш қоидаси.
3.Энг катта умумий бўлувчини топиш қоидаси (Евклид алгоритми).
4.Квадрат тенгламанинг ечимини топиш қоидаси.
5. -тартибли кўпҳаднинг ҳосиласини топиш қоидаси.
6. Рационал функцияни интеграллаш қоидаси.
Юқорида келтирилган ҳар бир мисолда бир хил типли (турдаги) масалалар синфи билан иш кўришга тўғри келади. Бир хил турдаги масалалар синфи оммавий муаммо деб айтилади. Бундай синфларнинг масалалари бир биридан фақат ифодасидаги параметрлар билан фарқ қилади. Масалан, квадрат тенгламанинг ечимини топиш масаласида , ва параметрлар қатнашади. Уларнинг қийматларини ўзгартириш йўли билан бир синфга мансуб турли хил масалаларга келамиз.
Айтилганларни ҳисобга олиб алгоритмнинг қуйидаги интуитив таърифини бериш мумкин.