Ma’ruza 10 Raqamli axborotlarni Furye qatoriga yoyish algoritmi. Ishonchliligini baholash. Algoritmlarni loyihalash algorithm Design

Ma’ruza 10
Raqamli axborotlarni Furye qatoriga yoyish algoritmi. Ishonchliligini baholash.
ALGORITMLARNI LOYIHALASH
Algorithm Design

• Ta'riflar
• Foydalanish sohalari
• Delon triangulyatsiyasi xususiyatlari
• Delon triangulyatsiyasini qurish usullari:
• Bosqich kiritish usullari
• Bosqichma-bosqich tanlash usullari
• Dekompazitsiya (Parchalanish) usullari
• Skanerlash usullari
• Ikki o'tishli usullari

Reja:

Delon triangulyatsiyasi

Ta'rifi, qo'llanilishi, xususiyatlari, qurish usullari

Triangulyatsiya ta’rifi

Triangulyatsiya

• Triangulyatsiya – barcha ichki sohalari uchburchak bo'lgan planar graf.
• “Triangulyatsiya” atamasi bu
• graf;
• grafni qurish jarayoni.

• S nuqtalar to’plami uchun triangulyatsiya masalasi – S to’plamning barcha nuqtalarini bo’laklari kesishmaydigan triangulyatsiya grafini hosil qilish uchun bog'lash muammosi.

S nuqtalar to’plami

Optimal triangulyatsiya ta’rifi

• Optimal triangulyatsiya – grafning barcha qirralari uzunliklarining minimal yig'indisiga ega bo’lgan triangulyatsiya.

! Talab qilinadigan, ammo juda ko'p vaqt talab qiladigan vazifa O(2n) !

Amalda, optimal triangulyatsiyaning taxminiy ko'rsatkichlaridan foydalaniladi:

• «Hasis» triangulyatsiya O(N2*logN)
• Delon triangulyatsiyasi O(N*logN)

Delone triangulyatsiyasi ta’rifi

• Delon triangulyatsiyasi (DT(S)) – Delone shartini qanoatlantiruvchi qavariq triangulyatsiya. Delon shati:
• uning har qanday uchburchagi atrofida aylanib o'ralgan doira ichida, grafning bironta ham uchi tushmasligi kerak