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.