מדעי המחשב

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

עיינו גם בפורטל

P Computer-science.png

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


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

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

Cquote2.svg

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

Cquote3.svg
אדסחר דייקסטרה

נושאים עיקריים במדעי המחשב[עריכת קוד מקור | עריכה]

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

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

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

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

אבני דרך והתפתחות המדע[עריכת קוד מקור | עריכה]

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

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

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

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

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

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

התפתחות התאוריה של מדעי המחשב[עריכת קוד מקור | עריכה]

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

המחשב הראשון[עריכת קוד מקור | עריכה]

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

התפתחות השפות הפורמליות והאוטומט הסופי[עריכת קוד מקור | עריכה]

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

חישוביות, סיבוכיות ואלגוריתמים[עריכת קוד מקור | עריכה]

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

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

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

1980 ואילך[עריכת קוד מקור | עריכה]

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

מדעי המחשב בישראל[עריכת קוד מקור | עריכה]

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

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

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

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

לקריאה נוספת[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ "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. ^ 2.0 2.1 2.2 2.3 ‏‎John E.Savage, Models Of Computation, Brown University, 1998 (pdf)‏
  3. ^ ‏הסדרה החלה לאחר שקנות' הבין שספר אחד לא יספיק לכסות את כלל המידע הקיים. כתיבת סדרת הספרים (3 הכרכים הראשונים) נכתבו במשך מעל לעשור, דבר שגרם לקנות' לפתח את השפה TeX, עקב העבודה הרבה שנדרשה ממנו לאור ‏שינויי הטכנולוגיה בתחום עימוד וסידור ספרים
  4. ^ סוכנויות הידיעות, שפי גולדווסר ממכון ויצמן זכתה בפרס טיורינג היוקרתי, באתר TheMarker‏, 13 במרץ 2013