29.12.2015
İLERİ ALGORİTMA ANALİZİ FİNAL SINAVI
Sorular
1. Tüm düğümlerden tüm düğümlere mesafe cetveli oluşturulurken matris çarpımının nasıl
kullanılabileceği derste tartışılmıştır. Aynı şekilde matris çarpımı ile bir düğümden tüm
düğümlere mesafeleri belirlemek mümkün müdür? Nasıl?
2.
En az sayıda para kullanarak para üstü verme problemi ile ilgili olarak;
a. Kullanılabilir bozukların sabit bir değerin tamsayı üssü olarak (a0, a1, a2, a3, a4, … ; a
tamsayıdır.) verildiği durumda Greedy Algoritmasının her zaman optimum sonuç
ürettiğini gösteriniz.
b. Bozukluklardan birisi 1 birim olmak üzere, k farklı bozukluk kümesi için para üstü
hesaplayan O(nk) karmaşıklığında algoritmayı bulunuz. Algoritma hangi sınıfta yer
almaktadır.
3. Bir nehrin kıyısına dizilmiş olan 1..n ile numaralandırılmış n adet şehir ve nehrin karşısından
her bir şehre ulaşmaya çalışan 1..n ile numaralandırılmış n yardım kafilesi bulunmaktadır.
Kafilelerin numaraları yardım ulaştırmaya çalıştıkları şehrin numarası ile aynıdır, ancak bu
kafileler şehirlerin tam karşısında bulunmamaktadır. Kafilenin hedefine ulaşabilmesi için bu
kafilelerin bulunduğu konumlar ile yardım götürecekleri şehirler arasında birbirini kesmeyen
düz çizgiler çizilmesi isteniyor. Azami sayıda kafile ile şehrin nasıl bağlanabileceğini bulan
dinamik programlama algoritmasını ve karmaşıklığını tartışınız.
4. Yukarıdaki soruda yardım kafilelerinin hedeflediği şehir ile ilgili kısıtlamayı kaldırmak istersek,
şehirler ve yardım kafilelerinin coğrafi koordinatları verildiğinde hiçbir rota diğerini
kesmeyecek şekilde kafileler ile şehirleri eşleyen algoritmayı ortaya koyunuz ve tartışınız.
5. G = (V, E) yönlü olmayan çizgesinde, pozitif we kenar ağırlıkları ile MST ve belirli bir s
düğümünden tüm düğümlere olan en kısa yollar hesaplanmıştır. Her bir kenarın ağırlığı we + 1
olacak şekilde bir artırılırsa, MST ve en kısa yollar ile ilgili nasıl yorumlar yapılabilir.
Download

29.12.2015 İLERİ ALGORİTMA ANALİZİ FİNAL SINAVI Sorular 1