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

From האנציקלופדיה היהודית
Revision as of 16:19, 13 September 2018 by Yr (talk | contribs) (נבדק ואושר)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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

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

הערות שוליים[edit | edit source]

  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 תווים

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

NivdakVeushar.png