יש לי שאלה...

[a s s i]

יש לי שאלה...

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

 

[DadleFish]

זה לא בדיוק ככה.

בעיית שיבוץ מערכת השעות היא אכן בעיית NP COMPLETE - אבל זה מתייחס לפתרון האופטימלי, שמשיג איזשהו ציון מקסימלי (למשל, עונה על כל האילוצים מבלי שיהיו שום חורים בלוח הזמנים וכו'). עכשיו, עזוב את התיאוריה ותתרכז בפרקטיקה. עובדה היא שכל מוסד לימודי באשר הוא מצליח למצוא פתרון שעונה על כל האילוצים. אולי זה לא הפתרון האופטימלי, אבל הוא עובד וזה מה שחשוב. מה האילוצים שיש לך? בדרך כלל מדובר ברשימת מורים, שצריכים להעביר כל אחד X שיעורים. אולי יש חדרים מסוימים וכו'. השיטה הכי פשוטה היא ללכת מהקל אל הכבד - לקחת את המקרים בהם יש לך את האילוצים הכי משמעותיים (דני, המורה לתנ"ך, חייב ללמד בכיתה 12, ויכול ללמד אך ורק ביום שני בין 8 לבין 10), ולשבץ אותם ראשונים. אח"כ לעבור הלאה על האילוצים וכו'. אתה יכול גם לעשות דברים מסוימים בצורה סטטית - למשל, ברוב בתי הספר לכל כיתה יש כיתה פיזית, והמורים נודדים ביניהן - שזו לא בעיה בכלל. ואז מה שנשאר לעשות הוא לשבץ את המורים לפי השעות לכל הכיתות. הבעיה הזו אינה פתירה באופן יעיל ברמה הגנרית-תיאורטית, אבל היא בהחלט פתירה כשיש לך מערכת אילוצים ידועה היטב, כשמספר הקלטים מוגבל, וכשאתה מחפש פתרון אחד שעובד - ולאו דווקא אופטימלי. אני חושב שתהיה לך התעסקות הרבה יותר גדולה ברמת ה-GUI של כל העסק. הייתי מצפה שתוכנה כזו תתמוך בכל הכנסת ועדכון המידע, בשאילתות שונות ומשונות, ועוד. כשמגיעים למערכת השעות עצמה הייתי מצפה מהתוכנה לאפשר להעביר בקלות מורה מסוים מכיתה מסוימת לכיתה אחרת, או שעה אחרת וכו'.

 

[a s s i]

תודה רבה.. אבל..

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

 

[vinney]

לא למדת איך לעשות את זה בבית ספר?

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

 

[a s s i]

חבל שאתה מגיב ככה..

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

 

[vinney]

אז באמת לא הבנתי, מצטער ../images/Emo13.gif

היה משתמע מההודעה שלך "בחרתי לעשות פרוייקט, אבל אין לי מושג איך עושים אותו"

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

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

 

[DadleFish]

כמה כיוונים.

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

 

[a s s i]

../images/Emo51.gif לשניכם

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

 

[DadleFish]

בהצלחה.

 

[vinney]

גם אם הפרוייקט לא כולל

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

 

[galh]

בעיה בלתי פתירה?

חבר שלי כתב בזמנו תוכנה שמארגנת מערכת שעות אישית לסטודנטים בטכניון. אנחנו מדברים על אותה "בעיית מערכת שעות" או לא? הפתרון היה שימוש ב- Back tracking (כמו פתרון חידת "שמונה המלכות").

 

[a s s i]

לא אותה בעיה ../images/Emo4.gif

הבעייה שאני מדבר עליה היא בניית מערכת שעות עבור ארגון מסויים (כמו למשל בי"ס) לא מערכת שעות לסטודנט.. אלה שתי בעיות שונות.

 

[DadleFish]

הבעיה הגנרית היא בעיית NPC.

בגדול, אתה אמור לנסות את כל האלטרנטיבות ולראות אלו מתוכן תקינות ואיזו מערכת היא המושלמת. נדמה לי שיש רדוקציה מהבעיה הזו לבעיית ה-Bin packing. ברור שיש בחוץ תוכנות שעושות את זה - אבל זה לא הפתרון האופטימלי מתימטית, וזה גם לא למידע גנרי, אלא יש מגבלות ידועות מראש. אגב, שמונה המלכות זה קל. בפתרון הנאיבי זה !N, שזה N בריבוע, ובפתרון המתוחכם זה N; פה לא מדובר בבעיה שאפשר לעשות לה BACK TRACKING.

 

[vinney]

אפשר הסבר על המשפט הזה

"בפתרון הנאיבי זה !N, שזה N בריבוע" בבקשה?

 

[BeyondTheWall]

סדר גודל ..

 

[DadleFish]

התלבלבתי כמובן

זה N מעל 2 (ולא N בחזקת 2) ולכן זה בערך N בחזקת 10. עדיין פולינומיאלי, בכל אופן.

 

[vinney]

הא....

במגבלת הקלט, ירד האסימון

 

[אופסשםמשתמש]

יש הגבלות סיבוכיות ?

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

 

[selalerer]

מסובך לא, מורכב כן.

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

 

[a s s i]

צודק לחלוטין..

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