בתשובה לראובן, 31/05/04 22:54
 |
|
 |
||
|
||||
 |
יש חסמים, אבל בדיקת כל מקרה לגופו היא קשה מאוד. אם אתה מחפש ומחפש סידור של 24 כדורים במימד 4 ולא מוצא, איך תדע שאין כזה? לא חסרות בעיות פתוחות שהתשובה להן היא מספר שלם וקטן למדי בתחום ידוע. למשל, מספר האנשים הדרושים כדי להבטיח שיהיו או (חמישה שאינם מכירים זה את זה) או (חמישה שכולם מכירים זה את זה) הוא מספר שלם בין 43 ל-49, אבל ככל הידוע לי לא ידוע מהו. ה"גישה של הפיסיקאי" שתיארת היא נאה ואף נדונה בהרחבה, אך אינני יודע אם החסמים ההדוקים ביותר באים ממנה. |
 |
 |
 |
|
|
|
||
|
||||
|
אנקדוטה: מיטשל פייגנבאום ( זה מהקבוע) פעם היה במסיבה ופגש בעל חברת מפות ( ראנד מקנאלי אאל"ט). לאחר שהחליפו דברי נימוסין, וכשהבין האטלסאי שלפניו עומד מדען מהמדרגה הראשונה, אמר לו "אם אתה כל כך חכם ..." וסיפר לו שיש הרבה בעיות בתחום עריכת אטלסים. מה למשל? - איך לכתוב את שם העיר ליד העיר, בלי לפגוע בשמות אחרים. לאחר כמה זמן, בא פייגנבאום עם הרעיון הבא: הוא שרטט אליפסה סביב כל שם של עיר וקיבע את השפה במרכז העיר. אחר כך הוא הדביק לכל אליפסה (במחשב) מטען חשמלי, ונתן להם ( בסימולציה) להסתדר. מכיוון שהאליפסות דחו זה את זה, אבל כל אחת מהם נישקה את העיר הרלוונטית, הוא פתר בצורה אוטומטית בעיה שעד אז היו פותרים ידנית. |
|
|
|
|
|
|
||
|
||||
|
אחת הדרכים החשובות לצייר גרפים1 היא "שיטת הגומייה" המתבססת על משפט של Tutte. כדאי מאוד לנסות את התוכנה שיש כאן: (כן, סליחה, מיקרוסופט. מה לעשות שלאצי לובאס עובד שם). בגדול, קובעים כמה קדקודים בנעצים למישור, ונותנים ליתר לנוע בחופשיות כשהצלעות מתנהגות כמו גומיות. יופי של דבר. 1 במובן הקומבינטורי: אוסף של קדקודים וצלעות. |
|
|
|
|
|
|
||
|
||||
|
באופן דומה, הדרך למצוא את קבוצת הקווים בעלי סך האורך הקצר ביותר המקשרים בין אוסף נקודות ("עץ שטיינר מינימלי"): לייצג את הנקודות כמסמרים נעוצים בעץ, ולכסות בלוח עץ נוסף; לטבול את שני הלוחות עם המסמרים באמבט מי סבון, ולהוציא. בין המסמרים יימתחו "קירות" של מי סבון העונים על הדרישה (בעולם אידיאלי, לפחות; במציאות, בעיות כמו זרמים במים, תזוזה של היד בעת הכנסת/הוצאת הלוח, וכו' פוגעות במושלמות הפתרון). (Dewdney, The Armchair Universe, בפרק "Analog Gadgets".) |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |