| |||||||||||||||||||||||||
![]() |
![]() |
||||||||||||||||||||||||
מתמטיקה בדידה
Discrete Mathematics |
0368-1118-04 | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
מדעים מדויקים | |||||||||||||||||||||||||
|
מתמטיקה בדידה
ספר לימוד לקורס: ארנון אברון "מבוא למתמטיקה בדידה"
ספרים נוספים בעברית: שי גירון ושוני דר "מתמטיקה בדידה"
נתי ליניאל ומיכל פרנס "מתמטיקה בדידה"
האוניברסיטה הפתוחה: "מתמטיקה דיסקרטית" (4 חלקים)
תוכנית הקורס:
חלק ראשון - מבוא ל"תרבות מתמטית"- לוגיקה ותורת הקבוצות
מושגים בלוגיקה
טענות ופסוקים; על הגישה הפורמלית; גרירה; שקילות; קוניונקציה ודיסיונקציה; שלילה; טאוטולוגיות; טבלאות אמת; משתנים ותבניות, הצבה וקשירה, משתנים קשורים ומשתנים חפשיים; כמתים; מנגנוני קשירה שונים; כלל אלפא; שלילה פורמלית.
מושגי יסוד בתורת הקבוצות
קבוצות ואברים; תת קבוצות; סימון קבוצות; הפרדוקס של ראסל; עקרונות לבניית קבוצות; הקבוצה הריקה; קבוצת החזקה; איחוד, חיתוך, משלים, הפרש ותכונותיהם; איחוד וחיתוך מוכללים
פונקציות ויחסים
זוגות סדורים; מכפלה קרטזית; יחסים; היחס ההפוך; הרכבת יחסים; יחס מלא ויחס חד ערכי
פונקציות: פונקציות ופונקציות חלקיות; סימון l; פעולת החזקה בין קבוצות; פונקציות הפיכות
יחסים בתוך קבוצה ומיונם: תכונות של יחסים; יחסי שקילות וחלוקות; יחסי סדר
עוצמות
עוצמה של קבוצה; המספרים הטבעיים; עוצמות אינסופיות; קבוצות בנות מניה ושימושיהן, אריתמטיקה של עוצמות; סדר העוצמות; משפט קנטור שרדר-ברנשטיין; קבוצות אינסופיות שאינן בנות מניה; משפט קנטור
חלק שני - מבוא לקומבינטוריקה
עקרונות קומבינטוריים כלליים
עקרונות החיבור והכפל; עקרון שובך היונים; תמורות וצירופים
קומבינטוריקה סופית בסיסית
תמורות עם או בלי חזרות; צרופים עם או בלי חזרות; הוכחות קומבינטוריות ; נוסחת הבינום; משולש פסקל; תכונות של המקדמים הבינומיים
עקרון ההכלה וההדחה
פיתוח הנוסחה; שימושים; אי-סדר מלא
פונקציות יוצרות
הגדרה; מציאת פונקציות יוצרות; מציאת סדרות נוצרות; אופרטור הסכימה; פונקציות יוצרות מעריכית; שימושים לבעיות קומבינטוריות
רקורסיה
סדרות המוגדרות ברקורסיה; סדרת פיבונצ'י; משוואות נסיגה; פתרון באמצעות פונקציות יוצרות רגילות; פתרון באמצעות הפולינום האופייני; משואות נסיגה לינאריות הומוגניות במקדמים קבועים
מבוא לתורת הגרפים
הגדרות ושמושים אלמנטריים; מסילות מעגלים וקשירות; עצים ונוסחת קיילי; נושאים נוספים ככל שיתאפשר.