Dokuz Eylül Üniversitesi Ders Katoloğu / Bilgi Paketi

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	Ödev 1; Proje konuları
4	OPL kullanarak bir kombinatoryel problemin modellenmesi - 2	Proje gruplarının oluşturulması
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ı	Ödev 2
7	Kısıt programlama için arama stratejileri, Değişken ve değer sıralama stratejileri
8	Ara sınav
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	Ödev 3
12	Optimizasyon problemleri
13	Kısıt programlamanın karışık tamsayılı programlama ile karşılaştırması ve hibrit stratejiler
14	Proje sunumları

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	OD	Ödev
3	FN	Final
4	BNS	BNS	VZ * 0.30 + OD * 0.30 + FN * 0.40
5	BUT	Bütünleme Notu
6	BBN	Bütünleme Sonu Başarı Notu	VZ * 0.30 + OD * 0.30 + BUT * 0.40

*** Bütünleme Sınavı Yapılmayan Birimlerde Bütünleme Kriteri Dikkate Alınmaz.

Değerlendirme Yöntemlerine İliskin Aciklamalar

Yok

Değerlendirme Kriteri

İlan Edilecektir.

Dersin Öğretim Dili

Türkçe

Derse İlişkin Politika ve Kurallar