|
Algoritmning asosiy xossalari.Algoritmning 5-ta asosiy xossasi bor:
Berilganlarni tasvirlash bosqichlari.
Berilganlar tuzilmasini klassifikatsiya qilish.
Berilganlarni abstrakt toifalari.
Yarimstatik berilganlar tuzilmalari.
Stek tuzilmasi va uni dasturda amalga oshirish, ustida amal bajarish
Stek Stek deb shunday strukturaga aytiladiki, stekka kelib tushgan oxirgi elementga birinchi bo’lib xizmat ko’rsatiladi va stekdan chiqariladi. Mazkur ko’rinishdagi xizmat ko’rsatishni LIFO (Last input-First output, ya’ni oxirgi kelgan – birinchi ketadi) nomlash qabul qilingan. Stek bir tomondan ochiq bo’ladi Masalan, Korobkaga taxlangan disklar, tagma-tag qo'yilgan tarelkalar va hokazo. Steklar asosan arifmetik ifodali masalalarni tahlil qilishda, perebor (ajratish) li masalalarda hamda graflardagi algoritmlarda ishlatiladi. Stek (asosiy funksiyalar) void pop(struct stack*p) – stek oxiridagi elementni o’chirish. void push(struct stack*p, void* val) –stek oxiriga element qo’shish. Bu yerda val kiritilayotgan ma’lumotga ko’rsatkich. char* top(struct stack p) – stek oxiridagi tugun axborot qismiga ko’rsatkich qaytarish. int empty(struct stack p) – stek bo’shligini tekshirish. int size (struct stack p) – stek elementlari soni.
Navbat tuzilmasi va dasturda ifodalanishi, ustida amal bajarilishi
Biz navbat bilan ko’p joylarda duch kelamiz: magazinda, o’qishda, ishda va hokazo. Odatda biz unga e’tibor bermaymiz. Dasturiy tizimlarda ham bu navbat tushunchasi ishlatiladi. Masalan, hujjatni chop etish uchun printerga jo’natsak, u navbatga turadi. Navbat bizga nima uchun kerak! ! Alabatta navbat 1-o’rinda tartib o’rnatish uchun zarur. Navbat qanday ishlaydi! Navbat Biz hammamiz magazinda navbatga turganmiz. Navbatni har xil turlari mavjud. Masalan, prioritet bo’yicha navbat. Hayotdan misol: veteranlar va nogironlar navbatsiz o’tkaziladi (ularni prioriteti yuqori). Klassik navbatni ko’rib chiqamiz: birinchi kelgan birinchi ketadi (FIFO – first input, first output) Navbat har ikkala tomondan ochiq bo’ladi.
Deklar. Ustida amal bajarish.
Dinamik berilganlar tuzilmasi.
Ko'pincha muammoni kichik miqdordagi kichik muammolarga ajratish mumkin emas, ularning echimlari kombinatsiyasi asl muammoga echim topishga imkon beradi. Bunday hollarda biz topshiriqni kerakli miqdordagi kichik topshiriqlarga ajratishga urinib ko'rishimiz mumkin, keyin har bir kichik topshiriqni hatto kichikroq vazifalarga ajratamiz va hokazo. Agar butun algoritm aynan shunday harakatlar ketma-ketligiga qisqartirilgan bo'lsa, biz bajarilish vaqti eksponentli algoritm bilan yakun topgan bo'lar edik.
Chiziqli bir bog’lamli ro’yhatlar va ular ustida amal bajarish algotirmlari.
11. Chiziqsiz malumotlar tuzilmasi haqida tushuncha va klassifikatsiyasi.
12. Chiziqsiz ro’yhatlarni mantiqiy tasvirlash
Rekursiya xaqida tushuncha.
Rekursiv algoritmlar muammoning yechimini xuddi shu muammoning kichik kichik muammolariga echim topish orqali topish mumkin degan fikrga asoslanadi. Rekursiv algoritmda funktsiya o'zi oldingi versiyasi nuqtai nazaridan belgilanadi. Shuni ta'kidlash kerakki, bu o'z-o'zidan murojaat qilish abadiy murojaat etmaslik uchun tugatish shartiga ega bo'lishi kerak. To'xtatish holati o'ziga murojaat qilishdan oldin tekshiriladi. Rekursiv algoritmning dastlabki bosqichi muammoning rekursiv ta'rifining asosiy bandiga bog'liq. Dastlabki bosqichdan keyingi bosqichlar muammoning induktiv bandlari bilan bog'liq. Rekursiv algoritmlar ko'p holatlarda sodda echimni ta'minlaydi va xuddi shu muammo uchun iterativ algoritmga qaraganda tabiiy fikrlash usuliga yaqinroq bo'ladi. Ammo umuman olganda, rekursiv algoritmlar ko'proq xotirani talab qiladi va ular hisoblash uchun qimmatga tushadi.
Funksiya murojaatlari va Rekursiya Joriyi
Rekusiv murojaat anatomiyasi
Dumli Rekursiya
Dumsiz Rekursiya.
Daraxtlar haqida tushucha. Daraxtlar klassifikatsiyasi va ularni mantiqiy tasvirlash.
Binar daraxtlar.
Ko’p o’lchamli daraxtni binar ko’rinishga keltirish.
Daraxtlar ustidagi bajariladigan amallar.
MERGE va SPLIT amallari
23. Graflar nazariyasining asosiy tushunchalari
24. Graflarni ifodalash usullari
25. Graflarda ko'rik o'tkazish.
26. Graflarda eng qisqa yo’lni aniqlash haqida.
Graflarda eng qisqa yo’lni aniqlash algoritmlar tahlili.
28. Floyd – Uorshell algoritmi.
29. Ford – Belmann algoritmi.
30. Deykstra algoritmi.
Yo’naltirilmagan graflar.
Yo’nalishi aniqlanmagan daraxtlarni ko’ruvdan o’tkazish algoritmi.
Minimal narxli daraxtlar skeleti.
Saralash tushunchasi, uning turlari.
Do'stlaringiz bilan baham: |
