מתמטיקה דיסקרטית למדעי המחשב

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

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

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

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