Genel Bilgi
Kod | CENG715 |
Ad | Graph Theory |
Dönem | 2023-2024 Eğitim-Öğretim Yılı |
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ı / Hedefi
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 |