1. Kombinatorika elementlari

1. Kombinatorika elementlari

1.Kombinatorika elementlari.

Kombinatorika – ma’lum xossalarga ega bo‘lgan elementlarning turli kombinatsiyalarini o‘rganuvchi matematikaning bo‘limi. Kombinatorikaning asosiy masalasi – berilgan ob’ektlardan u yoki bu shartlarga bo‘ysunuvchi bir nechta turli kombinatsiyalari tuzish mumkin. To‘plamlardan farqli elmentlar kombinatsiyalari bir xil (takroriy) elementlarni o‘z ichiga olishi mumkin. Kombinatsiya– bu kombinatorikaning asosiy tushunchasidir. Bu tushuncha yordamida ixtiyoriy to‘plamning qandaydir sondagi elementlaridan tashkil topgan tuzilmalar ifodalanadi. Kombinatorikada bunday tuzilmalarning o‘rin almashtirishlar o‘rinlashtirishlar va guruhlashlar deb ataluvchi asosiy ko‘rinishlari o‘rganiladi.Asosiy kombinatsiyalar:1. Takrorsiz o‘rin almashtirishlar. Ta’rif: n elementdan tuzilgan o’rin almashtirish deb shunday birlashmalarga aytiladiki, ularning har biriga berilgan n ta elementning hammasi kiradi , o’rin almashtirishlar bir-biridan faqat elementlarning tartibi bilan farq qiladi.2. O’rinlashtirishlar.Takrorlanmaydigan o’rinlashtirishlar. Ta’rif: n ta elementdan m tadan (nm) o’rinlashtirish deb shunday birlashmalarga aytiladiki , ularning har birida m tadan element bo’ladi: bitta birlashma ikkinchisidan elementlarning tarkibi yoki tartibi bilan farq qiladi.Takrorlanadigan o’rinlashtrishlar. Ta’rif: n elementdan m tadan takrorlanuvchi o’rinlashtirish deb, n ta elementni m talab shunday o’rinlash-tirishga aytiladiki bunda har bir element bir necha marta ishtirok etadi , faqat m martadan oshmasa bo’ldi.
2.Algoritm tushunchasi.
Berilgan ommaviy muammodagi barcha masalalarni umumiy bir xil shaklda, aniq ma’lum bo'lgan usul bilan yechish jarayoni algoritm deb ataladi. Matematikaning asosiy tushun- chalaridan biri algoritm tushunchasidir. Algoritm so'zi (ba’zan, bu so'z algorifm ko'rinishida yoziladi) IX asrda yashab ijod etgan vatandoshimiz, buyuk matematik Abu Abdullo Muhammad ibn Muso al-Xorazmiy nomining lotincha “Algorithmi” tarzida buzib yozilishidan kelib chiqqan. Algoritmning o‘ziga xos xusu- siyatlari. Endi algoritmning o‘ziga xos xususiyatlarini ko‘rib o‘taylik.1 Algoritmning diskretligi. Algoritm - miqdorlarni shunday ketma-ket qurish jarayoniki, boshlang‘ich holatda miqdorlaming dastlabki chekli sistemasi berilgan bo‘lib, har bir navbatdagi momentda miqdorlar sistemasi ma’lum aniqlangan qonun (dastur) asosida oldingi holatdagi miqdorlar sistemasidan hosil qilinadi. Algoritmning determinatsiyalanuvchanligi (aniqlanuvchanligi). Boshlang‘ich holatdan farq qiluvchi boshqa holatda aniqlangan miqdorlar sistemasi ilgarigi holatlarda hosil qilingan miqdorlar sistemasi orqali bir qiymatli aniqlanadi. Algoritm qadamlarining elementarligi. Ilgarigi miqdorlar siste- masidan keyingisini hosil qilish qonuni sodda qadamlardan iborat boMishi kerak. Algoritmning ommavivligi. Boshlang‘ich miqdorlar sistemasini ayrim potensial cheksiz to‘plamdan tanlash mumkin. Algoritmning natijaviyligi. Miqdorlarni topish jarayoni chekli boMishi va natijani (masalaning yechimini) berishi kerak. Matematik amallar asosiy rolni o‘ynaydigan algoritmlar sonli algoritmlar deb yuritiladi.
3.Graflar.
Graflar nazariyasi haqida umumiy ma’lumotlar. 1736- yilda L. Eyler tomonidan o‘sha davrda qiziqarli amaliy masalalardan biri hisoblangan Kyonigsberg1 ko'priklari haqidagi masalaning qo‘yilishi va yechilishi graflar nazariyasining paydo bo‘lishiga asos bo‘ldiAgar grafda yo (a,b) qirra, yo (a,b) yoy, yoki (b,a) yoy topilsa, u holda a va b uchlar tutashtirilgan deyiladi. Agar grafning ikkita uchini tutashtiruvchi qirra yoki yoy bor bo‘lsa, u holda ular qo‘shni uchlar deb, aks holda esa, qo‘shni boMmagan uchlar deb aytiladi. Grafning ikkita uchi qo‘shni bo‘lsa, ular shu uchlami tutashtiruvchi qirraga (yoyga) insident, o‘z navbatida, qirra yoki yoy bu uchlarga insident deyiladi. Grafda ikkita qirra (yoy) umumiy chetga ega bo‘Isa, ular qo‘shni qirralar (yoylar) deyiladi. Shuni ta’kidlash kerakki, qo‘shnilik tushunchasi grafning bir jinsli, insidentlik tushunchasi esa uning turli jinsli elementlari orasidagi munosabatni ifodalaydi. Ba’zan graf undagi elementlar soniga qarab, ya’ni uchlar soni m va qirralar (yoylar) soni n ga qarab beigilanadi va bu holda grafhi (m,n)- graf deb ataydilar. Agar G (V,U) grafda U kortej faqat qirralardan iborat bo‘lsa, u holda yo‘naltirilmagan (oriyentirlanraagan) va faqat yo‘naltirilgan (oriyentirlangan) qirralardan (ya’ni, yoylardan) tashkil topgan bo‘lsa, u holda u yo‘naltirilgan (oriyentirlangan) graf deb ataladi. Oriyentirlangan graf, qisqacha, orgraf deb ham ataladi. Qator hollarda oriyentirlanmagan qirralari ham, oriyentirlangan qirralari ham bo‘lgan graflar bilan ish ko'rishga to‘g‘ri keladi.
4.Pridikatlar va kvantorlar.
Mantiq algebrasida mulohazalar faqatgina chin yoki yolg‘on qiymat qabul qilishi nuqtai nazaridan qaralib, mulohazalarning tuzilishiga ham, hattoki, mazmuniga ham e’tibor berilmaydi. Ammo fanda va amaliyotda mulohazalarning tuzilishi va mazmunidan kelib chiqadigan xulosalardan (natijalardan) foydalaniladi. Masalan, «Har qanday romb parallelogrammdir; ABCD -Predikatlar mantiqi an’anaviy formal mantiq singari elementar mulohazani subyekt va predikat qismlarga bo‘ladi. Subyekt — bu mulohazada biror narsa haqida nimanidir tasdiqlaydi; predikat - bu subyektni tasdiqlash. Masalan, «5 - tub son» mulohazada «5» - subyekt, «tub son» - predikat. Bu mulohazada «5» «tub son bo‘lish» xususiyatiga ega ekanligi tasdiqlanadi Predikatlar ustida mantiqiy amallar Predikatlar ham mulohazalar singari faqatgina chin yoki yolg'on (1 yoki 0) qiymat qabul qiladi. Predikatni mulohazaga aylantirishning yana bir usuli kvantorlardan foydalanishdir. Kvantorlar 2xil bo’ladi: umumiylik va mavjudlik kvantorlari. Umumiylik kvantorlari “har bir”, “hamma”,”barcha” so’zlari bilan ifodalanadi.Mavjudlik kvantori “bor”, “mavjud”,”topiladi” so’zlari bilan ifodalanadi.
5.Daraxt tushunchasi.
Siklga ega bo‘lmagan orientirlanmagan bog'lamli graf daraxt deb ataladi1. Ta’rifga ko‘ra daraxt sirtmoqlar va karrali qirralarga ega emas. Siklga ega bo‘lmagan orientirlanmagan graf o‘rmon (asiklik graf) deb ataladi Uchlari soni m va qirralari soni n bo'lgan G graf uchun quyidagi tasdiqlar ekvivalentdir: 1) G daraxtdir; 2) G asiklikdir va n = m — 1; 3) G bog 'lamlidir va n = m — 1 ; 4) G bog'lamlidir va undan istalgan qirrani olib tashlash amalini qo'llash natijasida bog'lamli bo’l magan graf hosil bo'ladi, ya ’ni G ning har bir qirrasi ко 'prikdir; 5) G grafninng o'zaro ustma-ust tushmaydigan istalgan ikkita uchi faqat bitta oddiy zanjir bilan tutahtiriladi; 6) G asiklik bo'lib, uning qo‘shni bo‘Imagan ikkita uchini qirra bilan tutashtirish amalini qo’llash natijasida faqat bitta siklga ega bo‘Igan graf hosil bo'ladi.
6.Rekursiv to’plamlar.
Biror alfavit berilgan bo'lsin. Bu alfavitdagi hamma so‘zlar to'plamini S bilan va S to‘plamning qism to'plamini M bilan belgilaymiz. 1- ta’rif. Agar x so'zning M to'plamga qarashlilik muammosini hal qila oladigan algoritm mavjud bo'lsa, u holda M rekursiv to‘plam deb ataladi. 2- ta’rif. Agar M to‘plamning hamma elementlarini sanab chiqa oladigan algoritm mavjud bo ‘Isa, u holda M effektiv rekursiv sanaluvchi to‘plam deb ataladi. Agar M va L effektiv rekursiv sanaluvchi to 'plamlar bo ‘Isa, u holda MUL va M^L ham effektiv rekursiv sanaluvchi to 'plam bo 'ladi. Isboti. M va L effektiv rekursiv sanaluvchi to'plamlar bo'lsin. U holda, ularning har biri uchun alohida algoritm mavjudki, ular orqali mos ravishda M va L dagi hamma elementlami sanab chiqish mumkin. MUL va M^L to'plamlaming effektiv sanaluvchi algoritmi M va L to'plamlaming effektiv sanaluvchi algoritmlarini bir vaqtda qo‘llash natijasida hosil qilinadi
7.Qisman rekursiv va sanaluvchi to’plamlar.
Agar x so'zning M to'plamga qarashlilik muammosini hal qila oladigan algoritm mavjud bo'lsa, u holda M rekursiv to‘plam deb ataladi.Agar M to ‘plamning hamma elementlarini sanab chiqa oladigan algoritm mavjud bo ‘Isa, uholda M effektiv rekursiv sanaluvchi to ‘plam deb ataladi. Agar M va L effektiv rekursiv sanaluvchi to 'plamlar bo ‘Isa, и holda MUL va MUL ham effektiv rekursiv sanaluvchi to 'plam bo 'ladi. Isboti. M va L effektiv rekursiv sanaluvchi to'plamlar bo'lsin. U holda, 2- ta’rifga asosan, ularning har biri uchun alohida algoritm mavjudki, ular orqali mos ravishda M va L dagi hamma elementlami sanab chiqish mumkin. MUL va MUL to'plamlaming effektiv sanaluvchi algoritmi M va L to'plamlaming effektiv sanaluvchi algoritmlarini bir vaqtda qo‘llash natijasida hosil qilinadi.
8.Rekursiv funksiyalar.

