Təsadüfi alqoritm

Təsadüfi alqoritm (ing. Randomized Algorithm) — 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.[1] 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ə.[2]

Növləri və xüsusiyyətləri

[redaktə | mənbəni redaktə et]

Təsadüfi alqoritmlərin növləri

[redaktə | mənbəni redaktə et]

Monte Karlo alqoritmləri

[redaktə | mənbəni redaktə et]

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.[3]

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

[redaktə | mənbəni redaktə et]

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

[redaktə | mənbəni redaktə et]

Optimizasiya məsələləri

[redaktə | mənbəni redaktə et]

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.[4]

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

[redaktə | mənbəni redaktə et]

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

[redaktə | mənbəni redaktə et]

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.[5]

Təsadüfi alqoritmlərin üstünlükləri

[redaktə | mənbəni redaktə et]
  • 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.[6]
  • 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.[7]

Təsadüfi alqoritmlərin məhdudiyyətləri

[redaktə | mənbəni redaktə et]
  • 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.[8]

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.[9]

İstinadlar

[redaktə | mənbəni redaktə et]
  1. ↑ Kudelić, Robert. "Monte-Carlo randomized algorithm for minimal feedback arc set problem". Applied Soft Computing. 41. 2016-04-01: 235–246. doi:10.1016/j.asoc.2015.12.018.
  2. ↑ Hoare, C. A. R. "Algorithm 64: Quicksort". Commun. ACM. 4 (7). July 1961: 321–. doi:10.1145/366622.366644. ISSN 0001-0782.
  3. ↑ Hoare, C. A. R. "Algorithm 64: Quicksort". Communications of the ACM (ingilis). 4 (7). July 1961: 321. doi:10.1145/366622.366644. ISSN 0001-0782. 2019-12-18 tarixində arxivləşdirilib. İstifadə tarixi: 2024-10-29.
  4. ↑ Williams, H. C.; Shallit, J. O., Factoring integers before computers // Gautschi, Walter (redaktor), Mathematics of Computation 1943–1993: a half-century of computational mathematics; Papers from the Symposium on Numerical Analysis and the Minisymposium on Computational Number Theory held in Vancouver, British Columbia, August 9–13, 1993, Proceedings of Symposia in Applied Mathematics, 48, Amer. Math. Soc., Providence, RI, 1994, 481–531, doi:10.1090/psapm/048/1314885, ISBN 978-0-8218-0291-5, MR 1314885; see p. 504, "Perhaps Pocklington also deserves credit as the inventor of the randomized algorithm".
  5. ↑ Blum, Manuel; Floyd, Robert W.; Pratt, Vaughan; Rivest, Ronald L.; Tarjan, Robert E. "Time bounds for selection". Journal of Computer and System Sciences (ingilis). 7 (4). August 1973: 448–461. doi:10.1016/S0022-0000(73)80033-9. 2024-09-27 tarixində arxivləşdirilib. İstifadə tarixi: 2024-10-29.
  6. ↑ Aragon, C.R.; Seidel, R.G. Randomized search trees // 30th Annual Symposium on Foundations of Computer Science. October 1989. 540–545. doi:10.1109/SFCS.1989.63531. ISBN 0-8186-1982-1. 2024-06-05 tarixində arxivləşdirilib. İstifadə tarixi: 2024-10-29.
  7. ↑ Knuth, Donald E. The art of computer programming, volume 3: (2nd ed.) sorting and searching. USA: Addison Wesley Longman Publishing Co., Inc. 1998. 536–549. ISBN 978-0-201-89685-5. 2024-09-01 tarixində arxivləşdirilib. İstifadə tarixi: 2024-10-29.
  8. ↑ Carter, J. Lawrence; Wegman, Mark N. "Universal classes of hash functions". Journal of Computer and System Sciences (ingilis). 18 (2). 1979-04-01: 143–154. doi:10.1016/0022-0000(79)90044-8. ISSN 0022-0000.
  9. ↑ Berlekamp, E. R. Factoring polynomials over large finite fields // Proceedings of the second ACM symposium on Symbolic and algebraic manipulation - SYMSAC '71 (ingilis). Los Angeles, California, United States: ACM Press. 1971. 223. doi:10.1145/800204.806290. ISBN 9781450377867.