אלגוריתמים הסתברותיים Flashcards
1
Q
מהו “ניפוח” באלגוריתמים הסתברותיים?
A
2
Q
הגדירו:
הסתברות הצלחה של אלגוריתם גדולה כרצוננו.
A
3
Q
הגדירו:
אלגוריתם קירוב הסתברותי.
A
4
Q
הציגו אלגוריתם הסתברותי 8/7 מקרב ל MAX - 3SAT.
A
5
Q
פעמים רבות אלגוריתמים הסתברותיים מורכבים מאלגוריתם בסיסי שחוזרים עליו פעמים רבות כדי להעלות את סיכויי ההצלחה של האלגוריתם.
(שאלה על אינטואיציה:)
כמה פעמים סביר לנחש שיש לחזור על האלגוריתם הבסיסי כדי שנשיג הצלחה ב”הסתברות גדולה כרצוננו”?
A
k(m+1)
כאשר m מייצג את המספר הפסוקיות/המשוואות/האיברים בשאלה שברצוננו לספק.
6
Q
מהו זמן הריצה של האלגוריתם ההסתברותי ה8/7 מקרב ל MAX - 3SAT?
A
