Çevrimiçi Algoritmalar
Çevrimiçi algoritmalar, gelecekteki talepler hakkında bilgi sahibi olmadan, girdi geldikçe geri dönülemez kararlar vermek zorundadır; bu algoritmaların kalitesi, tüm girdiyi önceden gören optimal bir algoritmaya karşı rekabetçi analiz ile ölçülmektedir.
Tanım
Bir çevrimiçi algoritma, girdisini bir talep dizisi olarak alır ve gelecekteki talepleri görmeden her birine anında ve geri dönülemez şekilde yanıt vermek zorundadır; rekabetçi oranı, maliyetinin, tüm talep dizisini bilen optimal bir çevrimdışı algoritmanın maliyetine oranının en kötü durumudur.
Kapsam
Bu konu, girdiyi sıralı olarak işleyen ve sonraki girdiler bilinmeden kararlarını kesinleştiren algoritmaları ve bu algoritmaları optimal bir çevrimdışı rakibe karşı değerlendirmek için kullanılan rekabetçi oran çerçevesini kapsamaktadır. Paging ve önbellekleme, liste güncelleme, kayak kiralama problemi, k-sunucu problemi ile çevrimiçi çizelgeleme ve kutu paketleme gibi klasik problemleri ve daha zayıf rakiplere karşı rekabetçi oranları iyileştirmede rastgeleleştirmenin rolünü içermektedir.
Temel sorular
- Gelecek bilinmezken çevrimiçi algoritmalar nasıl değerlendirilir?
- Rekabetçi oran neyi ölçer ve çevrimdışı rakip nedir?
- Paging ve kayak kiralama gibi klasik problemler çevrimiçi ödünleşimleri nasıl örnekler?
- Rastgeleleştirme, habersiz bir rakibe karşı rekabetçiliği nasıl iyileştirebilir?
- Herhangi bir çevrimiçi algoritmanın ne kadar rekabetçi olabileceğini hangi alt sınırlar kısıtlar?
Anahtar kavramlar
- çevrimiçi ve çevrimdışı
- rekabetçi oran
- çevrimdışı rakip
- paging ve önbellekleme
- liste güncelleme
- kayak kiralama problemi
- k-sunucu problemi
- rastgeleleştirilmiş rekabetçilik
Temel kuramlar
- Rekabetçi analiz
- Rekabetçi analiz, bir çevrimiçi algoritmayı, maliyeti ile optimal bir çevrimdışı algoritmanın maliyeti arasındaki en kötü durum oranına göre değerlendirir ve girdi hakkındaki varsayımlara dayanmak yerine herhangi bir girdi dizisine karşı geçerli bir garanti sunar.
- Habersiz rakiplere karşı rastgeleleştirme
- Rastgeleleştirilmiş çevrimiçi algoritmalar, habersiz bir rakibe karşı herhangi bir deterministik algoritmaya göre kesinlikle daha iyi rekabetçi oranlar elde edebilir, çünkü rakip, algoritmanın rastgele seçimlerini bilmeden girdiyi sabitlemek zorundadır.
Klinik önem
Çevrimiçi algoritmalar, sistemlerin gelecekteki bilgilerden yoksun olarak gerçek zamanlı aldığı kararları modeller: işletim sistemleri ve CPU'lardaki önbellek ve sayfa değişimi, veri yapısı kendi kendine organizasyonu, dinamik kaynak tahsisi ve yük dengeleme ile bulut bilişimdeki kiralama veya satın alma kararları. Rekabetçi analiz, bu tür reaktif sistemler için en kötü durum garantileri sunmaktadır.
Tarihçe
Rekabetçi analiz, 1985 yılında Sleator ve Tarjan tarafından liste güncelleme ve paging kuralları üzerine yaptıkları çalışmalarla tanıtılmış, çevrimiçi algoritmaların değerlendirilmesini optimal bir çevrimdışı çözümle karşılaştırma etrafında yeniden şekillendirmiştir. Bu çerçeve, 1990'larda k-sunucu problemi ve rastgeleleştirilmiş çevrimiçi algoritmalar aracılığıyla genişlemiş, Borodin ve El-Yaniv'in 1998 tarihli monografisinde incelenmiştir.
Öne çıkan isimler
- Daniel Sleator
- Robert Tarjan
- Allan Borodin
- Ran El-Yaniv
İlgili konular
Temel eserler
- sleator1985
- borodin1998
- cormen2009
Sıkça sorulan sorular
- Rekabetçi oran nedir?
- Bu, bir çevrimiçi algoritmanın maliyetinin, tüm girdiyi önceden gören optimal bir algoritmanın maliyetine oranının en kötü durumudur. 2-rekabetçi bir algoritma, herhangi bir girdi dizisinde mümkün olan en iyi çevrimdışı maliyetin iki katından daha fazlasına asla mal olmaz.
- Rastgeleleştirme çevrimiçi algoritmalara neden yardımcı olur?
- Algoritmanın rastgele seçimlerini görmeden girdiyi sabitleyen habersiz bir rakibe karşı, rastgeleleştirme, rakibin algoritmanın davranışına göre en kötü durumu uyarlamasını engeller ve herhangi bir deterministik algoritmanın elde edebileceğinden kesinlikle daha iyi rekabetçi oranlara olanak tanır.