סמסטר א' תשע"ב

מה נלמד?

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

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

מטלות וציונים

בקורס יוטלו כשישה תרגילים שהגשתם חובה. בסיום הקורס יערך מבחן בית. הציון יורכב מציון מבחן הבית (85%) וציון על השתתפות (15%). מרכיב ההשתתפות יביא בחשבון השתתפות בכיתה והערכה כללית של רמת תרגילי הבית).

תקשורת

מרצה: סיון טולדו, שרייבר 013, stoledo@tau.ac.il

הרצאות בימי ד' 15-18.

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

מטרות מפורטות וסילבוס

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

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

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

  • להקנות מיומנות בסיסית בהבנת יציבות ודיוק של אלגוריתמים נומריים. כמעט כל החישובים הנומריים מתבצעים במחשב באריתמטיקה של נקודה צפה, שבה מתרחשות שגיאות עיגול בכל צעד. בחישוב טיפוסי המחשב גורם למיליוני או מיליארדי שגיאות כאלה ולכן נשאלת השאלה: מה משמעות הפלט? הקורס יציג באופן בסיסי את מושג ההתניה (conditioning) ומושג היציבות המאפשרים לפרש פלט של אלגוריתמים בנקודה צפה.
  • לתאר את האלגוריתמים העיקריים לפתרון בעיות באלגברה ליניארית.
  • להקנות מיומנות בשימוש בתוכנת Matlab, שהיא אחת מסביבות העבודה הנפוצות ביותר לפיתוח אלגוריתמים נומריים.

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

ספר לימוד

ספר הלימוד העיקרי הוא:

Numerical Linear Algebra, by Trefethen and Bau, SIAM, 1997.

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

Applied Numerical Linear Algebra, by Demmel, SIAM, 1997.

שני ספרי עזר מועילים, אם כי אנציקלופדיים מעט הם

Matrix Algorithms, by G. W. Stewart, both Volume I: Basic Decompositions and Volume II: Eigensystems. SIAM, 1998 (Volume I) and 2001 (Volume II).

Matrix Computations, III edition, by Golub and Van Loan, Johns Hopkins University Press, 1996.

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

חומר עזר נוסף לנושא אריתמטיקה של נקודה צפה, ובמיוחד סטנדרט IEEE 754, ניתן למצוא במאמר What every computer scientist should know about floating-point arithmetic (זמין מהארכיון הדיגיטלי של ה-ACM, בחרו ספריה דיגיטלית וחפשו לפי הכותרת; זמין רק ממחשבי האוניברסיטה), ובאתר האינטרנט של וֶלוֶל קהאן.

תרגילים

רשימות מהרצאות