לפניכם 8 בעיות שונות איתן התמודדו מדעני מחשב מפורסמים, חלקם מקבלי פרס טיורינג. הבעיות נלקחו מתחומים שונים במדעי המחשב כמו: חישוביות, אלגוריתמיקה, הנדסת תכנה, תקשורת, בינה מלאכותית ועוד. הבעיות נוגעות ישירות ובעקיפין בנושאים הנלמדים במדעי המחשב בתיכון וניתן לשלבן כהעשרה בנושאים אלו. עיסוק בבעיות מסוג זה מקשר אותנו להיסטוריה של המקצוע ומספק מבט רחב יותר על תחום מדעי המחשב והשורשים שלו. מאפיין בולט הקשור לאנשים שהתמודדו ופתרו את הבעיות שמוצגות כאן, הוא הרקע המתמטי הרחב של המדענים הללו והשימוש בכלים מתמטיים לפתרון הבעיות. כמו כן, בדומה לתחומים אחרים (כמו בפיסיקה והרעיון שכדור הארץ הוא עגול), פתרון של בעיות מסוימות לא תמיד התקבל בברכה על ידי התעשייה, שחששה מתחרות עם המוצרים שהיא פיתחה באותו זמן. אולם העובדה היא שפתרון טוב שנמצא שימושי ופתח אופקים להתמודדות עם תחומים ונושאים חדשים התקבל בסופו של דבר ומשתמשים בו גם כיום.
הבעיות ותיאורן נכתבו על ידי קבוצת מדעי המחשב במחלקה להוראת המדעים במכון ויצמן.
האתר מכיל 8 פרקים שכל אחד מהם כולל: תיאור הבעיה ומאפייניה, הסיבות שהובילו להתמודדות עם הבעיה, החשיבות של הבעיה במדעי המחשב. תיאור של הפתרון. ההשלכות של הפתרון על תחומים שונים במדעי המחשב. המדען “שמאחורי הבעיה”, כולל תיאור קצר על פועלו. ביבילוגרפיה ואתרים נוספים.
מבוא: הקדמה ותאור תמציתי של 8 הבעיות
The Busy Beaver Problem: בעיה שמתייחסת לכוח החישוב של מכונות ומהווה בסיס למודלים חישוביים. הוכן ע”י נוע רגוניס
על בינה מלאכותית ועיבוד רשימות: האם ניתן להקנות למחשב יכולת חשיבה אנושית ומה הדרך המתאימה להצגת השערות ולהסקת מסקנות במחשב? התמודודת עם בעיה זו הביאה את מקרתי לפיתוח שפת LISP. הוכן ע”י שרה פולק
זמן לוגי במערכות מבוזרות: פתרונו של לזלי למפורט לבעיה של קביעת סדר אירועים במערכת מבוזרת. הצגת הרעיון ופתרונו היתה נקודת מפנה בהיסטוריה של מדעי המחשב, והובילה לפיתוח של עשרות, אם לא מאות, אלגוריתמים המשמשים בכל מערכת מבוזרת. הוכן ע”י מוטי בן-ארי
האם P= NP או איך לארוז תרמיל ולהרוויח מליון דולר? הבעיה מתארת את המושגים הבסיסיים הקשורים לסיבוכיות, NP, ומתי בעיה היא פתירה. הוכן ע”י שמוליק שוורץ
מסדי נתונים טבלאיים ויישומים עיסקיים: בעיה המתארת את פיתוח המודל היחסי, שהוא המודל בו משתמשים לבניה של אחד הכלים רבי עוצמה לניהול מידע של ארגונים – מסדי נתונים טבלאיים. הוכן ע”י שרה פולק
על השימוש באלגורתמים הסתברותיים לזיהוי מספרים ראשוניים בתחום הצפנה: כפתרון לבעיות בתחום ההצפנה הציע רבין שימוש באלגוריתם הסתברותי לא דטרמיניסטי. האלגוריתם הזה “מטיל מטבעות” ופועל על-פי התוצאות, נותן תוצאה נכונה בהסתברות גבוהה, אולם עלול גם לטעות. האלגוריתם היה חדשני לחלוטין בזמו פרסומו וכיום מקובל להשתמש בו בתחומים שונים כמו בלשנות. הוכן ע”י גיל אבל
TCP\IP ורשת תקשורת של רשתות: איך לגרום למחשב המחובר ללווין ומחשב המחובר לגלי רשת רדיו ומחשב על רשת ARPANET לתקשר ביניהם בצורה אחידה זה עם זה, בלי תלות בדרך שבה התקשורת מתבצעת אצל כל אחד מהם. הוכן ע”י ססיל יחזקאל ושרה פולק
מציאת המסלול הקצר: מציאת המסלול הקצר ביותר בין שני צמתים בגרף משוקלל ושימוש של שיטות חיפוש בתחומים שונים במדעי המחשב. הוכן ע”י שרה פולק