DERS ADI

: Çizge Kuramı

Ders Bilgileri

Ders Kodu Ders Adı Ders Türü D U L AKTS
BİL 2009 Çizge Kuramı ZORUNLU 4 0 0 6

Dersi Veren Birim

Bilgisayar Bilimleri

Dersin Düzeyi

Lisans

Ders Koordinatörü

DOÇ. DR. ZEYNEP NİHAN BERBERLER

Dersi Alan Birimler

Bilgisayar Bilimleri

Dersin Amacı

Bilgisayar bilimleri problemlerinin çözümünde kullanılacak çizge kuramı kavramlarını öğretmek.

Dersin Öğrenme Kazanımları

1   Çizge kuramı'nın temel kavramları hakkında bilgi sahibi olabilme.
2   Çizge kuramı problemlerini çözebilme.
3   Çizge kuramı kavramları ile bilgisayar bilimleri problemlerini çözebilme.
4   Çizge kuramı kavramları ile etkin algoritmalar tasarlayabilme.
5   Çizge kuramı kavramları ile farklı disiplinlerdeki problemleri çözebilme.

Dersin Öğretim Türü

Örgün Öğretim

Dersin Önkoşulu/Önkoşulları

Yok

Ders İçin Önerilen Diğer Hususlar

Yok

Ders İçeriği

Hafta Konular Açıklama
1 Temel kavramlar Çizge nedir Yollar, çevreler ve zincirler
2 Temel kavramlar (devamı) Tepe dereceleri ve sayma Yönlü çizgeler
3 Ağaçlar ve uzaklık Temel özellikler Örten ağaçlar ve sayımlama
4 Ağaçlar ve uzaklık (devamı) Eniyileme ve ağaçlar Kısa sınav 1
5 Eşleme Eşleme ve örtüler Eşleme algoritmaları ve uygulamaları Genel çizgelerde eşleme
6 Birleştirilmişlik ve yollar Kesimler ve birleştirilmişlik k-birleştirilmiş çizgeler
7 Birleştirilmişlik ve yollar (devamı) Ağ akış problemleri
8 Genel tekrar
9 Çizgelerin boyanması Tepe boyama ve üst sınırlar k-kromatik çizgelerin yapıları
10 Çizgelerin boyanması (devamı) Sayımlama bakış açısı
11 Ayrıt ve çevreler Çizgi çizgeler ve ayrıt boyama Hamilton çevresi Düzlemsellik, boyama ve çevreler Kısa sınav 2
12 Temel Çizge Teorisi Algoritmaları Çizgelerin bilgisayarda temsil şekilleri Genişlik öncelikli arama Derinlik öncelikli arama Topolojik sıralama Güçlü bağlantılı bileşenler
13 En küçük örten ağaç algoritmaları Prim algoritması Kruskal algoritması
14 En kısa yol algoritmaları Dijkstra algoritması Bellman-Ford algoritması Floyd-Warshall algoritması En büyük akış algoritmaları Ford-Fulkerson algoritması Edmonds-Karp algoritması

Ders İçin Önerilen Kaynaklar

Ana kaynak: Introduction to Graph Theory, Dougles West, ISBN 0130144002.
Yardımcı kaynaklar: Handbook of Graph Theory, Jonathan L. Gross, Jay Yellen, ISBN 1-58488-090-2.

Öğrenme ve Öğretme Yöntemleri

Ders, anlatım, sınıf sunumu ve tartışma biçiminde öğretilecek. Öğretilen dersin yanı sıra, öğrencilere gruplar halinde sunumlar hazırlatılacak ve tartışmalı oturumlar şeklinde sundurulacaktır. Dersin bazı haftalarında, daha önce verilen ödev sonuçları tartışılarak pekiştirilecektir.

Değerlendirme Yöntemleri

SIRA NO KISA KOD UZUN ADI FORMUL
1 VZ Vize
2 FN Final
3 BNS BNS VZ * 0.40 + FN * 0.60
4 BUT BÜTÜNLEME
5 BUTBN BÜTÜNLEME SONU BAŞARI NOTU VZ * 0.40 + BUT * 0.60


Değerlendirme Yöntemlerine İliskin Aciklamalar

Yok

Değerlendirme Kriteri

İlan edilecektir.

Dersin Öğretim Dili

Türkçe

Derse İlişkin Politika ve Kurallar

İlan edilecektir.

Dersin Öğretim Üyesi İletişim Bilgileri

zeynep.berberler@deu.edu.tr

Ders Öğretim Üyesi Görüşme Gün ve Saatleri

İlan edilecektir.

Staj Durumu

YOK

İş Yükü Hesaplaması

Etkinlikler Sayısı Süresi (saat) Toplam İş Yükü (saat)
Ders Anlatımı 14 4 56
Haftalık Ders öncesi/sonrası hazırlıklar 14 5 70
Vize Sınavına Hazırlık 1 12 12
Final Sınavına Hazırlık 1 12 12
Final Sınavı 1 2 2
Vize Sınavı 1 2 2
TOPLAM İŞ YÜKÜ (saat) 154

Program ve Öğrenme Kazanımları İlişkisi

PK/ÖKPK.1PK.2PK.3PK.4PK.5PK.6PK.7PK.8PK.9PK.10PK.11PK.12PK.13
ÖK.15
ÖK.255
ÖK.3555
ÖK.455
ÖK.555