GERİ DÖN
Ders Öğretim Planı
| Dersin Kodu | Dersin Adı | Dersin Türü | Yıl | Yarıyıl | AKTS |
|---|---|---|---|---|---|
| 9105056022021 | Algoritmaların Karmaşıklık Analizi | Ders | 1 | 2 | 8,00 |
Dersin Seviyesi
Doktora
Dersin Sunulduğu Dil
Türkçe
Dersin Amacı
Öğrencilere verilen problemler için algoritma tasarlama ve tasarlanan algoritmaların karmaşıklıklarını analiz edebilme, doğruluk kanıtlarını yapabilme becerisi kazandırmak. Algoritmik hesaplama gücünün sınırlarını anlamak, Algoritmlarda NP-tamlık kavramı ve NP-zor problemlerle başetme yöntemlerini anlamak.
Dersi Veren Öğretim Görevlisi/Görevlileri
Prof. Dr. Mehmet Emin DALKILIÇ
Öğrenme Çıktıları
| 1 | Önemli problem türlerini (sıralama, arama, katar işleme, çizge problemleri vb.) bilme |
| 2 | Algoritmik Problem Çözme Becerisi elde etmek |
| 3 | Algoritma Tasarımında Doğru Temel Veri Yapılarının Seçiminin Önemini Kavramak |
| 4 | Asismptotik Notasyon ve Temel Karmaşıklık Sınıflarını Bilmek |
| 5 | Temel Algoritma Tasarım Tekniklerini (Kaba-kuvvet, Cimri Teknik, Dinamik Programlalama vb.) nerede ve nasıl uygulayacağını öğrenmek |
| 6 | Algoritma Tasarımında Zaman ile Belek Ödünleşimi kavramının önemini anlamak |
| 7 | Algoritmik Hesaplama Gücünün Sınırlarının Farkına Varmak |
| 8 | NP-Tamlık kavramının önemini ve pratik sonuçlarını kavramak |
Öğretim Sistemi
Birinci Öğretim
Dersin Ön Koşulu Olan Dersler
Yok
Ders İçin Önerilen Diğer Hususlar
Yok
Dersin İçeriği
Algoritmalara giriş, Algoritma Verimliliğinin Analizi, Kaba-kuvvet ve Bıktırıcı Arama Teknikleri, Azalt ve Fethet Yöntemi, Böl ve Fethet Yaklaşımı, Dönüştür ve Fethet Yaklaşımı, Bellek (Yer) ve Zaman Ödünleşimleri, Dinamik Programlama, Cimri Teknik, Tekrarlı İyileştirme Teknikleri, Yaklaşıklık (approximation) Algoritmaları, NP-tamlık.,
Haftalık Ayrıntılı Ders İçeriği
| Hafta | Konular (Teorik) | Öğretim Yöntem ve Teknikleri | Ön Hazırlık |
|---|---|---|---|
| 1 | Algoritma Nedir? Algoritmik Problem Çözme Temel Teknikleri Önemli Problem Türleri Temel Veri Yapıları | ||
| 2 | Analiz Çerçevesi Asimptotik Notasyon ve Temel Karmaşıklık Sınıfları Tekrarlı Algoritmaların Matematiksel Analizi Özyinelemeli Algoritmaların Matematiksel Analizi N. Fibonacci sayısının Hesaplanması Algoritmaların Amprik Analizi | ||
| 3 | Seçme Sıralama ve Kabarcık Sıralama Sıralı Arama ve Kaba-kuvvet Katar Eşleme Enyakın-çift problemleri Bıktırıcı Arama Derinlik Önce Arama ve Genişlik Önce Arama | ||
| 4 | Araya Eklemeli Sıralama Topolojik Sıralama Kombinatorik Nesneler Üretme Algoritmaları Sabit çarpan ile azaltmalı algoritmalar Değişken büyüklükte azaltma algoritmaları | ||
| 5 | Birleştirmeli Sıralama Hızlı sıralama İkili Ağaç Gezme ve İlişkili Problemler En Yakın Çift Problemine Böl Fethet Yaklaşımı | ||
| 6 | Ön Sıralama Dengeli Arama Ağaçları Yığınlar ve Yığın sıralama Problem İndirgeme | ||
| 7 | Arasınav öncesi ödev sorularının çözümü ve konu tekrarı | ||
| 8 | Sayarak sıralama Katar Eşleştirmede Girdi Zenginleştirme Özütleme | ||
| 9 | Dinamik Programlama Prim'in algoritması Kruskal'ın algoritması Dijkstra'nın algoritması Huffman Ağaçları ve Kodları | ||
| 10 | Cimri Teknik | ||
| 11 | Tekrarlı İyileştirme Üç Temel Örnek Sırtçantası Problemi ve Bellek Fonksiyonları Optimal İkili Ağaç Aramaları Warshall ve Floyd Algoritmaları | ||
| 12 | Algoritmik Hesaplama Gücünün Sınırları Alt Sınır Argümanları Karar Ağaçları P, NP ve NP-Tam Problemler | ||
| 13 | Algoritmik Hesaplama Gücünün Sınırlılığıyla Başetme Yoları Geriyeizleme Dalla ve Sınırla NP-Zor Problemler için Yaklaşıklık Algoritmaları | ||
| 14 | Final Sınavına Hazırlık Ödev Sorularının Çözümü Final öncesi konuların tekrarı | ||
| 15 | Final Sınavı |
Ders Kitabı / Malzemesi / Önerilen Kaynaklar
Ders kitabı: Introduction to the Design and Analysis of Algorithms by Anany Levitin, 3rd ed., Pearson 2012. Önerilen Kaynak: Algorithm Design by John Kleinberg and Eva Tardos, Addision Wesley, 2006.
Planlanan Öğrenme Aktiviteleri ve Metodları
Değerlendirme
| Yarıyıl (Yıl) İçi Etkinlikleri | Adet | Değer |
|---|---|---|
| Ara Sınav | 1 | 50 |
| Ev Ödevi | 1 | 50 |
| Toplam | 100 | |
| Yarıyıl (Yıl) Sonu Etkinlikleri | Adet | Değer |
| Final Sınavı | 1 | 100 |
| Toplam | 100 | |
| Yarıyıl (Yıl) İçi Etkinlikleri | 60 | |
| Yarıyıl (Yıl) Sonu Etkinlikleri | 40 | |
Staj Durumu
Yok
İş Yükü Hesaplaması
| Etkinlikler | Sayısı | Süresi (saat) | Toplam İş Yükü (saat) |
|---|---|---|---|
| Ara Sınav | 1 | 50 | 50 |
| Final Sınavı | 1 | 60 | 60 |
| Problem Çözümü | 50 | 1 | 50 |
| Okuma | 11 | 1 | 11 |
| Ev Ödevi | 11 | 5 | 55 |
| Toplam İş Yükü (saat) | 226 | ||
Program ve Öğrenme Çıktıları İlişkisi
| PÇ 1 | PÇ 2 | PÇ 3 | PÇ 4 | PÇ 5 | PÇ 6 | PÇ 7 | |
| ÖÇ 1 | 2 | 1 | 5 | 3 | |||
| ÖÇ 2 | 5 | 1 | 4 | 3 | |||
| ÖÇ 3 | 5 | 4 | 4 | 3 | |||
| ÖÇ 4 | 3 | 2 | 4 | ||||
| ÖÇ 5 | 5 | 3 | 3 | ||||
| ÖÇ 6 | 2 | 1 | 4 | 3 | |||
| ÖÇ 7 | 2 | 2 | 3 | 2 | 5 | ||
| ÖÇ 8 | 2 | 2 | 1 | 2 | 5 |
* Katkı Düzeyi : 1 Çok düşük 2 Düşük 3 Orta 4 Yüksek 5 Çok yüksek