✅ Algorithm Correctness haqida

❗️ Disclaimer: Mazkur maqola Steven Skienaning "Algorithm Design Manual" kitobidan UZ-EN aralash tilda konspekt sifatida yozilgandir. Iltimos, xato-kamchilik ko'rsangiz kommentda feedback qoldiring.

👉 Biz hozirgacha aynan algoritm haqida ko'p fikr yuritdik, hayotiy misollar orqali tasavvurga ega bo'ldik. Biroq bu approach qaysidir ma'noda siz-u bizda "Algoritm universal narsa ekan. Hamma narsa algoritm ekan" degan sodda tushunchani shakllantirgan bo'lsa ajab emas. Lekin aslida rostdan ham shundaymi?
Algoritmlar ishlashiga qarab yaxshi va yomon turlarga bo'linadi. Yaxshi algoritmning 3 xil asosiy xususiyati mavjud:

• correct
• efficient
• easy to implement

Kitobning dastlabki chapterida correctness haqida so'z boradi va biz ham maqola davomida mazkur jihatga e'tibor qaratamiz.

📏 7-sinfda geometriya darslaridan "teorema" va "aksioma" atamalariga duch kelgansiz-a? Algoritmlarda ham xuddi shu kabi struktura ishlar ekan:
Algoritm - qabul qilishi mumkin bo'lgan har qanday input uchun har doim to'g'ri natija chiqaradigan steplar ketma-ketligi algoritmdir.
Heuristic - kamida 1 ta shunday input instance topiladiki *algoritm noto'g'ri output chiqaradi va bu heuristic deyiladi.

Keling bir misol orqali tushunib olsak.
❓ Aytaylik bir aktyorga rasmdagi kabi kinolardan takliflar kelgan. Har bir kino qancha davom etishidan qat'iy nazar bir xil pul to'laydi. Aktyor qanday algoritm orqali kinolarni tanlasa eng ko'p pul ishlay oladi?
✅ Hah, osonku degandirsiz. Ehtimol har safar eng birinchi boshlanadigan kinolarni tanlab borish kerakdir? Ha siz haqsiz va.. nohaqsiz! Agar holat quyidagi rasm kabi bo'lsachi?

E'tibor bering, agar birinchi boshlanadiganni tanlasak, boshqa hech bir kinoni tanlay olmaymiz!
Yaxshi, demak ko'proq pul topish uchun kino qisqaroq bo'lishi kerak. Demak eng qisqa kinolarni tanlab ketaversak bo'lmaydimi? Ok, siz aytgandek bo'laqolsin:

Bu holatda esa eng qisqasini tanlash eng optimal yechim bo'lmaydi. Demak bu ikki ehtimoliy yechimlar algoritm bo'la olmaydi, ular heuristicdir. Yechim esa greedy algorithm usulida bo'ladi. Ya'ni, eng tez tugaydigan kinolarni tanlab boramiz. Mazkur holatda kinolar qay tartibda joylashishidan qat'iy nazar baribir biz eng optimal yechimga ega bo'lamiz. Buni esa algoritm deb tushunish mumkin.

Mantiqan to'g'ri algoritmlar osongina xato bo'lishi mumkin.

Xo'sh, demak biz algoritm degan hamma ketma-ketlik ham to'g'ri bo'lavermas ekan. Mayli, lekin uni to'g'ri ekanini qanday aniqlash mumkin? Buning uchun bizga maxsus tool kerak va bu isbot deb ataladi.
Proper matematik isbot 3 ta asosiy qismdan tashkil topadi:

• isbot qilinishi kerak bo'lgan narsa haqida aniq tavsif
• isbotning bir qismi sifatida foydalanish mumkin bo'lgan, to'g'ri deb olinadigan farazlar to'plami
• mazkur farazlardan isbot tomon olib boradigan mulohazalar zanjiri

Osonroq tushunadigan bo'lsak, bu xuddi biror matematik masalani yechayotganimizda masala nimani so'rayotganini aniqlab, foydalanish mumkin bo'lgan formulalarni topib, zanjir tarzida formuladan yechimga qarab yurishga o'xshaydi.

