Mavzu: Ma’lumotlarning nochiziqiy tuzilmasi kirish 2 I. Ma’lumotlar tuzilmalari va algoritmlari

I. Ma’lumotlar tuzilmalari va algoritmlari.

1.1 Ma’lumotlar tuzilmalari va axborotlarni xotirada tasvirlash.

Ma’lumotlar tuzilmalari va algoritmlari dasturlar tuzish uchun ashyo bo’lib hizmat qiladi. Bundan tashqari kompyuterlarni o’zi ma’lumotlar tuzilmalari va algoritmlardan iborat. Ma’lumotlar tuzilmalarini tayyor kiritmalari ikkilik sanoq va qiymatlar saqlanuvchi xotira registrlari va lug’atlari ko’rinishida aks ettiriladi. Apparatura konstruktsiyasiga kiritib qo’yilgan algoritmlar - bu elektron mantiqiy zanjirlardagi qat’iy qoidalarni o’z ichiga olgan bo’lib, unga ko’ra xotira ichiga joylashgan ma’lumotlar buyruq xolatida qabul qilinib bajarilishga tayyor turadi. SHu sababli har qanday kompyuter ishi asosida alohida olingan bitlar, yoki ikkilik raqamlari bilan ish olib borishga mo’ljallangan ma’lumotlarni ayrim ko’rininshlari yotadi. Kompyuter ushbu ma’lumotlar bilan faqat markaziy protsessor buyruqlari tizimi bilan aniqlanadigan o’zgarmas algoritmlar nabori (termasi) bilan ish olib boradi.

Kompyuter yordamida echiladigan masalalar kam xollarda “bitlar” tilida ifodalanadilar. Qoidaga ko’ra ma’lumotlar son, liter, matn, belgi va yanada murakkab tuzilmaga ega bo’lgan ketma-ketliklar, ro’yxatlar va daraxtlar ko’rinishidagi shakllardan iborat bo’ladi.

Abstrakt ma’lumotlar tuzilmalarini va dasturlar algoritmlarini yanada aniq ta’riflash uchun har qanday taklif ma’nosi aniq va bir qiymatli aniqlangan dasturlash tillari deb nomlanuvchi formal belgilar qo’llaniladi. Deyarli barcha dasturlash tillarida mavjud vositalar orasida unga berilgan nomdan yoki boshqacha aytganda identifikatordan foydalanilgan xolda ma’lumotlar elementiga murojaat etish imkoniyati mavjud. Ba’zi nomlangan qiymatlar konstantalar hisoblanib, ular aniqlangan joylarida - dasturiy qismida doimiy qiymatlarini saqlab qoladilar, boshqalari o’zgaruvchilar hisoblanib, dasturiy operator yordamida ixtiyoriy yangi qiymat berilishi mumkin. Ammo dastur bajarilgunga qadar, ularning qiymatlari aniqlanmagan bo’ladi.

Konstanta yoki o’zgaruvchining nomi dasturchiga yordam bergan xolda kompilyator uchun xech qanday ma’no bermaydi. Dastur matnini ikkilik kodiga translyatsiya qiluvchi kompilyator esa har bir identifikatorni xotirani ma’lum bir adresi bilan bog’laydi. Lekin ushbuni kompilyator amalga oshirishi uchun har bir nomlangan qiymatni turi haqida xabar berish kerak. Qandaydir masalani “qo’lda” hisoblovchi inson ma’lumotlar turini va har bir turga qo’llaniladigan amallarni intuitiv tarzda ajrata olish qobiliyatiga ega. Masalan so’zdan kvadrat ildiz chiqarish yoki sonni bosh harflar bilan yozish mumkin emas. Chunki so’zlar, sonlar va boshqa ifodalar turlicha ko’rinishga ega bo’lib, bu ularni ajratib olishni sabablaridan biridir. Ammo kompilyator uchun barcha ma’lumotlar turlari oxir oqibat bitlar ketma-ketligidan qabul qilinadi, shu sababli turlar orasidagi farqlanishlarni yaqqolligini amalga oshirish kerak.

Dasturlash tillarida qabul qilingan ma’lumotlar turlari o’z ichiga natural va butun sonalrni, haqiqiy sonlarni (taqribiy o’nli kasr ko’rinishida), literlar, satrlar va hokazolar.ni oladi.

