מתמטיקה בדידה 89195, פרופ'
מרגוליס ופרופ' שיף
ספר מומלץ לקורס: "מתמטיקה בדידה" מאת נתי לניאל ומיכל פרנס
סילבוס (עם ציונים לפרקים הרלוונטיים בספר)
1. תורת הקבוצות
(פרק 1). הגדרות בסיסיות בתורת הקבוצות, פעולות על הקבוצות, יחסים בינאריים, יחסי שקילות,
פונקציות, יחסי סדר חלקיים וליניאריים.
2. אנדוקצייה
ורקרסיות (פרקים 3 ו-6). אנדוקצייה מתמטית
והכללותיה, הגדרה רקורסיבית של קבוצות ושל פונקציות, רקורסיות (יחסי נסיגה). פתרון רקורסיות
לליניאריות הומוגניות ואי-הומוגניות. פונקציות יוצרות ויישומים.
1. קומבינטוריקה
(פרק 4). עקרונות ספירה ובעיות בסיסיות. מקדמים בינומיים. פתרון בעיות
קומבינטרויים דרך רקורסיות, עקרון שובך היונים וכלל הכללה-הדחה.
2. הסתברות (פרק
8). מרחב מדגם ומאורעות. הגדרה של הסתברות. הסתברות אחידה. הסתברות מותנית
ובלתי-תלות. משתנים מקריים דסקרטיים, תוחלת, שונות וסטיית תקן. ההתפלגות הבינומית.
3. קצב גידול של
פונקציות (פרק 7). הגדרות בסיסיות. גידול פולינומי ומעריכי (אקספוננציאלי).
קירובים לסכומים, מקדמים בינומיים, פתרונות רקורסיות וכו'.
89-195
Discrete Mathematics, Professor Margolis and Professor Schiff
Course book: Linial and
Parness, Discrete Mathematics (in Hebrew)
Syllabus (references are to Linial and Parness)
1. Set theory (Chapter
1). Basic definitions of set theory, operations on sets, binary relations,
equivalence relations, functions, partial and linear order relations.
2. Induction and recursion (Chapters 3 and 6). Mathematical induction and
generalizations, recursive definitions of sets and functions, recursion
relations. Solution of linear recursion relations (homogeneous and nonhomogeneous), generating functions and
applications.
3. Combinatorics (Chapter 4). Basic counting principles and problems. Binomial
coefficients.Solution of combinatorial problems using recursion relations, the
pigeonhole principle, the inclusion-exclusion principle.
4. Discrete probability
spaces (Chapter 8). Sample space and events, definition of probability. Uniform
probability. Conditional probability and independence. Discrete random
variables, expectation, variance and standard deviation. The binomial distribution.
5. Rates of growth of functions (Chapter 7). Basic definitions, polynomial and
exponential growth. Approximations of sums of series, binomial coefficients,
solutions of recursion relations etc.