UBI 602 - Algoritmik Karmaşıklık Teorisi

ÖĞRETİM ÜYESİ
Mehmet Emin Dalkılıç, Prof.Dr.
ASİSTANT
Gül Boztok Algın
DERS NOTU

DERSİN AMACI
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.

DETAYLAR

Dersin Adı

Algoritmik Karmaşıklık Teorisi

Dersin Kodu

UBI602 

Dersin Türü

Zorunlu

Dersin Seviyesi

Doktora

Dersin AKTS Kredisi

7,5

Haftalık Ders Saati

3

Haftalık Uygulama Saati

Yok

Haftalık Laboratuar Saati

Yok

Dersin Verildiği Yıl

1

Dersin Verildiği Yarıyıl

2

Dersin Öğretim Üyesi

(Üyeleri)

Prof. Dr. Mehmet Emin Dalkılıç

Öğretim Sistemi

Örgün Eğitim

Eğitim Dili

Türkçe

Dersin Ön Koşulu Olan Ders(ler)

Veri Yapıları, Ayrık Matematik, İleri Algoritmik Yöntemler

Ders İçin Önerilen Diğer Hususlar

Yok

Staj Durumu

Yok

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.

Öğrenme Çıktıları

1.       Bir algoritmanın gerçekçi kıstlar altında;  zamansal ve alansal analizini ve maliyet araştırmasını yapabilme.

2.       Bir problemi çözebilmek için yeni algoritma tasarlayabilme.

3.       Algoritmaları yaklaşımlarına göre sınıflandırabilme.

4.       Yeni bir problemi var olan başka bir probleme benzeterek çözebilme.

5.       Farklı algoritmaları birbirleriyle çeşitli kısıtlar üstünden karşılaştırabilme.

6.       Algoritmaların performans çıktılarını yorumlayabilme.

7.       Bilgisayar bilimlerinin bilinen algoritma problemleri hakkında geliştirilen çağdaş çözümler hakkında bilgi sahibi olma.

8.       Algoritmaların performanslarını bilinen diğer algoritmalarla eş özelliklerini tespit ederek ölçebilme.

9.       Çözülmesi zor problemlere yaklaşık algoritmalar tasarlayabilme.

Dersin İçeriği

Algoritmaların tasarımı ve  analizi: agoritma analizinin temelleri, computational tractability, asimtotik 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.

Haftalık Ayrıntılı Ders İçeriği (16 Haftalık)

HAFTA

KONULAR

Teorik Dersler

Uygulama

1

Stabil eşleme problemi,  propose-and-reject algoritması, aralık planlama, çift taraflı eşleme paroblemlerinin incelenmesi.  Computational tractability, asimtotik büyüme oranı, çalışma zamanı analizleri.

Problem

Çözümü

2

Ç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ı.

Problem

Çözümü

3

Açgözlü algoritmalar: aralık planlama problemi, optimum Caching, Dijkstra'nın en kısa yol algoritması, coin-changing algoritması.

Problem

Çözümü

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ı.

Problem

Çözümü

5

Dağıtık sistemler, dağıtık algoritmalar: yayın, flooading, convergecast, dağıtık BFS algoritması , dağıtık DFS algoritması, Bellman Ford BFS algoritması, Chang-Robert’ın minimum kapsama ağacı bulmak için Gallagher-Humblet-Spira (GHS) Algoritması, lider seçimi algoritmaları: Bully algoritması, LeLann’ın ring bazlı algoritması, Chang-Robert’ın Algoritması.

Problem

Çözümü

6

Ağ Akışı, maksimum akış ve minimum kesme problemleri, Ford-Fulkerson algoritması, çift taraflı eşleme ve  Fordmaksimum akış probleminin ilişkisi, atama problemi.

Literatür

Tarama

7

NP’nin tanımı, polinom zaman indirgemeleri, denklik yoluyla indirgeme,  gadgetler yardımıyla indirgeme,  3-Satisfiability, hamiltonian cycle problem. P,NP, EXP terimleri. NP tamlık, NP tam problemler , circuit satisfiability, 3-SAT, co-NP ve NP’nin asimetrisi.

 

8

Ara Sınav

 

9

Sıralama problemleri, Hamiltonian Cycle  Problemi, çizge boyama: 3-boyanabilirlik ve clique cover problemleri ilişkisi

 

10

Clique problemi, bağımsız küme ve köşe örtme problemlerinin ilişkisi,  NP zor kavramı, NP tam problem örnekleri: planarcircuitsat, notallequal3sat, hittingset.


11

Pspace kavramı, Quantified Satisfiability,  planlama problemi, 15-Puzzle problemi, Pspace tamlık kavramı, Psapace tam problemler.


12

Tractability’nin sınırlarını genişletmek: az sayıda düğüm içeren köşe örtme bulma, NP zor problemleri ağaçlar üzerinde çözme: ağaç üzerinde bağımsız küme bulma, dalgaboyu Bölümleme çoğullamasıg,  sirküler ok boyama ve aralık boyama problemleri ilişkisi.

Problem

Çözümü

13

Yaklaşık algoritmalar, yük dengeleme, k-merkez seçimi problemi, ücretlendirme yöntemi, vertex cover, set cover, bin packing, gezgin satıcı problemlerine yaklaşık algoritmalar.

Literatür

Tarama

14

Merkez seçimi problemi,  vertex cover,  açgözlü yaklaşımlı köşe örtme problemi, küme örtme probleminin yaklaşık algoritması,  gezgin satıcı problemi ile minimum kapsama ağacı problem ilişkisi.

Problem

Çözümü

15

Rassal algoritmalar, rassallaştırma kavramı,  çekişme problemi çözümü, evrensel minimum dilim: kısaltma algoritması, beklenen değerin doğrusallığı, maksimum 3-SAT, evrensel hashing,  Chernoff sınırları, yük dengeleme, rassal böl ve yönet yaklaşımı.


16

Final Sınavı


 

Ders Kitabı/Malzemesi/Önerilen Kaynaklar

 

 

 

 

1.        Algorithm Design by Jon Kleinberg and Eva Tardos. Addison Wesley, 2006.  

 

2.       Introduction to the Design and Analysis of Algorithms by Anany Levitin, 2nd edition Pearson-Addison-Wesley ,  Michael Sipser,

 

3.       Intro. to the Theory of Computation, 2nd ed., Thompson Course Technology, 2005.

© 2014 Uluslararası Bilgisayar Enstitüsü. TÜM HAKLARI SAKLIDIR.