שאלית קצת דחופה בC...

[Makover]

לא בדקתי

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

 

[neko]

למעשה, עברתי על מבחנים קודמים

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

 

[אלדד28]

כי ככה צריך, מבחן ב-C אמור להיות

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

 

[ChipsMan]

זאת שאלה בתכנון דינאמי..

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

 

[neko]

ומה שהכי מעצבן אותי, זה שהייתי

יכול לתת את הפתרון הנאיבי של הN^3 (פשוט להשוות את כל הסכומים האפשריים) ואז בטח הייתי מקבל לפחות חצי שאלה - אבל סתם התברדקתי והסתבכתי ואם המרצה יהיה נחמד אני אקבל כמה נק' על הנסיון...

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

 

[Zack DA]

שאלה מאוד הגיונית.

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

 

[ChipsMan]

אממ...

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

 

[Zack DA]

זו שאלת חשיבה.

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

 

[ChipsMan]

תראה...

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

 

[Zack DA]

"לא נותנים" זו עובדה, שדבר ראשון -

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

 

[ChipsMan]

בוא נעשה סדר בבלגן ../images/Emo13.gif

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

 

[ChipsMan]

ועוד משהו ../images/Emo13.gif

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

 

[Zack DA]

הבהרת את עצמך ../images/Emo13.gif

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

 

[neko]

ZACK - רסמי, אם היית מקבל את

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

 

[Zack DA]

זו שאלה לא הוגנת.

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

 

[neko]

התרגילים שכתבנו במהלך הקורס:

1. יישום המשחק של מגדלי האנוי ברקורסיה 2. מציאת כל המספרים הראשוניים באמצעות האלגוריתם של ארסטוטנס (שניתן לנו במקום) 3. זיהוי פלינדרום ברקורסיה. 4. חישוב טור טיילור של E בחזקת X 5. ספירת כמות ההופעה של כל אות במשפט 6. מציאת ORDER STATISTIC של מספר ברשימת מספרים שניתנה (כולל ביצוע BUBBLE SORT). 7. כתיבת מחשבון מטריצות (חיבור חיסול כפל והופכי) 8. מציאת אות הכי נפוצה בטקסט והחזרת כל המילים בה היא מופיעה. 9. כתיבת ספרייה לעבודה עם INT-ים ללא מגבלת אורך (ע"י רשימה מקושרת) כולל הפעולות הבסיסיות: חיבור חיסור וכפל. 10. כתיבת קומפיילר וסימולטור לאסמבלר בסיסי (הופך קוד ל"שפת מכונה" ומריץ אותו בסימולציה. האם אתה חושב שלאור התרגילים שקיבלנו (עם שבוע בממוצע לכל תרגיל, וגישה לספרים שעודדנו להשתמש בהם ע"מ למצוא אלגוריתמים וטכניקות) הם ברמה האלגוריתמית של מה שקיבלנו במבחן? האם אדם שלא למד את הקורס "אלגוריתמים" (שאינו מהווה קורס קדם) היה מסוגל בחצי שעה למצוא וליישם את האלגוריתם הנדרש, כאשר למד בשלושת הימים שלפני רק את הפקודות של C וה"םינות" שלהן (כי עיקר המבחן הוא שאלות אמריקאיות שמנסות להפיל את הנבחן בפינות כמו כתיבת A.A->A במקום A->A.A בשאלה "מה התוכנית תדפיס")? אני חושב שהמבחן הזה פגע בי ובציונים שלי בצורה לא ראוייה.

 

[Zack DA]

ובכן, אם על כל התרגילים הללו נדרשת

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

 

[neko]

בכל התרגילים הנ"ל עודדנו לפתוח

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

 

[Zack DA]

טוב, נו - ככה זה במבחן.

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

 

[neko]

זה לא בדיוק המימוש הכי מסובך בעולם,

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