החומר המופיע בעמוד זה פורסם לראשונה בכתב העת "הבטים בהוראת מדעי המחשב" גליון יוני 2003, עמודים 59-63

לא ניתן לעשות שימוש מסחרי בחומר זה ללא רשות בכתב מן המחברים או מערכת כתב העת

פורום מודלים חישוביים

 

 

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

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

הפורום פתוח לקריאה וכתיבה לכל המורים הרשומים במאגר המורים של המרכז הארצי וכתובתו:

http://cse.proj.ac.il/forum/ReadLogin.asp?Fnumber=19

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

 

דוגמה 1 – אי דטרמיניזם

בתאריך 14.12.02 שאלה מורה את השאלה הבאה:

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

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

 

דוגמה 2 – הקשר למדעי המחשב

בתאריך 24.12.02 שאלה מורה את השאלה הבאה:

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

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

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

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

 

דוגמה 3 – בניית אוטומט מחסנית

בתאריך 5.1.03 שאל מורה את השאלה הבאה:

נתונה השפה הבאה

L={ax cy a3x+2 | x>0, y>0, y mod 2=0 }

אני מעוניין לבנות אוטומט מחסנית. [...] רציתי לשאול איך אני אדע שנשארו לי 2x+2 תווים של a ?

תשובתה של איריס: אפשר לפתור במספר דרכים:

1. לכל מופע של a לדחוף למחסנית A, לדאוג למספר זוגי של מופעי c ואז בקבלת a שוב, לשלוף מהמחסנית לאחר כל מופע שלישי של a. לאחר שהמחסנית מתרוקנת, לדאוג לקבל עוד שני מופעי a.

2. כמו קודם אך בעת קבלת מופעי a בפעם השניה (לאחר קבלת מופעי c), לקבל ראשית שני מופעי a בלא התייחסות למחסנית, ורק אח"כ לשלוף מהמחסנית אחרי כל מופע שלישי של האות a.

3. בעת קבלת מופעי האות a בתחילת המילה, עבור כל מופע של a לדחוף למחסנית את המילה AAA. לדאוג לקבלת מספר זוגי של מופעי c ועתה עבור כל מופע של a לשלוף אות אחת מהמחסנית. לגבי שני המופעים הנוספים, שוב ניתן להתייחס אליהם כאילו הם שני המופעים הראשונים ברצף או שני המופעים האחרונים ברצף. כמו בפתרונות 1,2.

 

דוגמה 4 – איזו הוכחה עדיפה?

בתאריך 19.1.03 שאלה מורה את השאלה הבאה:

לאחרונה נתקלתי בבעיה הבאה:

כאשר נתונה השפה הבאה: L שפת כל המילים מעל א"ב {a,b} המקיימות את התנאים הבאים: אינן מתחילות ב a ואינן מכילות את הרצף bb. האם L רגולרית ? הוכח תשובתך.

רוב התלמידים בכתתי פרקו את השפה לשתי שפות:

L1 שפת כל המילים ... שאינן מתחילות ב- a.

L2 שפת כל המילים ... שאינן מכילות את הרצף bb.

הוכיחו עבור כל שפה כי ניתן לבנות לה אס"ד והיות ומשפחת השפות הרגולריות סגורה תחת חיתוך - השפה L רגולרית.

אולם המגמה בתשובות במדריך למורה היא לפרק לשתי השפות L1 שפת כל המילים ... המתחילות ב- a.

L2 שפת כל המילים ... המכילות את הרצף bb.

ובהוכחת הרגולריות להשתמש בשפת המשלים של L1 ו- L2.

שאלתי היא: האם פתרון אחד עדיף על השני? אם כן כיצד אסביר לתלמידי את העדיפות?

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

 

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

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

 

דוגמה 5 – האם קיים אוטומט מחסנית?

בתאריך 20.1.03 שאל מורה את השאלה הבאה:

אני מתקשה לבנות אוטומט מחסנית לשפה הבאה  (אולי לא ניתן לפתרון)

L={an bk cm dp | m>n, p=k }

אשמח אם מישהו יוכל לעזור לי.

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

 

דוגמה 6 – מה הקשר בין שפות רגולריות ושפות חסרות הקשר?

בתאריך 22.1.03 שאל מורה את השאלה הבאה:

האם כל שפה חופשית הקשר היא אינה רגולרית? ומה ההבדל בין שפות חופשיות הקשר ולא רגולריות לבין אינםן חופשיות הקשר?

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

L= {W.R(W).c.X.c.R(X) }

W ו- X הן מילים מעל הא"ב {a,b}

תשובתה של איריס: כל שפה רגולרית היא בהכרח גם חופשית הקשר. ההפך כמובן לא נכון.

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

L={W.R(W).c.X.c.R(X)}

W ו- X הן מילים מעל הא"ב  {a,b}

שפה זו היא חופשית הקשר. ניתן לקבלה ע"י שרשור של 3 שפות: שפת הראי הלא מסומנת –   W.R(W). השפה המכילה את המלה c בלבד ושפת הראי המסומנת –  X.c.R(x)

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

 

דוגמה 7 – איחוד וחיתוך של שפות

בתאריך 5.2.03 שאל מורה את השאלה הבאה:

רציתי לקבל עזרה בשאלה הבאה:

