פעילויות תשס"ד – סדנה לקידום האולימפיאדה במדעי המחשב

למשתתפי הסדנה: הועבר דו"ח השתתפות למשרד החינוך לצורך טיפול בגמול

 

סיכום מפגש 1

טופס הרשמה

מידע כללי

 

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

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

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

המשתתפים יוזמנו להשתתף בפורום פעיל בין המפגשים.

כל מורה מתחייב לעבוד במהלך הסדנה לפחות עם 5 תלמידים (מבית הספר או מבתי ספר בסביבה).

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

 

המפגשים יתקיימו באוניברסיטת ת"א, בימי רביעי אחה"צ, בשעות 16:00-19:00

תאריכי המפגשים 29.10.03, 26.11.03, 17.12.03, 21.1.04, 18.2.04

התשלום לקבלת גמול הוא 50 ש"ח.

 

המפגש הראשון של הסדנה התקיים ביום רביעי 29.10.03

במסגרת המפגש הוצגו מטרות הסדנה, וניתנה סקירה על האלימפיאדה הישראלית והבינלאומית.

לאחר מכן נידונו 4 בעיות ונותחו פתרונות שונים שלהן וגישות לפתרון בעיות דומות.

תוכלו למצוא כאן את הבעיות.

 

הבעיות שנידונו במפגש הראשון של הסדנה

בעייה 1 –  Josephus Problem

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

כיצד שרד יוספוס?

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

הם מיספרו את עצמם מ-1 עד 41, וקבעו שמספר 7 יתאבד. לאחר התקדמות של 7 לוחמים נוספים במעגל שנותר יתאבד הלוחם הבא, וכך הלאה. כלומר, תחילה התאבד לוחם מספר 7, אח"כ 14, 21, 28, 35, 1, 9, 17, ... שים לב ש-1 נמצא 7 מקומות מ-35 במעגל, ו-9 נמצא 7 מקומות מ-1 לאחר שלוחם 7 יצא מן המעגל (כיון שהתאבד). יוספוס טוען בכתביו שהוא ידע היכן לעמוד במעגל כדי להבטיח שיישאר אחרון, וניצל.

כיצד ידע יוספוס היכן לעמוד במעגל?

נגדיר מאופן כללי את הבעיה:

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

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

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

 

בעייה 2 – טורניר טניס

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

בהינתן N, מספר השחקנים התחילי (למשל, 317), כמה משחקים יהיו בסך הכל בטורניר?

רמז: אפשר לפתור את הבעייה בסיבוכיות  Time O(1)

 

בעייה 3 – נקודות ירוקות וחומות

נתונות N נקודות ירוקות N ... 1,2, ועוד N נקודות חומות N ... 1,2,

כל הנקודות מסודרות על קו אחד כך ש- I ירוק יהיה תמיד לפני I חום, אבל לא בהכרח לפני J חום.

דוגמאות לסידורים חוקיים:

3

2

2

1

3

1

 

 

 

 

3

3

2

2

1

1

 

אנחנו רוצים לחבר בחוטי חשמל נקודות תואמות (לחבר כל I ירוק עם I חום).

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

רמז: ניתן לפתור את הבעייה בסיבוכיות  Time O(n), Space O(1)

 

בעייה 4 – מגדלי קוביות

נגדיר את המשחק הבא:

נתונים שני מגדלים של קוביות. במגדל אחד יש X קוביות ובשני יש Y קוביות.

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

המנצח במשחק הוא השחקן שהוריד את הקוביה האחרונה.

מצא אסטרטגיה לנצח במשחק.

גרסה נוספת למשחק: נוסיף מגדל שלישי של קוביה אחת.