Ders Öğretim Planı

Ders Kodu Ders Adı Ders Türü Yıl Dönem AKTS
BM631 Algoritma Tasarımı ve Karmaşıklık Analizi 927003 1 2 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 100 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 67 67
2 Final Sınavı 1 120 120

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ığı
2 Temel Bilgiler: Ayrık matematik; Veri yapıları. Algoritmalara Giriş: Algoritma nedir; Çeşitli problemler. Algoritma Analizi: Algoritma karmaşıklığı
3 Böl ve fethet yaklaşımlı algoritmalar: mergesort, en yakın nokta çiftleri bulma algoritması, tamsayı çarpma, Karatsuba çarpma algoritması, matris çarpım algoritmaları.
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 Böl ve fethet yaklaşımlı algoritmalar: mergesort, en yakın nokta çiftleri bulma algoritması, tamsayı çarpma, Karatsuba çarpma algoritması, matris çarpım algoritmaları.
6 Sıralama algoritmaları
7 Sıralama algoritmaları, arama algoritmaları
8 Genel Tekrar
9 Ara Sınav
10 NP’nin tanımı, polinom zaman indirgemeleri, denklik yoluyla indirgeme
11 Yaklaşık algoritmalar
12 Açgözlü algoritmalar
13 Ç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ı.
14 Ç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ı.
15 Genel Tekrar
16 Final

Dersin Öğrenme Çıktıları

# Öğrenme Çıktı Id Açıklama
1 1245172 Bir algoritmanın gerçekçi kısıtlar altında; zamansal ve alansal analizini ve maliyet araştırmasını yapabilme.
2 1245173 Bir problemi çözebilmek için yeni algoritma tasarlayabilme.
3 1245174 Algoritmaları yaklaşımlarına göre sınıflandırabilme.
4 1245175 Yeni bir problemi var olan başka bir probleme benzeterek çözebilme.
5 1245176 Farklı algoritmaları birbirleriyle çeşitli kısıtlar üstünden karşılaştırabilme.
6 1245177 Çözülmesi zor problemlere yaklaşık algoritmalar tasarlayabilme.

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

# Program Çıktı Id Açıklama
1 67006 Lisans düzeyinde edinilen bilgileri derinleştirerek uygulamaya koyabilme.
2 67007 Analiz, sentez, eleştirel değerlendirme yeteneklerini geliştirerek karmaşık problemleri bağımsız olarak çözebilme.
3 67008 Modern tasarım yöntemleri ve araçları kullanarak bir süreci ya da bir sistemi tasarlayabilme.
4 67009 Bilimsel yöntemler kullanarak veri toplayabilme, değerlendirebilme ve yorumlayabilme.
5 67010 Çok disiplinli takımlarda yer alarak farklı alanlardan gelen bilgileri kendi alanıyla bütünleştirerek çözüm yöntemleri belirleyebilme.
6 67011 Bilimsel bilgi birikimini yazılı ve sözlü olarak etkin bir şekilde ifade edebilme, en az bir yabancı dilde iletişim kurabilme.
7 67012 Bilimsel gelişmeleri izleyerek kendini sürekli yenileyebilme.
8 67013 Toplumsal, çevresel ve etik değerleri dikkate alarak bilimsel araştırma yürütebilme.
9 67014 Proje planlaması ve zaman yönetimi yapabilme, alternatif çözüm yolları belirleyebilme.
10 67015 Bilimsel araştırma sürecinde uygun araçları belirleyebilme ve bilişim teknolojilerini kullanabilme.

Ögrenme Çıktı Matrisi

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