GERİ DÖN
Ders Öğretim Planı
| Dersin Kodu | Dersin Adı | Dersin Türü | Yıl | Yarıyıl | AKTS |
|---|---|---|---|---|---|
| 9105055452012 | Dağıtık Algoritmalar | Seçmeli Ders Grubu | 1 | 1 | 8,00 |
Dersin Seviyesi
Yüksek Lisans
Dersin Sunulduğu Dil
Türkçe
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.
Dersi Veren Öğretim Görevlisi/Görevlileri
Doç. Dr. Orhan Dağdeviren
Öğrenme Çıktıları
| 1 | 1. Dağıtık Algoritma kavramını anlayabilmek. |
| 2 | 2. Problemlere farklı bir bakış açısıyla dağıtık bir şekilde çözüm üretebilmek. |
| 3 | 3. Bilinen dağıtık problemleri ve çözümler hakkında bilgi sahibi olmak. |
| 4 | 4. Dağıtık algoritmaların analizini yapabilmek. |
| 5 | 5. Dağıtık ortamda oluşabilecek problemleri fark edebilmek. |
| 6 | 6. Problemleri dağıtık bir şekilde düşünerek dağıtık algoritmasını tasarlayabilmek. |
| 7 | 7. Dağıtık yazılım geliştirmek için çağdaş teknolojileri kullanabilmek. |
| 8 | 8. Bilinen seri çalışan bir algoritmayı dağıtık hale çevirebilmek. |
Öğretim Sistemi
Dersin Ön Koşulu Olan Dersler
Yok
Ders İçin Önerilen Diğer Hususlar
Yok
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.
Haftalık Ayrıntılı Ders İçeriği
| Hafta | Konular (Teorik) | Öğretim Yöntem ve Teknikleri | Ön Hazırlık |
|---|---|---|---|
| 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 | Proje Sunumları | ||
| 16 | Final Sınavı |
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).
Planlanan Öğrenme Aktiviteleri ve Metodları
Etkinlikler ayrıntılı olarak "Değerlendirme" ve "İş Yükü Hesaplaması" bölümlerinde verilmiştir.
Değerlendirme
| Yarıyıl (Yıl) İçi Etkinlikleri | Adet | Değer |
|---|---|---|
| Ara Sınav | 1 | 100 |
| Toplam | 100 | |
| Yarıyıl (Yıl) Sonu Etkinlikleri | Adet | Değer |
| Final Sınavı | 1 | 100 |
| Toplam | 100 | |
| Yarıyıl (Yıl) İçi Etkinlikleri | 40 | |
| Yarıyıl (Yıl) Sonu Etkinlikleri | 60 | |
Staj Durumu
Yok
İş Yükü Hesaplaması
| Etkinlikler | Sayısı | Süresi (saat) | Toplam İş Yükü (saat) |
|---|---|---|---|
| Ara Sınav | 1 | 3 | 3 |
| Final Sınavı | 1 | 3 | 3 |
| Derse Katılım | 14 | 3 | 42 |
| Rapor Hazırlama | 8 | 3 | 24 |
| Proje Hazırlama | 9 | 4 | 36 |
| Proje Sunma | 1 | 3 | 3 |
| Ödev Problemleri için Bireysel Çalışma | 7 | 7 | 49 |
| Ara Sınav İçin Bireysel Çalışma | 1 | 21 | 21 |
| Final Sınavı içiin Bireysel Çalışma | 1 | 30 | 30 |
| Okuma | 7 | 3 | 21 |
| Toplam İş Yükü (saat) | 232 | ||
Program ve Öğrenme Çıktıları İlişkisi
| PÇ 1 | PÇ 2 | PÇ 3 | PÇ 4 | PÇ 5 | PÇ 6 | PÇ 7 | |
| ÖÇ 1 | 5 | 5 | |||||
| ÖÇ 2 | 5 | 5 | |||||
| ÖÇ 3 | 5 | 5 | |||||
| ÖÇ 4 | 4 | 5 | |||||
| ÖÇ 5 | 5 | ||||||
| ÖÇ 6 | 4 | 5 | 5 | ||||
| ÖÇ 7 | 5 | 3 | |||||
| ÖÇ 8 | 4 | 5 |
* Katkı Düzeyi : 1 Çok düşük 2 Düşük 3 Orta 4 Yüksek 5 Çok yüksek