1. Anasayfa

Ders Notları

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

Öğretim Üyesi (Üyeleri): Doç. Dr. Sercan Demirci *

(*) 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: 2025, Dönem: Güz
ASM712, Dağıtık Algoritmalar (mufredatId:6458, dersId: 5613, programId: 5358)
Ders Kitabı / Malzemesi / Önerilen Kaynaklar

1.Sukumar Ghosh, Distributed Systems : An Algorithmic Approach, Chapman and Hall, (2006) . 2.Vijay Garg, Elements of Distributed Computings, John Wiley, (2002). 3.Gerard Tel, Introduction to Distributed Algorithms, 2nd Ed., Cambridge University Press, (2000). 4.David Peleg, Distributed Algorithms, Locality Sensitive Approach, SIAM, Philadelphia, PA, (2000). 5.Jon Kleinberg and Eva Tardos, Algorithm Design, Addison Wesley, (2006). 6.Douglas West, Introduction to Graph Theory, 2nd Edition, Prentice-Hall, (2000). 7. J.Gross and J. Yellen, Graph Theory and Its Applications, 2nd Edition, Chapman & Hall, (2005).

Dersin İçeriği

Dağıtık çizge algoritmaları: Dağıtık hesaplama modelleri, çizge teorisine ve çizge teorik algoritmaların tekrarı, köşe ve ağaç kapsama (cover) algoritmaları, dağıtık herkese gönderim (broadcast), kapsayan ağaç algoritmaları, GHS algoritması, dağıtık DFS ve dağıtık BFS algoritmaları, eşleme, bağımsız küme ve hâkim küme, kümeleme. Temel dağıtık algoritmalar: Zaman senkronizasyonu, dağıtık karşılıklı dışlama algoritmaları, sonlanma tespiti, dağıtık ortamlarda ölü-kilit problemleri ve örnek çözüm algoritmaları, anlaşma protokolleri, oto-stabilizasyon.

Dersin Amacı

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

Haftalık Ders İçeriği

Hafta Teorik Uygulama Laboratuar Ders Notları
1 Dağıtık sistemlerin tanımı, dağıtık uygulama örnekleri, mesaj gönderimi modelleri, paylaşımlı bellek modeli.
2 Sonlu durum makineleri, görevler, threadler, thread çeşitleri ve semafor örnekleri.
3 Çizge teorisi ve temel çizge algoritmaları: BFS algoritması, DFS algoritması, çizge bağlılığı, topolojik sıralama algoritması.
4 Köşe ve ağaç boyama algoritmaları, dağıtık köşe ve ağaç boyama algoritması, dağıtık ağaç tabanlı algoritmalar: broadcast (herkese gönderim) ve convergecast (herkesten toplama) algoritmaları.
5 BFS ağaç oluşturma, yayma (flooding), seri ve dağıtık MST algoritmaları, döngü (cycle) ve kesim (cut) kavramları.
6 Dağıtık sistemlerde zaman senkronizasyonu, Berkeley zaman protokolü, mantıksal saatler, Lamport’un mantıksal saat algoritması, vektör saatleri, matris saatleri
7 Kaynak paylaştırma, kritik bölge problemi, donanımsal senkronizasyon, semaforlar, semafor problem örnek kod incelemesi.
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ı.
10 Dağıtık sistemlerin global durumu, Chandy Lamport’un algoritması, Lai Yang’ın algoritması, snapshot.
11 Ölü kilitler ve sonlanma tespiti, Dijkstra-Scholten algoritması, dağıtık ölü kilit, Chandy Misra Haas ölü kilit ö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 Final Sınavı