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
Algoritma Analizi CMPE 353 Güz 03+00+00 Seçmeli 3 5
Akademik Birim: Bilgisayar Mühendisliği Bölümü
Öğrenim Türü: Örgün Eğitim
Ön Koşullar CMPE 242
Öğrenim Dili: İngilizce
Dersin Düzeyi: Lisans
Dersin Koordinatörü: Doğan ÇÖRÜŞ
Dersin Amacı: Bu dersin temel amacı öğrenciye problem çözmenin temelleri ve hesapsal verimlilik ile ilgili gerekli bilgiyi, bilgisayar bilimleri ve hesapsal problemlerde yaygın olarak kullanılan algoritmaların tasarım, hesapsal verimlilik analizi ve gerçekleştirimi becerisini kazandırmaktır.
Dersin İçeriği: Algoritma tasarım ve analizi temel kavramlarına giriş. Temel analiz araçlarına genel bir bakış: Fonksiyonları asimtotik olarak yakınsama, toplamları sınırlama ve tekrar bağıntılarını çözme. Verimli olarak çözülebilen problemlerin böl-çöz, randomizasyon, dinamik programlama, amortizasyon, ve obur buluşsallar gibi tasarım tekniklerine odaklı tartışılması. Çeşitli algoritmik kavramların küme, dizi, çizge gibi yapılarla ilgili problemlerde uygulanması.
Dersin Öğrenme Çıktıları (ÖÇ):
  • 1- Özyinelemeyi bir problem çözme ve programlama tekniği olarak kullanabilme becerisi.
  • 2- Randomizasyon, dinamik programlama, obur buluşsallar gibi teknikleri kullanarak algoritma tasarımı becerisi.
  • 3- Algoritmaların zaman verimliliği analizi becerisi.
  • 4- Kümeler, diziler, çizgeler ve geometrik problemlere yönelik geliştirilmiş algoritmaları anlama becerisi.
  • 5- Algoritma gerçekleştirim ve mühendisliği becerisi
  • 6- Algoritma doğruluğu ve verimliliğini sınamaya yönelik hesapsal deneylerin tasarımı becerisi.
Dersin Öğrenme Yöntem ve Teknikleri Sınıfta ders anlatımı, katılımlı problem çözme, kodlama projesi


HAFTALIK PROGRAM

HaftaKonularÖn Hazırlık ÖÇ
1 Dersin genel özeti, bilgisayar bilimlerinde algoritmaların rolü
2 Tümevarımsal tasarım ve örneği: Insertionsort, algoritmaların analizi 1, 3
3 Böl-çöz`e dayalı tasarım ve örneği: Mergesort ve analizi. Randomize algoritmalar ve örneği: Quicksort, ortalama zaman analizi. Lineer zamanda sıralama ve Countingsort algoritması, Enformasyon-teorik altsınırlar. 1,2,3,4
4 Asimtotik notasyon, yaygın fonksiyonlar 3
5 Tekrar bağıntılarını çözme, yaygın tekrar bağıntıları 1,4
6 Artımlı ve Özyinelemeli algoritma tasarım tekniklerinin karşılaştırmasına bir örnek: Maksimum Çarpımı/Toplamı Veren Altdizi Problemi. Vize sınavı öncesi problem çözme. 1,3,4
7 Proje sunumları
8 Çizge algoritmaları: Enine Arama 4
9 Çizge algoritmaları: Boyuna Arama 4
10 Dinamik programlama: Çubuk kesme problemi 2
11 Dinamik programlama: Dinamik Programlama Elementleri, En uzun ortak altdizi problemi 2,4
12 Dinamik programlama: Sırt çantası problemi, Pseudo-polinom zamanlı algoritmalar 2,4
13 Obur buluşsallar: Aktivite seçimi 2,4
14 Obur buluşsallar: Huffman kodlaması 2,4


ZORUNLU ve ÖNERİLEN OKUMALAR

Introduction to algorithms, Cormen, Leiserson, Rivest, SteIn, the mit press, 2nd edition, 2001.


DİĞER KAYNAKLAR

Steven Skiena, The Algorithm Design Manual, 2nd Edition. Springer, 2008.


DEĞERLENDİRME SİSTEMİ

Yarıyıl İçi ÇalışmalarıSayıKatkı Payı (%)
Proje 2 60
Sözlü Sınavlar 1 30
Kısa Sınavlar 2 10
Total: 5 100


İŞ YÜKÜ HESAPLAMASI

EtkinliklerSayısıSüresi (saat)Toplam İş Yükü (saat)
Ders Saati14342
Proje23060
Ödev6318
Final Sınavı155
Toplam İş Yükü (saat):125


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

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