1. Anasayfa

Ders Notları

100% Complete (success)
Dikkat !!! Lütfen okuyunuz ...

Öğretim Üyesi (Üyeleri): Dr. Öğr. Üyesi Sercan Demirci Dr. Öğr. Üyesi Meryem Soysaldı Şahin *

(*) Ders notu girebilmek için, bu alanda kendi isminiz yazıyor olmalı...

  • Bologna verilerinin girilmesi;
    ubys.omu.edu.tr adresinden,
    ÜBYS' de Öğretim Elemanları yetkisi seçilmeli... Öğretim elemanı danışmanlık işlemlerinden yapabilirsiniz...
Yıl: 2023, Dönem: Güz
HB747, Ayrık Yapılar ve Algoritmalar (mufredatId:6463, dersId: 47307, programId: 5229)
Ders Kitabı / Malzemesi / Önerilen Kaynaklar

 Algorithm Design by Jon Kleinberg and Eva Tardos. Addison Wesley, 2006.  Introduction to the Design and Analysis of Algorithms by Anany Levitin, 2nd edition Pearson-Addison-Wesley , Michael Sipser,  Intro. to the Theory of Computation, 2nd ed., Thompson Course Technology, 2005.  Introduction to Algorithms, T.Cormen, C.Leiserson, R.Rivest, MIT Press, 2009.

Dersin İçeriği

Algoritmaların tasarımı ve analizi: algoritma analizinin temelleri, computational tractability, asimptotik büyüme oranı, çizgeler: çizge bağlılığı ve çizge üzerinde geçiş algoritmaları, çift taraflılık, topolojik sıralama algoritması, açgözlü algoritmalar: aralık planlama, minimum kapsama ağacı algoritmaları, kümeleme algoritmaları. Böl ve fethet yaklışımlı algoritmaların, dinamik programlama yaklaşımı içeren algoritmalar ve dağıtık algoritmaların detaylı incelenmesi. NP ve computational intractability: polinom zamanlı indirgemeler, etkin sertifikasyon yöntemleri ve NP’nin tanımı, NP tam problem örnekleri, sıralama problemleri, partitionin problemleri, çizge boyama, numerik problemler, co-NP ve the asymmetry of NP intractability. Pspace’deki bazı zor problemlerin analizleri, yaklaşıklık algoritmalar ve örnekleri, rassal algoritmalar ve örnekleri.

Dersin Amacı

Bu dersin amacı, öğrencilerin algoritma tasarlayabilmesini ve bu algoritmaların analizini yapabilmesini, bir algoritmanın doğruluğunun kanıtlayabilmesini, NP tamlık, tractability, yaklaşık ve rassal algoritma kavramlarını öğrenmelerini sağlamaktır.

Haftalık Ders İçeriği

Hafta Teorik Uygulama Laboratuar Ders Notları
1 Temel Bilgiler: Ayrık matematik; Veri yapıları. Algoritmalara Giriş: Algoritma nedir; Çeşitli problemler. Algoritma Analizi: Algoritma karmaşıklığı
2 Temel Bilgiler: Ayrık matematik; Veri yapıları. Algoritmalara Giriş: Algoritma nedir; Çeşitli problemler. Algoritma Analizi: Algoritma karmaşıklığı
3 Böl ve fethet yaklaşımlı algoritmalar: mergesort, en yakın nokta çiftleri bulma algoritması, tamsayı çarpma, Karatsuba çarpma algoritması, matris çarpım algoritmaları.
4 Böl ve fethet yaklaşımlı algoritmalar: mergesort, en yakın nokta çiftleri bulma algoritması, tamsayı çarpma, Karatsuba çarpma algoritması, matris çarpım algoritmaları.
5 Böl ve fethet yaklaşımlı algoritmalar: mergesort, en yakın nokta çiftleri bulma algoritması, tamsayı çarpma, Karatsuba çarpma algoritması, matris çarpım algoritmaları.
6 Sıralama algoritmaları
7 Sıralama algoritmaları, arama algoritmaları
8 Genel Tekrar
9 Ara Sınav
10 NP’nin tanımı, polinom zaman indirgemeleri, denklik yoluyla indirgeme
11 Yaklaşık algoritmalar
12 Açgözlü algoritmalar
13 Çizgeler, çizge gösterimi, ağaçlar, breadth first search algoritması, depth first search algoritması, bağlı bileşen bulma algoritması, çift taraflı çizgeler, yönlü döngü içermeyen çizgeler, topolojik sıralama algoritması.
14 Çizgeler, çizge gösterimi, ağaçlar, breadth first search algoritması, depth first search algoritması, bağlı bileşen bulma algoritması, çift taraflı çizgeler, yönlü döngü içermeyen çizgeler, topolojik sıralama algoritması.
15 Genel Tekrar
16 Final