TÜRKÇE
ENGLISH
Genel Bilgi
| Kod | CENG715 |
| Ad | Graph Theory |
| Yarıyıl | . Yarıyıl |
| Süre (T+U) | 3-0 (T-U) (17 Hafta) |
| AKTS | 6 AKTS |
| Yerel Kredi | 3 Yerel Kredi |
| Eğitim Dil | İngilizce |
| Seviye | Doktora Dersi |
| Tür | Normal |
| Öğretim Şekli | Yüz Yüze Öğretim |
| Bilgi Paketi Koordinatörü | Prof. Dr. UMUT ORHAN |
Dersin Amacı
Amaç, çizgelerin teorik arka planını anlamak ve grafik algoritmalarını en bilinen problemlere uygulamaktır.
Dersin İçeriği
Connected graphs, paths, distance, cut-vertices, cut-edges, weighted graphs, shortest path, Spanning trees, Bipartite graphs, Eulerian graphs, Hamilton graphs, Independent-covering-mathcing graphs, Vertex colorings, Edge colorings, Planar graphs, Directed graph
Dersin Ön Koşulu
yok
Kaynaklar
D. B. West, Introduction to Graph Theory,Prentice-Hall of India/Pearson, 2009.
Notlar
J. A. Bondy and U. S. R. Murty, Graph Theory and Applications, 2008.
Dersin Öğrenme Çıktıları
| Sıra | Dersin Öğrenme Çıktıları |
|---|---|
| ÖÇ01 | Grafların temsilini bilir, problemlere uygular |
| ÖÇ02 | Bağlı grafları bilir |
| ÖÇ03 | Kapsayan ağaçları bilir |
| ÖÇ04 | İki-parçalı grafları bilir |
| ÖÇ05 | Hamilton ve Euler yollarını bilir |
| ÖÇ06 | Köşe ve kenar renklemeyi bilir |
| ÖÇ07 | Düzlem grafları bilir |
Program Öğrenme Çıktıları ile İlişkisi
| Sıra | Tür | Program Öğrenme Çıktıları | Duzey |
|---|---|---|---|
| PÖÇ01 | Bilgi - Kuramsal, Olgusal | Lisans düzeyinde kazanılan yetkinlikler temelinde Bilgisayar Mühendisliği temel alanında özgün çalışmalar için gerekli temeli sağlayan ileri düzeyde bilgi ve kavrayışa sahiptir. | 4 |
| PÖÇ02 | Bilgi - Kuramsal, Olgusal | Mühendislik alanında bilimsel araştırma yaparak bilgiye genişlemesine ve derinlemesine ulaşır, bilgiyi değerlendirir, yorumlar ve uygular. | 4 |
| PÖÇ03 | Yetkinlikler - Öğrenme Yetkinliği | Mesleğinin yeni ve gelişmekte olan uygulamalarının farkında olup, gerektiğinde bunları inceler ve öğrenir. | 3 |
| PÖÇ04 | Yetkinlikler - Öğrenme Yetkinliği | Mühendislik problemlerini kurgular, çözmek için yöntem geliştirir ve çözümlerde yenilikçi yöntemler uygular. | 3 |
| PÖÇ05 | Yetkinlikler - Öğrenme Yetkinliği | Analitik, modelleme ve deneysel esaslı araştırmaları tasarlar ve uygular, bu süreçte karşılaşılan karmaşık durumları çözümler ve yorumlar. | 4 |
| PÖÇ06 | Yetkinlikler - Öğrenme Yetkinliği | Yeni ve/veya özgün fikir ve yöntemler geliştirir, sistem, parça veya süreç tasarımlarında yenilikçi çözümler geliştirir. | |
| PÖÇ07 | Beceriler - Bilişsel, Uygulamalı | Öğrenme becerilerine sahip olur. | 3 |
| PÖÇ08 | Beceriler - Bilişsel, Uygulamalı | Bilgisayar Mühendisliğinin yeni ve gelişmekte olan uygulamalarının farkında olup gerektiğinde bunları inceler ve öğrenir. | 2 |
| PÖÇ09 | Beceriler - Bilişsel, Uygulamalı | Çalışmalarının süreç ve sonuçlarını Bilgisayar Mühendisliği alanındaki veya alan dışındaki ulusal ve uluslararası ortamlarda açık bir şekilde yazılı veya sözlü olarak aktarır. | 2 |
| PÖÇ10 | Beceriler - Bilişsel, Uygulamalı | Bilgisayar Mühendisliğinde uygulanan güncel teknik ve yöntemler ile bunların kısıtları hakkında kapsamlı bilgiye sahip olur. | 3 |
| PÖÇ11 | Beceriler - Bilişsel, Uygulamalı | Bilgisayar Mühendisliğinin gerektirdiği düzeyde bilgisayar yazılımı ile birlikte bilişim ve iletişim teknolojilerini ileri düzeyde etkileşimli olarak kullanır. | 2 |
| PÖÇ12 | Bilgi - Kuramsal, Olgusal | Mesleki tüm etkinliklerde toplumsal, bilimsel ve etik değerleri gözetir. |
Haftalık Akış
| Hafta | Konu | Ön Hazırlık | Yöntemler |
|---|---|---|---|
| 1 | Introduction to Graphs, isomorphism, subgraphs, matrix representations, degree | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 2 | Connected graphs, paths, distance, cut-vertices, cut-edges, weighted graphs, shortest path | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 3 | Kapsayan ağaçlar | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 4 | Bipartite graflar, line graflar, chordal graflar | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 5 | Eulerian grafları, Fleury algoritması, chinese-postman problemi | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 6 | Hamilton grafları | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 7 | Arasınav için tekrar | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 8 | Ara Sınav | Ders notları ve uygulamalara hazırlanmak | Ölçme Yöntemleri: Proje / Tasarım |
| 9 | Independent-covering-mathcing graflar, mükemmel eşleme | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 10 | Düğüm renkleme, kromatik sayı ve klikler, açgözlü renkleme, Brook teoremi | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 11 | Kenar renkleme, Gupta-Vizing teoremi, class-1 ve class-2 grafları | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 12 | Düzlem graflar, 4 ve 5 renkleme | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 13 | Directed graph, underlying graph, outdegree, in-degree, connectivity, orientation, Eulerian directed graphs, Hamilton directed graphs, tournaments | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 14 | Öğrenci sunumları | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 15 | Final için tekrar | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 16 | Yarıyıl Sonu Sınavları | Ders notları ve uygulamalara hazırlanmak | Ölçme Yöntemleri: Yazılı Sınav |
| 17 | Yarıyıl Sonu Sınavları | Ders notları ve uygulamalara hazırlanmak | Ölçme Yöntemleri: Yazılı Sınav |
Öğrenci İş Yükü - AKTS
| Çalışmalar | Sayısı | Süresi (Saat) | İş Yükü (Saat) |
|---|---|---|---|
| Ders ile İlgili Çalışmalar | |||
| Ders (Sınav haftaları dahil değildir) | 14 | 3 | 42 |
| Sınıf Dışı Ders Çalışma (Ön çalışma, pekiştirme) | 14 | 5 | 70 |
| Değerlendirmeler ile İlgili Çalışmalar | |||
| Ödev, Proje, Diğer | 0 | 0 | 0 |
| Ara Sınavlar (Yazılı, Sözlü, vs.) | 1 | 15 | 15 |
| Yarıyıl/Yıl Sonu/Final Sınavı | 1 | 30 | 30 |
| Toplam İş Yükü (Saat) | 157 | ||
| Toplam İş Yükü / 25 (s) | 6,28 | ||
| AKTS | 6 AKTS | ||