אלגוריתם חמדן
אלגוריתם חמדן זה דרך לפתור בעיות. אלגוריתם = סדרת חוקים לפתרון. חמדן = בוחר את מה שנראה הכי טוב עכשיו. זה בדרך כלל מהיר. לפעמים הוא נותן פתרון טוב. לפעמים לא. חמדנים עוזרים כשאין זמן לחשוב הרבה. יש בעיות שקשה מאוד לפתור מהר. לפעמים הבחירה החמדנית גם היא הכי טובה. - סוכן נוסע: כל פעם נוסעים ליישוב ...
בעיית כיסוי קבוצות
יש קבוצה של פריטים שנקראת U. יש גם אוסף של קבוצות קטנות שנקרא S. כל קבוצה ב־S מכילה חלק מהפריטים ב־U. כיסוי הוא בחירה של קבוצות מ־S כך שכל הפריטים ב־U יהיו כלולים לפחות בקבוצה אחת. נניח U = {1,2,3,4,5}. הקבוצות ב־S הן: {1,2,3}, {2,4}, {3,4} ו־{4,5}. אם בוחרים את {1,2,3} ואת {4,5}, אז כל המספרים מ...
חידת מסע הפרש
חידת מסע הפרש היא משחק על לוח שחמט. צריך להזיז את הפרש כך שיבקר בכל משבצת פעם אחת. הפרש קופץ בצורת האות L: שתי משבצות ישר ואז אחת לצד. יש שתי גרסאות: פתוח וסגור. מסלול סגור חוזר להתחלה. החידה ידועה כבר לפני יותר מאלף שנה. אנשים הודים וערבים כתבו עליה במאה ה-9 וה-10. גם במאות הבאות מדענים חשבו עליה....
שידוך (תורת הגרפים)
שידוך הוא בחירה של קווים (קשתות) בגרף כך ששום קו לא נוגע ביותר מצומת אחד. צומת = נקודה, קשת = קו שמחבר בין שתי נקודות. כל צומת שבשידוך מקבל בן זוג אחד בלבד. הגודל הוא מספר הקווים שבחרנו. שידוכים חשובים כי הם עוזרים לפתור בעיות של חיבור בין זוגות. יש שני רעיונות עיקריים: שידוך מקסימלי שאי אפשר להוסי...
עץ פורש מינימלי
עץ פורש מינימלי הוא דרך לחבר את כל הנקודות בגרף עם פחות עלות. גרף הוא קווים וצמתים. צומת זה נקודה; קשת זה קו שמחבר בין נקודות. משקל של קשת זה עלות או אורך שלה. חברת כבלים רוצה לחבר בתים. כל בית זה נקודה. כל כביש הוא קשת בעלות מסוימת. עץ פורש מקשר את כל הבתים בלי מעגלים. עץ פורש מינימלי מוצא את הקוו...
האלגוריתם של קרוסקל
קרוסקל היא שיטה למצוא חיבור זול בין כל הנקודות בגרף. הגרף מורכב מקודקודים (נקודות) וקשתות (קווים) עם משקלים. המטרה היא לבחור קווים שמחברים את כל הנקודות. הסכום של המשקלים צריך להיות הכי קטן. איך עושים את זה: 1. ממוינים את כל הקווים לפי משקל מהקטן לגדול. 2. לוקחים את הקו הכי קטן כשרק הוא לא יוצר מע...
קוד האפמן
קוד האפמן הוא דרך לקצר ולשמור מידע בלי לאבד אותו. הקוד נותן לסימנים (כמו אותיות) קודים באורכים שונים. סימנים נפוצים מקבלים קודים קצרים. הקוד הומצא על ידי דייוויד האפמן ב־1951 כשהיה סטודנט. הוא בנה עץ מהעלים אל השורש. כך קיבל קוד יעיל יותר מקוד קודם. בשיטות פשוטות כמו ASCII כל תו תופס אותו מספר סיב...