Agar f(x1,x2,…,xn)=g funksiyaning qiymatini hisoblovchi ketma-ketlik ya’ni algoritm mavjud bo’lsa, bunday funksiyaga effektiv yoki samarali hisoblovchi funksiya deyiladi. Agar f(x1, x2,…,xn) funksiyani boshlang’ich funksiyalardan superpozitsiya, primitiv rekursiya sxemasi va minimallash operatori amallarini chekli son marta qo’llash natijasida hosil etish mumkin bo’lsa, u holda f(x1, x2, …,xn) qismiy rekursiv funksiya deyiladi. Agar f(x1,x2,…,xn) funksiya qismiy rekursiv va argumentlarning barcha qiymatlarida aniqlangan bo’lsa, u holda f(x1,x2,…,xn) umumrekursiv funksiya deyiladi. Har qanday intuitiv hisoblanuvchi funksiya qismiy rekursiv funksiya bo'ladi. Qismiy rekursiv funksiya tushunchasi algoritmlar nazariyasining asosiy tushunchalaridan biridir. Rekursiya — 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^[1]. Rekursiv funksiya oʻzini — oʻzi chaqirgani uchun dasturchilar orasida quyidagi jumla mashhur: „Rekursiya nimaligini tushunish uchun oldin rekursiya nimagligini tushunish kerak“ — Stephen Hawking^[2]. Rekursiya funksional dasturlashning asosiy elementlaridan hisoblanadi. Rekursiya deyarli hamma joyda ishlatiladi. Baʼzi masalalarning iterativ yechimi juda ham uzun boʻlib ketishi mumkin. Rekursiya esa kodni bir necha barobar qisqartirib berishi mumkin. Aksariyat tuzilmalar va algoritmlarni rekursiyasiz tasavvur qilib boʻlmaydi. Tree, Graph, Heap, Quick Sort, Merge Sort, … Bu ro'yhatni juda uzoq davom ettirish mumkin. Ayniqsa, murakkab tuzilmalar boʻlgan Tree va Graphlarda rekursiya har qadamda uchraydi.

