20476 מתמטיקה בדידה: תורת הקבוצות, קומבינטוריקה ותורת הגרפים

20476 מתמטיקה בדידה: תורת הקבוצות, קומבינטוריקה ותורת הגרפים‏1

4 נקודות זכות ברמה רגילה

שיוך: מדעים / מתמטיקה

ידע קודם מומלץ: הקורס אשנב למתמטיקה.

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

יועצים: פרופ' מרצל הרצוג, פרופ' עמירם יהודאי, ד"ר לאוניד גרינבלט, פרופ' יהודה רודיטי, ד"ר אלכס אוסוויאצוב, ד"ר ורדה ליברמן

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

נושאי הלימוד

• מבוא קצר ללוגיקה – פסוקים, קַשָרִים, לוחות אמת. משתנים, פרדיקטים, כמתים. זהויות שימושיות.

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

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

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

1 להשלכות על צבירת נ"ז בשל חפיפה עם קורס(‏ים‎)‏ אחר(‏ים‎)‏, ראו פירוט החפיפה.