Təsadüfi alqoritm - Haqqinda Melumat

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. 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.

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

Kudelić, Robert. "Monte-Carlo randomized algorithm for minimal feedback arc set problem". Applied Soft Computing. 41. 2016-04-01: 235–246. doi:.
Hoare, C. A. R. "Algorithm 64: Quicksort". Commun. ACM. 4 (7). July 1961: 321–. doi:. ISSN .
Hoare, C. A. R. . Communications of the ACM (ingilis). 4 (7). July 1961: 321. doi:. ISSN . 2019-12-18 tarixində . İstifadə tarixi: 2024-10-29.
; , 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:, ISBN 978-0-8218-0291-5, ; see p. 504, "Perhaps Pocklington also deserves credit as the inventor of the randomized algorithm".
Blum, Manuel; Floyd, Robert W.; Pratt, Vaughan; Rivest, Ronald L.; Tarjan, Robert E. . Journal of Computer and System Sciences (ingilis). 7 (4). August 1973: 448–461. doi:. 2024-09-27 tarixində . İstifadə tarixi: 2024-10-29.
Aragon, C.R.; Seidel, R.G. // 30th Annual Symposium on Foundations of Computer Science. October 1989. 540–545. doi:. ISBN 0-8186-1982-1. 2024-06-05 tarixində . İstifadə tarixi: 2024-10-29.
Knuth, Donald E. . USA: Addison Wesley Longman Publishing Co., Inc. 1998. 536–549. ISBN 978-0-201-89685-5. 2024-09-01 tarixində . İstifadə tarixi: 2024-10-29.
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:. ISSN .
Berlekamp, E. R. // Proceedings of the second ACM symposium on Symbolic and algebraic manipulation - SYMSAC '71 (ingilis). Los Angeles, California, United States: ACM Press. 1971. 223. doi:. ISBN 9781450377867.

[1] Kudelić, Robert. "Monte-Carlo randomized algorithm for minimal feedback arc set problem". Applied Soft Computing. 41. 2016-04-01: 235–246. doi:.

[2] Hoare, C. A. R. "Algorithm 64: Quicksort". Commun. ACM. 4 (7). July 1961: 321–. doi:. ISSN .

[3] Hoare, C. A. R. . Communications of the ACM (ingilis). 4 (7). July 1961: 321. doi:. ISSN . 2019-12-18 tarixində . İstifadə tarixi: 2024-10-29.

[4] ; , 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:, ISBN 978-0-8218-0291-5, ; 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. . Journal of Computer and System Sciences (ingilis). 7 (4). August 1973: 448–461. doi:. 2024-09-27 tarixində . İstifadə tarixi: 2024-10-29.

[6] Aragon, C.R.; Seidel, R.G. // 30th Annual Symposium on Foundations of Computer Science. October 1989. 540–545. doi:. ISBN 0-8186-1982-1. 2024-06-05 tarixində . İstifadə tarixi: 2024-10-29.

[:0-7] Knuth, Donald E. . USA: Addison Wesley Longman Publishing Co., Inc. 1998. 536–549. ISBN 978-0-201-89685-5. 2024-09-01 tarixində . İ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:. ISSN .

[9] Berlekamp, E. R. // Proceedings of the second ACM symposium on Symbolic and algebraic manipulation - SYMSAC '71 (ingilis). Los Angeles, California, United States: ACM Press. 1971. 223. doi:. ISBN 9781450377867.