Expressing Algorithms

Algoritm haqida uning har bir qadami haqida aniq tavsif bo'lmasa fikr qilish imkonsizdir. Demak, biz albatta qandaydir usulda algoritmni ta'riflab berishimiz shart. Buni ham 3 xil usul yoxud tilda amalga oshirish mumkin:

- English
- Pseudocode
- Programming language

Har birining o'z ustunlik va kamchiliklari bor: English ko'proq natural, lekin aniqligi past. Java, C++ kabi dasturlash tillari aniq, lekin tushunish qiyin. Pseudocode esa oltin o'rtalikda - uni yozish ham o'qish ham tushunish ham oson, hamda hech qanday syntax errorlar mavjud emas. Ammo pseudocode yozishda ham eng muhim narsa aniqlik ekanini unutmaslik shart, zero ko'pgina xatoliklar psevdokodni chiroyli qilaman deb aniqlikni kamayishi va ideaning buzilishi ortidan hosil bo'ladi.

Har qanday algoritmning yuragi aniq g'oyadan iborat.

Algoritmning to'g'riligini ko'rsatish uchun bizga uning ta'rifidan tashqari yechilayotgan muammoning ham aniq tavsifi kerak bo'ladi. Bular:

• barcha ruxsat etilgan input instancelar to'plami
• barcha talab etilgan outputlar to'plami

Shu ikki narsa qanchalik noaniq bo'lsa, muammo ham shunchalik well-specified holatidan uzoqlashib general bo'lib boradi. Bu esa o'z navbatida muammoga yechim topishning qiyinlashishi va hatto imkonsiz qilishi mumkin.

Generalized problem uchun hech qanday efficient algoritm mavjud emas.

Demak, hatto muammo umumiy bo'lsa ham uning miqyosini qisqartirgan holda yechim topish algoritm dizaynning eng asosiy texnikalaridan biridir.

Demonstrating Incorrectness

🖋 Yana matematikaga qaytamiz. Biror ayniyatni xato ekanini isbotlash uchun qanday harakat qilardik, eslaysizmi? Bitta bo'lsa ham holat topishga harakat qilardikki ayniyat xato bo'lsin, shundaymi?
Algoritm noto'g'ri ekanini isbotlashning ham usuli shunday: xato natija beradigan instance, ya'ni counter-example topishdir. Yaxshi counter-example quyidagi xususiyatlarga ega bo'ladi:
- Verifiability: 1) shu example kiritilganda algoritm chiqaradigan natijani hisoblash; 2) algoritm xato ekanini isbotlash uchun bundan yaxshiroq natija borligini ko'rsatish.
- Simplicity: algoritm nima uchun xato ekanini aniq va oddiy holda ko'rsata olish.

Shu o'rinda kitobda counter-example topish uchun bir necha maxsus texnika va maslahatlar keltirilgan, biroq ularga to'xtalmay oldinga o'tamiz.

Induction and Recursion

Ba'zida algoritm xato ekanini counter-example usuli bilan ham ko'rsata olmaymiz. Lekin bu ham algoritm to'g'ri ekanini anglatmas ekan. Bizga baribir isbot zarur va odatda bu matematik induksiya metodi orqali amalga oshiriladi.

Rekursiya aslida matematik induksiyadir.

Ha adashmadingiz, aynan shunday. Bir o'ylab ko'ring-a, har ikkisi uchun quyidagicha umumiyliklar mavjud:

- base case (like 1 or 2)
- Divide and Conquer metodi: muammoni sub-muammolarga ajratish
- Progressive approach

Agar siz rekursiya va matematik induksiya haqida yaxshi bilsangiz, menimcha ma'noni tushundingiz.

Tez orada davomini yozaman...

---

🏁 Xulosa qiladigan bo'lsak, bizga algoritm tuyulgan hamma ketma-ketlik ham aslida unday bo'lmasligi mumkin ekan. Algoritm to'g'riligini isbotlash Algoritm dizaynning eng muhim fundamental bilimlaridan ekanligi tushunildi. E'tiboringiz uchun rahmat!