Algoritmlashga kirish Hisoblashda algoritmlarning roli Algoritmlar

Algoritmlashga kirish

Hisoblashda algoritmlarning roli

Algoritmlar

• Yaxshi tanlangan algoritm Masalalarni hal qilishning qulay vositasi
• Algoritmlar quyidagilar bo'lishi kerak:
• To'g'ri : Har bir kirish uchun tegishli chiqishni ishlab chiqilishi kerak
• Samarali : Imkon qadar tez va iloji boricha kamroq xotiradan foydalanadigan - bu haqda keyinroq batafsilroq

Algoritm
Kiritish
Chiqish

To'g'ri va noto'g'ri algoritmlar

• Agar har bir kirish misoli to'g'ri chiqish bilan tugasa, algoritm to'g'ri bo'ladi. To'g'ri algoritm berilgan hisoblash masalasini hal qiladi.
• Noto'g'ri algoritm ba'zi kiritish misollarida umuman tugamasligi mumkin yoki u kerakli javobdan boshqa javob bilan tugaydi.

Muammolar va algoritmlar

• Biz hisoblash muammosini hal qilishimiz kerak
• “Dollarni kurs bo’yicha so’mdagi qiymatiga o'zgartiring"
• Algoritm uni qanday hal qilishni belgilaydi, masalan:
• 1. Summani dollarda o’qib oling A
• 2. Summa_sum=a*11200
• 3. Summani s’omda chiqaring
• Kompyuter dasturi bu algoritmning kompyuterda bajariladigan tavsifidir

Muammoni hal qilish jarayoni

Muammoning spetsifikatsiyasi
Algoritm
Dastur
Natija (yechim)
Tahlil
Dizayn
Amalga oshirish
Jamlama

Algoritmlardan dasturlargacha

Muammo
C++ dasturi
Algoritm : vazifani (yoki jarayonni) qanday bajarishni tavsiflovchi ko'rsatmalar ketma-ketligi.

Amaliy misollar

• Internet va tarmoqlar

Eng qisqa vaqt ichida katta hajmdagi ma'lumotlarga kirish zarurati.

Ma'lumotlar almashish uchun eng yaxshi marshrutlarni toppish muammolari .

Muayyan ma'lumotlar joylashgan sahifalarni tezda topish uchun bu katta hajmdagi ma'lumotlardagi qidirish algoritmlari .

• Elektron tijorat

 Ma'lumotni (kredit karta raqamlari, parollar, bank ko'chirmalari) maxfiy, xavfsiz va xavfsiz saqlash qobiliyati.

 Algoritmlar shifrlash/deshifrlash usullarini o‘z ichiga oladi.

Qiyin muammolar

• Biz algoritmning samaradorligini uning tezligidan aniqlashimiz mumkin ( natijani olish uchun algoritm qancha vaqt oladi ).
• Ba'zi muammolar noma'lum samarali echimga ega.
• Bu muammolar NP-to'liq muammolar deb ataladi.
• Agar muammo NP-to'liq ekanligini ko'rsata olsak, vaqtimizni yaxshi , lekin eng yaxshi yechimni bermaydigan samarali algoritmni ishlab chiqishga sarflashimiz mumkin.

Oddiy algoritm

• INPUT: n ta sonlar ketma-ketligi
• T - n ta elementdan iborat massiv
• T[1], T[2], …, T[n]
• OUTPUT: ular orasida eng kichik raqam
• Bu algoritmning ishlashi n qadamda bajariladigan funksiyadir

min = T[1]
for i = 2 to n do
{
if T[i] < min
min = T[i]
}
Output min

Eng katta umumiy boʻluvchi

• Tarixda “ixtiro qilingan” birinchi algoritm Evklidning ikkita natural sonning eng katta umumiy boʻluvchisini (GCD(EKUB)) topish algoritmi edi.
• Ta'rif: Ikki natural sonning GCD x, y ikkalasini (qoldiqsiz) bo'luvchi eng katta j butun sondir. ya'ni mod(j, x)=0, mod(j, y)=0 va j bu xususiyatga ega eng katta butun sondir.
• GCD muammosi:
• Kirish: natural sonlar x, y
• Chiqish: GCD(x,y) – ularning GCD

Evklidning GCD algoritmi

GCD(x, y)

{

if (y != 0)

{

t = mod(x, y)

x = y

y = t

}

Print(x)

}

Evklidning GCD algoritmi – namunali ishga tushirish

if (y!=0) {
int temp = x%y;
x = y;
y = temp;
}
Misol: GCD hisoblash (72 120)
temp x y
0 qadamdan keyin -- 72 120
1 qadamdan keyin 72 120 72
2 qadamdan keyin 48 72 48
3 qadamdan keyin 24 48 24
4 qadamdan keyin 0 24 0
Natija: 24

Algoritm samaradorligi

• Ikkita saralash algoritmini ko'rib chiqamiz
• Kiritish tartibi
• n ta elementni saralash uchun c1 n 2 qadamni bajaradi
• Bu erda c1 n ga bog'liq bo'lmagan doimiydir
• n 2 ga taxminan proportsional vaqt talab etiladi
• Birlashtirish tartibi
• n ta elementni saralash uchun c2 n lg(n ) ni oladi
• bu erda c2 ham n ga bog'liq bo'lmagan doimiydir
• lg(n) log 2 (n) ni bildiradi
• n lg(n ) ga taxminan proportsional vaqt talab etadi
• Faraz qilaylik
• Kompyuter A soniyada bir milliard (10 9 ) buyruqni bajaradi
• B kompyuteri soniyada o'n million (10 7 ) buyruqni bajaradi
• Shunday qilib , A kompyuteri B kompyuteridan 100 marta tezroq