Open main menu

האנציקלופדיה היהודית β

אלגוריתם אטלנטיק סיטי

Revision as of 16:19, 13 September 2018 by Yr (talk | contribs) (נבדק ואושר)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

אלגוריתם אטלנטיק סיטי הוא אלגוריתם אקראי הפועל בזמן-פולינומי ועונה בצורה נכונה לפחות 75% מהזמן (או, בכמה גרסאות, ערך אחר גדול מ-50%). המונח "אטלנטיק סיטי" הוצג לראשונה ב-1982 על ידי ג'יי פין בכתב יד שלא פורסם שכותרתו השוואה של בדיקות הסתברותית לבדיקת ראשוניות.[1]

המחלקות הנפוצות האחרות של אלגוריתמים אקראיים הן אלגוריתם מונטה קרלו ואלגוריתם לאס וגאס. אלגוריתם מונטה קרלו הוא תמיד מהיר, אבל צודק רק בהסתברות גבוהה. מצד שני, אלגוריתם לאס וגאס תמיד צודק, אבל מהיר רק בהסתברות גבוהה. אלגוריתם אטלנטיק סיטי הוא אלגוריתם זמן-פולינומי אקראי, שצודק בהסתברות גבוהה ומהיר בהסתברות גבוהה.[2]

הערות שולייםEdit

  1. ^ Richard A. Mollin (2003). RSA and Public Key Cryptography. CHAPMAN & HALL/CRC. עמ' 80. 
  2. ^ William J Turner (מאי 2002). Black Box Linear Algebra with the Linbox Library. North carolina State University. עמ' 3. בדיקה אחרונה ב-10 ביולי 2014. 

ערך זה מוגש באדיבות ויקיפדיה העברית. (הדף המקורי, רשימת התורמים)
הערך בוויקיפדיה גדול מערך זה ב +121 תווים

לעדכון מוויקיפדיה, לחץ כאן.