Ba’zi dasturlash tillarida har bir konstantaning yoki o’zgaruvchining turi kompilyator yordamida ularga beriladigan qiymatlarni yozishda: o’nli kasr nuqtasining mavjudligida, masalan haqiqiy son ekanligini belgisihizmatini bajaradi. Boshqa tillarda dasturchi har bir o’zgaruvchi turini avvaldan belgilab kiritishni talab qiladi va bu avvaldan muhim afzallikni beradi. Dasturni bajarilishi davomida o’zgaruvchining qiymati ko’p marotiba o’zgargani xolda, uning turi hech qachon o’zgarmaydi. Bu degani kompilyator ishi davomida, ushbu o’zgaruvchi ustida bajarilayotgan amallarni kuzatayotgan davrida, tur e’lon qilingan shartlari bajarilishi nazorat etiladi. Bunday nazorat dastur matnini to’liq taxlil qilish orqali amalga oshirilishi mumkin. Bu xolda ushbu dastur bo’yicha aniqlanishi mumkin bo’lgan barcha amallarni qamrab oladi.

Dasturning qo’llanilishiga ko’ra kompilyatsiya davrida amalga oshiriladigan turlar himoyasi nazorati ko’proq yoki kamroq qattiyat bilan amalga oshirilishi mumkin. Masalan, Pascal tili avvalda ma’lumotlar tuzilmalari va algoritmlarini illyustratsiya qilish vositasi hisoblanib kelingan bo’lsa, dastlabki qo’llanilishi asoslariga ko’ra turlarni nihoyatda qattiy himoyalashni o’zida saqlab qolgan. Pascal kompilyatorini ko’p xollarda ma’lumotlarning bir ifodasida turli turlarni joylashtirishni yoki ma’lumotlar turiga unga xos bo’lmagan amllarni fatal xato sifatida qo’llash deb baholanadi. Aksincha, avvaldan tizimli dasturlashga mo’ljallangan S tili turlarni kuchsiz himoyalovchi til hisoblanadi. S-tili kompilyatori bunday xollarda faqat ogohlantirishlarni beradi. Turlarni qattiq himoyasini yo’qligi S -tilida dastur yozuvchi tizim dasturchisi o’zining amallarini to’g’riligiga o’zi javobgar bo’ladi.

Ma’lumotlar tuzilmalari aynan “fazoviy” tushunchalarga ta’luqli bo’lib, uni kompyuter xotirasidagi axborotni tashkil etuvchi sxema deb ta’riflash mumkin . Algoritm esa dastur tuzilmasida mos ravishda protsedura elementi hisoblanadi va hisob-kitob retsepti bo’lib hizmat qiladi.

Dastlabki algoritmlar sonlarni ko’paytirish, umumiy bo’luvchini topish, trigonometrik funktsiyalarni echish kabi masalalarni uchun o’ylab topilgan. Bugungi kunda hisob -kitoblardan tashqari algoritmlar ham teng ma’noda muhim hisoblanadi. Bu algoritmlar masalan, matnda berilgan so’zni izlash, hodisalarni rejalashtirish, berilgan tartibda ma’lumotlarni saralash va hokazo masalalarni echish uchun tuzilgan. Sanoqsiz algoritmlar tarkibida son bo’lmagan ma’lumotlar bilan ham ish olib boriladi. Bundan tashqari Ushbu algoritmlarda ularni qurish va tushinish uchun hech qanday chuqur matematik ifodalar qo’llanilmaydi.

Matematik usullar sanoqsiz algoritmlar ichidan eng yaxshilarini tanlab olishda qo’l keladi.

Algoritmlarda qo’llaniluvchi ma’lumotlar tuzilmalari o’ta murakkab bo’lishi mumkin. Natijada ma’lumotlarni to’g’ri ifodalashni tanlash ko’pincha omadli dasturlash kaliti bo’lib xizmat qiladi va foydalanilayotgan algoritm detallariga nisbatan dastur unumdorligiga ko’proq ta’sir o’tkazishi mumkin. Bugungi kunda ma’lumotlar tuzilmalarini tanloab olishni umumiy nazariyasi mavjud emas. Bajarilishi mumkin bo’lgan imkoniyatlardan biri - barcha bazaviy “g’ishtchalar”ni va ulardan yig’ilgan tuzilmalarni aniqlab olishdir. Katta tizimlarni qurishda ushbu bilimlarni qo’llash imkoniyati - bu birinchi galda muxandisning ustaligi va maxorati bilan aniqlanadi.

