Ders Veri Yapıları & Algoritmalar I dersinin devamı niteliğinde olup algoritma tasarımı üzerine odaklanılacaktır. İleri düzey veri yapıları ve algoritmalar, algoritma analizi ile beraber ele alınacaktır. Amortize analiz, ağaç ve öncelik kuyrukları için kendiliğinden düzenlenen veri yapıları, AVL ağaçları, kırmızı-siyah ağaçları; union-find; ağaç, katar ve çizgeler için etkin algoritmalar; sıralama ve örüntü eşleştirme algoritmaları, metin işleme; dinamik programlama, greedy, böl-ve-yönet, yaklaşımları ele alınacaktır.
Ön Koşullar
Ayrık Matematik, Veri Yapıları ve Algoritmalar I dersini almış olmak
Eş Koşullar
XXX Ders Adı...
Özel Koşullar
Herhangi bir programlama dilini, örneğin C programlama dilini biliyor olmak
ØAnany Levitin, Introduction to the Design and Analysis of Algorithms. Pearson Education, 3rd ed. ISBN: 9780132316811.
ØIntroduction to Algorithms, 3rd Edition (The MIT Press) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
Diğer Kaynaklar
Haftalık Ders Programı
Hafta
Dersin İçeriği
Öğretim Yöntem ve Teknikleri
1. Hafta
Derse giriş ve genel tanıtım.
Algoritma analizi, Fonksiyonların büyümesi, Asimptotik gösterim, Böl-ve-yönet
Sözlü anlatım
2. Hafta
Sıralama ve Sıra istatistikleri: Öncelik kuyrukları, hızlı sıralama, doğrusal zamanda sıralama, medyanlar ve sıra istatistikleri.
Sözlü anlatım
3. Hafta
İkili arama ağaçları, düzenlenen veri yapıları, siyah-kırmızı ağaçları.
Sözlü anlatım ve lab. uygulaması
4. Hafta
Durum makinası ile metinde sözcük arama ve uygulaması. Bir programlama diliyle durum makinası uygulaması geliştirilmesi
Sözlü anlatım ve lab. uygulaması
5. Hafta
Graf teorisine giriş ve grafların gösterilimi: Komşuluk matrisi.
Sözlü anlatım ve lab. uygulaması
6. Hafta
Graf türleri ve grafların bellekte tutulması; örnek uygulamaları
Sözlü anlatım ve lab. uygulaması
7. Hafta
Graf teorisi ile çözülebilen problemlerin incelenmesi: Graf renklendirme, en kısa yol algoritması, yol ağacı problemi vs.
Sözlü anlatım ve lab. uygulaması
8. Hafta
Graf renklendirme ve çakışmadan ders atama probleminin çözülmesi
Sözlü anlatım ve lab. uygulaması
9. Hafta
En kısa yol (Shortest Path) algoritmaları: Dijkstra algoritmasının davranışı ve gerçeklenmesi
Sözlü anlatım ve lab. uygulaması
10. Hafta
Harita üzerinde Dijkstra algoritmasının uygulması
Sözlü anlatım ve lab. uygulaması
11. Hafta
En kısa yol ağacı (minumum spanning tree) algoritmaları: Kruskla algoritmasının incelenmesi ve uygulaması
Sözlü anlatım ve lab. uygulaması
12. Hafta
Algoritmaların yürütme zamanı (running time) ve karmaşıklğının (coplexity) hesaplanması. Büyük O notasyonu.
Sözlü anlatım ve lab. uygulaması
13. Hafta
Sıkıştırma algoritmaları ve programları
Sözlü anlatım ve lab. uygulaması
14. Hafta
Huffman kodlama ağacı ve örnek uygulması: Karakterlerin kullanım sıklığı ve Huffman ağacının oluşturulması.
Sözlü anlatım ve lab. uygulaması
15. Hafta
Olasılık Teorisi üzerine uygulama geliştirme
Sözlü anlatım ve lab. uygulaması
16. Hafta
Gramer çözümleme algoritmaları
Sözlü anlatım ve lab. uygulaması
17. Hafta
Bilgisayar Olimpiyat Sorularının İncelenmesi ve bazılarının çözülmesi
Sözlü anlatım ve lab. uygulaması
Değerlendirme Ölçütleri
Ölçüt Tipleri
Adet
Yüzdesi(%)
Ara sınav(lar)
1
25
Ödevler / Dönem Ödevi / Sunum
3
15
Projeler
1
20
Derse Devam / Katılım
1
5
Final
1
35
ÖÇ-1
Yazılım tabanlı problemlerin modellenmesi
ÖÇ-2
En uygun algoritmaların seçilebilmesi
ÖÇ-3
Graf teorisinin anlaşılması ve problem çözümlerinde kullanılması
ÖÇ-4
Veri modellerinin mühendislik uygulamalarında kullanma becerisi kazanma
ÖÇ-5
Durum makinalarının ve metin çözümlemesinin anlaşılması
Program Çıktıları
PÇ-1
Matematik, fen bilimleri ve ilgili mühendislik disiplinine özgü konularda yeterli bilgi birikimi; bu alanlardaki kuramsal ve uygulamalı bilgileri, karmaşık mühendislik problemlerinde kullanabilme becerisi.
PÇ-2
Karmaşık mühendislik problemlerini saptama, tanımlama, formüle etme ve çözme becerisi; bu amaçla uygun analiz ve modelleme yöntemlerini seçme ve uygulama becerisi.
PÇ-3
Karmaşık bir sistemi, süreci, cihazı veya ürünü gerçekçi kısıtlar ve koşullar altında, belirli gereksinimleri karşılayacak şekilde tasarlama becerisi; bu amaçla modern tasarım yöntemlerini uygulama becerisi.
PÇ-4
Mühendislik uygulamalarında karşılaşılan karmaşık problemlerin analizi ve çözümü için gerekli olan modern teknik ve araçları geliştirme, seçme ve kullanma becerisi; bilişim teknolojilerini etkin bir şekilde kullanma becerisi.
PÇ-5
Karmaşık mühendislik problemlerinin veya disipline özgü araştırma konularının incelenmesi için deney tasarlama, deney yapma, veri toplama, sonuçları analiz etme veyorumlama becerisi.
PÇ-6
Disiplin içi ve çok disiplinli takımlarda etkin biçimde çalışabilme becerisi; bireysel çalışma becerisi.
PÇ-7
Sözlü ve yazılı etkin iletişim kurma becerisi; en az bir yabancı dil bilgisi; etkin rapor yazma ve yazılı raporları anlama, tasarım ve üretim raporları hazırlayabilme, etkin sunum yapabilme, açık ve anlaşılır talimat verme ve alma becerisi.
PÇ-8
Yaşam boyu öğrenmenin gerekliliği bilinci; bilgiye erişebilme, bilim ve teknolojideki
gelişmeleri izleme ve kendini sürekli yenileme becerisi.
PÇ-9
Etik ilkelerine uygun davranma, mesleki ve etik sorumluluk bilinci; mühendislik uygulamalarında kullanılan standartlar hakkında bilgi.
PÇ-10
Proje yönetimi, risk yönetimi ve değişiklik yönetimi gibi, iş hayatındaki uygulamalar hakkında bilgi; girişimcilik, yenilikçilik hakkında farkındalık; sürdürülebilir kalkınma hakkında bilgi.
PÇ-11
Mühendislik uygulamalarının evrensel ve toplumsal boyutlarda sağlık, çevre ve güvenlik üzerindeki etkileri ve çağın mühendislik alanına yansıyan sorunları hakkında bilgi;mühendislik çözümlerinin hukuksal sonuçları konusunda farkındalık.