«amaliy matematika va informatika» kafedrasi «Algoritmlar nazariyasi» fanidan kurs ishi



Download 0,54 Mb.
bet13/13
Sana31.12.2021
Hajmi0,54 Mb.
#244346
1   ...   5   6   7   8   9   10   11   12   13
Bog'liq
ALGARITM kurs

O’rtacha holat tahlili. Ishni boshlang’ich massiv tеskari tartibda joylashgan eng yaxshi holatdan boshlaymiz. Elеmеntlarning bunday joylashuvi bizga avtomatik holda to’g’ri piramidani bеradi. Shuning uchun har bir Piramida protsеdurasiga murojaat vaqtida elеmеntlarning to’g’ri joylashganligini tasdiqlovchi ikkita taqqoslash amali bajariladi. Ushbu protsеdura elеmеntlarning taxminan yarmi uchun chaqirilganligidan piramida qurish mobaynida N ga yaqin taqqoslash amallari bajarilishi kеlib chiqadi. Saralangan massivga ega bo’lish uchun piramidadan barcha elеmеntlarni kеtma-kеt olib, uni har safar qaytadan shakllantirish lozim. Shuning uchun eng yaxshi holatda piramidali saralash algoritmi N Q NlogN ta taqqoslash amali bajarilib, uning murakkabligi O(NlogN) ga tеng bo’ladi. Shunday qilib, piramidali saralash algoritmining eng yaxshi holat murakkabligi bilan eng yomon holat murakkabligi mos tushadi. Bundan o’rtacha holat murakkabligining O(NlogN) ga tеng ekanligi kеlib chiqadi.

2.2 Piramidal saralashga doir masala yechish



Piramidali (top’lam) bu ikki tomonlama daraxtdir

a[i] a[2i+1];

a[i] a[2i+2].



a[0] piramidaning minimal elementi.

Piramidal tartiblashning asl g'oyasi, umumiy arifmetik elementlardan olingan piramidaning oldindan yasalishi va elementlarning tartiblashidir. Algoritmning bajarilishi 2 etapga bo’linadi.

1 –bosqich. Piramidani qurish. n/2-1 dan boshlab, daraxting o’ng qismini aniqlab olamiz (daraxtning pastki darajasi). Massivning bu qismidan chaproqda turgan elementlarini olamiz va uni piramida bo’ylab joylashtiramiz, undan kichik elementlar kelib qolsa, ularning kichigi bo’ylab harakatlanamiz.

Masalan saralash uchun massiv 24, 31, 15, 20, 52, 6

Elementlarni dastlabki piramida ko’rinishida joylashtiramiz; o’ng qism elementining nomeri (6/2-1)=2 – bu element 15.





15 elementini piramida bo’ylab joylashtirish natijasi:




Keyingi joylashtirilayotgan element – 1, 31 ga teng



keyingi element –0, 24 ga teng.

Albatta olingan massiv hali tartiblanmagan. Lekin joylashtirish jarayoni piramidali saralash asosi hisoblanadi. Joylashtirish natijasida eng kichik element piramida uchida bo’lib qoladi.



2– bosqich qurilgan piramidada saralash. Massivning eng oxirgi elementini joriy qilamiz. Joriy elementni uchidagi element(eng kichik) bilan joylarini almashtiramiz. Joriy elementni (uchidagi) n-1 elementli piramida bo’ylab joylashtiramiz. Keyin oxirgisidan bitta oldingi elementni tanlaymiz va h.k.



jarayonni davom ettiramiz. Natijada massiv kamayish tartibida saralangan bo’ladi.





Piramidali saralashning C++ dagi dasturi

#include

#include

// To’plamni shakllantirish – to’plam bo’yicha “joylashtirish”

void siftDown(int *numbers, int root, int bottom)

{

int maxChild; // maksimal avlod indeksi

int done = 0; // to’plam shakllanganligi bayrog’i

// Toki oxirgi qatorga bormaganimizcha

while ((root * 2 <= bottom) && (!done))

{

if (root * 2 == bottom) // agar oxirgi qatorda bo’lsak,

maxChild = root * 2;

// chap avlodni eslab qolamiz

// aks holda, ulardan kattasini eslab qolamiz

else if (numbers[root * 2] > numbers[root * 2 + 1]) maxChild = root * 2;

else

maxChild = root * 2 + 1;

// agar uchidagi element maksimal avloddan kichik bo’lsa

if (numbers[root] < numbers[maxChild])

{

int temp = numbers[root]; // ularning joylarini almashtiramiz

numbers[root] = numbers[maxChild];

numbers[maxChild] = temp; root = maxChild;

}

else // aks holda

done = 1; // piramida hosil bo’ladi

}

}

// to’plamda saralash funksiyasi

void heapSort(int *numbers, int array_size)

{

// piramidaning pastki qatorini shakllantiramiz



for (int i = (array_size / 2) - 1; i >= 0; i--)

siftDown(numbers, i, array_size);

// qolgan elementlarni piramida bo’ylab joylashtiramiz



for (int i = array_size - 1; i >= 1; i--)

{

int temp = numbers[0]; numbers[0] = numbers[i]; numbers[i] = temp; siftDown(numbers, 0, i - 1);

}

}