Hisoblash mashinalarida xotira qurilmalarining uch asosiy turini ajratish mumkin: o’ta tezkor, tezkor va tashqi xotira odatda o’ta tezkor xotira registrlardan quriladi. Registrlar axborotni vaqtincha saqlash va o’zgartirish uchun qo’llaniladi. O’ta muhim registrlarning ba’zilari kompyuterni markaziy protsessorida joylashgan bo’ladi. Arifmetik amallar argumenti (ya’ni operandlar) jaylashgan registrlar (akkumulyatorlar deb ham ataladi) markaziy protsessor tarkibiga kiradi.

Axborot akkumulyatorlari tarkibiga kiritilgan qo’shish, ayrish, ko’paytirish va bo’lish amallari juda murakkab mantiqiy sxemalar yordamida amalga oshiriladi. Bundan tashqari akkumulyatorlarda boshqarishni uzatishni normalb ketma-

ketligini o’zgartirish zaruratini tekshirish maqsadida, aloxida bitlar taxlil qilinishi mumkin. Operandlarni va arifmetik amallarni eslab qolishdan tashqari, registrlar shuningdek dastur buyruqlarini va keyingi bajariladigan buyruq raqamining boshqaruv axborotini vaqtincha saqlash uchun qo’llaniladi. Tezkor xotira tabiatiga ko’ra ko’proq o’zgarmas axborotni xotirada saqlash uchun qo’llaniladi. Tezkor xotirani muhim xususiyati bu manzillanishidir. Bu har bir xotira yacheykasi o’zining identifikatoriga ega ekanligidir, tom ma’noda uni umumiy xotira yacheykalari massivida nomlanishini bildiradi. Ushbu identifikator manzil (adres) deb ataladi. Tezkor xotiraga murojaat qiluvchi mashina buyruqlarini operandlari yacheyka manzillari hisoblanadilar. Hozirgi zamon hisoblash tizimlarining ko’pchiligida manzillashtirishning birligi etib bayt - 8 ta ikkilik razryadidan tashkil topgan yacheyka hisoblanadi. Tezkor xotiraning aniq yacheykasi yoki yacheykalari to’plami dasturda aniq o’zgaruvchi bilan bog’langan bo’lishi mumkin. Biroq o’zgaruvchi qatnashadigan arifmetik himoblarni bajarilishi uchun o’zgaruvchini qiymatini hisoblashga qadar xotira yacheykasidan registrga o’tkazilgan bo’lishi kerak. Bunda hisoblash natijasi o’zgaruvchiga qaytadan berilishi kerak bo’lsa, natija qiymati mos registrdan ushbu o’zgaruvchi bilan bog’langan tezkor xotira yacheykasiga qaytarilishi kerak.

Dasturni bajarilishi vaqtida uning buyruqlari va ma’lumotlari asosan tezkor

xotira yacheykalariga joylashtiriladi. Tezkor xotira elementlarining to’liq to’plami ko’pincha asosiy xotira deb ataladi.

Tashqi xotira avvalom bor ma’lumotlarni uzoq muddatga saqlash uchun xizmat qiladi. Tashqi xotirada joylashgan ma’lumotlarning xususiyatiga ko’ra, ularni yaratgan dastur ishlab to’xtaganidan so’ng ham saqlanib qolinadi va kelajakda uni yaratgan dasturi hamda boshqa dasturlar tomonidan ko’p marotiba qo’llab foydalanish mumkin. Tashqi xotira shuningdek dasturlarni, ishlatilmagan vaqtlarida saqlash uchun ham qo’llaniladi. Tashqi xotira narxi tezkor xotiraga nisbatan ancha arzon bo’lib, sig’imi nisbatan katta bo’ladi. Tashqi xotira bajarilayotgan dasturning kod va ma’lumotlarini saqlab turish uchun kerak.

Bajarilayotgan dasturning aktiv kodlari va ishlov berilayotgan ma’lumotlari albatta bu bosqichda tezkor xotiraga ko’chirilgan bo’lishi kerak, chunki tashqi xotira va operatsion qurilmalar (registrlar) bilan to’g’ridan to’g’ri almashuvni amalga oshirish mumkin emas.

