Dersin Amacı: |
Çizgeler ve çizge algoritmaları üzerine bilgi edinmek. Çizgelerin bilgisayar bilimlerindeki uygulamaları üzerine bilgi edinmek. Bilgisayar bilimleri ve mühendisliğindeki problemlerin çizgeler ile modelleme yeteneğinin kazandırılması. Çizge kuramındaki problemlerin bilgisayarlar ile çözebilme yeteneği kazandırılması.
|
Dersin İçeriği: |
Çizge Kuramının Tarihçesi, Çizge Kuramının Kullanım Alanları, Yollar, Ağaçlar ve Döngüler, En Kısa Yol Problemi, Bağlılık, Euler Turu, Hamilton Döngüleri, Ağlar, Minimum ve Maksimum Ağ Akış Problemleri, Çizge Ayrıştırma, Kombinatoryel Uygulamalar. |
Hafta |
Konu |
Ön Hazırlık |
1) |
Çizge kuramının temelleri. Çizgelerin uygulamaları (telekomünikasyon ağları ve benzerleri)
|
|
2) |
Bazı özel çizge aileleri. Euler çizgeleri. Derece dizileri. Havel-Hakimi algoritması. İzomorfik çizgeler.
|
|
3) |
Çizgelerin bilgisayarda gösterimi. DFS ve BFS algoritmaları.
|
|
4) |
Minimum kapsayan ağaçlar. Kruskal ve Prim algoritmaları
|
|
5) |
Eşleştirme problemleri ve uygulamaları. Hall teoremi. En kısa patika algoritmaları.
|
|
6) |
Bağlantı. Güçlü bağlantılı komponentler
|
|
7) |
Maksimum akış problemleri. Klik, köşe kaplaması, Bağımsız kümeler.
|
|
8) |
Ara sınav |
|
9) |
Çizge boyama sayısı, üst sınırlar, Brook teoremi.
|
|
10) |
Çizge boyama problemi ve ilgili algoritmalar.
|
|
11) |
Düzlemsel çizgeler. Kuratowski teoremi.
|
|
12) |
Kenar boyama problemi.
|
|
13) |
Hesaplama karmaşıklığına giriş. Çizgeler üzerinde tanımlanan NP tam problemlere örnekler (En uzun patika, Hamilton döngüsü).
|
|
14) |
Çizgeler üzerinde tanımlanan kombinatoryal oyunlar. Kenar arama problemi ve varyasyonlarının mühendislikteki uygulamaları. |
|
15) |
Final sınavı |
|
|
Dersin Program Kazanımlarına Etkisi |
Katkı Payı |
1) |
Bilgisayar mühendisliği çalışmalarını yürütmeyi sağlayacak kavram ve yetkinliklerin kazandırılması ve bilgisayar bilimleri yöntemlerini güncel sorunları çözümlemede veya ihtiyaçları gidermede kullanabilme becerisi. |
|
2) |
Bir bilgi sistemini modern tasarım araçları ile tasarlayabilme veya var olan bir sistemdeki sorunları saptama, tanımlama ve çözümleme becerisi. |
|
3) |
Gereksinimlerin analiz edilmesi, uygun donanım ve yazılım çözümlerinin belirlenmesi, kullanılması veya gerçeklenmesi becerisi. |
|
4) |
Bilimsel yöntemlere uygun olarak, deney, gözlem, uygulama ve akıl yürütmeye dayalı çözümleme ve yorumlama becerisi. |
|
5) |
Bireysel ve takım halinde veya gereğinde disiplinler arası takımlarda çalışma becerisi. |
|
6) |
Farklı ortamlarda ve farklı disiplinlerle iletişim kurma becerisi. |
|
7) |
Yeniliklere açık olma, öğrenmeye açık olma ve kendini yenileme becerisi. |
|
8) |
Mesleki ve ahlaki sorumluluk taşıma. |
|
9) |
Proje planlaması ve yönetimi yapabilme; gereğinde girişimcilik ve yenilik yapabilme becerisi. |
|
10) |
Sosyal, ekonomik, çevresel sorunlar hakkında farkındalık sahibi olma ve mesleğini bu bilinç ile gerçekleştirme. |
|
11) |
Sorgulayıcı ve sıra dışı düşünerek, özgün çözüm yolları bulabilme, alternatif çözüm yollarını karşılaştırabilme. |
|
12) |
İnsan ve toplum odaklı olma, kültürel duyarlılık kazanma ve sosyal sorumluluk projelerinin farkında olma. |
|