טענת נכונות
טענת נכוֹנוּת היא משפט בקוד שאומר "זה חייב להיות נכון כאן". (מפרט = המסמך שאומר איך התוכנית אמורה לעבוד.) כותבים טענות אלה בתוך הקוד או כהערה. הן עוזרות לראות כשמשהו לא עובד כמו שצריך. כשהטענה שגויה, התוכנית יכולה לעצור ולהראות היכן הבעיה. בחלק מהשפות אפשר לכבות את הטענות כשהתוכנית מוכנה לשימוש. כ...
הקצאת זיכרון דינמית
הקצאה דינמית היא לתת לתוכנית מקום בזיכרון בזמן שהיא רצה. זיכרון זה נשמר עד שמחזירים אותו. אספן זבל (garbage collector) יכול להשיב זיכרון שלא משתמשים בו. השיטה טובה כי נותנת מקום רק כשצריך. לפעמים נוצרים חלקים קטנים של זיכרון שלא ניתן להשתמש בהם. זה נקרא פרגמנטציה. לעתים המערכת לא יכולה לתת עוד זי...
קבוצה בלתי תלויה (תורת הגרפים)
קבוצה בלתי תלויה היא קבוצה של נקודות (קודקודים) בגרף. נקודות בקבוצה כאלו לא מחוברות זו לזו. אם צובעים את הקודקודים כך ששכנים לא מקבלים את אותו צבע, כל צבע נותן קבוצה כזו. סימול נפוץ לגודל הגדול ביותר הוא α של הגרף. השאלה: האם יש קבוצה בלתי תלידה בגודל מסוים? זו שאלה קשה מאוד. ריצ'רד קארפ הראה שהי...
מיון בחירה
מיון בחירה הוא שיטה פשוטה לסדר רשימה. מיון השוואתי אומר שמשווים בין שני איברים כדי לסדר אותם. 1. מוצאים את הפריט הכי קטן ברשימה. 2. מחליפים אותו עם הפריט הראשון. 3. חוזרים על זה בשאר הרשימה. השיטה קלה להבין ולעשות. היא משתמשת מאוד מעט בזיכרון. השיטה איטית אם יש הרבה פריטים. ככל שיש יותר פריטים, ה...
ZPP
ZPP היא קבוצה של בעיות שמתקבלות על ידי אלגוריתם שאף פעם לא טועה. אלגוריתם הסתברותי עושה בחירות אקראיות, כמו הטלת מטבע. תוחלת זמן ריצה היא הזמן הממוצע שהאלגוריתם לוקח. בבעיות מסוימות יש פתרון מהיר שקובע תמיד את אותה תשובה. יש גם אלגוריתמים שמשתמשים באקראיות. חלקם יכולים לטעות לפעמים. ZPP שונה: הוא ת...
סיבוכיות
סיבוכיות היא מדד למספר המשאבים שמחשב צריך כדי לפתור בעיה. המשאבים העיקריים הם זמן (כמה זמן לוקח) וזיכרון (כמה מקום בתוכו). לפעמים בודקים גם כמה מחשבים קטנים עובדים ביחד. "בעיה" היא קבוצה של שאלות דומות. שאלה בודדת נקראת מופע. לדוגמה, בעיית הפירוק: למצוא את הגורמים של מספר. השאלה "למה 15 מתפרק?" היא...
האלגוריתם של פרים
האלגוריתם של פרים מוצא את הדרך הזולה לחבר כל הנקודות ברשת. רשת זו נקראת גרף; קשת היא הקו שמחבר נקודות. מתחילים מנקודה אחת שבוחרים. בכל פעם בוחרים את הקו הכי קצר שיוצא מהחיבור שכבר בנו. אסור לבחור קווים שגורמים למעגל. האלגוריתם חמדן אומר: כרגע בחר את האפשרות הכי טובה. משתמשים במבנה שנקרא ערימה כדי למ...
מיון מיזוג
מיון מיזוג הוא דרך למיין רשימה של דברים בסדר עולה. המציא את השיטה ג'ון פון נוימן ב-1945. מעבירים את הרשימה לחלקים קטנים עד שכל חלק יש בו פריט אחד. פריט אחד כבר ממויין. כדי לחבר שני חלקים ממוינים, בוחנים את הפריט הראשון בכל חלק. לוקחים את הפריט הקטן יותר ומכניסים אותו לרשימה החדשה. חוזרים כך עד ש...
אלגוריתם אקראי
אלגוריתם אקראי הוא תוכנה שמשתמשת במקריות. מקריות = משהו שקורה בלי דפוס, כמו הטלת מטבע. מחלקים את האלגוריתמים האקראיים לשתי קבוצות עיקריות. חוקרים שואלים אם אלגוריתמים אלה יכולים להיות מהירים יותר מאלגוריתמים רגילים. יש שתי קטגוריות חשובות: BPP ו‑P. BPP = בעיות שנפתרות מהר בעזרת מקריות. P = בעיות ש...
סיבוכיות זמן
סיבוכיות זמן אומרת כמה צעדים צריך אלגוריתם כשהקלט גדול יותר. לא מודדים בשניות, כי מחשבים שונים עושים צעדים אחרת. לכן מסתכלים על איך מספר הצעדים גדל. לוגריתמי (לוגריתם הוא פעולה שמקטינה גדילה) אומר שהמספר של הצעדים גדל לאט מאוד. דוגמה: חיפוש בחצי ברשימה מסודרת. זה מהיר. ליניארי אומר שהצעדים שווים ...