Exam FAQ

מה יהיה המבנה של הבחינה?

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

מה חשוב שיהיה בפתרון שאני רושם בבחינה?

ברוב השאלות יש שלושה חלקים שצריכים להיות בפתרון – האלגוריתם, ניתוח סיבוכיות, והוכחת נכונות.

  • הדבר החשוב ביותר הוא שהאלגוריתם יהיה נכון. במקרה והאלגוריתם שגוי, אנו מורידים נקודות בהתאם לכמה שהוא רחוק מאלגוריתם נכון. אם מספיק שינוי קל על מנת לקבל אלגוריתם תקין, סביר שתקבלו את רוב הנקודות. לעומת זאת, אם האלגוריתם לא קרוב לשום אלגוריתם תקין לבעיה, כנראה שתסתפקו בנקודות מעטות, אם בכלל.
  • ‫הסיבוכיות חשובה! ישנן שאלות שמאוד קל לפתור בזמן $O(n\log n)$ וקשה לפתור בזמן לינארי. לכן, יכולות לרדת לכם הרבה נקודות על אלגוריתם בסיבוכיות שרק קרובה לסיבוכיות הנדרשת.
  • הוכחת הנכונות מעט פחות חשובה. כמובן שחשוב שתהיה הוכחת נכונות תקינה, אבל אנחנו לא מצפים שתוכיחו פורמלית את כל הפרטים הקטנים, ומספיק לנו לראות שאתם מבינים מדוע האלגוריתם נכון. בנוסף, אם פתרתם נכון את השאלה אבל לא הסברתם מספיק את הנכונות שלו, כנראה שתרדנה לכם כמות קטנה יחסית של נקודות (זו כמובן אינה התחייבות שזה מה שיקרה). מקרה יוצא דופן הוא שאלה בה האלגוריתם יחסית ברור והקושי הוא להוכיח את הנכונות. ראו לדוגמא שאלה 1 בבחינה מ-28/01/2011.

האם תהיה שאלת הוכחה בבחינה?

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

אפשר לראות דוגמא לפתרון לשאלה?

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

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

פתרון שאלה 5

נפתור את השאלה בעזרת תכנות דינאמי, ולצורך כך נתחיל מהגדרת תת הבעיות. נגדיר את $c[k,x,y]$ כמשתנה בוליאני שערכו 1 אמ"מ ניתן לחלק את $k$ האיברים הראשונים בסדרה לשלוש קבוצות כך שסכום האיברים בקבוצה הראשונה הוא $x$ וסכום האיברים בקבוצה השניה הוא $y$.

נסמן $A=\sum_{i=1}^n a_i$. זאת אומרת שאנחנו צריכים למצוא את הערך של $c[n, A/3, A/3]$ (אם $A$ לא מתחלק בשלוש התשובה היא כמובן מיידית שלילית). משתנה בוליאני זה בעצם מסמן האם ניתן לחלק את כל איברי הקבוצה לשלוש תת קבוצות כך שסכום האיברים בכל תת קבוצה הינו בדיוק $A/3$.

נתחיל מחישוב מקרי הבסיס. כאשר $n=0$, המשתנה היחיד שיקבל ערך 1 הוא $c[0,0,0]$ ולכל $x,y$ אחרים הערך $c[0,x,y]$ הוא 0 וזאת כי אפס האיברים הראשונים מגדירים בהכרח שלוש תת-קבוצות ריקות.

כעת נראה כיצד לחשב תת בעיה באמצעות פתרונות של תת בעיות קטנות יותר. הנוסחה הרקורסיבית היא $c[k,x,y] = c[k-1, x-a_k, y] \vee c[k-1, x, y-a_k] \vee c[k-1,x,y]$.
החלוקה לשלושה מקרים מתאימה לשלוש האפשרויות למיקום האיבר החדש $a_i$ (קרי: האיבר הראשון מתאים להכנסתו לתת הקבוצה הראשונה, האיבר השני מתאים להכנסה לתת הקבוצה השניה, וכו').

ניתוח סיבוכיות: ישנם $n+1$ ערכים אפשריים עבור $k$, $A/3+1$ ערכים אפשריים עבור $x$, ו-$A/3+1$ ערכים אפשריים עבור $y$. לכן, ישנם משתנים מסוג$c[k,x,y]$ שעלינו לחשב. ראינו שניתן לחשב כל אחד בזמן קבוע על סמך תת בעיות קטנות יותר וכן ידוע כי $A\le n^2$, ולכן זמן הריצה הוא $O(n^5)$.

נושא התאמת המחרוזות נלמד בשבוע שלפני הבחינה. האם יכולה להיות עליו שאלה בבחינה?

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

croc.jpg

אלו תנינים היו קיימים בארץ ישראל?

בארץ ישראל היו נפוצים תניני היאור (תניני הנילוס) עד לתחילת המאה ה-20. בתקופת המקרא ניתן להסיק על תפוצת התנינאים באזור מן האזכורים הרבים. חוקרים רבים שהתמקדו בפאונה של ארץ ישראל הזכירו ברישומיהם תנינים - החל מהאב שמיץ וכלה בזואולוג ישראל אהרוני. התנין האחרון הידוע שחי בארץ ניצוד ב-1912, והוא שמור באוסף הזואולוגי של האב שמיץ בירושלים. פרטים נוספים בנושא ניתן למצוא בפרק 38 בספר (וברור שצריך לדעת את זה לבחינה!).

‫האם צריך לדעת את הנושא X לבחינה? ובכלל, במה כדאי לי להשקיע זמן בלמידה?

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

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

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

  • P מול NPC (כיום הנושא נלמד בקורס מודלים חישוביים).
  • אלגוריתמים הסתברותיים (למשל שאלה 5 בבחינה מה-29.01.2010, כולל סעיף א').
  • בבחינה מה-04.04.2008 יש טעות בשאלה 2, ואנחנו לא מכירים פתרון לינארי עבורה.
  • שאלות הוכחה (למשל שאלה 3 מבחינה מה02.07.09).

האם יערכו חזרות לקראת הבחינה?

כמובן. יהיה תרגול חזרה ב-07.02, 15:00-17:00, באולם דאך.
בנוסף, לקראת הבחינה נערוך סדרת שעות קבלה שאתם מוזמנים להגיע אליהן:
ב-01.02 16:00-17:00 אצל אדם.
ב-05.02 13:00-15:00 אצל אדם.
ב-05.02 15:00-17:00 אצל שי.
ב-06.02 13:00-15:00 אצל שי.
ב-06.02 15:00-17:00 אצל אדם.
שי יושב בopen space, והוראות מפורטות אל אדם ניתן למצוא כאן: http://www.cs.tau.ac.il/~sheffera/room.html
(ואנו נשתדל להיות מאוד זמינים בפורום בימים שלפני הבחינה.)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License