|
22. Ma’ruza Mavzu: Graflarda erkin uchlarni tanlash, bo`yash. To`plamlarning to`plam ostilarini aniqlash, birlashtirish
|
| Sana | 09.06.2024 | | Hajmi | 67,62 Kb. | | #261881 |
Bog'liq 22. Ma\'ruza
22. Ma’ruza
Mavzu: Graflarda erkin uchlarni tanlash, bo`yash. To`plamlarning to`plam ostilarini aniqlash, birlashtirish.
Graflar nazariyasini o`rganayotganimizda, graflarni bo`yash bo`lmida biz bir xil rangdagi uchlarning bo`lmasligi sharti bilan graf uchlari masalasini ko`rib chiqqan edik. Shu bilan birga, ushbu masalani hal qilish uchun zarur bo`lgan ranglarning minimal sonini aniqlash to`g`risida savol tug`ildi. Xuddi shu masala, shunday shart ostida graf qirralarini bo`yash masalasi paydo bo`ladi. Bir xil ranglardagi qirralari hech bir uchlarida kesishmasligi kerak. Ushbu masalani vizual ravishda, grafning geometrik tasviri mavjud bo`lganda, tanlov usuli bilan hal k
qilish mumkin.
Bizga G –garf V={1,2,3,4,5,6} uchlari bilan berilgan bo`lsin va uning 11 ta qirralari U={a,b,c,d,e,f,g,h,k,e,n} bo`lsin (1-rasm).
4 e
2 2 f
a 1 b 5g 1 3
1 2 c k 5 n
d 4 3 4
1 l
6
rаsm
Graf uchlarini bo`yashning mumkin bo`lgan variantlaridan biri quyidagicha bo`lishi mumkin. Birinchi uchini yashilrangga bo`yaymiz. Savol tug`iladi yana qaysi uchlarni yashilrangga bo`yashimiz mumkin, ya’ni bo`sh (ozod) uchini olishimiz uchun. Bu holda, biz 2-chi, 4-chi, 5-chi, 6-chi uchlarni olmaymiz ular 1-chi bilan bog`langan, shu sababli 3-chini olamiz u 1-chi bilan bog`lanmagan. Shunday qilib, biz 1- chiva 3-chi uchlarni yashilrangga bo`yaymiz. Qolgan uchlarni bo`yash uchun boshqarangni tanlaymiz, masalan sariq rangni 2-chi uchi uchun tanlaymiz. Shunday qilib, biz 1,2,3 uchlarni bo`yab bo`ldik. Keyinggi bosqichda biz bo`sh, ya’ni ushbu uchlar bilan bog`lanmagan uchlarni topishga harakat qilamiz. Bunday uch yo`q, shundan so`ng rang berib bo`yash uchun biz boshqa yangi rang tanlashimiz kerak bo`ladi. Endi 6-chi uch uchun biz qizil rangni tanlaymiz. Keyin, masalaning talablariga rioya qilgan holda, 4-chi uch uchun sariq rangni, 5-chi uch uchun esa qizil rangni tanlashimiz mumkin. Natijada, uchlarni bo`yash uchun uchta rang yetarli degan xulosaga keldik. Ushbu jarayonni avtomatlashtirish uchun qo`shni (aralash) matrisa asosida uchlarning ranglarini tanlash algoritmini tuzib, va uning dasturini tuzish kerak bo`ladi.
Graf qirralarini bo`yashni boshlash uchun biz eng katta karrali uchlarini tanlab va bu uchlaridan chiqadigan qirralariga xar xil ranglarni tanlashimiz lozim. Keyin iloji boricha qolgan qirralarni bo`yash paytida ushbu ranglarni kombinasiyalashtiramiz (almashtiramiz). Xususan, biz misol uchun quyidagi qirralarni bo`yash variantini ko`rib chiqamiz.
Bu yerda 1,2,3,4,5 raqamlar bilan xar hil ranglar belgilangan.
Axborot texnologiyalaridagi aktual amaliy dolzarb muammolaridan biri bu ma’lum bir sinf masalalarini hal qilish uchun zarur bo`lgan belgilarning sonni aniqlashdir. Elektron kompyuterlarni yaratish arafasida biz bunday muammoga duch keldik. Bu muammo asosan amaliy, texnik jixatidan amalga oshiriladigan va axborot xarakteridagi masalalardir. Shu nuqtai nazardan, eng maqbul bo`lgan, faqati kkita 0 va 1 raqamlari asosida qurilgan hisoblashning ikkilik tizimi bo`lib, butun axborot va operasion tizimlar shu asosida qurilgan. Muammoning mohiyatini aniqlash uchun biz to`plamning kichik to`plamlarini qurish masalasini ko`rib chiqamiz.
1. Bizga n elementdan iboratA={a1,a2,…,an} to`plam berilgan bo`lsin. Ushbu to`plam elementlaridan nechta turli kichik to`plamlar qurish mumkin? Biz ushbu kichik to`plamlarning asosiy xususiyatlaridan kelib chiqib tekshirib ko`ramiz. A1 –to`plam bitta elementdan iborat kichik to`plamlardan biri. Bunday kichik to`plamlar soni n tabo`ladi, ya’n iular{a1}, {a2},…,{an}ga teng.Umumiylik uchun m(A1)=Cn1 formulani tavsiya etishimiz mumkin. Xuddi shunday, Ak uchun kelementlardan tashkil topgan to`plam lar kichik to`plami uchun m(Ak)=Cnk formulani tavsiya etishimiz mumkin. Shunday qilib, n to`plamdan iborat bo`lgan to`plamning barcha kichik to`plamlari to`plamining quvvatini quyidagi formula orqali ko`rishmumkin.
Izoh: Bu yerda A to`plamning bo`sh to`plamiga mos keladi, lar A to`plamning o`ziga mos keladi, A to`plam o`z o`ziga to`plam osti hisoblanadi. M ning qiymatini aniqlash uchun Nyuton binomi formulasini esga olamiz.
(1)
Agar (1) formulaning ikkala tomonini a=1; b=1deb olsak, u holda quyidagini olamiz
(2)
Shunday qilib biz to`plam ostilari sonining formulalarini oldik. (2) formulaning shakli bo`yicha, biz to`plamning barcha to`plam ostilarini aniqlash va saqlash masalasini NP –sinfiga tegishli vaqt va hajm masalasi degan xulosaga kelishimiz mumkin.
(2) formulani yana boshqa usul bilan ham tasniflash mumkin. Bizda faqat ikkita a va b xariflar bor deb olib, ulardan n uzunlikdagi qancha so`z hosil qilish mumkin? Izoh: hosil qilingan so`zlardagi xarflar takrorlanishi mumkin va har qanday xarflar ketma-ketligi lug`aviy ma’nosidan qat’iy nazar, so`z sifatida qabul qilinadi.
Natijada, foydalanilgan algoritmik tilning alifbosiga kiritilgan barcha muhim belgilarni ko`rsatish uchun zarur bo`lgan kompyuter so`zining uzunligini aniqlash uchun bo`lgan muhim formulani olamiz. Quyidagi tengsizlikdan
Shu tengsizlikni qanoatlantiruvchi minimal n nitopamiz. Bu esa shu so`zning uzunligi bo`ladi. Bu yerda S –so`zdagi belgilar soni bo`ladi.
Kompyuterlardagi bayt atamasi so`zning uzunligi sifatida ishlatiladi, bu sakkiz bitga to`g`ri keladi, bu yerda bit bitta (0 yoki 1) belgidan iborat. Shunday qilib, agar biz n=8(bittabayt) deb olsak, u holda biz quyidagi formulada qamrab olinadigan belgilar sonini ko`ramiz.
Bu shuni anglatadiki, har bir o`nlik sonlar 0,1,2,…,9 ga va lotin yoki ruscha harflarga, arifmetik amallar belgilari va boshqalarga bittadan bayt ajratilgan. Kompyuter ma’lumotlarini kodlash va shifrlash qabul qilingan kodlash qoidalariga muvofiq amalga oshiriladi.
Axborot xavfsizligi sohasida kodlash masalalari bilan ham tenishib chiqamiz. Dunyoda juda katta miqdordagi ma’lumotlar bazalari mavjud, ularning ba’zilariga bemalol kirishingiz mumkin. Bu holda biz internetdan foydalanishimiz va ko`plab masalalar bo`yicha ma’lumot olishimiz mumkin. Shu bilan birga, ma’lumotlar cheklangan bo`lishi kerak bo`lgan sohalar ham mavjud. Bunday hollarda, xavfsizlik maqsidida ular qulf-kalit rolini o`ynaydigan turli xil shifrlardan (parollardan) foydalanadilar. Qulfningishonchliligiushbubazadatasodifiyfoydalanuvchikirishimumkinliginisanabo`tgandanso`ng, mumkinbo`lganvariantlarsonibilanbaholanadi. Xakkerlar deb ataladiganlar ba’zan bunday ma’lumotlar bazasiga kirishga muvaffaq bo`lishadi. Buning oqibatida qimmatbaho ma’lumotlar yoki katta miqdardagi pullarni egallab olishlari mumkin. Bularning barchasi axborot xavfsizligi tizimlarini takomillashtirishni talab qiladi.
Biz bu yerda faqat parolni tanlash uchun raqamlar va harflardan foydalanish variantlariga e’tibor qaratamiz. Buning uchun biz n tartibli o`nlik raqamlari shaklidagi parol tanlash imkoniyatlari sonini aniqlaymiz. Bunday holda, variantlar soni quyidagicha bo`ladi.
(3)
Chunki bu holda mumkin bo`lgan variantlar soni:
Agar parol harflar va raqamlardan tuzilgan bo`lsa, masalan, lotin alifbosining dastlabki ikkita belgisi, qolgan to`rtta belgi o`nlik raqamlar bo`lsa, unda mumkin bo`lgan variantlarning soni ga teng bo`ladi.
(3) formuladan va misoldan ko`rinib turibdiki, bu holdabizNP –sinfidagi masalaga duch kelamiz. Shunday qilib, agar biz 26 taharfva 10 ta raqamni saqlagan holda parolning belgilari sonini ko`paytirsak, unda nta belgidan iborat parol parametrlari sonini olamiz, ularning k tasoni esa:
(4)
Ko`rib turganimizdek, bu yerda biz eksponinsial murakkabligidagi algoritmni olamiz.
Matnli ma’lumotlarni ma’lum bir tilda qayta ishlashni biz ushbu turdagi algoritmlarda ko`rishimiz mumkin. Bunday holda, tegishli tilning harflari belgilar bo`ladi va ular to`plamni tashkil etadi. Muayyan to`plam osti tartibidagi elementlarning har qanday to`plami so`zni ifodalaydi. Bu elementlar ketma ketligi bo`lishi mumkin yoki qandaydir qator belgilari bo`lishi mumkin. Agar alfavitdagi belgilar soni m bo`lsa, u holda k harflarning so`zlari soni quyidagicha bo`ladi.
Shunda ko`pi bilan nta harflardan iborat bo`lgan barcha so`zlarning soni quyidagiga teng:
(5)
Ensiklopedik lug`atlarni tuzishda bizning oldimizda tilning katt ahajmdagi ma’lumotlarni qayta ishlash vazifasi turibdi. Masalan m=26 va n=6 bo`lganda (5) formuladan quyidagi qiymatni olamiz:
N=321272406.
E’tibor bering, agar biz n=7ni olsak, ya’ni yetti harfdan iborat so`zlarni qo`shsak, u holda ushbu ma’lumotlarga 8.031.810.176 ta so`zlar haqida ma’lumotlar qo`shiladi. Bunday ma’lumotlarni qayta ishlash dasturlarini yoki bitta tildan boshqa tilga tarjima qilish dasturlarini tizimda mutaxassislar qanday murakkab muammolarga duch kelishayotganini tasavvur qilish qiyin emas. Lekin ushbu tillarni biladigan odam uchun bu vazifa oddiy bo`lib tuyulsa da, dasturiy ta’minotni amalga oshirish nuqtai nazardan bu vazifalar juda murakkab vazifalardir.
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
22. Ma’ruza Mavzu: Graflarda erkin uchlarni tanlash, bo`yash. To`plamlarning to`plam ostilarini aniqlash, birlashtirish
|
