יעילות – חלק א'

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

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

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

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

בעיות שזמן פתרונן לא סביר

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

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

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

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

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

להלן פתרון אפשרי, כאן צבענו בארבעה צבעים במקום חמישה
(למחשבה: האם ניתן לצבועה בשלושה צבעים בלבד? שניים אולי?)

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

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

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

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

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

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

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

המשך במאמר הבא…