1.2 Saralash algoritimlari.Saralash algaritimlarini murakkabligini baholash. Saralash algoritmlari – informatikada juda yaxshi o’rganilgan sohalardan biri va u juda keng qamrovli qo’llanilish sohasiga ega. Ularni katta hajmdagi ma’lumotlarni saqlash va qayta ishlash amallari bajariladigan har qanday joyda uchratish mimkin. Ba’zi ma’lumotlarni qayta ishlash masalalari agar ma’lumotlar saralangan bo’lsa oson yechiladi. Bunday masalalar ushbu laboratoriya ishida ko’rib chiqiladi. Kiritiluvchi ma’lumotlarning hajmi katta bo’lganda biror masalaning ekzemplyar(nusxa) asosida bajariluvchi yechimi, algoritmlarning ishlash vaqti analizini solishtirish asimptotik tahlil deb yuritiladi. Asimptotik murakkabligi kamroq bo'lgan algoritm ko'proq samarador (effektiv) hisoblanadi. Asimptotik tahlilda algoritmning murakkabligi – bu algoritmning ma’lumotlari hajmi ortishi bilan algoritmning ishlash vaqtining tezkor ravishta ortishini belgilovchi funksiyadir. Asimptotik tahlilda asosiy uchraydigan o'sishni baholash funksiyalari bular:
(O-katta) – vaqtni o'sishini yuqori asimptotik baholash funksiyasi;
Ω (Omega) – vaqtni o'sishini quyi asimptotik baholash funksiyasi;
Θ (Teta) - vaqtni o'sishini quyi vayuqori asimptotik baholash funksiyasi.
Bunda n – ma'lumotlarning hajmiy kattaligi bo'lsin. U holda f(n) algoritmning o’sish funksiyasini asimptotik jihatdan g(n) funksiya bilan chegaralash mumkin:
f(n) ∈ Ο(g(n))
f yuqoridan g funksiya bilan doimiy ko'paytiruvchi aniqligigacha chegaralangan
f(n) ∈ Ω(g(n))
f quyidan g funksiya bilan doimiy ko'paytiruvchi aniqligigacha chegaralangan
f(n) ∈ Θ(g(n))
f yuqori va quyidan g funksiya bilan chegaralangan
2.1 Berilganlarning soda strukturalari. Stack berilganlar strukturasi.
Berilganlarning sodda strukturalari.Stack berilganlar strukturasi
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)
pop()– stek oxiridagi elementni o’chirish.
push() –stek oxiriga element qo’shish.
top() – stek oxiridagi tugun axborot qismiga ko’rsatkich qaytarish.
empty() – stek bo’shligini tekshirish.
size () – stek elementlari soni.
2.2 Dasturlar murakkabligi tahlili.
Dastur murakkabligi tahlili
Algoritm tahlilini, qo’yilgan masalani ushbu algoritm bilan еchish qancha vaqt talab qilishi darajasi dеb tasavvur qilish mumkin. Har bir qaralayotgan algorimtni N o’lchovli boshlang’ich ma'lumotlar massividagi masalalarning qanchalik tеz еchilishi bilan baholaymiz. Masalan, saralash algoritmi N ta qiymatdan iborat ro’yxatni o’sish tartibida joylashtirish uchun qancha taqqoslash talab qiladi yoki N*N o’lchamli ikkita matritsani ko’paytirishda qancha arifmеtik amallar zarurligini hisoblash7. Bitta masalani turli algoritmlar bilan еchish mumkin. Algoritmlar tahlili bizga algoritmni tanlash uchun qurol bo’ladi. Algoritmlarning effеktivligini tahlili qilishda bizni birinchi navbatda vaqt masalasi qiziqtiradi, ammo xotira muhim rol o’ynaydigan vaziyatda uni ham muhokama qilamiz. Algoritmlaring turli xossalari bitta masalani еchuvchi ikki turdagi algoritmlarning effеktivligini taqqoslash uchun xizmat qiladi. Biz shuning uchun hеch qachon matritsalarni ko’paytirish algoritmi bilan saralash algoritmini emas, balki ikkita turli saralash algoritmlarini bir-biri bilan taqqoslaymiz. Algoritm tahlilining natijasi – bеlgilangan algoritmning kompyutеrdan qancha vaqt yoki takrorlash talab qilishini aniq hisoblovchi formula emas.
3.1 Graflar nazariyasi elementlari.
Graflar nazariyasi elementlari
Graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda L. Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi.Grafning uchlari va qirralari (yoylari) uning elementlari deb ataladi.
3.2 Rekursiv algoritimlar.
Rekursiv algoritmlar
Funksiya o'ziga o'zi to'g'ridan-to'g'ri yoki qandaydir vosita orqali murojaat qilish jarayoniga rekursiya deyiladi va bunday funksiya rekursiv funksiya deb ataladi.Aksariyat tuzilmalar va algoritmlarni rekursiyasiz tasavvur qilib bo'lmaydi. Tree, Graph, Heap, QuickSort, MergeSort, … Bu ro'yhatni juda uzoq davom ettirish mumkin. Ayniqsa, murakkab tuzilmalar bo'lgan Tree va Graphlarda rekursiya har qadamda uchraydi. Dasturchilikni esa ularsiz tasavvur qilib bo'lmaydi, bu esa o'z o'rnida rekursiya qanchalik muhimligini belgilab beradi.Rekursiv yechimda xato qilish ehtimoli yuqori. Avval ham aytganimizdek, rekursiya juda ham chalg'ituvchi. Shu sababli, uni ishlatishda osongina xato qilib qo'yish mumkin. Rekursiv yechimni xatosini topish qiyin. Bunday masalalarda xato qilib qo'yish ehtimoli yuqori bo'lishi bilan birga uni topib to'g'irlash ham qiyin bo'lishi mumkin. Buning asosiy sababi, bunday yechimlarni tasavvur qilib olish (hayolan debug qilish) juda qiyin. Rekursiv algoritmning murakkabligini hisoblash ko'pincha juda murakkab. Hattoki, ba'zan to'g'ri yechimni yozishning o'zi ham kam bo'lib qolishi mumkin. Chunki, uni iterativ yechim bilan solishtirishda uning murakkabligini hisoblash kerak bo'ladi. Rekursiv algoritmlarda bu ko'pincha juda murakkab va yaxshigina matematika talab qiladi.
4.1 Graflar. Grafni to`liq aylanib chiqish algoritimlari.
Graflar nazariyasi elementlari
Graflar nazariyasi haqida umumiy ma’lumotlar. 1736 yilda L. Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg ko‘priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldi.Grafning uchlari va qirralari (yoylari) uning elementlari deb ataladi.
5.2 Saralash masalasi u-n algoritimlar murakkabligimi aniqlash.
Saralash masalasi uchun algoritmlar murakkabligini hisoblash
Masalan, sizning vazifangiz bor: massivdagi 100 ta ismning ro'yxatini saralash... Bu vazifa juda sodda, ammo uni turli yo'llar bilan hal qilish mumkin. Mana bitta echim: Ismlarni alifbo tartibida saralash algoritmi:Internetda "Ruscha shaxsiy ismlar lug'ati" 1966 yilgi nashrni sotib oling yoki yuklab oling.Bizning ro'yxatimizdagi har bir ismni ushbu lug'atda toping.Lug'atning qaysi sahifasida nom borligini qog'ozga yozing.Qog'ozdagi yozuvlardan foydalanib, ismlarni tartib bilan joylashtiring. Ushbu harakatlar ketma-ketligi muammomizni hal qilishga imkon beradimi? Ha, shunday bo'ladi. Ushbu echim bo'ladimi samarali? Zo'rg'a. Bu erda biz algoritmlarning yana bir muhim xususiyati - ularning samaradorlik... Muammoni turli yo'llar bilan hal qilishingiz mumkin. Ammo dasturlashda va kundalik hayotda biz eng samarali usulni tanlaymiz. Dasturlashda algoritmlarning murakkabligini baholash uchun maxsus yozuv yaratildi Katta-O ("katta O"). Big-O algoritmning bajarilish vaqti unga uzatilgan ma'lumotlarga bog'liqligini taxmin qilishga imkon beradi..Big-O notation yordamida algoritmimizning murakkabligi quyidagicha aniqlanadi O (N)...
4.2 Elementar saralash usullari. Tezkor saralash.
Tez saralash(quicksort) algoritmi - Charlz Xoar tomonidan yaratilgan mashxur saralash algoritmidir. Ushbu algoritm n ta elementdan iborat massivni eng uzogʻi bilan O(n2) vaqtda saralaydi. Biroq algoritm bajarilish tezligining matematik kutilmasi O(n log n) ga teng va u boshqa shunday tezlikda bajariluvchi algoritmlardan tezroq ishlaydi. Ishlash printsipi[tahrir | manbasini tahrirlash]
Massivda ixtiyoriy tayanch element tanlaymiz.Keyin undan kichik yoki teng elementlarni uning chap tomoniga, katta elementlarni oʻng tomoniga oʻtkazamiz.1-2-chi qadamlarni tayanch elementning oʻng va chap tomonlaridagi elementlar uchun qoʻllaymiz. Algorimning 2 qadami turlicha boʻlib uning bir nechta realizatsiyalari mavjud. Ayni shu 2 qadamda elementlarni joylashtirish algoritmi tufayli algoritm saralash algoritmlari ichida eng tez ishlaydiganlaridan biridir.
Java realizatsiyasi
import java.util.Comparator; import java.util.Random;
public class Quicksort {
public static final Random RND = new Random();
private void swap(Object[] array, int i, int j) {
Object tmp = array[i]; array[i] = array[j];
array[j] = tmp;
}
private int partition(Object[] array, int begin, int end, Comparator cmp) {
int index = begin + RND.nextInt(end - begin + 1); Object pivot = array[index]; swap(array, index, end);
for (int i = index = begin; i < end; ++ i) {
if (cmp.compare(array[i], pivot) <= 0) {
swap(array, index++, i);
}
}
swap(array, index, end);
return (index);
}
private void qsort(Object[] array, int begin, int end, Comparator cmp) {
if (end > begin) {
int index = partition(array, begin, end, cmp);
qsort(array, begin, index - 1, cmp); qsort(array, index + 1, end, cmp);
}
}
public void sort(Object[] array, Comparator cmp) {
qsort(array, 0, array.length - 1, cmp);
}
}
5.1 Berilganlarning soda strukturalari. Queue(navbat) berilganlar strukturasi.
Navbat - bu FIFO (First In, First Out) tartibida elementlarni saqlaydigan chiziqli ma'lumotlar strukturasi yoki Java-dagi to'plam.
Navbat to'plamining ikkita uchi bor, ya'ni old va orqa. Elementlar orqa tomondan qo'shiladi va old tomondan chiqariladi.
Enqueue-navbatga element qo'shish
Peek-navbatdagi elementni ko'rish
Dequeue-navbatdan element o'chirish
Size-navbatdagi elementlar soni
Navbatni elon qilish:
Queue q=new Queue ();
23.1 Binar izlash algoritimi.
6.2 Elementar berilganlar strukturasi.
Berilganlar strukturasi bu EHMning dasturiy birligi bo’lib,u xotira yacheykasiga yozish, ma’lumotlarni bir xil tipda saqlash usullari to’plamidir. Elementar berilganlar strukturasi. Elementar berilganlar strukturasi shunday berilganlar strukturasiki, ularni EHMning ixtiyoriy bazaviy strukturalari deb atash mumkin. Shulardan massiv va bog’langan ro’yxat bilan tanishamiz.Shuni ta’kidlash lozimki, ularni avtomarniy berilganlar strukturasi deb atash mumkin, chunki, ularni modellashtirishda boshqa elementar berilganlar strukturasidan foydalanilmaydi.
21.1 Chiziqli berilganlar strukturasi.Massivlar
Massivlar.
Massiv- yacheyka xotirasidagi uzluksiz, tartiblangan ketma-ketlik, bir xil tipdagi ma’lumotlarni saqlash uchun mo’ljallangan chiziqli, bir o’lchovli, elementar berilganlar strukturasi hisoblanadi. Massiv elementlariga murojat indeks orqali bo’lib, bunda indeks birorta butun sondan iborat bo’lishi mumkin.Umumiy ko’rinishda massiv ko’p o’lchovli paralellipipedga qiyoslanadi. m o’lchovdan iborat A massivni m-o’lchovli massiv deyiladi va A[n1,n2,..,nm] ko’rinishida, bu yerda ni- elementlar soni, 1<=i<=m.Endi, bizga bir o’lchovli n ta elementdan iborat A[n] massiv berilgan bo’lsin. Massivda saqlanayotgan ma’lumotlarni manipulyatisya qiluvchi asosiy amallarni ko’rib chiqamiz.1) Massiv ixtiyoriy kirish ruxsati(dostup)ga ega bo’lsa, elementni o’qish/yozish uchun O(1) vaqt talab qilinadi.2) Massivdan elementni qidirish murakkabligi, u tartiblangan yoki tartiblanmaganligiga bo’g’liqdir. Agar u tartiblangan bo’lsa, O(log n) operatsiya, aks holda O(n) operatsiya bajarish talab qilinadi.3) Agar massivning ixtiyoriy joyiga elementni qo’shish/ o’chirish zarur bo’lsa, buning uchun O(n) operatsiya talab qilinadi. Agarda buni massiv oxiri elementidan keyin bajarish lozim bo’lsa, O(1) operatsiya bajarish talab qilinadi.
13.2 Evkilit algoritimi.
Evklid algoritmi - ikki sonni eng katta umumiy bo'luvchisini(EKUB) topib beruvchi effektiv algoritm hisoblanadi. Algoritm yunon matematiki Evklid nomiga berilgan. U bu algoritmni eramizidan 3 asr oldin o'ylab topgan. Evklid algoritmi ikkita musbat son uchun yangi juftlikni hosil qiladi, kattasini kichginasi orqali kamaytirib. Bu jarayon ikkala son teng bo'lib qolmaguncha davom ettiriladi. Misol tariqasinda (12,14) juftligini olaylik. Dastlab 12 ni 14 olib tashlaymiz. Hosil bo'lgan juftlik - (12,2). Keyin shu jarayon taqrorlanadi: EKUB(12,2)=EKUB(10,2)=EKUB(8,2)=EKUB(6,2)=EKUB(4,2)=EKUB(2,2)=2. Shunday qilib javob - 2. Bu algoritmini to'g'riligiga sabab agarda d=EKUB(a,b) bo'lsa demak ikki sonni ayirmasi ham d soniga bo'linadi. Ya'ni (a−b)=0(mod d). Bu algoritm agarda birorta son kichik bo'lib, boshqasi katta bo'lsa juda ko'p amal bajarishiga to'g'ri keladi. Masalan (2,10000001) juftligi uchun 5000000 amal bajariladi EKUBi birligini aniqlash uchun. Ya'ni eng yomon holatda algoritm O(max(a,b)) amal bajarishiga to'g'ri keladi. Buni yanada tez ishlaydigan qilish mumkin. Gap shundaki har safar katta son kichkinasidan max(a,b)/min(a,b) challi ayrilib tashlanadi. Ayirish o'rninga qoldiq olish amalini bajarish mumkin. Shunda har safar katta son kichginadan kichiklashadi. Har safar ikkala sondan bittasi kamida 2 baravar kichraygani uchun ishlash vahti O(log(min(a,b))) tashkil qiladi. Lekin gap shundaki amalda bu algoritm deyarli O(1) amal bajaradi. Chunki har qanday juftlik uchun bittasi kamida ikki baravarga kichiklashadi dedik, ammo amalda bu kichrayish tezroq va kattaroq suratda bo'ladi.
33.1 Statistik berilganlar strukturasi.
BeriIganIarning oddiy statik strukturalari
Ularga vektorlar, to’plamlar, yozuvlar, jadvallar kiradi.
1. Vektor - bir turdagi berilganlarning tartiblangan to’plamidir.
Vektorga bir o’Ichamli to’plam mos keladi. Uning elementlari xotirada qat'i biri-biridan keyin joylashadi. Bunday tartiblanish elementlami raqamlash imkoniyatini beradi (raqamlar-indekslar). Eng ko’p qo’llaniladigan amallardan biri - berilgan indeks bo’yicha elementga murojaat amalidir. Vektorlar ustidagi yana boshqa amallardan vektoming pastki va yuqorigi chegaralarini aniqlash, vektor elementi turini aniqlash kabilardan foydalaniladi. Vektoming fizik ko’rinishi xotiraning bir xil o’lchamdagi bo’laklari (maydon, slotlar) ketma-ketligi ko’rinishida amalga oshiriladi. Har bir maydonda bitta element saqlanadi. Bu slotlar xotirada element indekslari oshib borishi tartibida joylashadi.
Vektoming fizik strukturasi xotirada joylashgan va quyidagi tabiatga ega
diskreptor bilan kuzatiladi. Deskriptor quyidagi maydonlardan tashkil topadi:
• berilganlar strukturasining ichki kodi
• vektoming ismi
• birinchi elementning manzili
• indeksning pastki qiymati
• indeksning yuqori qiymati
• elementning toifasi
• slot o’lchami
Birinchi maydon diskreptor bilan bog’langan berilganlar strukturasini
aniqlashga imkon beradi.
