Tupikli dnshlarni aniqlash algoritmlari. Namunaviy misol va masala hamda uning yechimi. Amaliy topshiriqlar

4-5-AMALIY MASHG’ULOT

TUPIKLI DNSHLARNI ANIQLASH ALGORITMLARI. NAMUNAVIY MISOL VA MASALA HAMDA UNING YECHIMI. AMALIY TOPSHIRIQLAR.

Tupikli diz’yunktiv normal shakllarni yasash algoritmi
Tupikli diz’yunktiv normal shakllarni yasash algoritmi. Hamma tupikli DNShlarni topishning geometrik g‘oyalarga asoslangan algoritmini keltiramiz. to‘plamning hamma maksimal intervallar sistemasi bo‘lsin. va ixtiyoriy nuqta hamda funksiya aynan 1ga teng bo‘lmagan funksiya bo‘lsin. 1- jadvalni tuzamiz,

bu yerda 1- jadvalning ga mos 1- ustuni 0lardan iborat bo‘ladi, chunki . Qolgan har bir ustunida hech bo‘lmaganda bitta 1 mavjud bo‘ladi. Demak, birinchi ustun qolgan hamma ustunlardan farq qiladi.
Har bir ( ) uchun hamma satrlar raqamlari (nomerlari) to‘plami ni topamiz, bu yerda ustunda 1 mavjud bo‘ladi. Faraz qilaylik, bo‘lsin. U holda ifodani tuzamiz va  turdagi almashtirishni bajaramiz. Bu almashtirish vaqtida simvolni
buliy qiymatli deb hisoblaymiz.

1-jadval
			…		…
			…		…
…	…	…	…	…	…	…
			…		…
…	…	…	…	…	…	…
			…		…

Hosil qilingan ifodani
,
teng kuchli formulalardan foydalanib soddalashtiramiz. Buning natijasida ifodaning qismi bo‘lgan ifodani hosil qilamiz. Ravshanki, ifodadagi har bir qo‘shiluvchi had keltirilmaydigan qobiqni ifodalaydi.
Yuqorida o‘rganilgan algoritm ko‘p argumentli funksiyalar uchun ko‘p
mehnat talab qiladi va amalda deyarli ishlatilmaydi.