R va maf” fakulteti 812-21- guruh ca

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

“R va MAF” FAKULTETI

812-21- guruh CAL021 - patok talabasi
Jo`rayeva Mohinurning
“Algoritmlarni loyihalash”
fanidan tayyorlagan

MUSTAQIL ISHI

Topshirdi: Jo`rayeva M.
Tekshirdi: Begimov O‘. 

Toshkent – 2023

Mavzu: To`plamlarda qisqartma akslantirishlar. Ularning va amaliy tadbiqlariga misollar.

REJA:

1. 
   To`plamlarda qisqartma akslantirishlari.
   2. To`plamlarda qisqartma akslantirishlarning amaliy tadbiqlari.
   3. To`plarlarni dasturiy tillarda ishlash va uning algoritmlari.
   

4. Xulosa
5.Foydalanilgan adabiyotlar.
Tayanch iboralar:
To’plam, to’plamlarning akslantirishla, to’plamlarning qo’shish(birlashmasi), to’plamlarning ayirmasi(kesishmasi), to’plamlarning amaliyotda yechish usullari, to’plamlar ustida amallar, to’plam ayirmasi, to’plamalarning simmetrik ayirmasi, to’plamlarning dasturiy yechish usullari, to’plamlarning yechishda tuziladigan blok sxemalari.

Toplamni tashkil etuvchilar shu toplamning elementlari deb ataladi. Toplamlar nazariyasida toplamning elementlari bir-biridan farqli deb hisoblanadi, yani muayyan bir toplamning elementlari takrorlanmaydi.
Toplamni tashkil etuvchi elementlar soni chekli yoki cheksiz bolishi mumkin. Birinchi holda chekli toplamga, ikkinchi holda esa, cheksiz toplamga ega bolamiz.
Toplamlarni belgilashda, odatda, lotin yoki grek alifbosining bosh harflari, uning elementlari uchun esa alifboning kichik harflari qollaniladi. Toplamni tashkil etuvchi elementlar figurali qavslar orasiga olinib ifodalanishi mumkin. Masalan, toplamning elementlardan tuzilganligini korinishda yozish mumkin.
B to‘plamlar kesishmasini ta’riflaymiz. A va B to‘plamlarning
umumiy elementlaridan tashkil topgan to‘plam ularning kesishmasi deyiladi (1.2-
chizmaga qarang) va AI B shaklda belgilanadi.


Ixtiyoriy (chekli yoki cheksiz) sondagi to‘plamlarning kesishmasi
−IaAa
deb Aa to‘plamlarning barchasiga tegishli bo‘lgan elementlar to’plami tushuniladi.
To‘plamlar yig‘indisi va kesishmasi aniqlanishiga ko‘ra kommutativ va
assotsiativdir, ya’ni

AUB=BUA (AUB)UC=AU(BUC)
AIB=BIA (AIB)IC=AI(BIC)
Bundan tashqari, ular o‘zaro distributivlik qonunlari bilan bog‘langan

(AUB)IC=(AIC)U(BIC) (1.1 )
(AI B) UC = (AU C) I (B U C) (1.2)

