Algoritmlarni loyihalash fani

Algoritmlarni loyihalash fani

12-	hafta mashg’ulotlari bo’yicha mustaqil ish topshiriqlari

Mashg’ulot mazmuni	GRAFLAR
Quyida keltirilgan topshiriqlarning natijalarini mt.samtuit.uz tizimiga joylashtirishingiz talab etiladi

Mustaqil ish topshiriqlari

1. 
   Quyidagi nazariy savollarga javob bering
   

1. 
   Prim algoritmi ni tushuntirib bering
   
2. 
   Kraskal algoritmini tushuntirib bering
   
3. 
   Xoffman algoritmini namunaviy misol yordamida tushuntirib bering
   

2. 
   Quyidagi graf ko’rinishlari uchun matritsa quring va dastur kodini yozib natija oling.
   

1-masala:
Quyidagi grafdan foydalanib, 1-uchdan 6-uchgacha eng yaqin masofa va yo’nalishni aniqlash dasturini Prim, Xoffman va Kraskal algoritmlaridan foydalanib dastur tuzing va natijalarni taqqoslab tahlil qiling



Javoblar


Прим алгоритми.
Ушбу алгоритм Роберт Прим томонидан 1957 йили ишлаб чиқилган. Унгача 1930 йили чех математиги Войтек Ярник (Vojtěch Jarník) томонидан, кеийнроқ 1959 йилда Эдгар Дейкстра (Edsger Dijkstra) томонидан ишлаб чикилган.
Минимал нархли дарахтлар склетини қуришнинг иккита кенг тарқалган усули мавжуд. Улардан бири Прим алгоритми. Бу алгоритмда дарахтлар склети «ўсадиган» ("вырастает") U қирралар тўплами қурилади. V={1, 2,..., n} бўлсин. Аввал U={1} бўлади. Алгоритмнинг ҳар бир қадамида минимал нархли қирра топилади, ундан кейин v қирра V\U тўпламдан U тўпламга ўтказилади. Бу жараён U тўплам V тўпламга тенг бўлгунча такрорланади.
Мисол