DERS TANITIM ve UYGULAMA BİLGİLERİ
| Dersin Adı | Kodu | Yarıyıl | T+U+L (saat/hafta) | Türü (Z / S) | Yerel Kredi | AKTS |
|---|---|---|---|---|---|---|
| Çizge Kuramı | CMPE 304 | Bahar | 03+00+00 | Seçmeli | 3 | 6 |
| Akademik Birim: | Bilgisayar Mühendisliği Bölümü |
| Öğrenim Türü: | Örgün Eğitim |
| Ön Koşullar | Ayrık Hesaplama Yapıları, İspat metotları |
| Öğrenim Dili: | İngilizce |
| Dersin Düzeyi: | Lisans |
| Dersin Koordinatörü: | - - |
| Dersin Amacı: | Dersin temel amacı, öğrencilerin algoritmik çizge kuramı alanındaki klasik teoremleri ve algoritmaları öğrenmelerini ve kullanmalarını sağlamaktır. Öğrencilerden temel bazı pratik çizge problemlerini çözerek algoritma bilgisini göstermesi beklenir. Öğrenciler bu derste çizge algoritmalarının bilgisayar mühendisliğindeki uygulamarından birkaçını öğrenecek ve verilen bazı mühendislik probllemlerini çizgeler üzerinde tanımlayıp algoritma geliştirebileceklerdir. Öğrencilerden bir projeyi tamamlamaları ve sınıfta kısa bir simülasyon yapmaları istenecektir. |
| Dersin İçeriği: | Bu derste çizge kuramının unsurlarını çizge algoritmalarına vurgu yaparak tartışacağız. Dersin yaklaşık olarak yarısı çizge kuramsal konulara ve diğer yarısı ise algoritmik uygulamalara ayrılaca ktır. Konular arasında minimum kapsayıcı ağaçlar, Euler çizgeleri, boyama problemi, eşleşmeler, bağlantı ve Hamilton çizgeleri vardır. Bunlara ek olarak liste boyama problemi ve kombinatoryel oyunlar gibi bazi ileri konulardan da bahsedilecektir. |
| Dersin Öğrenme Çıktıları (ÖÇ): |
|
| Dersin Öğrenme Yöntem ve Teknikleri | Klasik konu anlatımı, Problem çözme tekniği, Programlama ve simülasyon. |
HAFTALIK PROGRAM
| Hafta | Konular | Ön Hazırlık |
|---|---|---|
| 1 | Çizge kuramının temelleri. Çizgelerin uygulamaları (telekomünikasyon ağları ve benzerleri) | Ayrık hesaplama yapıları ile ilgili konuların tekrarı. Douglas West 1. Ünite (1.1) |
| 2 | Bazı özel çizge aileleri. Euler çizgeleri. Derece dizileri. Havel-Hakimi algoritması. İzomorfik çizgeler. | Douglas West 1. Ünite (1.2) |
| 3 | Çizgelerin bilgisayarda gösterimi. DFS ve BFS algoritmaları. 1. Kısa sınav. | Douglas West 1. Ünite (1.3, 1.4), Cormen et. al 22. Ünite (22.1, 22.2, 22.3) |
| 4 | Minimum kapsayan ağaçlar. Kruskal ve Prim algoritmaları | Douglas West 2. Ünite, Cormen et. al 23. Ünite |
| 5 | Eşleştirme problemleri ve uygulamaları. Hall teoremi. En kısa patika algoritmaları. | Douglas West 3. Ünite (3.1, 3.2) Cormen et. al 24. Ünite (24.1, 24.2, 24.3) |
| 6 | Bağlantı. Güçlü bağlantılı komponentler. 2. Kısa sınav. | Douglas West 4. Ünite (4.1, 4.2) |
| 7 | Maksimum akış problemleri. Klik, köşe kaplaması, Bağımsız kümeler. | Douglas West 4. Ünite (4.3), Cormen et. al 26. Ünite (26.1, 26.2, 26.3) |
| 8 | Çizge boyama sayısı, üst sınırlar, Brook teoremi. | Douglas West 5. Ünite (5.1, 5.2) |
| 9 | Çizge boyama problemi ve ilgili algoritmalar. Ara sınav. | Douglas West 5. Ünite (5.3) |
| 10 | Düzlemsel çizgeler. Kuratowski teoremi. | Douglas West 6. Ünite (6.1, 6.2) |
| 11 | Kenar boyama problemi. | Douglas West 7. Ünite (7.1, 7.2) |
| 12 | Hesaplama karmaşıklığına giriş. Çizgeler üzerinde tanımlanan NP tam problemlere örnekler (En uzun patika, Hamilton döngüsü). 3. Kısa sınav. | Hamilton döngüsü. 3. Kısa sınav. Douglas West Ek C. |
| 13 | Ramsey Teoremi. Liste boyama problemi ve uygulamaları. | Douglas West 8. Ünite (8.3, 8.4) |
| 14 | Çizgeler üzerinde tanımlanan kombinatoryal oyunlar. Kenar arama problemi ve varyasyonlarının mühendislikteki uygulamaları. | Game Theory Methods for Pursuit-Evasion Problems. Yi Li et al 2022 J. Phys.: Conf. Ser. 2402 012024 |
Kadir Has Üniversitesi'nde bir dönem 14 haftadır, 15. ve 16. hafta sınav haftalarıdır.
ZORUNLU ve ÖNERİLEN OKUMALAR
| Douglas West, Introduction to Graph Theory, 2001, 2nd ed . Alan Gibbons, Algorithmic Graph Theory, 1985. Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 2009, 3rd ed. |
DİĞER KAYNAKLAR
| Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs, 2004. |
DEĞERLENDİRME SİSTEMİ
| Yarıyıl İçi Çalışmaları | Sayı | Katkı Payı (%) |
|---|---|---|
| Proje | 1 | 10 |
| Sunum/Jüri | 1 | 10 |
| Ara Sınavlar/Sözlü Sınavlar/Kısa Sınavlar | 4 | 40 |
| Final Sınavı | 1 | 40 |
| Total: | 7 | 100 |
İŞ YÜKÜ HESAPLAMASI
| Etkinlikler | Sayısı | Süresi (saat) | Toplam İş Yükü (saat) |
|---|---|---|---|
| Ders Saati | 14 | 3 | 42 |
| Proje | 1 | 10 | 10 |
| Sunum/Jüriye Hazırlık | 1 | 10 | 10 |
| Dersle İlgili Sınıf Dışı Etkinlikler | 14 | 5.5 | 77 |
| Ara Sınavlar/Sözlü Sınavlar/Kısa Sınavlar | 4 | 2 | 8 |
| Final Sınavı | 1 | 3 | 3 |
| Toplam İş Yükü (saat): | 150 | ||
1 AKTS = 25 saatlik iş yükü