בעיות מפורסמות במדעי המחשב

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

הבעיות נלקחו מתחומים שונים במדעי המחשב כמו: חישוביות, אלגוריתמיקה, הנדסת תכנה, תקשורת, בינה מלאכותית ועוד.

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

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

 

הבעיות ותיאורן נכתבו על ידי קבוצת מדעי המחשב במחלקה להוראת המדעים במכון ויצמן.

 

האתר מכיל 8 פרקים שכל אחד מהם כולל

* תיאור הבעיה ומאפייניה, הסיבות שהובילו להתמודדות עם הבעיה, החשיבות של הבעיה במדעי המחשב.

* תיאור של הפתרון.

* ההשלכות של הפתרון על תחומים שונים במדעי המחשב.

* המדען "שמאחורי הבעיה", כולל תיאור קצר על פועלו.

* ביבילוגרפיה ואתרים נוספים.

כל החומרים עומדים לרשותכם וניתן להשתמש בהם להוראה ללא תשלום.

שימו לב: לא ניתן לעשות בחומר הזה כל שימוש מסחרי ללא רשות בכתב מראש מיוצרי החומרים.

 

נושא

 

תאור

מבוא

PDF

הקדמה ותאור תמציתי של 8 הבעיות.

The Busy Beaver Problem

PDF

בעיה שמתייחסת לכוח החישוב של מכונות ומהווה בסיס למודלים חישוביים. 

הוכן ע"י נוע רגוניס

על בינה מלאכותית  ועיבוד רשימות

PDF

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

הוכן ע"י שרה פולק

זמן לוגי במערכות מבוזרות

PDF

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

הוכן ע"י מוטי בן-ארי

האם P= NP או איך לארוז תרמיל ולהרוויח מליון דולר?

PDF

הבעיה מתארת את המושגים הבסיסיים הקשורים לסיבוכיות, NP, ומתי בעיה היא פתירה.

הוכן ע"י שמוליק שוורץ

מסדי נתונים טבלאיים ויישומים עיסקיים

PDF

בעיה המתארת את פיתוח המודל היחסי, שהוא המודל בו משתמשים לבניה של אחד הכלים רבי עוצמה לניהול מידע של ארגונים – מסדי נתונים טבלאיים.

הוכן ע"י שרה פולק

על השימוש באלגורתמים הסתברותיים לזיהוי מספרים ראשוניים בתחום הצפנה

PDF

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

הוכן ע"י גיל אבל

TCP\IP ורשת תקשורת של רשתות

PDF

איך לגרום למחשב המחובר ללווין ומחשב המחובר לגלי רשת רדיו ומחשב על רשת ARPANET  לתקשר ביניהם בצורה אחידה זה עם זה, בלי תלות בדרך שבה התקשורת מתבצעת אצל כל אחד מהם.

הוכן ע"י ססיל יחזקאל ושרה פולק

מציאת המסלול הקצר

PDF

מציאת המסלול הקצר ביותר בין שני צמתים בגרף משוקלל ושימוש של שיטות חיפוש בתחומים שונים במדעי המחשב.

הוכן ע"י שרה פולק