Ma’lumotlarni saqlashga mo’ljallangan tashqi xotira asosan tezkor xotira singari xususiyatlarga ega, xususan - manzillashtirish xususiyati. SHu sababli, ma’lumotlarning tuzilmalari tezkor xotirada qanday bo’lsa, tashqi xotirada ham shu ko’rinishda bo’lishi mumkin. Ishlov berish algoritmlari ham bir xilda bo’lishi mumkin. Ammo tashqi xotira o’zining fizik tabiatiga ko’ra ma’lumotlarga kirishning tamoman o’zgacha usullarini qo’llaydi. Bu kirish o’zgacha vaqtinchalik tavsiflardan iborat. Boshqacha aytganda tezkor xotira uchun samarador bo’lgan tuzilmalar va algoritmlar tashqi xotira uchun o’zgacha natija berishi mumkin.

Axborot tizimlarini qo’llanish sohalari turli-tuman. Bu sharoitlarda ikkita bir xil tizimni topish qiyin. Ular asosiy xususiyatlari va o’ziga xos tomonlari bilan farqlanadi, masalan: ishlov berilayotgan axborot xarakteri, maqsadli funktsiyalari, tizimning texnik darajasi va hokazo. Sanab o’tilgan xususiyatlar axborotni ham tizimda, ham foydalanuvchi uchun taqdim etish shakli, axborotga ishlov berish jarayonlarining xarakteri va axborot tizimlarining muhit bilan o’zaro aloqasi, apparat va dasturiy ta’minotning tarkibiga ta’sir etadi.

Ravshanki, axborotni saqlash, ishlov berish va izlash uchun kompyuterlardan foydalaniladigan avtomatlashtirilgan va avtomat axborot tizimlarini ushbu ko’rib chiqish predmeti deb hisoblash kerak. So’zsiz, bugungi kunda bu tizimlar funktsional imkoniyatlarining kengligi, axborotning katta massivlarini saqlash va ishlov berish qobiliyati bilan farqlanadi. Bu tizimlarning o’ziga xos xarakterli xususiyati kompyuterlardan turli-tuman agregatlarda va bo’g’inlarda, xususan axborotni to’plash, tayyorlash, uzatish va taqdim etishda, keng foydalanishdan iborat.

Har qanday axborot tizimi uning uchun kiritiladigan axborot manbai va taqdim etiladigan axborot iste’molchisi hisoblanadigan tashqi muhit qurshovida ishlaydi. Bunday tizim doirasida, tizimga kirishdan boshlab va undan chiqqunga qadar, axborot oqimi bir nechta ishlov berish bosqichidan o’tadi. Ma’lumki, axborotga ishlov berishning asosiy bosqichlariga axborotni to’plash, ro’yxatga olish va dastlabki ishlov berish, aloqa kanali bo’ylab manbadan kompyuterga uzatish, axborot massivlarini yaratish va saqlab turish, axborotni chiqarib berish shakllarini shakllantirish, aloqa kanali bo’ylab kompyuterlardan iste’molchiga uzat, foydalanuvchi qabul qilishi uchun qulay shaklga o’tkazish kabilar kiradi Axborot tizimining kompyuteriga tushadigan axborot atrof muhitdagi obyektlar yoki alohida tarkibiy qismlarning holatini, algoritmlar esa unga tashqi muhitda ishlov berishning tegishli qoidalariga mos bo’lgan ishlov berishning ba’zi qoidalarini aks ettiradi.

Kompyuterlarga uzatiladigan axborot xotirada axborot massivlarini hosil qilib joylashadi, axborot massivlari esa birgalikda axborot fondini tashkil etadi. Axborot massivlari muayyan tuzilma tarzida tashkil etiladi, u haqiqiy olam obyektiningtuzilish tarkibi, uning ayrim elementlari o’rtasidagi aloqalar va ularning xarakterlari bilan bog’liqdir.

Massiv hamda fond elementlari bilan umuman olganda ishlov berishning turli operatsiyalari amalga oshiriladi, quyidagilar ular ichida eng asosiylari hisoblanadi: mantiqiy va arifmetik operatsiyalar, axborotni saralash va izlash, yuritish hamda tuzatish kiritish. Bu operatsiyalar natijasida axborotning dolzarbligi ta’minlanadi, ya’ni atrof muhit va uning kompyuterdagi modeli o’rtasida zaruriy muvofiqlik ta’minlanadi. Bundan tashqari, chiqarib beriladigan axborot ishlov berish topshiriqlariga muvofiq ravishda shakllantiriladi.