|
2- ma`ruza. Saralash algoritmlari. Kvadratik, logarifmik va chiziqli qiyinchilikdagi saralash algoritmlari
|
| bet | 2/9 | | Sana | 16.02.2024 | | Hajmi | 5,7 Mb. | | #157511 |
Bog'liq 2- ma`ruza(2023)Algoritm ta’riflari
Algoritmning bir nechta ta’rifi mavjud. Ulardan ayrimlarini keltirib oʻtamiz:
– “Algoritm - bu belgilaydigan cheklangan qoidalar toʻplami, muayyan
vazifalar toʻplamini hal qilish boʻyicha amallar ketma-ketligi va beshta muhim
xossaga ega: Diskretlilik (CHeklilik), Tushunarlilik, Aniqlik, Ommaviylik,
Natijaviylik”.
– “Algoritm - bu qat’iy belgilangan qoidalar asosida bajariladigan har qanday hisoblash tizimidir, bu ma’lum bir qator bosqichlardan soʻng, aniq qoʻyilgan masalani hal qilishga olib keladi" (A. Kolmogorov).
– “Algoritm - bu har xil boshlangʻich ma’lumotlardan kerakli natijaga oʻtadigan hisoblash jarayonini belgilaydigan aniq ketma-ketlik" (A. Markov).
Algoritm nazariyalari
tadqiqot
yoʻnalishlari
1960-1970 yillarda algoritm nazariyasida quyidagi shakllandi:
- Algoritmlarning klassik nazariyasi (rasmiy tillar nuqtai nazaridan masalalarni shakllantirish, yechuvchanlik muammosi tushunchasi, murakkablik sinflarini kiritish);
- Algoritmlarni asimptotik tahlil qilish nazariyasi (algoritmning murakkabligi tushunchasi, algoritmlarni baholash kriteriyalari, asimptotik baholarni olish usullari, xususan, rekursiv algoritmlar uchun, murakkablikni yoki bajarilish vaqtini asimptotik tahlil qilish);
- Hisoblash algoritmlarini amaliy tahlil qilish nazariyasi (funksiyalarning intervalli tahlili, algoritmlar sifatining amaliy mezonlari, ratsional algoritmlarni tanlash metodikasi).
Algoritmlar nazariyasida hal qilingan maqsad va vazifalar:
- "algoritm" tushunchasini formallashtirish (rasmiylashtirish) va formal (rasmiy) algoritmik tizimlarni oʻrganish;
- muammolarning algoritmik yechimini rasmiy tasdiqlash;
- vazifalarni tasniflash, murakkablik sinflarini aniqlash va tadqiq qilish;
- algoritmlarning murakkabligini asimptotik tahlil qilish;
- rekursiv algoritmlarni oʻrganish va tahlil qilish;
- algoritmlar sifatini qiyosiy baholash mezonlarini ishlab chiqish.
|
| |
