|
2.6. Veych xaritasi
Veych xaritasi(uning modifikatsiyasini Karno diagrammasi deb atashadi) – 5-6 ta argumentdan iborat bo`lgan bull funksiyalarini turli xil oson o`zgartirishga imkon beradigan ajoyib ixtiro.
Avval ikkita argumentning xaritasini ko`rib chiqamiz(1-rasm). Xaritaning chap qismining yarmiA harfi bilan ifodangan, o`ng qismi esa huddi o`sha harfning inversiyasi bilan. Xarita gorizontal bo`yicha ham ikki qismga ajralgan. Yuqori qismi B harfi bilan, quyi qismi esa B bilan ifodalangan.
1-rasm 2-rasm
nazorat savollari.
Graf deganda nimani tushunasiz?
Tugun tushunchasini izohlang.
Graflar qanday usullarda tasvirlanadi?
Graflarni qanday ko`rinishlarda tasvirlash mumkin. Chizmalar bilan tushuntiring.
Yo`naltirilgan graflar ustida qanday strukturaviy o`zgartirishlar bajariladi?
Insedent tushunchasini izohlang.
Graflarda yo`l va kontur tushunchasini izohlang.
Yo`l yoki kontur uzunligi qanday aniqlanadi?
Graflarni ifodalashning qanday usullari mavjud?
Qachon matritsa aloqadorlik matritsasi deyiladi?
Insedentlik matritsasi haqida tushuncha bering.
Tizimning strukturaviy sxemasini tasvirlashda graflar qurishni tushuntiring.
Graflarda Mezon formulasida yo`l va konturlarni hisoblashni tushuntiring.
Eng qisqa yo`lni aniqlashni Deykstra algoritmini tushuntiring.
Graflardagi yoy vaznlari nimani bildiradi?
Grafning boshlang`ich manzili deganda nimani tushunasiz?
CHekli avtomatlar. Asosiy tushuncha va ta’riflar.
Avtomatikada diskret qurilmalarning ikki turi ajratiladi. Birinchi turdagi qurilmalarning har bir vaqt momentidagi chiqish signallari shu vaqt momentidagi kirish signallari bilan aniqlanadi, bu oldingi vaqt momentlarida kirish signallari qanday qiymatlarni qabul qilganligiga bog‘liq emas. Bunday turdagi qurilmalarda xotira elementi bo‘lmaydi. Bu turdagilar kombinatsion qurilmalar deb ataladi.
Ikkinchi turdagi qurilmalar xotira elementi mavjudligi bilan xarakterlanadi. Bu qurilmalardagi chiqish signalining qiymati kirish signalining nafaqat ayni vaqtdagi qiymatiga, balki oldingi vaqt momentlarida qanday qiymatni qabul qilganligiga ham bog‘liq. Ikkinchi turdagi qurilmalar avtomatlar nomini olgan. Avtomatning «xotirasi» kirish signallari ta’siri ostida qabul qilishi va oxirgilari o‘zgarganda saqlab qolishi mumkin bo‘lgan turli xil ichki holatlar bilan aniqlanadi.
Avtomatlar axborotning diskret o‘zgartirgichlari bo‘lib, turli holatlarni qabul qilishi, kirish signallari ta’sir ostida bir holatdan ikkinchisiga o‘tish va chiqish signallari hosil qilish imkoniga ega bo‘ladi.
Agar avtomatning holatlari to‘plami, shuningdek kirish va chiqish signallarining to‘plami chekli bo‘lsa, u chekli avtomat deb ataladi. Barcha mavjud avtomatlar chekli hisoblanishadi.
Avtomatning kirishiga tushgan axborotni va o‘zgartirilgan (chiqish) axborotni kodlash uchun simvollarning chekli to‘plami qabul qilingan. Bu to‘plam alifbo deb, alifboni tashkil etuvchi alohida belgilar esa harflar deb, ushbu alifbodagi harflardan tuzilgan istalgan tartibli ketma-ketlikka esa so‘zlar deb aytiladi. Masalan, X={x1,x2} alifbosida so‘zlar quyidagicha bo‘ladi: (x1), (x2), (x1x1), (x2x1x2) va h.k.
Axborotni avtomat orqali diskret o‘zgartirish jarayonini alifbo operatorlari orqali yozish mumkin.
Alifbo operatori F deb alifboning kirish va chiqish so‘zlari orasidagi istalgan muvofiqlikka (funksiyaga) aytiladi.
Avtomatlar natural sonlar bilan ifodalanuvchi t=0,1,2,...,n diskret vaqt momentlarida ishlaydi. Har bir diskret vaqt momentida avtomatning kirishiga bitta signal (harf) tushadi, avtomatning ma’lum holati qayd qilinadi va chiqishidan bitta signal olinadi.
Mavjud avtomatlar bir necha kirish va bir necha chiqishlarga ega bo‘lishi mumkin. Ba’zi hollarda bunday avtomatlarni bir kirish va bir chiqishga ega bo‘lgan avtomatlar bilan almashtirgan qulaydir. Buning uchun dastlabki avtomatning kirish va chiqish signallarini mos tarzda kodlashning o‘zi etarli bo‘ladi. Misol uchun, agar avtomat har biridan 0 yoki 1 signallari tushuvchi ikkita kirishga ega bo‘lsa, kirish signallarining barcha bo‘lishi mumkin bo‘lgan kombinatsiyalarini to‘rtta harf orqali kodlash mumkin: (0,0)=X1, (0,1)=X2, (1,0)=X3, (1,1)=X4. Bunda ikkita kirishga ega bo‘lgan avtomatni to‘rtta harfli alifbodagi signal tushuvchi bir kirishga ega avtomat sifatida qarash mumkin.
CHekli avtomatni berish uchun quyidagilarni ko‘rsatish lozim:
- mumkin bo‘lgan kirish signallari to‘plami X={x1,x2,...,xm};
- mumkin bo‘lgan chiqish signallari to‘plami Y={y1,y2,...,yk};
- avtomatning mumkin bo‘lgan ichki holatlari to‘plami A={a1,a2,...,an};
- o‘tish funksiyalari, bu funksiyalar vaqtning t momentidagi avtomat holati a(t) va kirish signalining qiymati X(t) lardan kelib chiqib, diskret vaqtning t+1 momentidagi avtomat holatini aniqlaydi;
- chiqish funksiyalari, bu funksiyalar vaqtning t momentidagi chiqish signalining avtomat holati va kirish signalining qiymatiga bog‘liqligini aniqlaydi. Bundan tashqari, avtomatning holatlar to‘plamidagi ichki holatlardan birini boshlang‘ich holat sifatida qayd etib qo‘yadi.
CHekli avtomatlarning ikki turi mavjud. Birinchi turdagi avtomatlarning o‘tish va chiqish funksiyalari quyidagicha bo‘ladi:
a(t+1)=f[a(t),x(t)], y(t)=[a(t),x(t)].
Bu turdagi avtomatlarning berilgan taktdagi chiqish signali ichki holat va ushbu holatdagi kirish signali orqali aniqlanadi. Bunday avtomatlarga Mili avtomatlari deb nom qo‘yilgan.
Ikkinchi turdagi avtomatlar berilgan taktdagi chiqish signalining faqat shu taktdagi avtomatning ichki holati bilan aniqlanishi orqali farqlanadi.
Ikkinchi turdagi avtomatlarda kirish signallarining X={x1,x2,...,xm} to‘plamida, ichki holatlarning B={b1,...,bn} to‘plamida va chiqish signallarining Y={y1,...,yk} to‘plamida berilgan o‘tish va chiqish funksiyalari quyidagi ko‘rinishda bo‘ladi:
b(t+1)=f[b(t),x(t)], y(t)= [b(t)].
Bunday avtomatlarga Mur avtomatlari deb nom qo‘yilgan.
O‘tish va chiqish funksiyalarini o‘tish va chiqish jadvallari yoki avtomat grafi orqali ham berish mumkin. Quyidagi 29-rasmda Mili avtomatining o‘tish va chiqish funksiyalari keltirilgan.
O‘tishlar jadvalining ai harfi bilan berilgan ustun va xj harfi bilan berilgan satrlarning kesishgan joylaridagi kataklarga avtomatning f(ai,xj) holati yoziladi. Bu holatga avtomat xj kirish signali tushganda ai holatdan o‘tadi. Xuddi shu tarzda chiqishlar jadvaliga avtomat tomonidan shu kabi o‘tishda shakllantirilgan y signallar yoziladi.
Avtomatning grafini qurishda grafning cho‘qqilari avtomatning ichki holati bilan bir xil deb qaraladi. Har bir shox avtomatda berilgan mos keluvchi o‘tish shoxini chaqiruvchi kirish signali hamda ushbu o‘tishda hosil bo‘luvchi chiqish signali bilan belgilanadi. 29-rasm orqali berilgan Mili avtomatiga mos keluvchi avtomat grafi 30-rasmda keltirlgan.
Mur avtomatlarining o‘tish va chiqish funksiyalarini o‘tishlarning belgilangan jadvali deb ataluvchi birgina jadval orqali berish mumkin. Mur avtomatining o‘tishlarning belgilangan jadvali ham Mili avtomatining o‘tishlar jadvali kabi tuziladi, ammo har bir ichki holatning simvollari ustida avtomat shu holatda chiqaruvchi chiqish signallari yoziladi. Mur avtomatlarining grafida chiqish signallarining qiymati uzellar yoniga yoziladi. Misol tariqasida 31-rasm va 32-rasmlarda Mur avtomatining grafi va o‘tishlarining belgilangan jadvallari keltirilgan.
Do'stlaringiz bilan baham: |
