GERİ DÖN
Ders Öğretim Planı
| Dersin Kodu | Dersin Adı | Dersin Türü | Yıl | Yarıyıl | AKTS |
|---|---|---|---|---|---|
| 9101075392014 | Algoritmaların Matematiksel Analizi ve Tasarımı I | Seçmeli Ders Grubu | 1 | 1 | 8,00 |
Dersin Seviyesi
Yüksek Lisans
Dersin Sunulduğu Dil
Türkçe
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, izlenebilirlik, yaklaşık ve rassal algoritma kavramlarını öğrenmelerini sağlamaktır.
Dersi Veren Öğretim Görevlisi/Görevlileri
Prof.Dr. Urfat NURIYEV
Öğrenme Çıktıları
| 1 | Otomata teorisini kullanarak modelleme tekniklerinin öğrenilebilmesi |
| 2 | Problemlerin algoritmik olarak çözülüp çözülemediğinin tespit edilebilmesi |
| 3 | Farklı dillerin formal gramerlerle analiz edilebilmesi |
Öğretim Sistemi
Birinci Öğ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, hesaplanabilir izlenebilirlik, 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 hesaplanabilir izlenebilirlik : 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. Pspace’deki bazı zor problemlerin analizleri, yaklaşıklık algoritmalar ve örnekleri, rassal algoritmalar ve örnekleri.
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
1. Aho, A.V.,.Hopcroft, J.E, Ulman, J.D., “The Design and Analysis of Computer Algoritms”, Addison-Wesley, Massachusetts (1974). 2. Goodman, S.E., Hedetiemi, S.T., “Introduction to The Design and Analysis of Algoritms”, Mc.Graw.-Hill Book Company, New York., (1977). 3. Graham, R.L., Knuth, D.E., Parashnik,O., “Concrete Mathematics. A Foundation for Computer Science”, Addison-Wesley,USA,(1998) 4. 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 | 14 | 3 | 42 |
| Ara Sınav İçin Bireysel Çalışma | 1 | 60 | 60 |
| Final Sınavı içiin Bireysel Çalışma | 1 | 80 | 80 |
| Quiz için Bireysel Çalışma | 1 | 21 | 21 |
| Ev Ödevi | 1 | 25 | 25 |
| Toplam İş Yükü (saat) | 234 | ||
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 | 5 | 5 | 5 | 4 | ||
| ÖÇ 3 | 4 | 5 | 5 | 3 | 5 |
* Katkı Düzeyi : 1 Çok düşük 2 Düşük 3 Orta 4 Yüksek 5 Çok yüksek