20276 מתמטיקה דיסקרטית
20276 מתמטיקה דיסקרטית1
6 נקודות זכות ברמה רגילה
שיוך: מדעים / מתמטיקה
ידע קודם מומלץ: הקורס אשנב למתמטיקה.
פיתוח הקורס: פרופ' אברהם גינזבורג (ראש הצוות), שמואל ברגר, ד"ר נור ארד (כתיבה), ענת לרנר, טלי צורף-עילם, יוסי קאופמן; אורה מאור, תלמה מוקדי (עריכה)
יועצים: פרופ' מרצל הרצוג, פרופ' שלמה וינר, פרופ' עמירם יהודאי, פרופ' אלי לוין, ד"ר לאוניד גרינבלט, ד"ר ורדה ליברמן
מטרת הקורס היא ללמד מושגים, תוצאות ודרכי עבודה בנושאים מתמטיים המהווים כלים חשובים לטיפול ביסודות התאורטיים של מדעי המחשב; לתרום לפיתוח התחכום המתמטי של הסטודנט.
תוכן ספרי הקורס
כרך I – תורת הקבוצות – קבוצה, איבר, שוויון קבוצות, פעולות בין קבוצות (איחוד, חיתוך, חיסור, משלים). עצמה. מכפלה קרטזית. רלציה. כפל רלציות. רלציה הפוכה. רלציות רפלקסיביות, סימטריות, טרנזיטיביות. שקילות. מחלקות שקילות. קבוצת המנה. פונקציות. פונקציות על, פונקציות חד-חד-ערכיות. תמורות. סדר חלקי. אינדוקציה. קבוצות בנות מנייה. עצמת הרצף. משפט שרדר-ברנשטיין. משפט קנטור.
כרך II– מבנים אלגבריים – פעולה בינארית. גרופואיד. אגודה. שאריות מודולו n (חיבור וכפל). קונגרואנציה. הומומורפיזם. איזומורפיזם. איבר יחידה. איבר הפכי. חבורה. חוג. שדה. שדות סופיים. סריגים. אלגברה בוליאנית.2
כרך III – לוגיקה – תורת הפסוקים: קשרים, טבלאות אמת, טאוטולוגיות, קבוצות קשרים מינימליות. שפת תחשיב הפסוקים וכללי התחביר. מערכות היסק. הוכחות פורמליות. מודל. חוסר סתירה, אי-תלות, שלמות. מושגים מתורת הפרדיקטים: מושג הכמת, פרדיקטים, תבניות. שפת תחשיב הפרדיקטים. אינטרפרטציות והשמות. תורת ההיסק בתחשיב הפרדיקטים.
כרך IV – קומבינטוריקה – עקרונות החיבור והכפל. תמורות, צירופים, חליפות בלי חזרות ועם חזרות. הבינום של ניוטון. זהויות במקדמים בינומיאליים. רקורסיה ואינדוקציה. עקרון ההכלה וההפרדה. פונקציית אוילר. אי-סדרים. חלוקות לתאים. עקרון שובך היונים. פונקציות יוצרות.
1החל מסמסטר ב2003 החליף קורס זה את הקורס מתמטיקה דיסקרטית (20276, 6 נ"ז). בקורס הנוכחי (שמספרו 20283) לא נלמד הנושא מבנים אלגבריים, שהיה כלול בקורס הקודם וזו הסיבה לשוני בהיקפם. סטודנטים שלמדו את הקורס הקודם (20276) ייחשבו כעומדים בדרישה של לימוד הקורס הנוכחי (20283) בכל תכנית לתואר שבה נדרש קורס זה.
להשלכות על צבירת נ"ז בשל חפיפה עם קורס(ים) אחר(ים), ראו טבלת קורסים חופפים.