DERS TANITIM ve UYGULAMA BİLGİLERİ

Dersin Adı Kodu Yarıyıl T+U+L (saat/hafta) Türü (Z / S) Yerel Kredi AKTS
Hesaplamalı Geometri CE 506 Bahar 03+00+00 Seçmeli 3 8.0
Akademik Birim:
Öğrenim Türü:
Ön Koşullar Yok
Öğrenim Dili: İngilizce
Dersin Düzeyi: Yüksek Lisans
Dersin Koordinatörü: Öznur YAŞAR DİNER
Dersin Amacı: 1) Hesaplamalı Geometri problemleri için algoritma analizi
2) Geometrik problemleri çözmek için kullanılan gelişmiş veri yapıları ve algoritmaları anlamak
3) Voronoi diyagramları ve Delaunay Üçgenlemeleri kavramlarını tanıtmak.
4) Teorileri “En yakın komşu sorgusu” ve “Robot Hareket Planlaması” gibi gerçek geometrik
problemleri çözmek için kullanmak
Dersin İçeriği: Hesaplamalı geometri algoritmalarının performans analizi. Konveks gövde hesaplama
algoritmaları, üçgen poligonlar, düşük boyutlu doğrusal programlama ve Voronoi diyagramları.
Açgözlü, rastgele, dinamik programlama ve bölme-ve-fethetme algoritma tasarımı. Arazi araması,
nokta konumu, kesit kesişimi ve ışın çekimi için gerekli geometrik veri yapıları.
Dersin Öğrenme Çıktıları (ÖÇ):
  • 1- Hesaplamalı geometri algoritmalarının doğruluğunu ispatlayabilme ve performansını analiz edebilme
  • 2- Konveks gövde hesaplama algoritmaları, üçgen poligonlar, düşük boyutlu doğrusal programlama ve Voronoi diyagramları gibi çeşitli geometrik problemlerin algoritmalarını kullanabilme
  • 3- Açgözlü, rastgele, dinamik programlama ve bölme-ve-fethetme gibi algoritmaların tasarım tekniklerini kullanabilme
  • 4- Arazi araması, nokta konumu, kesit kesişimi ve ışın çekimi için gerekli geometrik veri yapılarını kavrama
Dersin Öğrenme Yöntem ve Teknikleri


HAFTALIK PROGRAM

HaftaKonularÖn Hazırlık ÖÇ
1 Hesaplamalı Geometri Matematiği 1
2 Çeşitli konveks gövde algoritmaları. Alt sınırlar. Uzaydaki dışbükey gövde. 2
3 Uçak süpürme algoritması. 2
4 Monoton poligonun üçgenlemesi. 2
5 Döküm geometrisi. Yarım düzlem kavşakları. 2
6 Artımlı ve rastgele hale getirilmiş algoritmalar. 4
7 1 boyutlu aralık araması 3
8 Kd-ağaçları. Aralık ağaçları. 4
9 Yüksek boyutlu aralık ağaçları. 4
10 Trapez haritalar. Nokta yeri saptama için rastgele artımlı bir algoritma. 4
11 Voronoi diyagramları 4
12 Düzlemsel nokta kümelerinin üçgenlemesi. 2
13 Hat düzenlemeleri. Artımlı yapım teknikleri. 4
14 Alandaki ileri uygulamaların tartışılması 1


ZORUNLU ve ÖNERİLEN OKUMALAR

M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkoph, “Computational Geometry: Algorithms and Applications, 3rd edition,” Springer, 2008, ISBN: 978-3-642-09681-5


DİĞER KAYNAKLAR

1) Efi Fogel, Dan Halperin, and Ron Wein (2012). CGAL Arrangements and Their Applications, A Step-by-Step Guide. Springer-Verlag. ISBN 978-3-642-17283-0.
2) Fajie Li and Reinhard Klette (2011). Euclidean Shortest Paths. Springer-Verlag. ISBN 978-1-
4471-2255-5.
3) Erik D. Demaine; Joseph O'Rourke (2007). Geometric Folding Algorithms: Linkages,
Origami, Polyhedra. Cambridge University Press. ISBN 978-0-521-85757-4.
4) Jacob E. Goodman; Joseph O'Rourke, eds. (2004) [1997]. Handbook of Discrete and
Computational Geometry. North-Holland. 1st edition: ISBN 0-8493-8524-5, 2nd edition: ISBN
1-58488-301-4.


DEĞERLENDİRME SİSTEMİ

Yarıyıl İçi ÇalışmalarıSayıKatkı Payı (%)
Katılım - -
Laboratuvar - -
Uygulama 1 10
Arazi Çalışması - -
Proje 1 20
Ödev - -
Sunum/Jüri - -
Derse Özgü Staj - -
Diğer Uygulamalar (seminer, stüdyo kritiği, workshop vb.) - -
Dersle İlgili Sınıf Dışı Etkinlikler (okuma, bireysel çalışma vb.) - -
Ara Sınavlar/Sözlü Sınavlar/Kısa Sınavlar 1 30
Final Sınavı 1 40
Total: 4 100


İŞ YÜKÜ HESAPLAMASI

EtkinliklerSayısıSüresi (saat)Toplam İş Yükü (saat)
Ders Saati14342
Laboratuvar000
Uygulama15050
Arazi Çalışması000
Proje18080
Ödev000
Sunum/Jüriye Hazırlık000
Derse Özgü Staj000
Diğer Uygulamalara Hazırlık000
Dersle İlgili Sınıf Dışı Etkinlikler000
Ara Sınavlar/Sözlü Sınavlar/Kısa Sınavlar14343
Final Sınavı13535
Toplam İş Yükü (saat):250


PROGRAM YETERLİLİKLERİ (PY) ve ÖĞRENME ÇIKTILARI (ÖÇ) İLİŞKİSİ

# PY1 PY2 PY3 PY4 PY5 PY6 PY7 PY8 PY9 PY10 PY11 PY12
OC1 3 3 3                  
OC2 3 3 3                  
OC3 3 3 3                  
OC4 3 3 3