רשימת הקורסים: תואר ראשון ושני

גם אם יש לך כל הזמן שבעולם, לא כל דבר ניתן לביצוע! בקורס זה נוכיח למשל שבשום אופן לא ניתן לכתוב תוכנית מחשב שמבצעת את הדבר הבא: נותנים לה תוכנית מחשב A וקלט X עבור A, ועל התוכנית שלנו לומר אם ל- A המופעלת על הקלט X  יש "באג". נתחיל עם המודל הפשוט של "מכונת המונים". נופתע לגלות שאם משהו ניתן לחישוב (אפשרי לעשותו), אז אפשר לבצעו כבר ע"י מכונה שיודעת רק להוסיף או להוריד אחד ולעשות קפיצה מותנית (עבור למקום אחר בתוכנית, אם ערך מסוים שונה מאפס). תוך קידוד של תוכניות חישוב ע"י מספרים טבעיים (מספרי גדל), נגלה שיש דברים רבים שאין שום דרך לבצעם (לא רקורסיביים), ושיש דברים שניתנים לביצוע רק למחצה (נל"ר). נדון ב"בעיית העצירה", במניה של קבוצות הנל"ר, קיום נל"ר שאיננה רקורסיבית, משפט הפרמטר ומשפט רייס, ובתוצאות המקסימות של משפטים אלו. "מכונת טיורינג" היא המחשב התיאורטי שהגה אלן טיורינג (משוברי צופן האניגמה הגרמני) הרבה לפני שמישהו ראה מחשב בעולם. נוכיח שמה שניתן בכלל להיעשות, ניתן להיעשות במכונת טיורינג. נדון בשאלות: מה ניתן להיעשות בזמן מעשי, ולא רק באופן תיאורטי? והאם הכנסת אקראיות לעבודת מכונת טיורינג יכולה לעזור? לצערנו לשאלות אלו אין כרגע תשובה, וכנראה לא תהיה אף פעם. נדון במושגים: P, NP, Co-NP, NP שלמות, ונבין את משפט קוק. מסתבר שיש אלפי בעיות תמימות למראה שאילו היינו יודעים לעשות אפילו אחת מהן בזמן מעשי, היינו יכולים לעשות את כולן בזמן מעשי, בעיות אלו נקראות "NP-שלמות". לדוגמא: נתונים n מספרים  האם ניתן לחלקם לשתי קבוצות שסכומן שווה? נוכיח על בעיות רבות שהן כאלה, ונכיר "אלגוריתמי קירוב", כלומר דרכים לפתור אותן בכל זאת בזמן מעשי לפחות בחלק מהמקרים.