מדעי המחשב
|
עיינו גם בפורטל
פורטל מדעי המחשב הוא שער לכל הנושאים הקשורים במדעי המחשב. ניתן למצוא בו קישורים אל תחומי המשנה של הענף, מושגי יסוד בתחום, מדענים חשובים ועוד.
|
מדְעי המחשב הוא ענף מדעי העוסק בלימוד הבסיס התאורטי והמעשי של השימוש במערכות מחשב[1], ואף, במידה מסוימת, גם בשאלה של תכנון ובנייה של מערְכות מחשב. ענפי המִשנה שלו רבים; חלקם מדגישים שימוש במחשב בתחום מסוים (כגון גרפיקה ממוחשבת או בניית מהדרים), אחרים עוסקים בחקר התכונות של בעיות חישוביות כלליות (לדוגמה, סיבוכיות), וענפי משנה אחרים מתמקדים בפתרון הבעיות הכרוכות ביישום מעשי של חישובים ואלגוריתמים. ענף בולט במדְעי המחשב הוא חקר ויישום שפות פורמליות לפתרון בעיות חישוביות מסוימות (לדוגמה, באמצעות שפת תכנות).
להדגשת ההיבט התאורטי של תחום זה, אמר אחד מהעוסקים הבולטים בו:
מדְעי המחשב אינם עוסקים במחשב יותר ממה שאסטרונומיה עוסקת בטלסקופ.
תוכן עניינים
הנושאים העיקריים
אלה הנושאים העיקריים הנחקרים ונלמדים במסגרת מדְעי המחשב –
- יסודות מתמטיים: מתמטיקה בדידה, אלגברה בוליאנית, לוגיקה, תורת הגרפים, שפות פורמליות, חישוביות, סיבוכיות חישובית.
- יעילות תוכניות: אלגוריתמים, יעילות אלגוריתמית, מיטוב אלגוריתמים ומבני נתונים.
- כלים לפיתוח תוכנה: שפות תכנות, הנדסת תוכנה, הידור, אימות תוכנה, מסדי נתונים.
- תשתיות מחשוב: מערכות הפעלה, רשתות מחשבים.
- ישומים: דחיסת נתונים, למידה ממוחשבת, ראייה ממוחשבת, גרפיקה ממוחשבת, בלשנות חישובית, בינה מלאכותית, קריפטוגרפיה.
מדעי המחשב מסייעים גם במידה רבה לתחום הביואינפורמטיקה וליישום פענוח הגנום האנושי.
חוג מדעי המחשב הראשון הוקם בשנת 1962 באוניברסיטת פורדיו שבארצות הברית.
אבני הדרך והתפתחות המדע
מדעי המחשב התהוו לענף מדע עצמאי רק באמצע המאה ה-20, אם כי התחילו להתפתח זמן רב קודם לכן. מכונות החישוב הראשונות הופיעו כבר בעת העתיקה.
בתקופות קרובות יותר לזמננו, תחום מדעי המחשב התחיל לתפוס תאוצה כשמדענים כמו קפלר, לייבניץ, פסקל (על שמו שפת התכנות פסקל) ואחרים היו צריכים לחשב חישובים מורכבים, והמציאו לשם כך מכונות חישוב מכניות מבוססות גלגלי שיניים.
באמצע המאה ה-19 תיכנן צ'ארלס בבג' מחשב מכָני ראשון מסוגו (אלם הוא מעולם לא קרם עור וגידים). המכונה של בבג' היא למעשה המכונה הראשונה שנבנתה מבלי שתכנונה יקבע מראש את יכולותיה, והיה אפשר לתכנתה למלא פקודות שונות. זוהי המכונה הראשונה מסוגה, ובשל כך, נחשב בבג' לממציא רעיון המחשב.
עדה לאבלייס, בתו של המשורר לורד ביירון, הייתה שותפה לבבג', וכתבה תוכנה למכונתו. בעקבות זאת היא נחשבת למתכנתת הראשונה. על שמה נקראת שפת התכנות Ada.
מאז אותם ימים התפתח תחום המחשבים בצעדי ענק. התרומה העיקרית נזקפת לזכותם של צִבאות העולם. הגרמנים והאמריקאים השתמשו במלחמת העולם הראשונה במכונות חישוב לירי ארטילרי, וכן להצפנה.
לקראת מלחמת העולם השנייה פיתחו הגרמנים מכונת הצפנה משוכללת, אניגמה, ובעזרתה הִצפינו את התשדורת הצבאית שלהם. פיצוח המכונה על ידי בעלות הברית ארך כעשור ואילץ את שירותי הביון של פולין, צרפת והממלכה המאוחדת לפתח כלים מתמטיים (למשל תורת החבורות). פיצוח צופן האניגמה על ידי הצוות הבריטי (הדמות המרכזית בו היה אלן טיורינג), נחשב לאחד הגורמים הבולטים לשימוש מעשי בנושאים שעד אז נחשבו לתאורטיים, והיה זרז לפיתוח תחום מדעי המחשב. טיורינג נחשב לאבי מדעי המחשב המודרניים, ועל שמו נקרא פרס טיורינג המחולק על ידי ארגון ACM, האגודה האמריקאית למחשבים, ונחשב לפרס היוּקרתי בענף.
התפתחות התאוריה של מדְעי המחשב
בשנות השלושים של המאה העשרים התפתח תחום התאוריה של מדעי המחשב, ניתוח האלגוריתמים והחישוביות. פריצת הדרך הייתה יצירת מודל מתמטי של רעיון ה"מחשב". מודל זה נקרא מכונת טיורינג. מודלים רבים אחרים לביצוע חישובים הועלו, והוכחו כשקולים זה לזה מבחינת יכולת החישוב. מכאן הגיעה תזת צ'רץ'-טיורינג שהציעו אלן טיורינג ואלונזו צ'רץ', הטוענת כי כל מודל חישובי "סביר" וחזק מספיק שקול למכונת טיורינג. התזה הזאת מקובלת כיום, על פי רוב, כהנחת עבודה במחקר.
המחשב הראשון
בשנת 1942 פותח המחשב הראשון – Z3 – על ידי קונראד צוזה. מחשב זה היה מחשב עולמי אוניברסלי: מכונה מכנית המסוגלת להריץ תוכנה כלשהי ולא תוכנה קבועה[2]. הוא קרא תוכנה מתוך סרטים מנוקבים. באמצע שנות ה-40 של המאה ה-20 נבנה המחשב ENIAC, המחשב האלקטרוני הראשון בר-התכנות. עם המצאת הטרנזיסטור ב-1947 נפוצו מחשבים אלקטרוניים.
התפתחות השפות הפורמליות והאוטומט הסופי
במהלך 1950 עד 1960 החל להתפתח תחום האוטומטים הסופיים– מודל מעט מוגבל יותר מאשר מכונת הטיורינג הכללית, אך מדמה בצורה טובה תוכנות מחשב פשוטות ותוכנות אשר מנתחות קלט בפורמט קבוע כגון מהדרים למיניהם. בד בבד זינק תחום השפות הפורמליות בשנים אלו, בעיקר לאור עבודתו של נעם חומסקי אשר הגדיר מושגים רבים במבנה השפות. מבנים אלו תורגמו לשפת שאפשר לזהותן במודל האוטומט הסופי, והם עזרו להבחנה בין יכולות מודלים אלו[2].
חישוביות, סיבוכיות ואלגוריתמים
בשנות השישים החל להיבחן נושא הסיבוכיות: עד כמה מהר אפשר לחשב חישובים. בשנים אלו הוגדרו מחלקות סיבוכיות שונות ונבנתה היררכיה של קושי החישוב של הבעיות השונות (כלומר, אילו בעיות "קלות" יותר, ואילו "קשות" יותר). בשנים אלו נתגלו בעיות NP קשות על ידי סטפן קוק ובד בבד על ידי לאוניד לוין. לאחר מכן נתגלו מספר רב של שפות NP שלמות, בעיקר על ידי ריצ'רד קארפ, שחקר בעיה זו לעומקה. בתקופה זו הוגדרה השאלה P=NP, וזו נותרה בעיה פתוחה מרכזית עד עצם היום הזה.
במהלך שנות ה-70 ניסו לפתור את בעיית P=NP מזוויות שונות, כגון ניתוח גודלם של מעגלי מחשוב לוגיים אשר פותרים בעיות שונות. בשנים אלו נוסח הקשר בין זמן הריצה של תוכנית לבין גודל המעגל הלוגי המממש את אותה תוכנית[2]. מעגלי המחשוב הלוגיים הם, למעשה, עוד מודל אשר שקול למכונת טיורינג, ומאפשר לנתח את בעיית החישוביות מזוויות נוספות. בשנים אלו חלה פריחה בתחום מבני הנתונים והאלגוריתמים. דונלד קנות' פרסם את סדרת הספרים[3] "The Art of Computer Programming", וזו הייתה אוסף כתוב ומסודר של הידע על אלגוריתמים בתחומים שונים. בנוסף פותחו ושוכללו אלגוריתמים עבור מיון, אחסון ואיחזור נתונים, אלגוריתמים בתורת הגרפים, פתרון מערכת משוואות לינארית וכן בעיות בחישוב מקבילי[2].
1980 ואילך
בשנים אלה זו חל גידול ניכר בכמות המחשבים ובשימושיהם השונים. המחשב הפך מכלי חישוב אוניברסיטאי ונדיר, לכלי יום-יומי ורחב־תפוצה. משנים אלו התפתחו תחומי תחומים, כגון חישוב מקבילי ומבוזר, קריפטוגרפיה וחישוב קוונטי.
מדְעי המחשב בישראל
מדעי המחשב נלמדים ונחקרים בכל האוניברסיטאות בישראל. הפעילות בתחום זה החלה באמצע שנות השישים, תחילה במסגרת החוגים למתמטיקה או הנדסת חשמל, ולאחר מכן כחוגים עצמאיים, הזוכים לביקוש רב בקרב הסטודנטים. מסלול הלימודים הראשון לתואר במדעי המחשב בישראל נוסד במכון ויצמן למדע בשנת 1969, ביוזמתו של פרופ' שמעון אבן.
ארבעה מדעני מחשב ישראליים קיבלו את פרס טיורינג, ואלה הם:
- מיכאל רבין מהאוניברסיטה העברית בירושלים בעבור תרומתו לתחום האלגוריתמים ופיתוח אלגוריתמים שונים (למשל אלגוריתם רבין קארפ, שפותח עם זוכה פרס טיורינג ריצ'רד קארפ).
- עדי שמיר ממכון ויצמן למדע, בעבור תרומתו לתחום ההצפנה ופיתוח אלגוריתמים שונים כמו פיאט-שמיר, RSA (פותח עם זוכי פרס טיורינג רונלד ריבסט ולאונרד אדלמן במהלך עבודתם המשותפת ב-MIT) ואחרים.
- אמיר פנואלי ממכון ויצמן למדע, בעבור תרומתו לתחום אימות תוכנה וחומרה ופיתוח לוגיקת זמן.
- שפי גולדווסר ממכון ויצמן למדע, על "עבודה מהפכנית שהניחה את היסודות התאורטיים לתורת ההצפנה בתחום הסיבוכיות, תוך המצאת שיטות חדשות וחלוציות לאימות יעיל של הוכחות מתמטיות בתחום תורת הסיבוכיות".[4]
ישראלים רבים קיבלו פרסים אחרים בתחום, כגון פרס גדל (מ-44 הזוכים בפרס עד שנת 2011, תריסר ישראלים) ופרס דייקסטרה.
בישראל נלמדים מדְעי המחשב בכל האוניברסיטאות, וכן במכון ויצמן למדע. מדעים אלה נלמדים גם במכללות, ובהן המרכז האקדמי לב, המכללה למינהל, המכללה האקדמית תל אביב-יפו, המרכז הבינתחומי ומכללת נתניה. בחלקם המוסדות אפשר לשלב מסלולים שונים, באוניברסיטה העברית ובמכללת נתניה קיים מסלול משולב של מדעי המחשב ומנהל עסקים, באוניברסיטת תל אביב קיים מסלול משולב של מדעי המחשב עם לימודי הנדסת חשמל ואלקטרוניקה, בטכניון ובאוניברסיטת אריאל ישנו מסלול משולב של מתמטיקה ומדעי המחשב, ובבר-אילן קיימים מסלולים משולבים של מתמטיקה ומדעי המחשב, ופיזיקה עם מדעי המחשב.
לקריאה נוספת
- דוד הראל, פרקי יסוד במדעי המחשב, סדרת אוניברסיטה משודרת, בהוצאת משרד הבטחון – ההוצאה לאור, 1985
- דוד הראל, אלגוריתמיקה - יסודות מדעי המחשב, האוניברסיטה הפתוחה, 1991 (הספר במיזם פא"ר)
- דוד הראל, המחשב אינו כל-יכול, תל אביב: משכל, 2004,ISBN 9655110278
קישורים חיצוניים
מיזמי קרן ויקימדיה
 ערך מילוני בוויקימילון: מדעי המחשב תמונות ומדיה בוויקישיתוף: מדעי המחשב |
|---|
- Donal Knuth, The Art of Computer Programming וכן באתר ויקיפדיה באנגלית
- מידע על תואר במדעי המחשב באוניברסיטאות ובמכללות
- הילה ויסברג, מתחילים מלמעלה: כמה מרוויחים בוגרי תואר במדעי המחשב?, באתר TheMarker, 6 באוקטובר 2011
הערות שוליים
- ↑ "Computer science is the study of information" Department of Computer and Information Science, Guttenberg Information Technologies
"Computer science is the study of computation." Computer Science Department, College of Saint Benedict, Saint John's University
"Computer Science is the study of all aspects of computer systems, from the theoretical foundations to the very practical aspects of managing large software projects." Massey University - ↑ 2.0 2.1 2.2 2.3 John E.Savage, Models Of Computation, Brown University, 1998 (pdf)
- ↑ הסדרה החלה לאחר שקנות' הבין שספר אחד לא יספיק לכסות את כלל המידע הקיים. כתיבת סדרת הספרים (3 הכרכים הראשונים) נכתבו במשך מעל לעשור, דבר שגרם לקנות' לפתח את השפה TeX, עקב העבודה הרבה שנדרשה ממנו לאור שינויי הטכנולוגיה בתחום עימוד וסידור ספרים
- ↑ שפי גולדווסר ממכון ויצמן זכתה בפרס טיורינג היוקרתי, באתר TheMarker, 13 במרץ 2013
