Algoritm tushunchasi Аlgоritm хоssаlаri Аlgоritmlаrni tаsvirlаsh usullаri

1-MAVZU: ALGORITM TUSHUNCHASI VA ULARDAN FOYDALANISH


Reja

1. 
   Algoritm tushunchasi
   
2. 
   Аlgоritm хоssаlаri
   
3. 
   Аlgоritmlаrni tаsvirlаsh usullаri
   

Algoritm bu aniq hisoblashlarni bajaruvchi protsedura bo’lib unga kirish qismida kattalik yoki kattaliklar berilib chiqishda natijaviy kattalik yoki kattaliklar olinadi. Demak algoritm hisoblovchi qadamlardan tashkil topgan bo’lib dastlabki qiymatlarga ko’ra natijaviy kattaliklar qiymatini beradi. Bu holatni sxematik tarzda quyidagicha tasvirlash mumkin.

Algoritmni qo’yilgan hisoblash masalani (computational problem) aniq bajaruvchi uskuna sifatida ham qaralishi mumkin. Algoritmlarda keltirilgan protseduralar yordamida kattaliklar bilan amallar bajarilib natijalar olinadi. Masalan, biror sonlar ketma-ketligini orta boorish tartibida saralash. Saralash masalasi (sorting problem) ga misol keltiramiz:

Kirish:n-ta sondan iborat sonlar ketma-ketligi (a₁,a₂,…,a_N).
Chiqish: n-ta sondan iborat sonlar ketma-ketligi (b₁≤b₂…≤b_N).
Misol, (31, 41, 59, 26, 41,56) kiruvchi ketma=ketlik bo’lsa, chiquvchi ketma-ketlik (26, 31, 41, 41, 56, 59) bo’lishi lozim. Bunga o’xshash kiruvchi ketma-ketlik saralash ekzemplyari (instanse) deb yuritiladi. Agar algoritm har qanday kiruvchi qiymatlar uchun aniq va mos chiquvchi qiymatlarni bera olsa u aniq (correct) deb yuritiladi. Algorimlardan amaliyotda foydalanishga ayrim misollarni keltiramiz:

• 
  Odam DNK si tarkibidagi 100 ming gen identifikatsiyasi, DNK-ni tashkil etuvchi 3 milliard asosiy juftlikni saralashva tahlili masalasi;
  
• 
  Internetda ma’lumotlar olish masalasi: kata hajmdagi ma’lumotlarni olish, jo’natish,qidiruv va optimal marshrut tanlash;
  
• 
  Electron kommertsiya masalalarida( kredit karta nomerlari , parollar, bank xisob-kitob raqamlari himoyasi, raqamli imzo va b);
  

Algoritmlarni ishlab chiqishda masalani yechimi uchun zarur bo’lgan vaqt va xotira hajmi muhim ko’rsatgichlar hisoblanib algoritmlarni yaratishda ularni samarali foydalanishni hisobga olish zarur. Aynan bir masalani yechish uchun turli algoritmlar tuzilishi mumkin. Ular bir-biridan samardorlik darajasi bilan farqlanadilar. Bu farq turli texnik va dasturiy ta’minotlarda har xil bo’lishi mumkin.
Misol uchun ikkita saralash algorutmlari farqini ko’rib chiqamiz:

Saralash algoritmi	Sarflanadigan vaqt	izoh
Joylashtirish usuli	C1n^2 bu N^2-ga propor- tsional	C1-n ga bog’liq bo’lmagan doimiylik n-saralanadigan elementlar soni
Qo’shish usuli	C2nlgn	lgn=log2n, C2-n ga bog’liq bo’lmagan doimiylik

Qo’shish usuli joylashtirish usulidan samaraliroq ekanligini quyida keltirilgan jadval ma’lumotlarini tahlili orqali keltiramiz.

komputerlar	Saralanadigan sonlar soni	Saralovchi algoritm	Talab qilinadigan vaqt
A(tez ishlovchi 1sekundda 10mlrd amal bajaradi)	10 mlnta(taqriban80 mb)	Joylashtirish usuli (tajribali dasturchi tomonidan yaratilgan algoritm saralash uchun 2n^2amal bajariladi)