ברוכים הבאים
ספר זה נועד ללוות את הלומדים בקורס גיאומטריה חישובית לתואר ראשון, המבוסס על עשרה פרקים מהספר Computational Geometry: Algorithms and Applications מאת Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars, ושני פרקים נוספים מהספר Geometric Approximation Algorithms מאת שריאל הר-פלד.
לפני שמתחילים
שלום וברוכים הבאים לקורס בגיאומטריה חישובית!
גיאומטריה חישובית היא תחום במדעי המחשב העוסק בפיתוח אלגוריתמים ומבני נתונים לפתרון בעיות גיאומטריות. המוטיבציה לבעיות הנדונות בתחום זה מגיעה לרוב מתחומים יישומיים במדעי המחשב, כמו ראייה ממוחשבת, גרפיקה ממוחשבת ורובוטיקה, וכן מיישומים בתחומים שאינם נמנים עם מדעי המחשב, כמו רשתות תקשורת ותעבורה, מערכות מידע גיאוגרפיות, חקר ביצועים, סטטיסטיקה וביולוגיה מולקולרית. במהלך הקורס נראה כיצד ניתן לתאר בעיות מעשיות באמצעות עצמים גיאומטריים, כמו נקודות, קטעים ומצולעים, במטרה להציג פתרונות פשוטים ויעילים לבעיות מורכבות, בעזרת כלים גיאומטריים. נדון במספר בעיות קלאסיות בגיאומטריה חישובית, בדרכי ניתוחן ובטכניקות שונות לפתרונן, וכן נראה אלגוריתמים ומבני נתונים מעודכנים, ונלמד טכניקות מתקדמות.
לפני שנתחיל, הנה כמה פרטים שכדאי לדעת:
למי מיועד הקורס? תלמידים בשלב מתקדם בתואר הראשון, וכן תלמידי תואר שני במתמטיקה ומדעי המחשב. הקורס מתאים למי שמעוניין להתנסות בתחום מחקר תיאורטי, וגם למי שמחפש בסיס תיאורטי ליישומים מעשיים.
למה לי בכלל ללמוד גאומטריה חישובית? לאלגוריתמים ולמבני הנתונים שנלמד יש אין־ספור יישומים מעשיים חשובים במגוון תחומים רלוונטיים, כמו גרפיקה וראייה מומחשבת, מערכות מידע גיאוגרפיות, ניתוח מידע רב ועוד. תוכלו לרכוש לעצמכם אוסף כלים, מודלים וטכניקות, המוכנים לשליפה ולמימוש בפתרון מגוון של בעיות אלגוריתמיות. נוסף על כך, יש בהם גם יופי מרתק שגלום בתכונות הגיאומטריות, בהגדרה הנקייה של הבעיות, ובאסתטיקה של הפתרונות. בקורס נלמד בעיקר את הטכניקות והאלגוריתמים המשמשים בסיס רעיוני למימושים נפוצים, אך גם נושאים הנמצאים בחזית המחקר כיום.
ידע קודם: בקורס נדרש ידע בנושאים של סיבוכיות אסימפטוטית, אלגוריתמים ומבני נתונים בסיסיים.
מאחלת לכם למידה מהנה!
עומרית
איך מומלץ ללמוד בקורס?
הנושאים בקורס מחולקים ל-12 יחידות לימוד, כאשר כל יחידה מחולקת למספר חלקים, ובל חלק מופיעים מספר עמודים. כל יחידה נפתחת בהצגה של בעיה חדשה (או אוסף חדש של בעיות), ולאחר מכן יוצגו הכלים (מבני נתונים, אלגוריתמים, מודלים) המתאימים לפתרון. למרות שבכל יחידה נלמד נושא חדש לגמרי, מומלץ לעבור על היחידות לפי הסדר מכיוון שחלק מהכלים הנלמדים ישמשו אותנו במספר יחידות בקורס.
ספרי הלימוד
הספר המרכזי אשר ישמש אותנו ביחידות 1–10 הוא Computational Geometry: Algorithms and Applications. שני הפרקים האחרונים בקורס, 11–12, מבוססים על שני פרקים בספר Geometric Approximation Algorithms. ספרים אלו מכילים את כל חומרי הלימוד בקורס, ובכל אחת מיחידות הלימוד מופיעות הפניות לקריאה של החלק הרלוונטי בספר, שמכיל את כל חומרי הלימוד בקורס.
הסברים, סרטונים ודוגמאות
בנוסף לספר הלימוד, כל יחידה כוללת הסברים מפורטים (בטקסט או בסרטון קצר) המלווים בדוגמאות שנועדו להמחיש את הנושאים הנלמדים ביחידה. לעיתים ההסברים המופיעים באתר הקורס אינם מלאים, ונועדו בעיקר כדי להקל עליכם בהבנת החומר הנלמד. לכן אין לוותר על הקריאה בספר, שמכיל את כל הפרטים המלאים והמדויקים שתצטרכו לדעת כדי לענות על המטלות ולפתור את הבחינה.
שימו לב! בחלק מהיחידות מופיעים חומרי עזר לקריאה נוספת ולהעשרה. אלו אינם חלק מחומר הקורס, כפי שמצוין במקומות הרלוונטיים.
תרגילי הבנה פשוטים ושאלות למחשבה
בתוך כל אחת מיחידות הלימוד מופיעים תרגילי הבנה פשוטים, שיעזרו לכם לוודא שהבנתם באופן בסיסי את ההגדרות והרעיונות הנלמדים ביחידה.
בנוסף לתרגילי ההבנה הפשוטים, לפעמים תפגשו גם שאלות למחשבה, שהפתרון עבורן מורכב יותר ואינו מופיע באתר. מומלץ לחשוב ולנסות לענות על השאלות בעל פה או באופן מלא בכתב, וכן לדון בהן בפורום של הקורס ולשתף פתרונות.
כלים ומקורות נוספים
בעמוד זה ירוכזו כלים שימושיים לקורס, ומקורות נוספים ללמידה ולהעשרה.
הרצאות מוקלטות וחומרי לימוד נוספים.
למעוניינים בכך, ניתן למצוא חומרי לימוד מצוינים מקורסים דומים הניתנים ברחבי העולם. הנה רשימה חלקית ביותר של הבולטים בהם:
- CMSC 754 Computational Geometry, by David M. Mount.
- Geometry: Combinatorics and Algorithms, by Luis Barba Bernd Gärtner, Michael Hoffmann and Emo Welzl.
- Computational Geometry, video lectures by Philipp Kindermann.