Akslantirishlar.
Ko’pgina hollarda diskret matematika va uning tatbiqlarida o’rganish ob’yekti sifatida to’plam bilan birga uning tuzilishi ham ahamiyatga ega bo`ladi.
Ma’lumki, odatdagi arifmetika, geometriya ob’yektlari bilan sonli amallarni bog’laydigan chiziqli fazo hamda biror binar munosabat aniqlangan to’plamlar asosida maydon tushunchasi kiritiladi. Barcha bunday strukturalar algebraik sistemalarni tashkil etadi. Algebraik sistemalarning aniq ta’rifini keltiramiz.
Bo’sh bo’lmagan A to’plamni qaraymiz. Bu to’plamda n-o’rinli f akslantirishni kiritamiz: f : An → A. f funksiya bo’lganligi sababli, ixtiyoriy
elementlar uchun f amalini qo’llash natijasi bir
qiymatli aniqlanadi. f amalining qiymatlar sohasi A to’plamga tegishli bo’lgani uchun f amalni A to’plamda yopiq amal deb ataymiz.
Signatura yoki til ∑ deb o’rni ko’rsatilgan predikat va funksional simvollar to’plamiga aytiladi. 0-o’rinli funksional simvolga constanta deyiladi.
∑ signaturali algebraik sistema U={A, ∑} deb bo’sh bo’lmagan A to’plamga aytiladi, bunda har bir n o’rinli predikat (funksional) simvolga A
to’plamda aniqlangan n-o’rinli predikat mos qo’yilgan. A to’plam {A, ∑} algebraik sistemaning tashuvchisi yoki universumi deb ataladi.
∑ dagi simvollarga mos keluvchi predikatlar va funksiyalar interpretatsiyalar deyiladi.
Algebraik sistemaning quvvati deb A “tashuvchi”ning quvvatiga aytiladi.
Nyuton binomi - ikki qo'shiluvchi yig'indisining ixtiyoriy butun msubat darajasi qo'shiluvchilar darajalari yig'indisi ko'rinishda ifodalovchi formula.Binomial koeffisiyentlari arifmetik uchburchak tashkil qiladi. N.b. formulasi I. Nyutondan ancha avval ham ma'lum boʻlgan. Mac, Umar Xayyom (11-12 a.lar), Jamshid Koshiy (14-15-a.lar) binomial koeffitsiyentlarni hisoblash qoidasini bilganlar.

Maktab kursidan maʼlumki

(a + b)²= a² + 2ab+b²

• (a + b)³= a³ +3a2b+3ab² + b²

Takrorli orin almashtirishlar. Kombinatorikada oldin qaralgan
birlashmalardan tashqari tarkibidagi elementlari takrorlanishi mumkin bolgan boshqa birlashmalar ham organiladi. Masalan, takrorlanuvchi elementlar qatnashgan orin almashtirishlar, orinlashtirishlar va gruppalashlar.
Avval organilgan orin almashtirishlar shunday tuzilmalar ediki, ular
tarkibidagi elementlar bir-biridan farq qilardi. Endi orin almashtirishlar tarkibidagi elementlar takrorlanishi mumkin bolgan holni qaraymiz. Tabiiyki, aynan bir xil elementlar orinlari almashtirilishi natijasida yangi orin almashtirish hosil bolmaydi. Shuning uchun tarkibidagi elementlari soni ozgarmaganda elementlari takrorlanishi mumkin bolgan orin almashtirishlar soni turli elementlardan tashkil topgan orin almashtirishlar soniga qaraganda kichik boladi.
Faraz qilaylik, qandaydir kortejning n ta elementlari orasida bir xil (aynan bir xil) ta birinchi tur, bir xil ta ikkinchi tur, va hokazo, bir xil ta k - tur elementlar bolsin, bu yerda ,, hech bolmaganda bittasi 1dan farqli natural sonlar. Bu n ta elementlarning orinlarini imkoniyati boricha almashtirishlar natijasida hosil bolgan kortejlar (kombinatsiyalar) takrorlanuvchi elementlar qatnashgan orin almashtirishlar (qisqacha, takrorli orin almashtirishlar) deb ataladi.
Dastlab graflar haqida qisqacha tarixiy ma'lumotlar, grafning abstrakt matematik tushuncha sifatidagi ta'rifi va u bilan bog'liq boshlang'ich tushunchalar, graflarning geometrik ravishda, maxsus turdagi ko'phad yordamida, qo'shnilik va insidentlik matritsalari vositasida berilishi yoritiladi. So'ngra grafning elementlari ustida sodda amallar, graflari birlashtirish, biriktirish va ko'paytirish amallari, mar shrutlar va zanjirlar, grafning bog'lamliligi tushunchasi, Eyler va Gamilton graflari, graflarda masofa tushunchasi, minimal masofali yo'l haqidagi masala, daraxt va unga ekvivalent tushunchalar, grafning siklomatik soni bayon qilinadi. Tarmoq tushunchasi, tar-moqdagi oqimlar, maksimal oqim haqidagi masala va bu masalalarni hal qilish uchun Ford algoritmi ham ushbu bobda keltiriladi.
Graflar nazariyasming boshlang'ich ma'lumotlari
Graf, uch, qirra, yoy, yo'nalish, orgraf, qo'shni uchlar, yakkalangan uch, karrali qirralar, multigraf, psevdograf nolgraf, to 'la, belgilangan va izomorf grafiar, grafning geometrik ifodalanishi, uchlar, qirralar va yoylar insidentligi.
Graflar nazariyasi haqida umumiy ma'lumotlar.
1736-yilda L. Eyler tomonidan o'sha davrda davrda qiziqarli amaUy masalalardan bin hisoblangan Kyonigsberg ko'priklari haqidagi masalaning qo'yi va yechilishi graflar nazariyasining paydo bo'lishiga bo'ldi.
Daraxt va unga ekvivalent tushunchalar. Siklga ega bo'lmagan oriyentirlanmagan bog'lamli graf daraxt deb ataladi. Ta'rifga ko'ra, daraxt sirtmoqlar va karrali qirralarga ega emas. Siklga ega bo'lmagan oriyentirlanmagan graf о'rmon (asiklik graf) deb ataladi.
1-misol.1-shaklda bog'lamli komponentali soni beshga teng bo'lgan graf tasvirlangan bo'lib, u o'rmondir. Bu grafdagi bog'lamli komponentalarning har bin daraxtdir.


2-misol 2-shaklda to'rtta uchga ega bir-biriga izomorf bo'lmagan barcha (ular bor-yog'i ikkita) daraxtlarning geometrik ifodalanishi tasvirlangan.Beshta uchga ega birbiriga izomorf bo'lmagan barcha daraxtlar uchta, oltita uchga ega bunday barcha daraxtlar esa oltita ekanligini ko'rsatish qiyin emas.
Daraxt tushunchasiga boshqacha ham ta'rif berish mumkin. Umuman olganda, G(m,n)-gvaf uchun daraxtlar haqidagi asosiy teorema, deb ataluvchi quyidagi teorema o'rinlidir.
1-teorema. Uchlari soni m va qirralari soni n bo 'Igan G graf uchun quyidagi tasdiqlar ekvivalentdir:
G daraxtdir;
G asiklikdir va n=m—l;
G bog'lamlidir va n=m—\;
Induksion o'tish: G daraxt uchun k>2 vam=k bo'lganda, 2) tasdiq o'rinli bo'lsin deb faraz qilamiz. Endi uchlari soni m=k+l va qirralari soni n bo'lgan daraxtni qaraymiz. Bu daraxtning ixtiyoriy qirrasini (vp v2) bilan belgilab, undan bu qirrani olib tashlasak, Vj uchdan v2 uchgacha marshruti (aniqrog'i, zanjiri) mavjud bo'lmagan grafni hosil qilamiz, chunki agar hosil bo'lgan grafda bunday zanjir bor bo'lsa edi, u holda G daraxtda sikl topilar edi. Bunday bo'lishi esa mumkin emas.
Daraxt va unga ekvivalent tushunchalar. Siklga ega bo'lmagan oriyentirlanmagan bog'lamli graf daraxt, deb ataladi1. Ta'rifga ko'ra, daraxt sirtmoqlar va karrali qirralarga ega emas. Siklga ega bo'lmagan oriyentirlanmagan graf о'rmon (asiklik graf), deb ataladi.
1-misol.1-shaklda bog'lamli komponentali soni beshga teng bo'lgan graf tasvirlangan bo'lib, u o'rmondir. Bu grafdagi bog'lamli komponentalarning har bin daraxtdir. ■
2-misol 2-shaklda to'rtta uchga ega bir-biriga izomorf bo'lmagan barcha (ular bor-yog'i ikkita) daraxtlarning geometrik ifodalanishi tasvirlangan.Beshta uchga ega birbiriga izomorf bo'lmagan barcha daraxtlar uchta, oltita uchga ega bunday barcha daraxtlar esa oltita ekanligini ko'rsatish qiyin emas.
Daraxt tushunchasiga boshqacha ham ta'rif berish mumkin. Umuman olganda, G(m,n)-gvaf uchun daraxtlar haqidagi asosiy teorema, deb ataluvchi quyidagi teorema o'rinlidir.