מדעי המחשב
|
עיינו גם בפורטל  פורטל מדעי המחשב הוא שער לכל הנושאים הקשורים במדעי המחשב. ניתן למצוא בו קישורים אל תחומי המשנה של הענף, מושגי יסוד בתחום, מדענים חשובים ועוד. |
מדעי המחשב הוא ענף מדעי העוסק בלימוד הבסיס התאורטי למידע ולחישוביות, והחלתם של אלה על מערכות מחשב[1]. למדעי המחשב מספר רב של ענפי-משנה; חלקם מדגישים את היבטי החישוביות של תוצאות פרטניות (לדוגמה, גרפיקה ממוחשבת), אחרים עוסקים בחקר התכונות של בעיות חישוביות כלליות (לדוגמה, סיבוכיות), וענפי-משנה אחרים מתמקדים בפתרון הבעיות הכרוכות ביישום מעשי של חישובים ואלגוריתמים. ענף משמעותי במדעי המחשב הוא חקר ויישום שפות פורמליות לפתרון בעיות חישוביות מסוימות (לדוגמה, באמצעות שפת תכנות).
להדגשת ההיבט התאורטי של תחום זה, אמר אחד מהעוסקים הבולטים בו:
 |
מדעי המחשב אינם עוסקים במחשב יותר משאסטרונומיה עוסקת בטלסקופ |  |
| – אדסחר דייקסטרה | ||
תוכן עניינים |
[עריכה] נושאים עיקריים במדעי המחשב
נושאים עיקריים הנחקרים ונלמדים במסגרת מדעי המחשב כוללים:
- יסודות מתמטיים: מתמטיקה בדידה, אלגברה בוליאנית, לוגיקה, תורת הגרפים, שפות פורמליות, חישוביות, סיבוכיות.
- יעילות של תוכניות: אלגוריתמים, יעילות אלגוריתמית, מיטוב אלגוריתמים ומבני נתונים.
- כלים לפיתוח תוכנה: שפות תכנות, הנדסת תוכנה, הידור, אימות תוכנה, מסדי נתונים.
- תשתיות מחשוב: מערכות הפעלה, רשתות מחשבים.
- ישומים: דחיסת נתונים, למידה ממוחשבת, ראייה ממוחשבת, גרפיקה ממוחשבת, בלשנות חישובית, בינה מלאכותית, קריפטוגרפיה.
מדעי המחשב מסייעים גם במידה רבה לתחום הביואינפורמטיקה, וליישום פענוח הגנום האנושי במידה רבה.
חוג למדעי המחשב הוקם לראשונה בשנת 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, ביוזמתו של פרופ' שמעון אבן.
שלושה מדעני מחשב ישראליים קיבלו את פרס טיורינג:
- מיכאל רבין מהאוניברסיטה העברית בירושלים עבור תרומתו לתחום האלגוריתמים, ופיתוח אלגוריתמים שונים (כמו למשל אלגוריתם רבין קארפ שפותח עם זוכה פרס טיורינג ריצ'רד קארפ).
- עדי שמיר ממכון ויצמן למדע, עבור תרומתו לתחום ההצפנה, ופיתוח אלגוריתמים שונים כמו פיאט-שמיר, RSA (שפותח עם זוכי פרס טיורינג רונלד ריבסט ולאונרד אדלמן במהלך עבודתם המשותפת בMIT), ואחרים.
- אמיר פנואלי ממכון ויצמן למדע, עבור תרומתו לתחום אימות תוכנה וחומרה, ופיתוח לוגיקת זמן.
ישראלים רבים קיבלו פרסים אחרים בתחום, כגון פרס גדל (מבין 44 הזוכים בפרס עד שנת 2011, 12 הם ישראלים) ופרס דייקסטרה, וישראל נחשבת למעצמה בתחום מדעי המחשב.[1]
[עריכה] לקריאה נוספת
- דוד הראל, פרקי יסוד במדעי המחשב, סדרת אוניברסיטה משודרת, בהוצאת משרד הביטחון - ההוצאה לאור, 1985
- דוד הראל, אלגוריתמיקה - יסודות מדעי המחשב, האוניברסיטה הפתוחה, 1991 (הספר במיזם פא"ר - יש להירשם לאתר ללא תשלום)
- דוד הראל, המחשב אינו כל-יכול, הוצאת משכל, 2004
[עריכה] קישורים חיצוניים
- Donal Knuth, The Art of Computer Programming וכן באתר ויקיפדיה באנגלית
[עריכה] הערות שוליים
- ^ "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, עקב העבודה הרבה שנדרשה ממנו לאור שינויי הטכנולוגיה בתחום עימוד וסידור ספרים
