UBI 545 - Dağıtık Algoritmalar

ÖĞRETİM ÜYESİ
Orhan Dağdeviren, Doç.Dr.
ASİSTANT
Murat Kurt
DERS NOTU

DERSİN AMACI
Bu dersin amacı öğrencilerin; dağıtık algoritmaları kavramaları, analiz edebilmeleri, dağıtık algoritmaların doğrulukları ve perfonmansları hakkında yorum yapabilmeleri , limitlerini kavrayabilmelerini ve yeni dağıtık algoritmalar geliştirebilmelerini sağlamaktır.

DETAYLAR

Dersin Adı

Dağıtık Algoritmalar

Dersin Kodu

UBI 545

Dersin Türü

Seçmeli

Dersin Seviyesi

Yüksek Lisans

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

1

Dersin Öğretim Üyesi

(Üyeleri)

Yrd.Doç.Dr. Orhan Dağdeviren

Öğretim Sistemi

Örgün Eğitim

Eğitim Dili

Türkçe

Dersin Ön Koşulu Olan Ders(ler)

İşletim Sistemleri, Dağıtık Sistemler

Ders İçin Önerilen Diğer Hususlar

Yok

Staj Durumu

Yok

Dersin Amacı

Bu dersin amacı öğrencilerin; dağıtık algoritmaları kavramaları, analiz edebilmeleri, dağıtık algoritmaların doğrulukları ve perfonmansları  hakkında yorum yapabilmeleri , limitlerini kavrayabilmelerini  ve yeni dağıtık algoritmalar geliştirebilmelerini sağlamaktır.

Öğrenme Çıktıları

1.       Dağıtık Algoritma kavramını kavrayabilme.

2.       Problemlere farklı bir bakış açısıyla dağıtık bir şekilde çözüm üretebilme.

3.       Bilinen  dağıtık problemleri ve çözümler hakkında bilgi sahibi olma.

4.       Dağıtık algoritmaların analizini yapabilme.

5.       Dağıtık ortamdaki çözümlerde oluşabilecek problemleri fark edebilme.

6.       Problemlerin dağıtık bir şekilde düşünerek dağıtık algoritmasını yazabilme.

7.       Dağıtık yazılım geliştirmek için çağdaş teknolojilerini kullanabilme.

8.       Bilinen seri çalışan bir algoritmayı dağıtık hale çevirebilme.

Dersin İçeriği

Dağıtık çizge algoritmaları: dağıtık hesaplama modelleri, çizge teorisine ve algoritmaları tekrarı, köşe ve ağaç kapsama cover algoritmaları, dağıtık broadcast, convergecast minimum spannin tree  algoritması, GHS algoritması, dağıtık DFS ve dağıtık BFS, matching, bağımsız küme ve hakim küme, clustering; temel dağıtık algoritmalar: zaman senkronizasyonu, dağıtık karşılıklı dışlama algoritmaları, sonlanma tespiti ve dağıtık ortamlarda ölü-kilit problemleri ve örnek çözüm algoritmaları, anlaşma protokolleri, oto-stabilizasyon.

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

HAFTA

KONULAR

Teorik Dersler

Uygulama

1

Dağıtık sistemlerin tanımı, dağıtık uygulama örnekleri,  mesaj gönderimi modelleri, paylaşımlı bellek modeli.

Programlama Ödevi

2

Sonlu durum makineleri, görevler, threadler, thread çeşitleri ve semafor örnekleri.

 

3

Çizge teorisi ve temel çizge algoritmaları: breadth first search algoritması, depth first search algoritması,  çizge bağlılığı, topolojik sıralama algoritması.

Programlama Ödevi

4

Köşeve ağaç boyama algoritmaları, dağıtık köşe ve ağaç boyama algoritması, dağıtık ağaç tabanlı algoritmalar: broadcast ve convergecast algoritmaları.

 

5

Breadth first search  ağaç oluşturma, flooding, seri ve dağıtık MST algoritmaları, cycle ve cut kavramları.

Programlama ödevi

6

Dağıtık sistemlerde zaman senkronizasyonu, Berkeley zaman protokolü, mantıksal saatler,  Lamport’un logical clock algoritması, vektör saatleri,  matris saatleri

Araştırma Ödevi

7

Kaynak paylaştırma, kritik bölge problemi, donanımsal senkronizasyon,  semaforlar, semafor problem örnek kod incelemesi.

Literatür Tarama

8

Ara Sınav

 

9

Karşılıklı dışlama algoritmaları: Lamport’un algoritması, Ricart-Agrawala’nın algoritması, Suzuki-Kasami’nin algoritması, Raymond’ın algoritması, Maekawa’nın algoritması.

Araştırma Ödevi

10

Dağıtık sistemlerin global durumu, Chandy Lamport’un algoritması,  Lai Yang’ın algoritması, snapshot.

Literatür

Tarama

11

Ölü kilitler ve sonlanma tespiti,  Dijkstra-Scholten algoritması, dağıtık ölüilit, Chandy Misra Haas ölüilit önleme algoritması,

 

12

Lider seçimi algoritmaları: Bully algoritması,  LeLann’ın algoritması, Chang Roberts algoritması, Senkronizörler.

 

13

Anlaşma protokolleri, Bizans generalleri problemi, konsensus.

 

14

Anlaşma  protokolleri,  oto stabilizasyon.

 

15

Proje Sunumları

 

16

Final Sınavı

 

 

Ders Kitabı/Malzemesi/Önerilen Kaynaklar

 

 

 

 

1.Sukumar      Ghosh, Chapman and Hall, (2006)  Distributed Systems : An Algorithmic Approach, (we will follow this book   more closely than all others)

2.Vijay Garg, , John   Wiley, (2002)Elements of Distributed Computings

3.Gerard Tel, Cambridge University Press, (2000)Introduction to Distributed Algorithms, 2nd Ed.,

4.David   Peleg, SIAM, Philadelphia, PA, 2000.Distributed Algorithms, Locality Sensitive Approach

5.Jon Kleinberg and Eva Tardos(2006) Algorithm Design Addison Wesley,.

6.Douglas West (2000)Introduction to Graph Theory, 2nd Edition, Prentice-Hall,

7. J.Gross and J. Wellen, Chapman & Hall, (2005)  Graph Theory and Its Applications, 2nd Edition,

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