Algoritm tushunchasi, xossalari va tasvirlash usullari. Chiziqli, tarmoqlanuvchi va takrorlanuvchi algoritmlar 1-MARUZA. - презентация

1 Algoritm tushunchasi, xossalari va tasvirlash usullari. Chiziqli, tarmoqlanuvchi va takrorlanuvchi algoritmlar 1-MARUZA

2 Algoritm bu qoyilgan masalani yechish uchun zarur bolgan amallar ketma-ketligidir. Algoritm sozi va tushunchasi IX asrda yashab ijod etgan buyuk alloma Muhammad al- Xorazmiy nomi bilan uzviy bogliq. Algoritmning asosiy xossalari 1.Diskretlilik (Cheklilik) 2.Tushunarlilik 3.Aniqlik. 4.Ommaviylik. 5.Natijaviylik. Algoritm

3 Diskretlilik (Cheklilik) - algoritm doimo chekli qadamlardan iborat bolishi, qadamlar esa oddiy korsatmalar ketma-ketligi bilan ifodalanishi lozim. Tushunarlilik - Ijrochiga tavsiya etilayotgan korsatmalar, uning uchun tushunarli mazmunda bolishi shart. Aniqlik - Ijrochiga berilayotgan korsatmalar aniq mazmunda bolishi, korsatmalar ketma-ketligi aniq tartib bilan korsatilishi lozim. Ommaviylik - har bir algoritm mazmuniga kora bir turdagi masalalarning barchasi uchun ham orinli bolishi, yani masaladagi boshlangich malumotlar qanday bolishidan qatiy nazar algoritm shu xildagi har qanday masalani yechishga yaroqli bolishi kerak.

4 Natijaviylik - har bir algoritm chekli sondagi qadamlardan song albatta natija berishi shart. Chekli qadamdan song qoyilgan masala yechimga ega emasligini aniqlash ham natija hisoblanadi. Algoritmning tasvirlash usullari 1.Algoritmning sozlar orqali ifodalanishi 2.Algoritmning formulalar bilan berilishi 3. Algoritmlarning grafik shaklida tasvirlanishi 4. Algoritmning jadval korinishda berilishi 5.Algoritmning dastur shaklida ifodalanishi

5 Algoritmning grafik shaklida tasvirlanishi

6

7 XX asrning 70-yillarida golland olimi Edsger Deykstra (1930– 2002) har qanday algoritm uning nima maqsadda tuzilganligi va murakkabligidan qati nazar, uchta: ketma-ketlik, tarmoqlanish va takrorlanish algoritmik konstruksiyadan foydalanilgan holda yozilishi mumkinligi haqidagi goyani ilgari surdi va tоliq asoslab berdi. Har qanday algoritm mantiqiy tuzilishi, yani bajarilish tartibiga kora uchta asosiy turga bolinadi: chiziqli, tarmoqlanuvchi va takrorlanuvchi. Chiziqli algoritm deb, barcha korsatmalari hech qanday shartsiz, faqat ketma-ket bajariladigan jarayonlarga aytiladi. Chiziqli tuzilish bir chiziq boylab joylashgan, ketma-ket bajariladigan kоrsatma (buyruq)lar tоplami korinishida boladi va ular algoritmda qanday tartibda yozilgan bolsa, aynan shu tartibda bajariladi CHIZIQLI ALGORITM

8 Sayyoh qishloqdan chiqib, shahar tomon jonadi. U a kilometr piyoda yurganidan keyin avtobusga otirdi va avtobusda t soatda shaharga yetib keldi. Agar avtobus 60 km/soat tezlik bilan harakat qilgan bolsa, a = 5 va t = 0,5 bolganda, qishloq bilan shahar orasidagi S masofani hisoblash algoritmini tuzing.

9 Shunday hisoblash jarayonlari borki, unda qoyilgan ayrim mantiqiy shartlarning bajarilishiga kora jarayonlar bir necha tarmoqqa bolinadi hamda ulardan hech bolmaganda bittasi bajariladi. Bunday jarayonlar bajarilishi uchun tarmoqlanuvchi algoritmlar tuziladi. Agar hisoblash jarayoni qandaydir berilgan shartning bajarilishiga qarab turli tarmoqlar boyicha davom ettirilsa va hisoblash jarayonida har bir tarmoq faqat bir marta bajarilsa, bunday hisoblash jarayonlariga tarmoqlanuvchi algoritmlar deyiladi. Tarmoqlanuvchi struktura, odatda, qandaydir mantiqiy shartni tekshirish blokini oz ichiga oladi. Tekshirish natijasiga kora, tarmoq deb ataluvchi u yoki bu amallar ketma-ketligi bajariladi. Tarmoqlanuvchi tuzilish shart tekshirish natijasiga (ha yoki yoq) qarab ikki yoldan birini tanlash imkoniyatini beradi, yani korsatilgan tarmoqdan faqat bittasining bajarilishini taminlaydi. TARMOQLANUVCHI ALGORITM

10 Berilgan A son 0 (nol)dan katta musbat son bolsa, u holda uning kvadratini hisoblash algoritmini tuzing.

11 Takrorlanuvchi algoritm deb, biron bir shart tekshirilishi yoki qandaydir parametrning har xil qiymatlari asosida algoritmda takrorlanish yuz beradigan jarayonlarga aytiladi. Bunday jarayonlar uchun algoritmlar tuzishda takrorlanuvchi algoritmlardan foydalaniladi. Takrorlanuvchi algoritmlar i=i+1, S=S+i yoki P=P*i korinishidagi korsatmalarning ishtiroki bilan ajralib turadi (* – kopaytirish amali). Bunday korsatmalarning mohiyatini tushunish uchun takrorlanishning bir nechta qadamini korib chiqish lozim. TAKRORLANUVCHI ALGORITM

12 1 dan n gacha bolgan natural sonlar yigindisini hisoblash algoritmini tuzing. TAKRORLANUVCHI ALGORITM

13 E'tiboringiz uchun rahmat!