Ders Öğretim Planı
Dersin KoduDersin AdıDersin TürüYılYarıyılAKTS
9105056022008Algoritmaların Karmaşıklık AnaliziSeçmeli128
Dersin Seviyesi
Doktora
Dersin Amacı
Bu dersin amacı, öğrencilerin algoritma tasarlayabilmesini ve bu algoritmaların analizini yapabilmesini, bir algoritmanın doğruluğunun kanıtlayabilmesini, NP tamlık, tractability, yaklaşık ve rassal algoritma kavramlarını öğrenmelerini sağlamaktır.
Dersi Veren Öğretim Görevlisi/Görevlileri
Prof. Dr. Mehmet Emin DALKILIÇ
Öğrenme Çıktıları
1Bir algoritmanın gerçekçi kıstlar altında; zamansal ve alansal analizini ve maliyet araştırmasını yapabilme.
2Bir problemi çözebilmek için yeni algoritma tasarlayabilme.
3Algoritmaları yaklaşımlarına göre sınıflandırabilme.
4Yeni bir problemi var olan başka bir probleme benzeterek çözebilme.
5 Farklı algoritmaları birbirleriyle çeşitli kısıtlar üstünden karşılaştırabilme.
6Algoritmaların performans çıktılarını yorumlayabilme.
7Bilgisayar bilimlerinin bilinen algoritma problemleri hakkında geliştirilen çağdaş çözümler hakkında bilgi sahibi olma.
8Algoritmaların performanslarını bilinen diğer algoritmalarla eş özelliklerini tespit ederek ölçebilme.
9Çözülmesi zor problemlere yaklaşık algoritmalar tasarlayabilme.
Öğrenim Türü
Örgün Öğretim
Dersin Ön Koşulu Olan Dersler
Yok
Ders İçin Önerilen Diğer Hususlar
Yok
Dersin İçeriği
Algoritmaların tasarımı ve analizi: agoritma analizinin temelleri, computational tractability, asimtotik büyüme oranı, çizgeler: çizge bağlılığı ve çizge üzerinde geçiş algoritmaları, çift taraflılık, topolojik sıralama algoritması, açgözlü algoritmalar: aralık planlama, minimum kapsama ağacı algoritmaları, kümeleme algoritmaları. Böl ve fethet yaklışımlı algoritmaların, dinamik programlama yaklaşımı içeren algoritmalar ve dağıtık algoritmaların detaylı incelenmesi. NP ve computational intractability: polinom zamanlı indirgemeler, etkin sertifikasyon yöntemleri ve NP’nin tanımı, NP tam problem örnekleri, sıralama problemleri, partitionin problemleri, çizge boyama, numerik problemler, co-NP ve the asymmetry of NP intractability. Pspace’deki bazı zor problemlerin analizleri, yaklaşıklık algoritmalar ve örnekleri, rassal algoritmalar ve örnekleri
Haftalık Ayrıntılı Ders İçeriği
HaftaTeorikUygulamaLaboratuvar
1Stabil eşleme problemi, propose-and-reject algoritması, aralık planlama, çift taraflı eşleme paroblemlerinin incelenmesi. Computational tractability, asimtotik büyüme oranı, çalışma zamanı analizleri.Problem Çözümü
2Çizgeler, çizge gösterimi, ağaçlar, breadth first search algoritması, depth first search algoritması, bağlı bileşen bulma algoritması, çift taraflı çizgeler, yönlü döngü içermeyen çizgeler, topolojik sıralama algoritması.Problem Çözümü
3Açgözlü algoritmalar: aralık planlama problemi, optimum Caching, Dijkstra'nın en kısa yol algoritması, coin-changing algoritması.Problem Çözümü
4Böl ve fethet yaklaşımlı algoritmalar: mergesort, en yakın nokta çiftleri bulma algoritması, tamsayı çarpma, Karatsuba çarpma algoritması, matris çarpım algoritmaları.Problem Çözümü
5Dağıtık sistemler, dağıtık algoritmalar: yayın, flooading, convergecast, dağıtık BFS algoritması , dağıtık DFS algoritması, Bellman Ford BFS algoritması, Chang-Robert’ın minimum kapsama ağacı bulmak için Gallagher-Humblet-Spira (GHS) Algoritması, lider seçimi algoritmaları: Bully algoritması, LeLann’ın ring bazlı algoritması, Chang-Robert’ın Algoritması.Problem Çözümü
6Ağ Akışı, maksimum akış ve minimum kesme problemleri, Ford-Fulkerson algoritması, çift taraflı eşleme ve Ford maksimum akış probleminin ilişkisi, atama problemi.Literatür Tarama
7NP’nin tanımı, polinom zaman indirgemeleri, denklik yoluyla indirgeme, gadgetler yardımıyla indirgeme, 3-Satisfiability, hamiltonian cycle problem. P,NP, EXP terimleri. NP tamlık, NP tam problemler , circuit satisfiability, 3-SAT, co-NP ve NP’nin asimetrisi.
8Ara Sınav
9Sıralama problemleri, Hamiltonian Cycle Problemi, çizge boyama: 3-boyanabilirlik ve clique cover problemleri ilişkisi
10Clique problemi, bağımsız küme ve köşe örtme problemlerinin ilişkisi, NP zor kavramı, NP tam problem örnekleri: planarcircuitsat, notallequal3sat, hittingset.
11Pspace kavramı, Quantified Satisfiability, planlama problemi, 15-Puzzle problemi, Pspace tamlık kavramı, Psapace tam problemler.
12Tractability’nin sınırlarını genişletmek: az sayıda düğüm içeren köşe örtme bulma, NP zor problemleri ağaçlar üzerinde çözme: ağaç üzerinde bağımsız küme bulma, dalgaboyu Bölümleme çoğullamasıg, sirküler ok boyama ve aralık boyama problemleri ilişkisi.
13Yaklaşık algoritmalar, yük dengeleme, k-merkez seçimi problemi, ücretlendirme yöntemi, vertex cover, set cover, bin packing, gezgin satıcı problemlerine yaklaşık algoritmalar.
14Merkez seçimi problemi, vertex cover, açgözlü yaklaşımlı köşe örtme problemi, küme örtme probleminin yaklaşık algoritması, gezgin satıcı problemi ile minimum kapsama ağacı problem ilişkisi.
15Rassal algoritmalar, rassallaştırma kavramı, çekişme problemi çözümü, evrensel minimum dilim: kısaltma algoritması, beklenen değerin doğrusallığı, maksimum 3-SAT, evrensel hashing, Chernoff sınırları, yük dengeleme, rassal böl ve yönet yaklaşımı.
16Final Sınavı
Ders Kitabı / Malzemesi / Önerilen Kaynaklar
1. Algorithm Design by Jon Kleinberg and Eva Tardos. Addison Wesley, 2006. 2. Introduction to the Design and Analysis of Algorithms by Anany Levitin, 2nd edition Pearson-Addison-Wesley , Michael Sipser, 3. Intro. to the Theory of Computation, 2nd ed., Thompson Course Technology, 2005.
Planlanan Öğrenme Aktiviteleri ve Metodları
Değerlendirme
Yarıyıl (Yıl) İçi EtkinlikleriAdetDeğer
TOPLAM0
Yarıyıl(Yıl) Sonu EtkinliklerAdetDeğer
TOPLAM0
TOPLAM0
Dersin Sunulduğu Dil
Türkçe
Staj Durumu
Yok
İş Yükü Hesaplaması
EtkinliklerSayısıSüresi (saat)Toplam İş Yükü (saat)
Ara Sınav133
Final Sınavı133
Derse Katılım14342
Rapor Hazırlama2510
Proje Sunma133
Bireysel Çalışma9654
Ödev Problemleri için Bireysel Çalışma9545
Ara Sınav İçin Bireysel Çalışma12020
Final Sınavı içiin Bireysel Çalışma13636
Ev Ödevi919
TOPLAM İŞ YÜKÜ (saat)225
Program ve Öğrenme Çıktıları İlişkisi

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24
ÖÇ145       5    34    3  3
ÖÇ24 4445 54     2  4 2   3
ÖÇ3 4       2     4    5   
ÖÇ4  4554 54       25  5  3
ÖÇ5 4       4    3    34   
ÖÇ6 4       5 3     3  32 4
ÖÇ744         5   5      4 
ÖÇ85        3       3 35  3
ÖÇ9   545  3          55  3
* Katkı Düzeyi : 1 Çok düşük 2 Düşük 3 Orta 4 Yüksek 5 Çok yüksek
 
Ege University, Bornova - İzmir / TURKEY • Phone: +90 232 311 10 10 • e-mail: intrec@mail.ege.edu.tr