מדעי המחשב

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

מדְעי המחשב הם ענף מדעי העוסק בלימוד הבסיס התאורטי והמעשי של השימוש במערכות מחשב, ובמידה מסוימת, גם בשאלה של תכנון ובנייה של מערכות מחשב. ענפי המִשנה שלו רבים; חלקם מדגישים שימוש במחשב בתחום מסוים (כגון גרפיקה ממוחשבת או בניית מהדרים), אחרים עוסקים בחקר התכונות של בעיות חישוביות כלליות (לדוגמה, סיבוכיות), וענפי משנה אחרים מתמקדים בפתרון הבעיות הכרוכות ביישום מעשי של חישובים ואלגוריתמים. ענף בולט במדְעי המחשב הוא חקר ויישום כלים לפתרון בעיות חישוביות (לדוגמה, שפות תכנות).

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

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

הנושאים העיקריים

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

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

אבני הדרך והתפתחות המדע

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

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

באמצע המאה ה-19 תכנן צ'ארלס בבג' מחשב מכָני ראשון מסוגו (אולם הוא מעולם לא קרם עור וגידים). המכונה של בבג' היא למעשה המכונה הראשונה שנבנתה מבלי שתכנונה יקבע מראש את יכולותיה, והיה אפשר לתכנתה למלא פקודות שונות. זוהי המכונה הראשונה מסוגה, ובשל כך, נחשב בבג' לממציא רעיון המחשב.

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

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

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

התפתחות התאוריה של מדְעי המחשב

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

המחשב הראשון

ב-1942 פותח המחשב הראשון, Z3, על ידי קונראד צוזה. מחשב זה היה מחשב אוניברסלי: מכונה מכנית המסוגלת להריץ תוכנה כלשהי ולא תוכנה קבועה. הוא קרא תוכנה מתוך סרטים מנוקבים. באמצע שנות ה-40 של המאה ה-20 נבנה המחשב ENIAC, המחשב האלקטרוני הראשון בר-התכנות. עם המצאת הטרנזיסטור ב-1947 נפוצו מחשבים אלקטרוניים.

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

התפתחות השפות הפורמליות והאוטומט הסופי

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

חישוביות, סיבוכיות ואלגוריתמים

בשנות ה-60 החל להיבחן נושא הסיבוכיות: עד כמה מהר אפשר לחשב חישובים. בשנים אלו הוגדרו מחלקות סיבוכיות שונות ונבנתה היררכיה של קושי החישוב של הבעיות השונות (כלומר, אילו בעיות "קלות" יותר, ואילו "קשות" יותר). בשנים אלו נתגלו בעיות NP קשות על ידי סטפן קוק ובד בבד על ידי לאוניד לוין. לאחר מכן נתגלו מספר רב של בעיות NP שלמות, בעיקר על ידי ריצ'רד קארפ, שחקר בעיה זו לעומקה. בתקופה זו הוגדרה השאלה P=NP, וזו נותרה בעיה פתוחה מרכזית עד היום.

בשנת 1968 דונלד קנות' החל לפרסם את סדרת הספרים "The Art of Computer Programming", וזו הייתה אוסף כתוב ומסודר של הידע על אלגוריתמים בתחומים שונים.

במהלך שנות ה-70 ניסו לפתור את בעיית P=NP מזוויות שונות, כגון ניתוח גודלם של מעגלי מחשוב לוגיים אשר פותרים בעיות שונות. בשנים אלו נוסח הקשר בין זמן הריצה של תוכנית לבין גודל המעגל הלוגי המממש אותה. מעגלי המחשוב הלוגיים הם, למעשה, עוד מודל השקול למכונת טיורינג, ומאפשר לנתח את בעיית החישוביות מזוויות נוספות. בשנים אלו חלה פריחה בתחום מבני הנתונים והאלגוריתמים. בנוסף פותחו ושוכללו אלגוריתמים עבור מיון, אחסון ואיחזור נתונים, אלגוריתמים בתורת הגרפים, פתרון מערכת משוואות ליניארית וכן בעיות בחישוב מקבילי.

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