L1={ ים -b ים גדול ממספר ה- –a כל המילים בהן מספר ה-

L2={ מופיעה לפחות פעמיים b כל המילים בהן  }

L3={ c כל המילים המכילות רצף של שתי אותיות  }

הגדר את השפות הבאות

1.L1 איחוד L2
2.
 L1חיתוך L2
3. (
L2 איחוד L3) חיתוך L1

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

למשל, אפשר להגדיר חיתוך של שפות, שהאחת מכילה לפחות שני b, והאחרת מכילה לכל היותר שני b, מעל א"ב נתון, למשל {a,b}. כאן החיתוך יהיה שפת המלים, המכילות בדיוק שני b.

מורה אחרת הציעה את הפתרון הבא:

1.שפת כל המילים המכילות לפחות שני b – ים או מספר a – ים גדול ממספר ה- b- ים.

2.שפת כל המילים המכילות לפחות 2 b-ים ו 3 a –ים.

3.שפת כל המילים המכילות לפחות 2 b-ים ו 3 a –ים או המילים שבהן מופיע הרצף cc ומספר האותיות a גדול ממספר האותיות b.

 

דוגמה 8 – רגולריות

בתאריך 24.2.03 שאל מורה את השאלה הבאה:

אם w שפה רגולרית האם בהכרח w.R(w) שפה רגולרית? למשל,

w={ai bj | i,j>0 }

w שפה רגולרית, R(w) גם שפה רגולרית לכן שרשור שפות רגולריות הוא גם שפה רגולרית. האם זה נכון?

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

אם התכוונת לניסוח הבא: L שפה רגולרית, האם השפה LR(L) רגולרית? אז התשובה חיובית, בגלל הסגירות של משפחת השפות הרגולריות להיפוך ולשרשור.

לעומת זאת, אם התכוונת לניסוח: L שפה רגולרית, האם שפת כל המילים wR(w) כך ש-w מילה ב-L , היא רגולרית? אז התשובה היא לא במקרה הכללי. (עבור L ספציפיות זה מתקיים, עבור אחרות לא)

 

דוגמה 9 – תכנית הלימודים

בתאריך 25.3.03 שאל מורה את השאלה הבאה:

האם דרוש בתוכנית הלימודים ללמד:

1. כוחם של המודלים (אוטומט לא מלא, לא דטרמינסטי)

2. המרת אוטמט לא דטרמינסטי לאוטמט דטרמינסטי

3.אוטמט לקבלת שפת השרשור

תשובתה של מיכל: כל שלושת הנושאים שמנית הם בחומר הלימוד (איני מתייחסת למיקוד אלא לתוכנית הלימודים במהלך השנה).

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

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

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

 

דוגמה 10 – שאלות לדוגמה

בתאריך 15.4.03 ביקשה מורה דוגמאות לשאלות.

איריס נחלצה לעזרה והנה תשובתה:

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

למשל הנה שאלה:

נתבונן בשפה מעל הא"ב {a, b, c} המכילה בדיוק את כל המילים שמקיימות את שני התנאים הבאים:
א. אורך המילה מתחלק ל- 6, או ל- 15.

ב. המילה מורכבת משני חלקים, האחד אורכו זוגי ומספר אותיות b בו מתחלק ב- 3, והשני מכיל בדיוק 2 אותיות b או לפחות 2 אותיות a.

האם שפה זו היא רגולרית? הוכח את תשובתך.

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

לדוגמא:

נתבונן בשפה מעל הא"ב {a, b, c} המכילה את כל המילים שמקיימות אחד מהתנאים הבאים:

א. המלה היא פלינדרום.

ב. המילה מורכבת משני חלקים, האחד אורכו זוגי ומספר אותיות b בו מתחלק ב-3, והשני מכיל מספר אותיות b הגדול ממספר אותיות a.

ג. מספר אותיות a במילה מתחלק ב-4, מספר אותיות b במילה אי-זוגי ואורך המילה זוגי.

האם שפה זו היא חופשית הקשר? הוכח את תשובתך.

 

דוגמה 11 – חסרת הקשר

בתאריך 3.5.03 שאלה מורה את השאלה הבאה:

האם השפה  an bk , n<k<2n  ח"ה? ראיתי מבחן שבו היה צריך להוכיח שהיא ח"ה.

תשובתה של מיכל: אכן ח"ה. נניח לרגע שבהגדרת השפה כתוב בכל מקום <= במקום < .

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

כדי לטפל בשפה שבה משתמשים ב-< ולא ב-<= צריך לסבך קצת: האוטומט יכניס קודם שתי אותיות A עבור כל אות a שנקראת, ובאיזשהו שלב באופן לא דטרמיניסטי יעבור להכנסת אות A אחת עבור כל אות a שנקראת.

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

כלומר, עבור ה-a הראשונה לא יכניס כלום, עבור השנייה יכניס שתיים (בגין הראשונה), עבור השלישית יכניס שתיים או אחת (עבור השנייה), וכך הלאה. כשנקראת ה-b הראשונה עליו להכניס אות A אחת עבור ה-a האחרונה, וגם להוציא אות A אחת, ולכן ישאיר את המחסנית ללא שינוי. עבור שאר אותיות b יוציא אות מהמחסנית עבור כל אות b שנקראת.

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

 

השתכנעתם? יש סיבה טובה לבקר בפורום של מודלים חישוביים?

זו רק דוגמה לפעילות התוססת בכל הפורומים.

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

נשמח גם לקבל הערות והצעות לשיפור הפורומים.

 

אתר המרכז הארצי

אתר הבטים

גליון יוני 2003

חזרה לתחילת העמוד