| 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ü: |
Öznur YAŞAR DİNER |
| Dersi Veren(ler): |
Öznur YAŞAR DİNER |
| 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ı (ÖÇ): |
- 1- Çizgelerle ilgili temel kavramları tanımlayabilme ve kullanabilme
- 2- Çizge değişmezlerini pratik örneklerle ilişkilendirebilme
- 3- İspatlarda çizge kuramının temellerini kullanabilme ve çizge yapılarını anlama ve kullanmanın yanı sıra belirli çizge sınıfları için çizge değişmezlerini hesaplayabilme
- 4- Çizge parametreleri ve özelliklerini verimli bir şekilde çalışmak için algoritmik teknikleri kullanabilme
- 5- Çizgeler üzerinde tanımlanan birçok optimizasyon problemi için verimli algoritma tasarlayabilme
- 6- Çizge kuramında kullanılan teknikleri (çip tasarımı ve haberleşme ağları gibi) mühendislik konularına etkili bir şekilde uygulayabilme
|
| Dersin Öğrenme Yöntem ve Teknikleri |
Proje sunumu, Klasik konu anlatımı, Problem çözme, Soru ve Cevap, Grup Çalışması. |
| 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) |
1,2 |
| 2 |
Bazı özel çizge aileleri. Euler çizgeleri. Derece dizileri. Havel-Hakimi algoritması. İzomorfik çizgeler. |
Douglas West 1. Ünite (1.2) |
1, 2 |
| 3 |
Çizgelerin bilgisayarda gösterimi. DFS ve BFS algoritmaları. 1. Proje |
Douglas West 1. Ünite (1.3, 1.4), Cormen et. al 22. Ünite (22.1, 22.2, 22.3) |
1, 4, 6 |
| 4 |
Minimum kapsayan ağaçlar. Kruskal ve Prim algoritmaları |
Douglas West 2. Ünite, Cormen et. al 23. Ünite |
1, 2, 3 |
| 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) |
1, 2, 6 |
| 6 |
Bağlantı. Güçlü bağlantılı komponentler. 2. Proje |
Douglas West 4. Ünite (4.1, 4.2) |
1, 2, 6 |
| 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) |
1, 2, 3, 4 |
| 8 |
Çizge boyama sayısı, üst sınırlar, Brook teoremi. |
Douglas West 5. Ünite (5.1, 5.2) |
1, 2, 3, 4 |
| 9 |
Çizge boyama problemi ve ilgili algoritmalar. 3. Proje |
Douglas West 5. Ünite (5.3) |
1, 3,4,5 |
| 10 |
Düzlemsel çizgeler. Kuratowski teoremi. |
Douglas West 6. Ünite (6.1, 6.2) |
1, 2, 3, 4 |
| 11 |
Kenar boyama problemi. |
Douglas West 7. Ünite (7.1, 7.2) |
1, 3, 4 |
| 12 |
Hesaplama karmaşıklığına giriş. Çizgeler üzerinde tanımlanan NP tam problemlere örnekler (En uzun patika, Hamilton döngüsü). 4. Proje |
Douglas West Ek C. |
1, 3, 4, 5 |
| 13 |
Ramsey Teoremi. Liste boyama problemi ve uygulamaları. |
Douglas West 8. Ünite (8.3, 8.4) |
1, 2, 4, 5 |
| 14 |
Çizgeler üzerinde tanımlanan kombinatoryal oyunlar. Kenar arama problemi ve varyasyonlarının mühendislikteki uygulamaları. |
|
1, 2, 4, 5 |
Kadir Has Üniversitesi'nde bir dönem 14 haftadır, 15. ve 16. hafta sınav haftalarıdır.