9.Predikatlarda teng kuchli formulalar.

Predikatlar mantiqining ikkita A va В formulasi o'z tarkibiga kiruvchi M sohaga oid hamma о‘zgaruvchilarning qiymatlarida bir xil mantiqiy qiymat qabul qilsa, ular M sohada teng kuchli formulalar deb ataladi. Agar ixtiyoriy sohada A va В formulalar teng kuchli bo‘Isa, u holda ular teng kuchli formulalar deb ataladi va A = В kо‘rinishda yoziladi. Agar mulohazalar algebrasidagi hamma teng kuchli formulalar ifodasi tarkibiga kiruvchi o‘zgaruvchi mulohazalar o‘rniga predikatlar mantiqidagi formulalar qo'yilsa, u holda ular predikatlar mantiqining teng kuchli formulalariga aylanadi. Ammo, predikatlar mantiqi ham o ‘ziga xos asosiy teng kuchli formulalarga ega.

10.O’rinlashtirishlar va kombinatsiyalar.
kombinatorika deb ataluvchi bo‘limida chekli yoki muayyan ma’noda cheklilik shartini qanoatlantiruvchi to‘plamni (bu to‘plamning elementlari qanday bo‘lishining ahamiyati yo‘q: harflar, sonlar, hodisalar, qandaydir predmetlar va boshqalar) qismlarga ajratish, ularni o'rinlash va o‘zaro joylash ya’ni, kombinatsiyalar, kombinatorik tuzilmalar bilan bog‘liq masalalar o‘rganiladi. Hozirgi davrda kombinatorikaga oid ma’lumotlar inson faoliyatining turli sohalarida qo‘llanilmoqda. Jumladan, matematika, kimyo, fizika, biologiya, lingvistika, axborot texnologiyalari va boshqa sohalar bilan ish ko‘ruvchi mutaxassislar kombinatorikaning xilma-xil masalalariga duch keladilar. Chekli va n ta elementli to’plamning 1 elementlaridan tuzilib, bir-biridan yoki elementlarining joylashish tartibidn yoki elementlaridan farq qiluvchi va k ta elementdan iborat bo’lgan qism to’plamlariga n elementdan k tadan o’rinlashtirish deyiladi. Kombinatsiya– bu kombinatorikaning asosiy tushunchasidir. Bu tushuncha yordamida ixtiyoriy to‘plamning qandaydir sondagi elementlaridan tashkil topgan tuzilmalar ifodalanadi. Kombinatorikada bunday tuzilmalarning o‘rin almashtirishlar o‘rinlashtirishlar va guruhlashlar deb ataluvchi asosiy ko‘rinishlari o‘rganiladi.Asosiy kombinatsiyalar:1. Takrorsiz o‘rin almashtirishlar. Ta’rif: n elementdan tuzilgan o’rin almashtirish deb shunday birlashmalarga aytiladiki, ularning har biriga berilgan n ta elementning hammasi kiradi , o’rin almashtirishlar bir-biridan faqat elementlarning tartibi bilan farq qiladi.2. O’rinlashtirishlar.Takrorlanmaydigan o’rinlashtirishlar. Ta’rif: n ta elementdan m tadan (nm) o’rinlashtirish deb shunday birlashmalarga aytiladiki , ularning har birida m tadan element bo’ladi: bitta birlashma ikkinchisidan elementlarning tarkibi yoki tartibi bilan farq qiladi.Takrorlanadigan o’rinlashtrishlar. Ta’rif: n elementdan m tadan takrorlanuvchi o’rinlashtirish deb, n ta elementni m talab shunday o’rinlash-tirishga aytiladiki bunda har bir element bir necha marta ishtirok etadi , faqat m martadan oshmasa bo’ldi.
11.Eyler Gamilton graflari.
Grafning har bir qirrasidan faqat bir marta o‘tadigan zanjir Eyler zanjiri deb ataladi. Yopiq Eyler zanjiriga (ja’ni Eyler sikliga) ega graf Eyler grafi deb ataladi. Agar grafda yopiq boMmagan Eyler zanjiri topilsa, u holda bunday graf yarim Eyler grafi deb ataladi. 1- teorema. Bog'lamli graf Eyler graft bo'lishi uchun undagi barcha uchlarning darajalari juft bo ‘lishi zarur va yetarlidir. Grafning har bir uchidan faqat bir marta o‘tadigan zanjir Gamilton zanjiri deb ataladi. Yopiq Gamilton zanjiriga (ja’ni Gamilton sikliga) ega graf Gamilton graft deb ataladi. Agar grafda yopiq bo‘lmagan Gamilton zanjiri topilsa, u holda bunday graf yarim Gamilton grafi deb ataladi.. Uchlari soni uchtadan kam bo ‘Imagan grafdagi istalgan uchning darajasi uchlar sonining yarmidan kam bo ‘Imasa, bu graf Gamilton grafi bo ‘ladi. Agar uchlari soni m ga (m > 2 ) teng bo ‘Igan grafdagi qo ‘shni bo'lmagan ixtiyoriy uchlar darajalari yig'indisi m dan kam bo ‘Imasa, u holda bu graf Gamilton graft bo ‘ladi.
13.Hisoblanuvchanlik va rekursiv funksiyalar.
Hisoblanuvchi funksiyalar. 1- t a ’rif. Agar birorta funksiyaning aniqlanish sohasi ham, qiymatlar sohasi ham natural sonlar to ‘plamining qism to ‘plam lari bo ‘Isa, и holda bunday funksiya arifmetik (sonli) funksiya deb ataladi. Natural sonlar to'plamida berilgan har qanday munosabatlarga arifmetik munosabat deyiladi. Masalan, natural sonlar to'plamida f(x,y) = x-y (ko‘paytma) - ikki argumentli arifmetik funksiyadir, x + y < z - uch argumentli arifmetik munosabat. Arifmetik funksiya va arifmetik munosabat tushunchalari intuitiv tushunchalardir va hech qanday formal sistema bilan bogMangan emas. Arifmetik (sonli) funksiyaning qiymatini hisoblovchi algoritm mavjudligini aniqlash algoritmik muammolardan biridir. 2- ta ’rif. Agar g = f ( x l , x 2,...,xn) funksiyaning qiymatini hisoblovchi algoritm mavjud b o ‘Isa, и holda и effektiv (samarali) hisoblanuvchifunksiya deb ataladi. Bu ta’rifda algoritm tushunchasi intuitiv ma’noda tushunilganligi sababli, effektiv hisoblanuvchi funksiya tushunchasi ham intuitiv tushuncha bo‘ladi. Ammo algoritm tushunchasidan effektiv hisoblanuvchi funksiya tushunchasiga o‘tishning o‘ziga xos ijobiy tomoni bor. Masalan, algoritm tushunchasiga qo‘yilgan hamma talablar (o'ziga xos xususiyatlari sifatida) rekursiv (qaytarish) funksiyalar majmuasi deb ataladigan hamma hisoblanuvchi funksiyalar majmuasi uchun bajariladi. Gyodel birinchi bo‘lib biror formal sistemada aniqlangan hamma sonli funksiyalar sinfini rekursiv funksiyalar sinfi sifatida ifodaladi. 1936-yilda Chyorch ham boshqa asoslarga suyanib rekursiv funksiyalar sinfini tasvirlagan edi. Bu yerda hisoblanuvchi funksiyalar sinfi quyidagicha tuziladi.7- ta ’rif. Agar / ( x , , x 2,...,x n) funksiyani boshlang'ich (oddiy) funksiyalardan superpozitsiya va primitiv rekursiya sxemasi amallarini chekli son marta qo 'Hash natijasida hosil qilish mumkin bo ‘Isa, и holda f (x ,, x2 x n) primitiv rekursiv funksiya deb ataladi.8- t a ’rif. Agar /(x , ,x 2 ,...,x n) funksiyani boshlang'ich funksiyalardan superpozitsiya, prim itiv rekursiya sxemasi va minimallash operatori ( /I -operatori) amallarini chekli son marta qo ‘Hash natijasida hosil etish mumkin b o ‘Isa, и holda / ( x p x,,...,xn) qismiy rekursiv (rekursiv) funksiya deb ataladi. 8- ta’rif primitiv rekursiv funksiyaning ta’rifidan faqat boshlang'ich funksiyalarga qo'shimcha ravishda fl -operatorini qo'llashga ruxsat berilishi bilan farq qiladi. Shuning uchun ham har qanday prim itiv rekursiv funksiya о ‘z navbatida qismiy rekursiv funksiya bo ‘ladi. 9- ta’rif. Agar / ( x , , x 2,...,x n) funksiya qismiy rekursiv va argumentlarning barcha qiymatlarida aniqlangan bo ‘Isa, и holda f (x ,, x 2,..., x n) umumrekursiv funksiya deb ataladi. Shunday qilib, har bir primitiv rekursiv funksiya qismiy rekursiv (rekursiv) funksiya bo'lgani uchun, qismiy rekursiv funksiyalar sinfi primitiv rekursiv funksiyalar sinfidan kengdir. Qismiy rekursiv funksiya tushunchasi algoritmlar nazariyasining asosiy tushunchalaridan biridir. Shuni ham ta’kidlab o'tamizki, birinchidan, har qanday qismiy rekursiv funksiyaning qiymati mexanik xarakterga ega bo‘lgan ma’lum bir protsedura yordamida hisoblanadi va bu protsedura bizning algoritm haqidagi intuitiv tasavvurimizga to'g'ri keladi. Ikkinchidan, hozirgacha qanday muayyan algoritmlar yaratilgan bo‘lmasin, ular yordamida qiymatlari hisoblanuvchi sonli (arifmetik) funksiyalar albatta qismiy rekursiv funksiyalar bo‘lib chiqdilar. Shuning uchun ham hozirgi paytda qismiy rekursiv funksiya tushunchasi algoritm tushunchasining ilmiy ekvivalenti sifatida qabul qilingan. Buni birinchi bo‘lib, yuqorida ta’kidlab o‘tganimizdek, ilmiy tezis sifatida A.Chyorch va S.Klini o ‘rtaga tashladilar. Xuddi shu kabi har qanday algoritmni mos Tyuring mashinasi yordamida realizatsiya qilish mumkin. Algoritmning ilmiy ekvivalenti qismiy rekursiv funksiya bo‘lgani uchun hamma qismiy rekursiv funksiyalar sinfi A bilan Tyuring mashinalari yordamida hisoblanuvchi funksiyalar (Tyuring bo'yicha hisoblanuvchi funksiyalar) sinfi В bilan bir xildir, ya’ni A = В .
14.Algoritmik yechilmas muammo.Vaqt muammosi.

