Ders Öğretim Planı

Ders Kodu Ders Adı Ders Türü Yıl Dönem AKTS
ASM601 Algoritmalar ve Karmaşıklık 927003 1 1 8

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.

Dersin Veren Öğretim Görevlisi/Görevlileri

Doç.Dr. Sedat Akleylek

Ön Koşul Dersleri

Yok

Önerilen Diğer Hususlar

Yok

Ders Kitabı / Malzemesi / Önerilen Kaynaklar

- Algorithm Design by Jon Kleinberg and Eva Tardos. Addison Wesley, 2006. - Introduction to the Design and Analysis of Algorithms by Anany Levitin, 2nd edition Pearson- Addison-Wesley , Michael Sipser, - Intro. to the Theory of Computation, 2nd ed., Thompson Course Technology, 2005. - Introduction to Algorithms, T.Cormen, C.Leiserson, R.Rivest, MIT Press, 2009.

Dersin Sunulduğu Dil

Türkçe

Staj Durumu

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.

Değerlendirme

# Etkinlikler Adet Yuzde Katkısı Yarıyıl İci Etkinlik Yıl Sonu Etkinlik
90 Yarıyıl (Yıl) İçi Etkinlikleri 0 40
91 Yarıyıl (Yıl) Sonu Etkinlikleri 0 60
1 Ara Sınav 1 60 1
22 Proje Hazırlama 1 20 1
23 Proje Sunma 1 20 1
2 Final Sınavı 1 100 1

Ders İş Yükü Verisi

# Etkinlikler Adet Süresi(saat) Toplam İş Yükü(saat)
1 Ara Sınav 1 20 20
2 Final Sınavı 1 40 40
5 Derse Katılım 14 3 42
22 Proje Hazırlama 1 40 40
23 Proje Sunma 1 9 9
34 Okuma 12 1 12
54 Ev Ödevi 2 12 24

Haftalık Ders İçeriği

Hafta Teorik Uygulama Laboratuar Ders Notları
1 Temel Bilgiler: Ayrık matematik; Veri yapıları. Algoritmalara Giriş: Algoritma nedir; Çeşitli problemler. Algoritma Analizi: Algoritma karmaşıklığı; Soruşur gösterim.)
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ı.
3 Açgözlü algoritmalar: aralık planlama problemi, optimum Caching, Dijkstra'nın en kısa yol algoritması, coin-changing algoritması.
4 Böl ve fethet yaklaşımlı algoritmalar: mergesort, en yakın nokta çiftleri bulma algoritması, tamsayı çarpma, Karatsuba çarpma algoritması, matris çarpım algoritmaları.
5 Dağı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ı.
6 Ağ Akışı, maksimum akış ve minimum kesme problemleri, Ford-Fulkerson algoritması, çift taraflı eşleme ve Fordmaksimum akış probleminin ilişkisi, atama problemi.
7 NP’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.
8 Sıralama problemleri, Hamiltonian Cycle Problemi, çizge boyama: 3-boyanabilirlik ve clique cover problemleri ilişkisi
9 Ara Sınav
10 Clique problemi, bağımsız küme ve köşe örtme problemlerinin ilişkisi, NP zor kavramı, NP tam problem örnekleri: planarcircuitsat, notallequal3sat, hittingset.
11 Pspace kavramı, Quantified Satisfiability, planlama problemi, 15-Puzzle problemi, Pspace tamlık kavramı, Psapace tam problemler.
12 Tractability’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ı, sirküler ok boyama ve aralık boyama problemleri ilişkisi.
13 Yaklaşı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.
14 Merkez 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.
15 Rassal 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ı.
16 Final Sınavı

Dersin Öğrenme Çıktıları

# Öğrenme Çıktı Id Açıklama
1 1235159 Bir algoritmanın gerçekçi kısıtlar altında; zamansal ve alansal analizini ve maliyet araştırmasını yapabilme.
2 1235160 Bir problemi çözebilmek için yeni algoritma tasarlayabilme.
3 1235161 Algoritmaları yaklaşımlarına göre sınıflandırabilme.
4 1235162 Yeni bir problemi var olan başka bir probleme benzeterek çözebilme.
5 1235163 Farklı algoritmaları birbirleriyle çeşitli kısıtlar üstünden karşılaştırabilme.
6 1240078 Algoritmaların performans çıktılarını yorumlayabilme.

Bölüm Program Çıktıları

# Program Çıktı Id Açıklama
1 69070 Temel bilimlerin metodolojik ve uygulamalı öğeleri hakkında uygun bilgi birikimine sahip olurlar ve bu bilgiyi akıllı sistemler kapsamında mühendislik ilişkili problemleri tanımlamak için uygulayabilirler
2 69071 En yeni yöntemleri, teknikleri ve ekipmanı kullanarak akıllı sistemlerin mühendisliği ilişkili problemleri tanımlayabilir, formülize edebilir ve çözebilirler
3 69074 Akıllı sistemlerin analizini ve tasarımını kaliteden ödün vermeden yapmak için teknikler ve araçları kullanabilirler
4 69087 Testler yapabilirler ve elde edilen sonuçları analiz edebilir ve yorumlayabilirler
5 69088 Teknolojinin insani, etik ve ekolojik boyutlarını dikkate alabilirler
6 69073 Tüm ortamlarda hem yazılı hem de sözlü olarak İngilizce iletişim kurabilirler
7 69072 Hayat boyu öğrenmeye yatkındırlar
8 69086 Temel araştırmaları yürütebilir ve ilgili konferans ve dergilerde makaleler yayınlayabilirler

Ögrenme Çıktı Matrisi

Program Çıktısı
1 2 3 4 5 6 7 8
Öğrenme Çıktısı
1 3 3 4 4 3
2 4 4 4 4 4
3 4 3 4 5 4
4 4 4 4 4 4
5 4 4 4 4 4
6 5 5 5 5 5
* Katkı Düzeyi : 1 Çok düşük 2 Düşük 3 Orta 4 Yüksek 5 Çok yüksek