Алгоритмы и их сложности

Алгоритмларни лойихалаш ва тахлил қилиш фанига кириш

Абдуқодиров

Абдувохид

Гапирович

Курс мазмуни

• Алгоритмлар назариясига кириш
• Хисоблаш назарияси асослари
• Алгоритмлар мураккаблигини тахлил қилиш асослари
• Алгоритмларни қуриш методлари
• Ахборотни қайта ишлаш алгоритмлари

Алгоритм тушинчасини идрок қилиш :

• Алгоритм — инструкциялар аниқ бирлашмаси бўлиб, чекли вақтда масала ечими натижасинин топадиган ижрочи учун ёзилган харакат тартибидан иборат.
• Алгоритм — ижрочини қўйилган масалани ечишга йўналтирувчи чекли қадамлардан иборат, тушинарли ва аниқ йўриқномадан иборат.
• Алгоритм — чекли қоидалар тўпламидан иборат бўлиб, конкрет масалалар тўпламини ечимини аниқловчи операциялар кетма-кетлигидан иборат ва бешта хоссага эга: якунланганлик, аниқлик, кириш, чиқиш, самарадорлик.

(Д. Кнут)

• Алгоритм — бу аниқ йўриқнома бўлиб, хисоблаш жараёнини аниқлайди, ўзгарувчи бошлангич маълумотлардан ахтарилаётган натажавий маълумотга йўналтирилган бўлади. (А. Марков)

Алгоритм асосий хоссалари

• Дискретлик
• Детерминланганлик (аниклик)
• Тушинарлилик
• Якунланганлик (натижавийлик, тугалланганлик)
• Оммавийлик (универсаллик)
• Натижа бир қийматлилиги

Дискретлик. Алгоритм масала ечими жараёнини ифодалаб, чекли элементар қадамлардан ташкил топиши керак. Хар бир алгоритм қадами чекли вақт интервалида бажарилади, дастлабки маълумотларни натижага ўтказиш дискрет вақтда содир бўлади.
Детерминланганлик(аниқлик). Хар бир вақт моментида алгоритм навбатдаги иши қадами тизимнинг холати билан бир қийматли аниқланади, яъни хар бир қадамдан сўнг навбатда бажариладиган иш қадами кўрсатилади ёки алгоритм иши қачон тугатилиши аниқланган бўлади.
Тушинарлик. Алгоритм таркиби фақат ижрочи тушинадиган командалардан ташкил топиши талаб этилади, ёки бошқача ижрочи командалари тизимидан ташкил топган бўлиши зарур.
Натижавийлик(якунланганлик). Коррект киритилган дастлабки маълумотлар учун алгоритм чекли қадамлардан сўнг ишини тугатиши ва натижани чиқариши зарур.
Оммавийлик(универсаллик). Алгоритм умумий холда тузилиб фақат дастлабки маълумотлари билан фарқ қилувчи қандайдир масалалар синфига қўлланилиши мумкин
Натижани бир қийматлилиги. Алгоритм қандай шаклда ифодаланишидан қаттъий назар бир хил бошлангич маълумотлар учун доимо бир хил натижага олиб келиши керак
Асосий масалалар

• «алгоритм» тушинчасини формализацияси ва формал алгоритмик тизимлар тадқиқи;
• қатор масалаларни алгоритмик ечиб бўлмаслигининг формал исботи;
• масалалар классификацияси, мураккаблик синфларини аниқлаш ва тадқиқ қилиш;
• Алгоритмлар мураккаблик даражасини асимптотик анализ қилиш;
• рекурсив алгоритмларни тадқиқ ва тахлил қилиш;
• алгоритмларни қиёсий тахлил қилиш учун мураккаб-лик даражасини кўрсатувчи функцияларни олиш;
• алгоритмлар сифатини қиёсий бахолаш меёрларини ишлаб чиқиш.

• Маълумотлар тушинчаси
• Хотира
• Элементар қадам
• Детерминланганлик
• Натижавийлик

«Алгоритм» тушинчасини аниқловчи схема:

• Алгоритм детерминлашган қурилма - абстракт машиналар. Тьюринга ва Пост машиналари.
• Алгоритм қандайдир сонли функцияни хисоблаш жараёни сифатида. Черч рекурсив функциялари .
• Алгоритм қандайдир алфавитда алмаштиришлар занжири сифатида.(Сўзлар устида комбинаторик амаллар). Марков нормал алгоритмлари (НАМ).

Алгоритмик модел асосий типлари
С П А С И Б О З А
В Н И М А Н И Я !
e-mail [e-mail]
mobile [phone]
Люди могут вести себя по-разному в одинаковых ситуациях, и этим они принципиально отличаются от машин.