GERİ DÖN
Ders Öğretim Planı
| Dersin Kodu | Dersin Adı | Dersin Türü | Yıl | Yarıyıl | AKTS |
|---|---|---|---|---|---|
| 9101076482015 | Algoritmaların Matematiksel Analizi ve Tasarımı II | Seçmeli Ders Grubu | 1 | 2 | 12,00 |
Dersin Seviyesi
Doktora
Dersin Sunulduğu Dil
Türkçe
Dersin Amacı
Bu dersin amacı algoritmaların karmaşıklığı kavramlarını kullanarak Hesaplama problemlerini analiz etmektir.
Dersi Veren Öğretim Görevlisi/Görevlileri
Prof.Dr. Urfat NURIYEV
Öğrenme Çıktıları
| 1 | Algoritmaların süresel karmaşıklığını bulabilmek |
| 2 | Polinom sınırlı ve polinom sınırlı olmayan algoritmaları öğrenmek |
| 3 | NP ve P sınıfı kavramlarını, tanıma problemlerini ve Turing makinasını öğrenmek |
| 4 | NP-tamlığın ispat yöntemlerini öğrenmek |
| 5 | NP-tamlık kavramını yaklaşık çözüm bulmak için kullanabilmek |
| 6 | NP-tamlık kavramını kullanarak problemlerin analizini yapabilmek |
Öğretim Sistemi
Birinci Öğretim
Dersin Ön Koşulu Olan Dersler
Yok
Ders İçin Önerilen Diğer Hususlar
Yok
Dersin İçeriği
NP-tamlık Teorisinin Problemlerin analizinde kullanılması, NP-zor Problemler, NP-tam Problemlerin incelenmesi yöntemleri, NP-tam sınıfının dışında kalan problemler, Bazı Problemlerin NP-tamlığının ispatı
Haftalık Ayrıntılı Ders İçeriği
| Hafta | Konular (Teorik) | Öğretim Yöntem ve Teknikleri | Ön Hazırlık |
|---|---|---|---|
| 1 | Problem, soru ve algoritma kavramları, Algoritmanın süresel karmaşıklığı kavramı | ||
| 2 | Polinom sınırlı ve polinom sınırlı olmayan algoritma kavramları | ||
| 3 | Grafların kodlama yöntemleri | ||
| 4 | Tanıma problemi kavramı, Alt grafın izomorfluğu ve gezgin satıcı tanıma problemleri | ||
| 5 | Dil ve tanıma problemleri, Deterministik Turing makinası | ||
| 6 | P sınıf kavramı | ||
| 7 | Deterministik olmayan hesaplama, Deterministik olmayan Turing makinesi | ||
| 8 | Ara sınav | ||
| 9 | NP sınıf kavramı, Polinomiyal indirgenebilirlik kavramı | ||
| 10 | NP-tam sınıf kavramı ve örnekleri, NP-tamlığın ispat yöntemleri | ||
| 11 | NP-tamlık kavramını kullanarak problemlerin analizi, Sayısal parametreli problemler ve güçlü NP-tamlık, Güçlü NP-tamlığın ispat yöntemleri | ||
| 12 | NP-zor problemler, NP-tam problemlerin çözüm yöntemleri | ||
| 13 | Yaklaşık algoritmaların hatasının değerlendirilmesi | ||
| 14 | NP-tamlık kavramının yaklaşık çözüm bulmak için kullanılması | ||
| 15 | NP-tam problemler dışındaki sınıflar | ||
| 16 | Yarıyıl sonu sınavı |
Ders Kitabı / Malzemesi / Önerilen Kaynaklar
• Graham, R.L., Knuth, D.E., Parashnik,O., “Concrete Mathematics. A Foundation for Computer Science”, Addison-Wesley,USA,(1998) • Garey, M.R., Johnson, D.S., “Compures and Intractability. A Guide to the Theory of NP-Completeness”, W.H.Freeman and Company, San Francisco, (1979)
Planlanan Öğrenme Aktiviteleri ve Metodları
Değerlendirme
| Yarıyıl (Yıl) İçi Etkinlikleri | Adet | Değer |
|---|---|---|
| Ara Sınav | 1 | 50 |
| Quiz | 1 | 25 |
| Ev Ödevi | 1 | 25 |
| 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 | 40 | |
| Yarıyıl (Yıl) Sonu Etkinlikleri | 60 | |
Staj Durumu
Yok
İş Yükü Hesaplaması
| Etkinlikler | Sayısı | Süresi (saat) | Toplam İş Yükü (saat) |
|---|---|---|---|
| Ara Sınav | 1 | 2 | 2 |
| Final Sınavı | 1 | 2 | 2 |
| Quiz | 1 | 2 | 2 |
| Derse Katılım | 16 | 3 | 48 |
| Ara Sınav İçin Bireysel Çalışma | 1 | 85 | 85 |
| Final Sınavı içiin Bireysel Çalışma | 1 | 120 | 120 |
| Quiz için Bireysel Çalışma | 1 | 45 | 45 |
| Ev Ödevi | 1 | 50 | 50 |
| Toplam İş Yükü (saat) | 354 | ||
Program ve Öğrenme Çıktıları İlişkisi
| PÇ 1 | PÇ 2 | PÇ 3 | PÇ 4 | PÇ 5 | PÇ 6 | PÇ 7 | |
| ÖÇ 1 | 4 | 5 | 4 | 5 | 4 | ||
| ÖÇ 2 | 4 | 4 | 5 | 5 | 4 | ||
| ÖÇ 3 | 4 | 4 | 5 | 5 | 5 | ||
| ÖÇ 4 | 4 | 5 | 5 | 4 | 4 | ||
| ÖÇ 5 | 4 | 5 | 5 | 4 | 3 | ||
| ÖÇ 6 | 4 | 5 | 4 | 5 | 4 |
* Katkı Düzeyi : 1 Çok düşük 2 Düşük 3 Orta 4 Yüksek 5 Çok yüksek