ב-Online
 
 
 
 
 
 
 
לפרק את הבייט 
הפסיכומטריקן האוטומטי - חלק ב' 
 
לפרק את הבייט |
 

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

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

שלב ההגדרות

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

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

 
יחידת הנתונים הבסיסית - הנחה לוגית (צילומסך: עידו גנדל)
 יחידת הנתונים הבסיסית - הנחה לוגית (צילומסך: עידו גנדל) 
 

סוקרטס היה גאה בנו

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

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

זהירות, מלכודת

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

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

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

בשבוע הבא: רקורסיה

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

לכל טורי לפרק את הבייט
 
 
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
@@@@@@@@@@@@@@@@@@@ ilan @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 
 
תגובות
הוסף תגובה0 תגובות
הוספת תגובה
מאת
 
נושא
 
תוכן
 
 
 
 
תודה! תגובתך התקבלה.
התגובה תתפרסם בכפוף לתנאי האתר.
 
 
 
 
 

כל הזכויות שמורות 2011 © נענע 10 בע"מ
 
 
 
 
כל הזכויות שמורות © Nana10 בע"מ
Video powered by