אלגוריתמים דטרמיניסטיים שמשתמשים ברנדומיות

[kiri...@gmail.com]

בתרגול האחרון הראנו אלגוריתם למציאת חתך מקסימלי בקירוב 0.5 ע"י בחירת
שני אפשרויות לכל קודקוד, הגרלת הצבה לשאר הקודקודים, ובחירת ההצבה של
הקודקוד אשר מקסימלית, וממשיכים....

מדוע האלגוריתם הנ"ל הוא פול' למרות שהוא משתמש ברנדומיזציה? הוא לא יכול
לתת תוצאה גרועה יותר?

[ptyl eyal]

זה לא רנדומי
זה תוחלת
זה אלגוריתם דטרמיניסטי שמשתמש במסקנות מהסתברות

2009/7/2 kiri...@gmail.com <kiri...@gmail.com>

[ptyl eyal]

אפשר להגדיר את זה כאלגוריתם חיפוש לאלגוריתם ההכרעה של התוחלת

2009/7/2 ptyl eyal <the....@gmail.com>

[yuval rochman]

האלגוריתם הוא פולינומאלי, מכיוון שחישוב תוחלת הקשתות שהיו לנו בחתך, אם קודקוד i  יצבע או באדום או בכחול, הוא פולינומאלי(וניתן לעשות בצורה דטרמינסטי)
כמוכן האלגוריתם עצמו הוא דטרמינסטי.

2009/7/2 ptyl eyal <the....@gmail.com>

[itay]

תסתכל על השעורי בית האחרונים, שאלה 4 - זה מדריך אותך צעד אחרי צעד איך
לבנות את האלג' הדטרמיניסטי הפולינומיאלי.

On 2 יולי, 13:13, yuval rochman <yuval...@gmail.com> wrote:
> האלגוריתם הוא פולינומאלי, מכיוון שחישוב תוחלת הקשתות שהיו לנו בחתך, אם
> קודקוד i  יצבע או באדום או בכחול, הוא פולינומאלי(וניתן לעשות בצורה
> דטרמינסטי)
> כמוכן האלגוריתם עצמו הוא דטרמינסטי.
>

> 2009/7/2 ptyl eyal <the.p...@gmail.com>

>
> > אפשר להגדיר את זה כאלגוריתם חיפוש לאלגוריתם ההכרעה של התוחלת
>

> > 2009/7/2 ptyl eyal <the.p...@gmail.com>

>
> > זה לא רנדומי
> >> זה תוחלת
> >> זה אלגוריתם דטרמיניסטי שמשתמש במסקנות מהסתברות
>

> >> 2009/7/2 kirils...@gmail.com <kirils...@gmail.com>

[אריאל‎]

האם בדרך זאת אפשר לפתור גם נוסחת E3SAT שכל משתנה מופיע בדיוק 3 פעמים?
כלומר להגיד שמבצעים הצבה כלשהיא, ואז בתוחלת מספקים 7/8 מהסוגרים, ואז
עבור כל משתנה בודקים האם הצבת T או F גורמת לכך שבתוחלת יותר סוגרים
מסופקים, ואז האופן הזה נחשב אלגוריתם דטרמיניסטי ופולינומי?

[itay]

משהו כזה.
כל פעם תבחר השמה למשתנה אחד ותבדוק מה התוחלת תהיה אם תיתן לו T ומה עם
F. ככה תעבור משתנה משתנה עד שתקבל השמה שתספק לפחות 7/8 מהסוגרים.