Rastgele algoritmalar
- Algoritmalar kursu
- Uzman seviye
- Ders 10/41
- 4 dk
Rastgele seçimle çalışan algoritmaları öğrenirsin.
Rastgele algoritmalar
Rastgele algoritma, rastgele seçimler yaparak çözüme ulaşır. Bazı durumlarda deterministik algoritmalardan daha hızlıdır.
Rastgele algoritmalar iki türlüdür: her zaman doğru sonuç veren Las Vegas ve yüksek olasılıkla doğru veren Monte Carlo.
Örnekleme ile maksimum
Bir dizideki en büyük elemanı, rastgele seçilen indekslerden de bulabiliriz. Bu, rastgele algoritmaların temelini gösterir.
Eğer tüm indeksler seçilirse sonuç kesindir. Alt küme seçilirse olasılıklı sonuçtur. Bu, Monte Carlo tarzıdır.
Uygulama sample_max fonksiyonu
sample_max(arr, indices) yaz. indices listesindeki indekslerin arr değerleri arasından en büyüğü döndür. print(sample_max([3, 5, 7, 1, 9], [0, 2, 4])) ile 9 yazdır.
Başlangıç kodu
def sample_max(arr, indices):
# Örneklenen indekslerde en büyüğü bulÖrnek çözüm
def sample_max(arr, indices):
# Örneklenen indekslerde en büyüğü bul
best = arr[indices[0]]
for i in indices:
if arr[i] > best:
best = arr[i]
return best
print(sample_max([3, 5, 7, 1, 9], [0, 2, 4]))Beklenen çıktı
9
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 örnekleme
for i in ____:for i in indices:Açıklama: indices doğru.
2 Monte Carlo algoritması ne sağlar?
- Hiç sonuç
- Sabit zaman
- Yüksek olasılıkla doğru sonuç Doğru cevap
- Her zaman doğru sonuç
Açıklama: Monte Carlo yüksek olasılıkla doğru sonuç verir.
3 Rastgele algoritmalar: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
random |
Rastgele |
Monte Carlo |
Olasılıklı |
Las Vegas |
Kesin |
örneklem |
Alt küme |