MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

2-MUSTAQIL ISH Dek. Dekni massiv yordamida tasvirlash va ular ustida amal bajarish algoritmlari. Axatov Asadbek variant

MALUMOTLAR, ALGORITMLAR VA MALUMOTLAR TUZILMASI TUSHUNCHALARI. Reja: 1. Asosiy tushuncha va tariflar. 2. Malumotlarni tasvirlash(ifodalash) bosqichlari. 3. Malumotlar tuzilmasini klassifikatsiya qilish. 4. Malumotlarni toifalari.

Dek. Dekni massiv yordamida tasvirlash va ular ustida amal bajarish algoritmlari. using System; internal class ArrayErr { private static void Main() { int[] sample = new int[10]; int i; // Chegaradan chiqish holati yuz bermoqda for (i = 0; i < 100; i = i + 1) sample[i] = i; }

ASOSIY TUSHUNCHA VA TARIFLAR Malumotlar tuzilmasi bu xotirada tashkil etiladigan elementlar yigindisi bolib, ular ustida dastur yordamida amallar bajariladi. Malumotlar tuzilmasi – bu bironta toifaga tegishli bolgan va ozaro malum munosabatga ega bolgan elementlar toplamiga aytiladi. Malumot – bironta qiymat yoki qiymatlar toplami hisoblanadi.Misol uchun bu bironta eksperiment natijalari, yoki talabalarning imtixon ballari bolishi mumkin. Malumotlar tuzilmasi elementi – bu qiymatlar toplamining bir bolagi hisoblanadi. Tuzilma elementi – qiymatlar jamlanmasi bolib, misol uchun talabalarning ismi, sharifi, yoshi har bir fandan olgan bahosi va x.k. larni keltirish mumkin.

ASOSIY TUSHUNCHA VA TARIFLAR Elementlar 2 taga bolinishi mumkin: -Element sifatida malumotlar guruhi olib qaraladi. Bunda e;lementlar yana qism bolak;arga bolinishi mumkin. Masalan, ota-onalar maydoni talabalarning ota va onalari xaqida malumot saqlaydigan alohida maydonlardan tashkil topadi. -Elementar, yani bolinmas, bunda element qism bolaklarga ajratilmaydi. Obekt – bu xususiyatlar va attributlariga ega bolgan va bu xususiyatlarga qiymat qabul qilishi mumkin bolgan tuzilma hisoblanadi. Masalan, talaba bu obekt deb qaralishi mumkin tuzilma. Maydon – bu obektlarning attributlari yoki xususiyatlarini ifodalovchi tushuncha bolib, sonli yoki son bolmagan qiymatlarni ozlashtirishi mumkin. Yozuv – bu bironta obektga tegishli turli toifadagi maydonlar toplamidir. Fayl- bu bir-biriga bogliq bolgan yozuvlar toplamidir. Masalan, barcha talabalar xaqidagi yozuvlarni oz ichiga olishi mumkin, Kalit – bu yozuvdagi maydon bolib, aynan shu yozuvni boshqa yozuvlardan ajratib turishga xizmat qiladi, uning qiymati boshqa yozuvlarda takrorlanmas hisoblanadi. Bazida bittadan kop maydonlar qiymatlari elementlararo betakror bolishi mumkin va bunga karrali kalit deyiladi. Kopincha asosiy kalit hisoblanadigan bitta maydon malumoti ishlatiladi va u boshlangich kalit deyiladi, qolganlari esa alternativ kalit deyiladi.

ASOSIY TUSHUNCHA VA TARIFLAR

MALUMOTLARNI TASVIRLASH(IFODALASH) BOSQICHLARI. Malumotlar toifalari 3 turga ajratiladi: 1.Primitiv (sozlangan) toifalar (malumotlarning sodda toifalari). Oldindan malum boladigan, sozlangan toifalar deb ham ataladigan toifalar bolib, turli dasturlash tillarida turlicha bolishi mumkin. Masalan, C++ tilida int (long, short,… ), float(double), char,… 2.Foydalanuvchi tomonidan aniqlanadigan toifalar, qachonki mavjud sozlangan toifalar qoyilgan masalani yechishga yetarli bolmasa qollaniladi. Abstrakt toifalar. Malumotlar toifalarining mantiqiy xususiyatlarini aniqlashda foydali instrument hisoblanadi. Abstrakt toifa atamasi bazaviy matematik tushunchasiga bogliq. Ushbu toifalardagi malumotlar qisman apparat va dasturiy taminot yordamida tuzilma sifatida fizik amalga oshirilishi mumkin. Biz abstrakt toifalarni matematik tushuncha sifatida aniqlaymiz.

Malumotlar tuzilmasi Malumotlar turli yolar asosida tashkil etilishi mumkin, mantiqiy yoki matematik modelni tashkil etilishi malumotlar tuzilmasi deyiladi. Konkret bir malumotlar tuzilmasini tanlash quyidagilarga bogliq: -Real voqelikda elementlararo munosabatni yaqqol ifodalay olishi kerak; -U shunday soda tuzilishi kerakki, zarur bolganda ustida samarali amal bajarish mumkin bolsin. Malumotlar tuzilmasini organish quyidagilardan iborat: -Tuzilmani mantiqiy ifodalash; -Tuzilmani fiizik amalga oshirish; Tuzilmani sifatiy taxlili, yani elementlarni saqlash uchun qancha xotira xajmi sarflanishini aniqlash (xotira sarfi) va qayta ishlashga ketadigan vaqtni (vaqt sarfi) xisoblash nazarda tutiladi.

Vaqt sarfi.Tuzilma ustida amal bajarish algoritmini bajarilish vaqtini hisoblash kozda tutiladi.Buni hisoblashda mashxur katta O notatsiya tushunchasi ishlatiladi. Xotira sarfi.Kirish malumotlarini inobatga olmagan xolda, ishlatilayotgan algoritm uchun xotiradan talab qilinadigan qoshimcha joy sarfi tushuniladi.Bunda xam katta O notatsiyasi qollaniladi. Vaqt va xotira sarfini hisoblash uchun quyidagi yondashuvlar mavjud: -Katta O notatsiya. f(x)=O(g(n)) deb belgilanadi, faqat va faqat shunday musbat c va m konstanta mavjud bolib, f(n) =m holatlarda. Masalan, ushbu funksiyani 3n+2=O(n)deb olish mumkin,chunki 3n+2 =2 tengsizlik orinli. Eng ogir holat. Bunda kirish malumotlari algoritm bajarilishi uchum eng yomon holatda boladi va juda sekin bajariladi. Eng ogir holat tahlilda muxim hisoblanadi, chunki bu algoritm bajarilishi uchun ketishi mumkin bolgan maksimal vaqtni tasavvur qilishimizga sabab boladi. Misol uchun, qidirilayotgan element tuzilmaning oxirgi elementi bolsa, uni toppish uchun barcha solishtirishlar amalga oshiriladi

-Ortacha holat. Bunda algoritmning ortacha ishlash imkoniyatini beruvchi kirish malumotlari toplami olib qaraladi. Malumotlar tuzilmalari ustida quyidagi amallarni bajarish mumkin: 1.Korikdan otkazish (traversing) - tuzilma elementlariga 1 martadan murojaat qilish amali. 2.Kiritish – tuzilmaga yangi element kiritish amali. 3.Ochirish – tuzlmadan bironta elementni ochirish amali. Bunda element shunday ochirilishi kerakki, qolgan elementlar stabil holatda bolishi kerak, yani ayrim tuzilmalarda nosozlik sezilishi kerak emas. 4.Qidirish – tuzilmadan bironta elementni joylashgan ornini aniqlash amali. 5.Saralash – elementlarni malum bir tartibda joylashtirish amali. 6.Birlashtirish (merging) – ikkita tuzilmani birlashtirish amali.

Algoritm.Bironta masalani echish uchun moljallangan amallarningmalum ketma-ketligi hisoblanadi.Algoritmlar quyidagi tamoyillarga asoslanishi kerak: 1.Kiritish – bosh qiymat yoki bir nechta qiymatlarni kiritish mumkin bolishi; 2.Chiqarish – kamida bitta qiymat chiqarilishi; 3.Aniqlik – xar bir amal aniq va bitta manoga ega bolishi; 4.Cheklilik–algoritm chekli sondagi amallardan tashkil topishi; 5.Samaradorlilik – xar bit amal oddiy va soda bolishi kerak. Mantiqiy bosqichda malumotlar tuzilmasini biror bir dasturlash tilida ifodalanishi tushuniladi. Fizik(jismoniy) bosqichda esa informatsion obektni mantiqiy tavsiflanishiga mos ravishda EXM xotirasida akslantirilish tushiniladi. EXM xotirasi chekli bolganligi sababli, xotirani taqsimlash va uni boshqari muammosi yuzaga keladi. Yuqoridan korinib turibdiki, mantiqiy bosqich bilan fizik bosqichlar bir biridan farq qiladi. Shu sababli, hisoblash tizimlarida mantiqiy bosqichni fizik bosqichga va aksincha, fizik bosqichni mantiqiy bosqichga akslantirish muamosi vujudga keladi.

Koplab dasturlash tillarida malumotlar standart va foydalanuvchi tomonidan beriladigan toifalarga ajratiladi. Malumotlarni standart toifalariga quyidagi 5 ta tur ozgaruvchilari kiradi: a) butun (INT); b) haqiqiy (FLOAT) ; c) mantiqiy (BOOL); d) belgili (simvol) (CHAR); e) korsatkichli (*). Foydalanuvchi tomonidan aniqlanadigan toifalar esa: a) sanaladigan; b) diapazonli (oraliqli).

MALUMOTLAR TUZILMASINI KLASSIFIKATSIYA QILISH. Haqiqiy toifa Haqiqiy toifaga kasr qismlari bor chekli sonlar toplami kiradi. Toplamni chekli bolish sharti EXMda sonlarni ifodalash chegaralanganligi bilan bogliq. Haqiqiy sonlar ustida quyidagi amallarni bajarish mumkin: qoshish, ayrish, bolish, kopaytirish, trigonometrik funksiyalarini xisoblash, darajaga oshirish, kvadrat ildiz chiqarish, logarifmlash, minimum va maksimum elementlarni topish va boshqalar. Bularning natijalari ham haqiqiy toifaga kiradi. Bu yerda ham binar amallarga nisbatan masalaning yechimlari mantiqiy toifaga tegishli boladi. EHM xotirasida haqiqiy sonlar asosan qozgaluvchan nuqta formatida saqlanadi. Bu formatda x haqiqiy son quyidagi korinishda ifodalanadi:

Etiboringiz uchun rahmat