1980 ואילך

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

מדעי המחשב בישראל

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

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

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

• מיכאל רבין מהאוניברסיטה העברית בירושלים בעבור תרומתו לתחום האלגוריתמים ופיתוח אלגוריתמים שונים (למשל אלגוריתם רבין קארפ, שפותח עם זוכה פרס טיורינג ריצ'רד קארפ).
• עדי שמיר ממכון ויצמן למדע, בעבור תרומתו לתחום ההצפנה ופיתוח אלגוריתמים שונים כמו פיאט-שמיר, RSA (פותח עם זוכי פרס טיורינג רונלד ריבסט ולאונרד אדלמן במהלך עבודתם המשותפת ב-MIT) ואחרים.
• אמיר פנואלי ממכון ויצמן למדע, בעבור תרומתו לתחום אימות תוכנה וחומרה ופיתוח לוגיקת זמן.
• יהודה פרל מאוניברסיטת קליפורניה בלוס אנג'לס, ישראלי־אמריקאי, על תרומה יסודית לחקר בינה מלאכותית באמצעות פיתוח תחשיב להסקה סיבתית והסתברותית.
• שפי גולדווסר ממכון ויצמן למדע, על "עבודה מהפכנית שהניחה את היסודות התאורטיים לתורת ההצפנה בתחום הסיבוכיות, תוך המצאת שיטות חדשות וחלוציות לאימות יעיל של הוכחות מתמטיות בתחום תורת הסיבוכיות".
• אבי ויגדרזון מהמכון למחקר מתקדם בפרינסטון, על הבנת האקראיות במחשוב ועל הובלתו ארוכת הטווח במדעי המחשב התיאורטיים.

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

מתוך כ-20,000 מחלקות למדעי מחשב אקדמיות בעולם, מוסדות ישראליים מדורגים סביב מקומות 50–150 בדירוג שנחאי שמתעדכן מדי שנה וכולל קריטריונים כגון עומק מחקרי, תרומה למדע, לתעשייה ולחברה, שכיחות ציטוטי פרסומים, מספר פטנטים חדשים, איכות הוראה ועוד.

לקריאה נוספת

• דוד הראל, ‏פרקי יסוד במדעי המחשב, סדרת אוניברסיטה משודרת, בהוצאת משרד הביטחון – ההוצאה לאור, 1985
• דוד הראל, ‏אלגוריתמיקה - יסודות מדעי המחשב, האוניברסיטה הפתוחה, 1991
• דוד הראל, המחשב אינו כל-יכול, תל אביב: משכל, 2004, מסת"ב 978-965-545-717-9

Overview

• Tucker, Allen B. (2004). Computer Science Handbook (2nd ed.). Chapman and Hall/CRC. ISBN 1-58488-360-X.
  • "Within more than 70 chapters, every one new or significantly revised, one can find any kind of information and references about computer science one can imagine. […] all in all, there is absolute nothing about Computer Science that can not be found in the 2.5 kilogram-encyclopaedia with its 110 survey articles […]." (Christoph Meinel, Zentralblatt MATH)
• van Leeuwen, Jan (1994). Handbook of Theoretical Computer Science. The MIT Press. ISBN 0-262-72020-5.
  • "[…] this set is the most unique and possibly the most useful to the [theoretical computer science] community, in support both of teaching and research […]. The books can be used by anyone wanting simply to gain an understanding of one of these areas, or by someone desiring to be in research in a topic, or by instructors wishing to find timely information on a subject they are teaching outside their major areas of expertise." (Rocky Ross, SIGACT News)
• Ralston, Anthony; Reilly, Edwin D.; Hemmendinger, David (2000). Encyclopedia of Computer Science (4th ed.). Grove's Dictionaries. ISBN 1-56159-248-X.
  • "Since 1976, this has been the definitive reference work on computer, computing, and computer science. […] Alphabetically arranged and classified into broad subject areas, the entries cover hardware, computer systems, information and data, software, the mathematics of computing, theory of computation, methodologies, applications, and computing milieu. The editors have done a commendable job of blending historical perspective and practical reference information. The encyclopedia remains essential for most public and academic library reference collections." (Joe Accardin, Northeastern Illinois Univ., Chicago)
• Edwin D. Reilly (2003). Milestones in Computer Science and Information Technology. Greenwood Publishing Group. ISBN 978-1-57356-521-9.

Selected literature

• Knuth, Donald E. (1996). Selected Papers on Computer Science. CSLI Publications, Cambridge University Press.
• Collier, Bruce. The little engine that could've: The calculating machines of Charles Babbage. Garland Publishing Inc. ISBN 0-8240-0043-9.
• Cohen, Bernard (2000). Howard Aiken, Portrait of a computer pioneer. The MIT press. ISBN 978-0-2625317-9-5.
• Tedre, Matti (2014). The Science of Computing: Shaping a Discipline. CRC Press, Taylor & Francis.
• Randell, Brian (1973). The origins of Digital computers, Selected Papers. Springer-Verlag. ISBN 3-540-06169-X.
  • "Covering a period from 1966 to 1993, its interest lies not only in the content of each of these papers — still timely today — but also in their being put together so that ideas expressed at different times complement each other nicely." (N. Bernard, Zentralblatt MATH)

Articles

• Peter J. Denning. Is computer science science?, Communications of the ACM, April 2005.
• Peter J. Denning, Great principles in computing curricula, Technical Symposium on Computer Science Education, 2004.
• Research evaluation for computer science, Informatics Europe report. Shorter journal version: Bertrand Meyer, Christine Choppy, Jan van Leeuwen and Jorgen Staunstrup, Research evaluation for computer science, in Communications of the ACM, vol. 52, no. 4, pp. 31–34, April 2009.

Curriculum and classification

• Association for Computing Machinery. 1998 ACM Computing Classification System. 1998.
• Joint Task Force of Association for Computing Machinery (ACM), Association for Information Systems (AIS) and IEEE Computer Society (IEEE CS). Computing Curricula 2005: The Overview Report. September 30, 2005.
• Norman Gibbs, Allen Tucker. "A model curriculum for a liberal arts degree in computer science". Communications of the ACM, Volume 29 Issue 3, March 1986.

קישורים חיצוניים

• Donal Knuth, The Art of Computer Programming וכן באתר ויקיפדיה באנגלית
• הילה ויסברג, מתחילים מלמעלה: כמה מרוויחים בוגרי תואר במדעי המחשב?, באתר TheMarker‏, 6 באוקטובר 2011
• מדעי המחשב, דף שער בספרייה הלאומית
• מדעי המחשב, באתר אנציקלופדיה בריטניקה (באנגלית)

• Scholarly Societies in Computer Science
• What is Computer Science?, סרטון באתר יוטיוב
• Best Papers Awards in Computer Science since 1996
• Photographs of computer scientists by Bertrand Meyer
• EECS.berkeley.edu

Bibliography and academic search engines

• CiteSeer^x: search engine, digital library and repository for scientific and academic papers with a focus on computer and information science.
• DBLP Computer Science Bibliography: computer science bibliography website hosted at Universität Trier, in Germany.
• The Collection of Computer Science Bibliographies

Professional organizations

• Association for Computing Machinery
• IEEE Computer Society
• Informatics Europe
• AAAI
• AAAS Computer Science

Misc

• Computer Science—Stack Exchange: a community-run question-and-answer site for computer science
• What is computer science (אורכב 18.02.2015 בארכיון Wayback Machine)
• Is computer science science?
• Computer Science (Software) Must be Considered as an Independent Discipline.