Eğitmen: Prof. Dr. Tınaz Ekim
Kurum: Boğaziçi Ü.
Tarih: 18-29 Temmuz 2022
Dersin Adı: Graf Teorisi, Optimizasyon ve Algoritmik Düşünme
İçerik: Königsberg şehrinin köprülerinde Euler turları atmak veya haritaları 4 renkle boyamak gibi eğlenceli matematiksel oyunlardan doğan graf teorisi, günümüzde son derece karmaşık ve zor problemlerin çözümünde kullanılıyor: baz istasyonlarına frekans atama, ders çizelgeleri oluşturma, sosyal ağ analizi, hastalıkların (COVID19) yayılması, elektronik devre tasarımı vs.
Öncelikle, günlük hayatta karşılaştığımız bu kombinatoryal optimizasyon problemlerinde optimal çözümü bulmanın zorluğuna değineceğiz. Ardından, bu problemlere bilgisayar yardımıyla çözümler önerebilmek için algoritmik düşünme yöntemlerini inceleyeceğiz. Temel graf teorisi bilgilerini verdikten sonra, zor problemlerin çözümünde graf teorisini nasıl kullandığımızı örneklerle anlatacağız. Bunların yanı sıra, ‘‘bilgisayarlar matematiksel ispatlar yapabilir mi’’ gibi felsefik boyutları da olan soruları örnekleriyle birlikte tartışacağız.
Anahtar Kelimeler: Königsberg köprüleri problemi, Hamiltonian graflar ve Gezgin Satıcı Problemi, hesaplama karmaşıklığı ve NP-zor problemler, 4 renk teoremi, düzlemsel çizgeler, Ramsey sayıları, bilgisayarlı ispatlar.