int main()

{

int a[10];

// Massivni tasodifiy sonlar bilan to’ldiramiz

for (int i = 0; i<10; i++)

a[i] = rand() % 20 - 10;

// massivning saralashgacha bo’lgan elementlarini chiqaramiz

for (int i = 0; i<10; i++)

printf("%d ", a[i]); printf("\n");

heapSort(a, 10); // saralash funksiyasini chaqirish

// Saralashdan keying massiv elementlarini chiqarish

for (int i = 0; i<10; i++) printf("%d ", a[i]); printf("\n");

getchar(); return 0;

}

Natija:

Piramidali saralash algoritmining tahlili


Ba'zi tashqi murakkabliklarga qaramay, piramidali saralash eng samarali hisoblanadi. Saralash algoritmi katta n lar uchun samarali. Eng yomon holatda o’zgaruvchan elementlar qadamlari soni 𝑛 log2 𝑛.

Almashtirishlarning o’rtacha soni taxminan quyidagiga teng:
XULOSA

Axborot texnologiyasining maqsadi axborotlarni inson ularni tahlil qilishi va shu asosda biror ishni bajarish bo’yicha qaror qabul qilishi uchun ishlab chiqishdan iborat. Shunday qilib, tizim - bu o’zaro bog’liq va yagona maqsadga erishish uchun ma’lum qoida asosida o’zaro munosabatda bo’ladigan unsurlar to’plami. Bu unsurlar to’plami oddiy unsurlar yig’indisidangina iborat bo’lmay, har bir unsur ham o’z navbatida tizim bo’lishi mumkin. Tizimlar tuzilishi bo’yicha oddiy yoki murakkab bo’lishi mumkin. Oddiy tizimlarni tashkil etuvchi unsurlar soni kam bo’lib, sodda tuzilishga ega bo’ladi. Murakkab tizimlar esa, bir nechta unsurlardan tashkil topgan bo’lib bu unsurlar ham o’z navbatida alohida tizimlarga bo’linishi mumkin. Axborot texnologiyalarida Algoritmlash nazaryasini ham o’rni katta.

Hozirgi kunda Respublikamizda keng tarqalib borayotgan ish joylarini avtomatlashtirish va ish joylarida axborot kommunikatsiya vositalaridan keng foydalanishga katta e’tibor berilmoqda.

Men ushbu kurs ishini qilish davomida algoritmlashda Piramidal saralash haqida ancha o’rganib oldim. O’zimga berilgan mavzuni tushunganimcha yoritishga harakat qildim. Kurs ishini qilish davomida algoritmlashda bir qator saralash turlarini o’rgandim va buni kelajakda bilganlarimni qo’llashga harakat qilaman. Ushbu mavzuni yoritar ekanman, men algoritmlashda Piramidal saralashning o’z o’rniga ega ekanligini va qachon, qayerda ishlatilishini va afzalliklariyu kamchiliklari haqida bilib oldim.



FOYDALANILGAN ADABIYOTLAR

  1. O`.T.Haitmatov va b.Informatika va axborot texnologiyalari. O’quv qo’llanma. T. TKTI. 2005 y.

  2. Aripov M., Xaydarov A. Informatika asoslari T. “O`qituvchi”2002y.

  3. Holmatov T.X.,Toyloqov N.I. Amaliy matematika, dasturlash va kompyuterning dasturiy ta’minoti. T.Mexnat, 2000 y. 27-32 b.

  4. А.В. Петров и др. Вычислительная техника и программирование. Учебник для технических вузов.М.:Высш. шк.,1990.

  5. Культин Н.Б.Программированиев Турбо Паскаль и Дельфи. СПб.:БХВ-Сaнкт-Петербург,1999.

  6. Дж. Макконел. Основы современных алгоритмов. 2-е дополненное издание Москва:Техносфера, 2004.

  7. Джулиан М. Бакнелл.Фундаментальные алгоритмы и структуры данных в Дельфи..СПб.-ДиаСофтЮП,2003.

  8. Л.Г. Гагарина, В.Д. Колдаев. Алгоритмы и структуры данных. М: Финансы и статистика. ИНФРА-М.2009.

  9. Роберт Седжвик. Фундаментальные алгоритмы на C++. К.: Издательство «ДиаСофт», 2001.

  10. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. М., Наука, 1987.

  11. Кнут Д. Искусство программирования для ЭВМ. Основные алгоритмы. М., 2000.

  12. В.И.Игошин. Математическая логика и теория алгоритмов. Издательство Саратовского Университета, 1991.

Internet saytlari:

  • https://hozir.org

  • https://fayllar.org

  • http://intsys.msu.ru/stuff/vnosov/theorald.htm#top

  • http://structur.h1.ru/hash.htm

  • http://sorting2.shtml


Download 0,54 Mb.

Do'stlaringiz bilan baham:
1   ...   5   6   7   8   9   10   11   12   13




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish