DERS ADI

: Matematiksel Modellemede Graf Teori Teknikleri

Ders Bilgileri

Ders Kodu Ders Adı Ders Türü D U L AKTS
CSC 5031 Matematiksel Modellemede Graf Teori Teknikleri SEÇMELİ 3 0 0 8

Dersi Veren Birim

Fen Bilimleri Enstitüsü

Dersin Düzeyi

Doktora

Ders Koordinatörü

DOÇ. DR. FİDAN NURİYEVA

Dersi Alan Birimler

Bilgisayar Bilimleri Doktora (İngilizce)
Bilgisayar Bilimleri Yüksek Lisans

Dersin Amacı

Bu dersin amacı graf teori ile kolayca çözülebilen problemlerin genel doğrusal programlama modellerini yazmak ve graf ile çözüm algoritmalarını vermektir.

Dersin Öğrenme Kazanımları

1   Gerçek hayat problemlerini grafla ve dogrusal denklemlerle modelleyebilme
2   Uygun graf teori algoritmalarıyla 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 Graflar ve bilgisayar bilimleri arasındaki ilişkiler ve bazı tanımlar
2 Grafların oluşturulması. Havel Hakimi Teoremi. Tümleyen graf, Düzenli Graflar. Yıldız Graflar. İki Parçalı (Tam) Graflar. Etkilenmiş Alt Graf. İzomorfik Graflar.
3 Graflarda Birleştirilmişlik Kavramı ve bazı Teoremler. Graf İşlemleri (Birleşim, Toplama ve Çarpım). Ağaç tanımı ve bazı Teoremler. Grafların Ortalama Derecesi. Dallanmış alt graf. Tekerlek graf
4 Grafların Boyanması tanımı. Kritik graf tanımı. Graflarda boyama ile ilgili bazı teoremler. Güncel bir problemin Graf boyama kavramı ile çözülmesi. Ayrıt Boyama.
5 Büzülme işlemi. Kromatik polinomlar. Büzülme işlemini kullanarak grafların kromatik polinomlarının ve dallanmış ağaçlarının sayısının bulunması için algoritmalar.
6 Königsberg köprü problemi. Problemin Çözümü için gerekli teoremler ve kavramlar. Bu teoremlerin günlük yaşamda nasıl kullanılabileceğini göstermek.
7 Grafların bilgisayarlarda gösteri şekilleri. Grafların tepe tepe ve tepe ayrıt bağlantı matrisleri. Bu matrislerin rankları ve matrislerin bazı özellikleri. Teoremler.
8 Genel Tekrar
9 Bir grafta en kısa dallanmış ağaç problemi ve doğrusal programlama modeli
10 Steiner problemi
11 En kısa yol problem ve doğrusal programlama modeli
12 Tüm tepe çiftleri arasındaki en kısa yol problemi ve çözüm algoritmaları
13 Belirlenmiş iki tepe arasındaki en kısa yol problem ve çözüm algoritmaları
14 Eşlemeler ve çözüm algoritmaları

Ders İçin Önerilen Kaynaklar

Ana kaynak:
1. Chiristofides, N., Graph Theory An Algorithmic Approach,Academic Press,London,(1975)

Yardımcı kaynaklar:
1. Taha, H.,Operation Research , Printice Hall, Fayetville, (1995)

Öğ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 ODV ÖDEV
2 ARS ARASINAV
3 YSS YIL SONU SINAVI
4 YSBN YIL SONU BAŞARI NOTU ODV * 0.30 + ARS * 0.30 + YSS * 0.40
5 BUT BÜTÜNLEME
6 BUTBN BÜTÜNLEME SONU BAŞARI NOTU ODV * 0.30 + ARS * 0.30 + BUT * 0.40


Değerlendirme Yöntemlerine İliskin Aciklamalar

Yok

Değerlendirme Kriteri

İlan Edilecektir.

Dersin Öğretim Dili

İngilizce

Derse İlişkin Politika ve Kurallar

İlan Edilecektir.

Dersin Öğretim Üyesi İletişim Bilgileri

fidan.nuriyeva@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 3 42
Haftalık Ders öncesi/sonrası hazırlıklar 13 4 52
Vize Sınavına Hazırlık 1 20 20
Final Sınavına Hazırlık 1 20 20
Ödev Hazırlama 2 20 40
Sunum Hazırlama 2 15 30
Final Sınavı 1 2 2
Vize Sınavı 1 2 2
TOPLAM İŞ YÜKÜ (saat) 208

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

PK/ÖKPK.1PK.2PK.3PK.4PK.5PK.6PK.7PK.8PK.9PK.10
ÖK.15555
ÖK.25555