- This topic has 3 תגובות, 4 משתתפים, and was last updated לפני 20 שנים, 11 חודשים by
.
-
תגובות
-
אני בוחר קלף אחד מתוך שמונה קלפים (נניח ארבעת המלכים וארבעת האסים).
שאלת חימום קלה:
אתה צריך למצוא איזה קלף בחרתי בכמה שפחות שאלות כן/לא.
צריך בדיוק X (כמה?) שאלות. אפשר להראות (איך?) שאפשר למצוא את הקלף תוך X שאלות, ולהוכיח (כיצד?) שאין דרך להבטיח את גילוי הקלף בפחות מ X שאלות.עכשיו החלק האמיתי של השאלה:
נניח שמותר לי לשקר לכל היותר פעמיים. לכמה שאלות תזדקק?כותרת: תשובה לחלק הראשון
X = 3. (בהנחה שבחלק הראשון של השאלה אתה לא יכול לשקר)נעשה מעין "חיפוש בינארי".
האם הקלף הוא אחד מתוך 1, 2, 3 או 4? (כן/לא)
נניח שכן: האם הקלף הוא אחד מתוך 1, 2? (כן/לא)
נניח שלא: האם הקלף הוא 3? (כן/לא)אפשר לתרגם את המספרים לקלפים:
1. האם הקלף הוא מלך?
2. האם הקלף הוא אדום?
3. (אם הקלף אדום) האם הקלף הוא לב?
3. (אם הקלף שחור) האם הקלף הוא תלתן?כותרת: הוכחת המינימליות
ניתן להראות את המינימליות של חיפוש הקלף (כלומר שמספר הפעולות הוא לוגריתמי) על-ידי התבוננות בעץ ההחלטה:
ברור כי ישנם 8 מצבים סופיים (כלפים שאנחנו יכולים להגיע אליהם כפתרון לבעיה). מן הסתם, כל שאלה שנשאל מקטינה את גודל הקבוצה, ולכן למעשה ההכרעה שלנו ביחס לקלף היא תהליך של הליכה על עץ בינארי כאשר כל צומת (עלה או לא-עלה) מציין קבוצת קלפים, בעלים יש קלף יחיד, ובכל צומת-אב יש את איחוד שני הבנים. תהליך ההכרעה הוא בהגעה מהשורש (כל קלף יכול להיות היעד) לעלה מסויים. בעץ בעל n עלים יש לא פחות מ-n צמתים נוספים, ולכן יש בעץ לא פחות מ-2n עלים. העץ המינימלי הוא עץ שלם, וגובהו פרופורציונלי ללוגירתמים מספר הצמתים, ולכן גם ההחלטה אינה יכולה לקחת פחות מסדר גודל לוגריתם של מספר העלים.עתה לגבי הסעיף השני: ניתן בכל שלב של ה"חיפוש" לבדוק את התקיימות התנאי על _שתי_ תתי-הקבוצות, ואם התנאי מתקיים על שתיהן, או לא מתקיים על שתיהן, לחזור לרמה הקודמת (למעלה). בכל מקרה, לא ידרשו יותר משתי "חזרות" כאלה. יחד עם זאת, הכפלנו את מספר השאלות, והוספנו עוד 4 שאלות (לכל היותר), ולכן לפי האלגוריתם ניתן להבטיח את ההגעה לקלף המתאים בעזרת 10 שאלות . מבחינת הסיבוכיות האסימפטוטית, נשארנו בסיבוכיות לוגריתמית, אך אינני בטוח כי זהו הפתרון המינימלי מבחינת הקבועים.
- יש להתחבר למערכת על מנת להגיב.