Inforatikaning algoritmik asoslari

Muallif: Mengliyev SH.

Qo`shilgan sana: 2014-09-07

Inforatikaning algoritmik asoslari

Algoritm tushunchasi va uni formallashtirish.Algoritm – bu algoritmik jarayon bilan ifodalanuvchi aniq ko‘rsatmalar bo‘lib, ixtiyoriy berilgan boshlang‘ich ma’lumotdan boshlanadi (ushbu algoritm uchun mumkin bo‘lgan berilganlar majmuasi) va ushbu berilganlar bilan ifodalanuvchi natija olishga qaratiladi.
Algoritmik jarayon – bu konstruktiv ob’ektlar (so‘zlar, sonlar, ifodalar)ning diskret qadamlar bilan amalga oshiriluvchi ketma-ket shakl o‘zgartirish jarayonidir.
Protsedura (ko‘rsatalar kompleksi) – alohida amallar barilishi qoidalarning knstruktiv aniqlanuvchi tizimidir.
Algoritm - algoritm bajaruvisi amalga oshiruvchi qaralayotgan masalalar sinfiga taalluqli bo‘lgan ixtiyoriy masalaning echimini topish uchun zarur bo‘lgan chekli sondagi amallar ketma-ketligi va mazmunini ifodalovchi formallashtirilgan va konstruktiv , aniq va to‘liq ko‘rsatalar tizimi vositasida realizatsiya qilinadi.
Algoritm xossalari: aniqlik, tushunarlilik, cheklilik (natijaviylik), diskretlik, umumiylik.
Algoritmlashning vazifalari:
1. YAngi algoritm yaratish, protsedurani formallashtiri yoki oldindan ishlab chiqilgan algoritmni modifikatsiyalash.
2. Algoritm to‘g‘riligini isbotlash (verifikatsiya, testlash).
3. Ishlab chiqilgan yoki modifikatsiya qilingan algoritmni realizatsiya qilish, unin boshqa bajaruvchilar buyruqlar tiziiga o‘girish.
4. Algoritmni effektivlik kriteriylari bo‘yicha tahlil qilish va baholash.
Algoritmik jarayon xarakteristikalari. Algoritmni xarakterlovchi parametrlar:

mumkin bo‘lgan boshlang‘ich berilganlarning majmuasi;

mumkin bo‘lgan oraliq natijalar majmuasi;

natijalar majmuasi;

boshlash qoidasi;

axborotni bevosita qayti ishlash qoidasi;

tugallash qoidasi;

Natijani olish qoidasi.

Algoritmlar nazariyasida qat’iy formal ko‘rinishda ifodalangan algoritmlar o‘rganidadi. Masalan, ikki natural sonning EKUB (Evklid algoritmi) ini topish algoritmini qaraylik:

Birinchi qadam – qoldiqni topish: r := m MOD n

Ikkinchi qadam– o‘rin almashtiri: m := n n := r

Uchinchi qadam – to‘xtash?: agar <> 0, u xolda 1 ga o‘tish.

To‘rtinchi qadam –to‘xtash: m – izlangan son.m = 10, n = 4 uchun konstruktiv ob’ektlar sxemasi(trassirovka) :
(10, 4) -> (4, 2) -> (2, 0) -> NOD = 2

Algoritmik muammo. Algoritmik muammo – bu konkret masalalr sinfi uchun natijaviy berilganlar bilan boshlang‘ich ma’lumotlar orasida bog‘lanishni beruvchi xossalarga ega bo‘lgan algoritm izlash masalasidir.
Umumiy algoritmik muammo – bu konkret sinfga talluqli barcha masalarni echishga mo‘ljallangan umumiy algoritmni izlash muammosidir.
Xususiy algoritmik muammo – bu konkret masalalar sinfiga taalluqli bir gurux masalalarning echimini topishga qaratilgan algoritmik jarayonni yaratuvchi algoritmni izlash masalasidir.
Agar umumiy yoki xususiy algoritmik muammo echimini izlash natijasida echimning mavjudligi aniqlansa, muamo echimli, aks holda muammo echimsiz deb hisoblanadi. Masala algoritmik echimsiz deb hisoblanadi, agar uni hal etadigan Tьyuring mashinasi (rekursiv funksiya yoki normal arkov algoritmi) mavjud bo‘lmasa.
Markov tezisi. Har qanday algoritm normal algoritm (intuitiv ma’noda) ko‘rinishida ifodalanishi mumkin.
Echimsizligi oldindan ma’lum yoki algoritmlar nazariyasi doirasida isbotlanuvchi algoritmik echimsiz muammolar mavjud. Masalan,
1. Ikki ixtiyoriy algoritm yoki dasturning bitta funksiyani hisoblash-hisoblamasligini aniqlovchi algoritm qurish mumkin emas.
2. Qandaydir dasturning o‘zi yozilgan matnga qo‘llanuvchan ekanligini aniqlovchi algoritm mavjud emas (o‘z-o‘ziga qo‘llanuvchanlik muammosi)
Algoritmik modellar va ularning berilishi Algoritmik modellar sinflariga quyidagilarni kiritish mumkin:
1. Hisoblash algoritmlari. Bunda barcha berilganlar sonlar ko‘rinishida ifodalanib, ularni qayta ishlash jarayoni arifetik hisoblashlarga keltiriladi. Bunday algoritmik modellar qandaydir sonli funksiya qiymatini hisoblab, elementar qadamlar esa arifmetik amallardan iborat bo‘ladi. Qadamlar ketma-ketligi superpozitsiya va rekursiya usullari orqali aniqlanadi.
2. Simvolli algoritmlar. Bunda algoritm boshlang‘ich ma’luotlari simvollardan iborat bo‘lib, ushbu simvollarning konkret alfaviti va o‘rniga qo‘yishlar qoidasi (masalan, Markovning noral algoritmi) beriladi.

3. Bajaruvchilar uchun algoritmlar.Algoritm mashina yoki avtomat bajarishi mukin bo‘lgan qoidalar (ko‘rsatmalar)ketma-ketligi bilan beriladi(masalan,Tьyuring va Post abstrakt ashinalari).
Tipik algoritmik konstruksiyalar: mantiqiy (og‘zaki), jadvalli, grafil (graf, diagramma, rasm) lardan iborat bo‘lib, maxsus belgilashlar yordaida beriladi.

1 sxema – CHiziqli algoritmni ifodalab, bunda hisoblashlar additiv(ketma-ket) deb ataladi.
2 sxema – Tarmoqlanuvchi algoritmni ifodalab, hisoblashlar alьternativ deb ataladi.
3 sxema – Takrorlanuvchi algoritmni ifodalab, bunda hisoblashlar iteratsion deb ataladi.
Strukturali blok -sxema uchta bazaviy bloklar kopozitsiyasidan iborat bo‘ladi.

5964 marta o`qildi.

shoydullo adminstrator