27-01-2005, 16:23
|
|
|
|
חבר מתאריך: 20.10.04
הודעות: 1,341
|
|
פיתרון טוב
במתימטיקה לפיתרון יש שני תפקידים, המרכזי בהם הוא להוכיח מעל לכל ספק שמשהו הוא נכון.
התפקיד השני הוא להסביר למה הוא נכון, מתוך ההנחות הראשוניות למה יוצא שהמשפט נכון.
את משפט 4 הצבעים הוכיחו ע"י תוכנת מחשב שניסתה את כל האפשרויות וזה מה שיצא, כדי לאמת את זה ולהראות שהקומפילר שינה משהו היו צריכים לעבור פקודה פקודה באסמבלי ולראות אם זה באמת בודק את כל האפשרויות (יש לציין ש"כל האפשרויות" זה צימצום של כמות האפשרויות המקורית, חלוקה של אפשרויות למחלקות שקולות). בכל מקרה זאת נחשבת להוכחה תקפה כי היא מוכיחה מעל לכל ספק שמפה אפשר לצבוע ב 4 צבעים. אולם כשבאים לשאול את ההוכחה הזאת מאיפה זה נובע ההוכחה אומרת "כי ככה זה יצא" ולכן זה לא כזה פיתרון טוב (צריך לציין שהוכיחו בצורה טובה את העובדה שכל מפה אפשר לצבוע ב 5 צבעים).
בנוסף פתרונות באלגוריתמים נחשבים הכי טובים אם הם פותרים בעיה בצורה הטובה ביותר שניתן להוכיח. כלומר אם מוכיחים שאי אפשר לרדת מתחת ל"סיבוכיות" מסויימת ומצליחים להגיע אליה אז פתרת אותה בצורה האופטימלית.
(צריך להיזהר בהוכחות, הוכיחו בעזרת עץ החלטה שאי אפשר למיין n עצמים בפחות מ (!log(n השוואות (ככה שהסיבוכיות יוצאת( O(n*log n ) אולם כיום קיימים אלגוריתמים שממינים בסיבוכיות של (O(n הפירצה בהוכחה היא שההוכחה תקפה רק על אלגוריתמים שממיינים בעזרת השוואות)
אם לא מצליחים להוכיח אז
פתרונות באופן כללי *נחשבים* טובים אם הם נפתרים ב"סיבוכיות" פולינומיאלית (כלומר שהסיבוכיות שלהם היא (O(n^x כאשר x הוא קבוע כלשהו) אולם הרבה מהבעיות הגדולות בתעשייה נפתרות בינתיים רק באלגוריתמים בסיבוכיות אקספוננציאלית, סיבוכיות כזאת גורמת לפיתרונות של nים קטנים יחסית לקחת המון זמן, מה שאין לתעשייה. כרגע מנסים לפתח פונקציות קירוב שיהיו פולינומיאליות, כלומר במקום לתת את הפיתרון הטוב ביותר נותנים את פיתרון קרוב (רצוי בכל אפסילון קטן ככל שנירצה) שנבחר. כבר יצרו אלגוריתמים כאלה והם עובדים טוב.
_____________________________________
חתימתכם הוסרה כיוון שלא עמדה בחוקי האתר. לפרטים נוספים לחצו כאן. תוכלו לקבל עזרה להתאמת החתימה לחוקים בפורום חתימות וצלמיות.
|