1-ta‟rif. Algoritm - bu ma‘lum bir tilda berilgan, mumkin boʻlgan dastlabki ma‘lumotlar sinfi uchun masalani hal qilish uchun mumkin boʻlgan elementar amallarning cheklangan ketma-ketligi. Masalaning dastlabki ma‘lumotlarining toʻplami D boʻlsin va R - mumkin boʻlgan natijalar toʻplami, shunda algoritm 𝐃 → 𝐑 koʻrinishida tasvirlanadi. Bu tasvirlanish toʻliq boʻlmasligi mumkin. Agar natija faqat ba‘zi 𝑑 ∈ 𝐷 uchun olingan boʻlsa, algoritm qismiy algoritm va agar barcha 𝑑 ∈ 𝐷 uchun toʻgʻri natija olsa toʻliq algoritm deyiladi. 2-ta‟rif. Algoritm - bu cheklangan vaqt ichida masalani yechish natijasiga erishish uchun ijrochining harakatlari tartibini tavsiflovchi aniq koʻrsatmalar toʻplami. Algoritmning aniq yoki bilvosita turli xil ta‘riflari bir qator talablarni keltirib chiqaradi: - algoritmda cheklangan miqdordagi elementar bajarilishi mumkin boʻlgan ketma-ketlik boʻlishi kerak, ya‘ni yozuvning aniqligi talabi bajarilishi kerak; - algoritm masalani yechishda cheklangan sonli bosqichlarni bajarishi kerak, ya‘ni harakatlarning aniqligi talabi bajarilishi kerak; - barcha qabul qilingan kirish ma‘lumotlari uchun algoritm bir xil boʻlishi kerak, ya‘ni universallik talabiga javob berish; - algoritm qoʻyilgan vazifaga nisbatan toʻgʻri yechimga olib kelishi kerak, ya‘ni toʻgʻrilik talabi bajarilishi kerak. Algoritmning asosiy xossalari haqida quyidagilarni ta‘kidlash mumkin: 1-xossa. Diskretlilik, ya‘ni algoritmni chekli sondagi oddiy koʻrsatmalar ketma-ketligi shaklida ifodalash mumkin. 2-xossa. Tushunarlilik, ya‘ni ijrochiga tavsiya etilayotgan koʻrsatmalar uning uchun tushunarli boʻlishi shart, aks holda ijrochi 11 oddiy amalni ham bajara olmay qolishi mumkin. Har bir ijrochining bajara olishi mumkin boʻlgan koʻrsatmalar tizimi mavjud. 3-xossa. Aniqlik, ya‘ni ijrochiga berilayotgan koʻrsatmalar aniq mazmunda boʻlishi lozim hamda faqat algoritmda koʻrsatilgan tartibda bajarilishi shart. 4-xossa. Ommaviylik, ya‘ni har bir algoritm mazmuniga koʻra bir turdagi masalalarning barchasi uchun yaroqli boʻlishi lozim. Masalan, ikki oddiy kasr umumiy maxrajini topish algoritmi har qanday kasrlar umumiy maxrajini topish uchun ishlatiladi. 5-xossa. Natijaviylik, ya‘ni har bir algoritm chekli sondagi qadamlardan soʻng albatta natija berishi lozim. Bu xossalar mohiyatini oʻrganish va konkret algoritmlar uchun qarab chiqish talabalarning xossalar mazmunini bilib olishlariga yordam beradi. Algoritmning tasvirlash usullari haqida gapirganda algoritmning berilish usullari xilma-xilligi va ular orasida eng koʻp uchraydiganlari quyidagilar ekanligini koʻrsatib oʻtish joiz: 1. Algoritmning soʻzlar orqali ifodalanishi. 2. Algoritmning formulalar yordamida berilishi. 3. Algoritmning jadval koʻrinishida berilishi, masalan, turli matematik jadvallar, lotereya yutuqlari jadvali, funksiyalar qiymatlari jadvallari bunga misol boʻladi. 4. Algoritmning dastur shaklida ifodalanishi, ya‘ni algoritm kompyuter ijrochisiga tushunarli boʻlgan dastur shaklida beriladi. 5. Algoritmning algoritmik tilda tasvirlanishi, ya‘ni algoritm bir xil va aniq ifodalash, bajarish uchun qoʻllanadigan belgilash va qoidalar majmui algoritmik til orqali ifodalashdir. Ulardan oʻquv oʻrganish tili sifatida foydalanilmoqda. Boʻlardan E-praktikum yoki E-tili algoritm ijrochisi algoritmik tili ham mavjud. 6. Algoritmlarning grafik shaklda tasvirlanishi. Masalan, grafiklar, sxemalar ya‘ni blok - sxema bunga misol boʻla oladi. Blok sxemaning asosiy elementlari quyidagilar: oval (ellips shakli)-algoritm boshlanishi va tugallanishi, toʻgʻri burchakli toʻrtburchak-qiymat berish yoki tegishli koʻrsatmalarni bajarish. Romb - shart tekshirishni 12 belgilaydi. Uning yoʻnaltiruvchilari tarmoqlar boʻyicha biri ha ikkinchisi yoʻq yoʻnalishlarni beradi, parallelogramm- ma‘lumotlarni kiritish yoki chiqarish, yordamchi algoritmga murojaat - parallelogramm ikki tomoni chiziq, yoʻnaltiruvchi chiziq - blok-sxemadagi harakat boshqaruvi, nuqta-toʻgʻri chiziq (ikkita parallel) - qiymat berish. Algoritmda bajarilishi tugallangan amallar ketma-ketligi algoritm qadami deb yuritiladi. Har bir alohida qadamni ijro etish uchun bajarilishi kerak boʻlgan amallar haqidagi koʻrsatma buyruq deb aytiladi. Algoritmlarni koʻrgazmaliroq qilib tasvirlash uchun bloksxema, ya‘ni geometrik usul koʻproq qoʻllaniladi. Algoritmning bloksxemasi algoritmning asosiy tuzilishining yaqqol geometrik tasviri: algoritm bloklari, ya‘ni geometrik shakllar koʻrinishida, bloklar orasidagi aloqa esa yoʻnaltirilgan chiziqlar bilan koʻrsatiladi. Chiziqlarning yoʻnalishi bir blokdan soʻng qaysi blok bajarilishini bildiradi. Algoritmlarni ushbu usulda ifodalashda vazifasi, tutgan oʻrniga qarab quyidagi geometrik shakl(blok) lardan foydalaniladi. Algoritmlar berilishi va ifodalanishiga qarab: chiziqli, tarmoqlanuvchi va takrorlanuvchi turlarga boʻlinadi. Algoritmning turlari bilan tanishtirganda, avvalo hech qanday shart tekshirilmaydigan va tartib bilan faqat ketma-ket bajariladigan jarayonlarni ifodalaydigan chiziqli algoritmlar aytib oʻtiladi. Algoritm xato natijalarni keltirib chiqaradigan yoki umuman natija bermaydigan boʻlsa, xatolarni oʻz ichiga oladi.
15.Qisman rekursiv va rekursiv funksiyalar.
Agar f(x1,x2 ,...,xn) funksiyani boshlang'ich funksiyalardan superpozitsiya, primitiv rekursiya sxemasi va minimallash operatori amallarini chekli son marta qo ‘llash natijasida hosil etish mumkin bo‘Isa, u holda f( x1, x2,...,xn) qismiy rekursiv (rekursiv) funksiya deb ataladi. Agar f( x1 , x 2,...,xn) funksiya qismiy rekursiv va argumentlarning barcha qiymatlarida aniqlangan bo‘Isa, u holda f(x1, x2,..., xn) umumrekursiv funksiya deb ataladi. g ( y1, y2,.. . ,yk) primitiv rekursiv (qismiy rekursiv) funksiya va x1,x2,…, xn har xil o ‘zgaruvchilar bo'lsin. Agar har bir i (1 <= i <= к) uchun zi o'zgaruvchi x1, x2,…, xn о ‘zgaruvchilarning biri bo'lsa, u holda f(x1, x2,...,xn) = g ( z1, z2,...,zk) funksiya ham primitiv rekursiv (qismiy rekursiv) funksiya bo‘ladi. Agar f(x1,x2,…,xn)=g funksiyaning qiymatini hisoblovchi ketma-ketlik ya’ni algoritm mavjud bo’lsa, bunday funksiyaga effektiv yoki samarali hisoblovchi funksiya deyiladi. Agar f(x1, x2,…,xn) funksiyani boshlang’ich funksiyalardan superpozitsiya, primitiv rekursiya sxemasi va minimallash operatori amallarini chekli son marta qo’llash natijasida hosil etish mumkin bo’lsa, u holda f(x1, x2, …,xn) qismiy rekursiv funksiya deyiladi. Agar f(x1,x2,…,xn) funksiya qismiy rekursiv va argumentlarning barcha qiymatlarida aniqlangan bo’lsa, u holda f(x1,x2,…,xn) umumrekursiv funksiya deyiladi. Har qanday intuitiv hisoblanuvchi funksiya qismiy rekursiv funksiya bo'ladi. Qismiy rekursiv funksiya tushunchasi algoritmlar nazariyasining asosiy tushunchalaridan biridir. Rekursiya — 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^[1]. Rekursiv funksiya oʻzini — oʻzi chaqirgani uchun dasturchilar orasida quyidagi jumla mashhur: „Rekursiya nimaligini tushunish uchun oldin rekursiya nimagligini tushunish kerak“ — Stephen Hawking^[2]. Rekursiya funksional dasturlashning asosiy elementlaridan hisoblanadi. Rekursiya deyarli hamma joyda ishlatiladi. Baʼzi masalalarning iterativ yechimi juda ham uzun boʻlib ketishi mumkin. Rekursiya esa kodni bir necha barobar qisqartirib berishi mumkin. Aksariyat tuzilmalar va algoritmlarni rekursiyasiz tasavvur qilib boʻlmaydi. Tree, Graph, Heap, Quick Sort, Merge Sort, … Bu ro'yhatni juda uzoq davom ettirish mumkin. Ayniqsa, murakkab tuzilmalar boʻlgan Tree va Graphlarda rekursiya har qadamda uchraydi.
17.Tyuring mashinasi.
Agar qandaydir ommaviy muammoni yechish algoritmi ma’lum bo‘lsa, u holda uni realizatsiya qilish uchun shu algoritmda aniq yoritilgan ko'rsatmalarni ijro qilish zarur. Algoritmni realizatsiya qilish jarayonini avtomatlashtirish g ‘oyasi, tabiiyki, inson bajaradigan ishni mashinaga uzatishni taqozo qiladi. Bunday mashinani XX asrning 30- yillarida E.Post va A.Tyuring tavsiya etishgan. Tyuring mashinasi tushunchasi intuitiv ma’lum bo‘lgan hisoblash protsedurasini elementar operatsiyalarga ajratish natijasida hosil bo'lgan. Tyuring ta’kidlaydiki, istalgan mumkin bo‘lgan hisoblashni o ‘tkazish uchun uning elementar operatsiyalarini qaytarish yetarli. Tyuring ayrim turdagi nazariy hisoblash mashinasini izohlab berdi. Bu mashina muayyan mexanik quriima emas, balki «xayoliy» matematik mashinadir. Berilgan ko‘rsatmani bajaruvchi hisoblovchi odamdan yoki mavjud raqamli hisoblash mashinasidan Tyuring mashinasi ikki jihati bilan farq qiladi. Birinchidan, «Tyuring mashinasi» xato qila oimaydi, ya’ni u og‘ishmay (chetga chiqmasdan) ko'rsatilgan qoidani be kami-ko‘st bajaradi. Ikkinchidan. «Tyuring mashinasi» potensial cheksiz xotira bilan ta’minlangan. Endi Tyuring mashinasi tushunchasi bilan batafsil tanishamiz. Tyuring mashinasini quyidagilar to‘liq aniqlaydi. Tashqi alfavit, ya’ni A = {д0, a ,, u2 an} chekli simvollar to‘plami. A to‘plam elementlarining chekli ketma-ketligi A to'plamdagi so‘z deyiladi. So‘zni tashkil etuvchi simvollar soni shu so‘zning uzunligi deyiladi. Masalan, A alfavitning har bir elementi uzunligi lga teng bo'lgan so'zdir. Bu alfavitda so‘z ko'rinishida mashinaga beriladigan axborot kodlashtiriladi. Mashina so‘z ko'rinishida berilgan axborotni qayta ishlab, yangi so‘z hosil qiladi. Ichki alfavit, ya’ni q0,q „ q 2,...,qm,O',Ch,J simvollar. q0,qvq2,-~qm mashinaning chekli son holatlarini ifodalaydi. Istalgan mashinaning holatlari soni tayinlangan bo'ladi. Ikki holatda maxsus vazifa bajariladi: q x mashinaning boshlang'ich (dastlabki) ’ holati, q 0 natijaviy (oxirgi) holati (to'xtash holati). 0 ',C h ,J surilish simvollaridir (mos ravishda, o ‘ngga, chapga va joyida)
2. Tyuring mashinasining ishlashi. Barcha komandalar majmuasi Tyuring mashinasining dasturini tashkil qiladi. Dastur ikki oichovli jadval shaklida bo‘lib, u Tyuring funksional sxemasi deb ataladi. Bunday sxema 1- jadvalda misol sifatida berilgan. Tyuring mashinasining ishi butunlayiga uning dasturi bilan aniqlanishi ravshan. Agar ikkita Tyuring mashinasining funksional sxemalari bir xil bo‘lsa, u holda ular bir-biridan farq qilmaydi. Har xil Tyuring mashinalari har xil dasturga ega bo‘ladi. Bundan keyin Tyuring mashinasining har xil konfiguratsiyalarini (ko‘rinishlarini) soddaroq ifodalash uchun lenta va uning katakchalarini ifodalamasdan axborotni faqat so‘z shaklida yozamiz: Boshqaruvchi kallak va mashina holatini ifodalash sifatida mashina holatini yozamiz.
Tyuring mashinasida o‘nlik sistemada n dan n + 1 ga o‘tish algoritmini realizatsiya qilish. 0 ‘nlik sanoq sistemasida n sonning yozuvi berilgan bo‘lsin va n +1 sonning o ‘nlik sistemasidagi yozuvini ko'rsatish, ya’ni / (n) = n +1 funksiyani hisoblash talab etilsin. Ravshanki, mashinaning tashqi alfaviti 0,1,2,3,4,5,6,7,8,9 raqamlardan va bo‘sh katakcha a 0dan iborat bo‘lishi kerak. Lentaga o ‘nlik sistemada n sonini yozamiz. Bu yerda qatorasiga bo‘sh joysiz har bir katakchaga bitta raqam yoziladi. Qo^yilgan masalani yechish uchun ishning birinchi taktida mashina n sonning oxirgi raqamini o‘chirib, uni bir birlik katta songa almashtirib va agar oxirgi raqam 9 sonidan kichik bo‘lsa, u holda to‘xtash holatiga o‘tishi kerak. Agar n sonning oxirgi raqami 9 bo‘lsa, u holda mashina 9 raqamni o‘chirib, bo‘sh qolgan katakchaga 0 raqamni yozib, o‘sha holatda qolgan holda chapga yuqoriroq razryadli qo‘shnisiga surilishi kerak. Bu yerda ishning ikkinchi taktida mashina yuqoriroq razryadli raqamga 1 sonini qo‘shishi kerak. Tabiiyki, chapga surilish paytida yuqoriroq razryadli raqam bo'lmasa, u holda mashinaning boshqaruvchi kallagi bo‘sh katakchaga chiqishi mumkin. Bu holatda bo‘sh katakchaga mashina 1 raqamini yozadi. Aytilganlardan shu narsa kelib chiqadiki, f (n) = n + 1 funksiyani hisoblash algoritmini realizatsiya qilish paytida mashina bor yo‘g‘i ikkita q1, va q2holatlarda bo‘ladi.
19.Paradokslar va sofizimlar.