DERS ADI

: Kısıt Programlama

Ders Bilgileri

Ders Kodu Ders Adı Ders Türü D U L AKTS
BİL 3122 Kısıt Programlama SEÇMELİ 3 0 0 5

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ı

Bu ders, sonlu alanlar üzerindeki kısıtlamalara dayalı yeni bir programlama paradigmasına giriş sunmayı ve kombinatoryel problemleri çözmek için bu yöntemlerin nasıl kullanılacağıyla ilgili deneyim kazandırmayı amaçlamaktadır. Farklı kısıt modelleme dilleri ve programlama araçlarının, karmaşık kesikli optimizasyon ve kombinatoryel problemlerinin kısıt programlama modellerine dönüştürülmesinde ve belirli arama yöntemlerinin yazımında nasıl kullanılabileceği uygulamalı olarak tanıtılacaktır.

Dersin Öğrenme Kazanımları

1   Bir genel kısıt çözücünün çalışma prensipleri hakkında temel bilgilere sahip olma.
2   Bir kombinatoryel problemi verilen bir kısıt çözücünün yapısal temel kısıt ifadelerini kullanarak bir kısıt problemi olarak modelleyebilme.
3   Kısıt programlarının çalışma hızlarında iyileştirmeye yönelik simetri tespiti ve elemesi, veya filtreleme algoritmaları gibi teknikler hakkında temel bilgilere sahip olma.
4   Tamsayılı doğrusal programlama ve yerel arama gibi kombinatoryel problemlerin modellenmesi ve çözümü için kullanılan teknolojiler konusunda temel bilgiye sahip olma.
5   Farklı kısıt modelleme dilleri ve kısıt programlama araçlarını kullanabilme.

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 Kombinatoryel optimizasyona giriş, Kombinatoryel optimizasyon problemleri için çözüm teknikleri
2 Kombinatoryel optimizasyon uygulamaları, Kısıt programlamaya giriş, Yöneylem araştırmasındaki kısıt sağlama problemleri IBM ILOG OPL dili ve CP Çözücüsü
3 Kısıt programlamada temel kavramlar, OPL kullanarak bir kombinatoryel problemin modellenmesi - 1
4 OPL kullanarak bir kombinatoryel problemin modellenmesi - 2
5 Kısıt tutarlılığı ve yayılması (propagasyonu) - 1, Tanım uzayı daraltma teknikleri
6 Kısıt tutarlılığı ve yayılması - 2, Geri izleme araması
7 Kısıt programlama için arama stratejileri, Değişken ve değer sıralama stratejileri
8 Genel tekrar
9 Global kısıtlar Diğer modelleme dil ve araçları (Choco, GECODE, MiniZinc, vd.)
10 Arama sezgiselleri - 1
11 Arama sezgiselleri - 2, Simetri
12 Optimizasyon problemleri
13 Kısıt programlamanın karışık tamsayılı programlama ile karşılaştırması ve hibrit stratejiler
14 Genel tekrar

Ders İçin Önerilen Kaynaklar

Ana kaynak: Rossi, F., Van Beek, P., Walsh, T., Handbook of Constraint Programming, Elsevier Science, New York, 2006 (ISBN: 9780080463803).
Yardımcı kaynaklar: Marriott, K., Stuckey, P., Programming with Constraints: An Introduction, MIT Press, 1998 (ISBN: 9780262133418).
Hooker, J.N., Integrated Methods for Optimization, Springer International Series in Operations Research & Management Science, Vol. 170, 2012 (ISBN: 9781461419006).

Öğ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

İlgili dönem başında ilan 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 14 4 56
Vize Sınavına Hazırlık 1 10 10
Final Sınavına Hazırlık 1 20 20
Vize Sınavı 1 2 2
Final Sınavı 1 2 2
TOPLAM İŞ YÜKÜ (saat) 132

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

PK/ÖKPK.1PK.2PK.3PK.4PK.5PK.6PK.7PK.8PK.9PK.10PK.11PK.12PK.13
ÖK.1545354
ÖK.245455
ÖK.35545553455
ÖK.454433554
ÖK.54555554555