Computer Science
|
0368.1118.10
|
Fall 2005 |
| Lectures |
Sunday 12:00-14:00, Shenkar 9 Monday 17:00-19:00, Dach 5 |
| Instructor |
Oded Regev | Schreiber 220 | 5379 | Office hours: Monday 19:00-20:00 or by appointment |
| Tutorials |
Wednesday 13:00-15:00 Orenstein 102 (Tamir) Wednesday 15:00-17:00 Dan David 106 (Tamir) Thursday 15:00-17:00 Schreiber 8 (Itai) Thursday 16:00-18:00 Dan David 202 (Dan) |
| Teaching Assistants |
Itai Leshem Tamir Tuller Dan Hefez |
| Textbooks |
Introduction to Discrete Math, A. Avron (available from Sifrut Zola
and online), Discrete Mathematics, S. Dar and S. Gueron (out of print), Discrete Mathematics, N. Linial and M. Parnas, Discrete Math for Computer Science Students, Bogart, Drysdale, and Stein, entire book from a Discrete Math course given in Dartmouth College. Lecture notes by László Lovász and Kati Vesztergombi |
| Other Resources |
Videos
of lectures by Prof. Tarsi Doron Chen's homepage with exams and excercises Previous exams (exams are free) |
| Work |
One homework per class, due at the start of next class. |
| Links |
Last year's course And the one before that Fibonacci numbers in nature Encyclopedia of integer sequences (try typing 1,1,2,3,5,8,13,21) A great collection of puzzles (some require things we learned; others are unrelated but still fun) |
| Date | Class Topic | Some Links |
| Oct 30 | הצרנה, פסוק, קשרים, שקילויות לוגיות, איך מוכיחים | On De Morgan and other mathematicians. |
| Oct 31 | קבוצת קשרים שלמה, כמתים, שקילויות לוגיות עם כמתים, שלילת פסוקים | On some mathematical symbols |
| Nov 6 | סימון יוטה, סימון קיים יחיד, על שימוש במשתנים, כלל אלפא, קבוצות,שייכות בקבוצות | |
| Nov 7 | הכלה בין בקבוצות, פרדוקס ראסל, פעולות על קבוצות | Berry's paradox |
| Nov 13 | תכונות בסיסיות של הפעולות | |
| Nov 14 | קבוצת החזקה, זוגות סדורים ומכפלה קרטזית, פונקציות, תחום, טווח | Power set axiom and others |
| Nov 20 | תמונה, סימון למדא | |
| Nov 21 | פונקציה כקבוצה,סימון יוטה, צמצום פונקציה, הרכבת פונקציות, חד חד ערכיות, על | How to prove a function is one-to-one and onto |
| Nov 27 | פונקציה הפיכה והפונקציה ההופכית | |
| Nov 28 | פונקציית קארי | |
| Dec 4 | יחסים, תכונות של יחסים | |
| Dec 5 | יחס סדר, יחס סדר מלא, יחס שקילות, מחלקות שקילות, קבוצת מנה | Hasse diagrams |
| Dec 11 | על חלוקות ויחסי שקילות, עוצמות | Cardinal numbers |
| Dec 12 | סופיות, אינסופיות, שיטת האלכסון | Hilbert's Hotel |
| Dec 18 | איפיון קבוצות אינסופיות, סדר על עוצמות | |
| Dec 19 | משפט קנטור ברנשטיין ועקרון הסנדוויץ, משפט קנטור, פעולות על עוצמות | Continuum hypothesis |
| Dec 25 | חוקי הפעולות ושימושים | |
| Dec 26 | קומבינטוריקה, בחירת אברים | Lecture notes by Rudich (look under Counting I/II/III) |
| Jan 1 | חנוכה | |
| Jan 2 | מקדמים בינומיים, מספרי קטלן | |
| Jan 8 | עקרון שובך היונים | Two examples |
| Jan 9 | עקרון ההכלה וההדחה | |
| Jan 15 | תמורות ללא נקודת שבת, נוסחאות נסיגה | Derangements, Fibonacci |
| Jan 16 | פתרון נוסחאות נסיגה הומוגניות ולא הומוגניות | Solving recurrence relations |
| Jan 22 | פונקציות יוצרות, פתרון נוסחאות נסיגה בעזרתן | |
| Jan 23 | תורת הגרפים, מסלולים וטיולים, קשירות | Graphs of the Internet and of protein interactions |
| Jan 29 | עצים ויערות, קצת על הלמה של שפרנר | Sperner's lemma |
| Jan 30 | נוסחת קיילי |
