Təsadüfi alqoritm

Təsadüfi alqoritm () — giriş verilənlərinə təsadüfi elementlər əlavə edərək nəticələr yaradan bir alqoritmdir. Bu alqoritmlər bəzi hallarda daha sürətli, sadə və ya daha effektiv ola bilər. Təsadüfi alqoritmlərdə alınan nəticələr giriş məlumatları ilə yanaşı, həm də təsadüfi ədədlərin seçilməsindən asılıdır. Onlar geniş tətbiq sahəsinə malikdirlər, xüsusən də böyük məlumatlar, optimallaşdırma problemləri və statistik modelləşdirmə kimi sahələrdə.

 Növləri və xüsusiyyətləri 
 Təsadüfi alqoritmlərin növləri 
 Monte Karlo alqoritmləri 
Monte Karlo alqoritmlərində nəticə təsadüfi seçimlərlə əldə olunur, lakin çıxış nəticəsi hər zaman doğru olmaya bilər. Bu alqoritmlər çıxış nəticəsini müəyyən dərəcədə səhv payı ilə təqdim edir. Əsas xüsusiyyəti odur ki, nəticənin doğruluğunu artırmaq üçün təsadüfi seçimlərin sayını artırmaq kifayət edir.

Məsələn: Bir çoxsaylı inteqralın qiymətləndirilməsi və ya çətin optimallaşdırma məsələlərinin həlli üçün Monte Karlo üsulu istifadə oluna bilər. Bu üsul, məsələn, Pi ədədinin təqribi hesablanmasında istifadə edilir.

 Las Veqas alqoritmləri 
Las Veqas alqoritmlərində nəticə hər zaman doğrudur, lakin alqoritmin icra müddəti təsadüfi seçimlərdən asılıdır. Yəni, bu alqoritmlər bəzən sürətli, bəzən isə yavaş nəticə verir. Təsadüfi seçimlər icra müddətini təsir etsə də, çıxışın doğruluğu zəmanət altındadır.

Məsələn: QuickSort alqoritminin təsadüfi seçilən pivot element ilə tətbiqi Las Veqas alqoritminə misaldır. Burada pivot təsadüfi seçilir, lakin nəticə həmişə doğrudur.

 Təsadüfi alqoritmlərin istifadə sahələri  
 Optimizasiya məsələləri 
Bəzi optimallaşdırma problemlərində mükəmməl həll tapmaq çox çətin və vaxt aparıcı ola bilər. Təsadüfi alqoritmlər optimal və ya yaxşı bir yaxınlaşmanı tez bir zamanda təmin edə bilər.; see p. 504, "Perhaps Pocklington also deserves credit as the inventor of the randomized algorithm".

Simulated Annealing kimi üsullar optimal həll tapmağa çalışır və bu, çox sayda tətbiq sahəsində istifadə olunur.

 Statistik nümunələr və təxminlər 
Təsadüfi nümunə seçimi tələb edən məsələlərdə, məsələn, böyük məlumat dəstlərində məlumatların təxminən emalı və ya statistika yığılması üçün Monte Karlo alqoritmləri geniş istifadə edilir.

 Kriptoqrafiya 
Təsadüfi alqoritmlər kriptoqrafik sistemlərdə təsadüfi ədədlərin yaradılması və məlumatların şifrələnməsi üçün istifadə edilir.

 Təsadüfi alqoritmlərin üstünlükləri 
Sadəlik — çox vaxt təsadüfi yanaşmalar müəyyən problemləri daha sadə yollarla həll etməyə imkan verir.
Effektivlik — əksər hallarda təsadüfi alqoritmlər ənənəvi alqoritmlərdən daha sürətli ola bilər.
Geniş tətbiq sahəsi — çətin və ya qeyri-müəyyənlik olan problemlərdə (məsələn, optimallaşdırma, kriptoqrafiya və statistik analiz) uğurla istifadə olunur.

 Təsadüfi alqoritmlərin məhdudiyyətləri 
Nəticənin qeyri-müəyyənliyi — Monte Karlo üsullarında nəticə hər zaman doğru olmaya bilər.
Müxtəliflik — eyni problem üçün hər dəfə fərqli nəticə yarada bilərlər, buna görə sabitlik tələb olunan sahələrdə təsadüfi alqoritmlər çətinlik yarada bilər. QuickSort alqoritmində pivot elementin təsadüfi seçilməsi QuickSort-un daha bərabər paylanmış bölmələrə bölünməsinə səbəb olur, bu da orta hal mürəkkəbliyini azaldır. Bu yanaşma, Las Veqas alqoritmi olaraq adlandırılır, çünki nəticə həmişə düzgün olsa da, icra müddəti giriş məlumatlarının xüsusiyyətlərindən və təsadüfi seçimlərdən asılıdır.

Təsadüfi alqoritmlər, qeyri-müəyyənlik və böyük məlumat həcmi ilə işləyən problemlər üçün optimal həllər təklif edir. Onların xüsusilə böyük məlumatlar və mürəkkəb problemlərin həllində geniş tətbiqi var.

 İstinadlar 

Kateqoriya:Alqoritmlərin analizi