MVE505 Diskret matematik
På denna sida finns programmet för kursen: föreläsningar, räkneövningar, datorlaborationer och duggor. Övriga uppgifter, såsom t.ex. kursmål, lärare, kurslitteratur och examination, finns i ett separat kurs-PM.
Program
Kursens schema finns i TimeEdit.
Kursen består av 21 föreläsningar och 7 övningar. Var 4:e pass blir ett övningspass.
Föreläsningarna ges i hybrid form. Dvs de livestreamas, spelas in och läggs upp i Canvas, men man kan också delta på plats. Alla ges i någon av salarna EA, EB och EE förutom ett tillfälle i MA (31/3).
Heltäckande föreläsningsanteckningar kommer också att läggas upp i Canvas. Dessa kommer att finnas med redan från början av kursen men kan komma att justeras under kursens gång beroende på hur det fortskrider.
Övningarna ämnas att ges endast på plats (ingen livestreaming). Det kommer att finnas tid på övningarna både för demonstrationsräkning på tavlan och eget arbete.
Föreläsningar (Kursöversikt och Detaljerat Innehåll)
Mötes-ID: 69551004389
Lösenord: 975196
Webb: https://chalmers.zoom.us/j/69551004389
Föreläsningsanteckningarna kommer att skrivas på engelska. Jag ämnar att föreläsa på svenska, men kan byta till engelska om folk föredrar.
Den tilltänkta kursen kan delas upp grovt i tre delar.
Del 1: (Enumerativ) kombinatorik (ca 6 föreläsningar)
Del 2: Talteori och gruppteori (ca 8 föreläsningar)
Del 3: Grafteori (ca 7 föreläsningar)
Om det går snabbare än vad jag räknar med, kan det komma några extra särksilda ämnen under de sista föreläsningarna. Se den detaljerade planeringen längre ner.
OBS 1: Vissa kapitel i Vol. 1 innehåller material som jag inte kommer att ta upp explicit men som jag betraktar som nödvändiga förkunskaper för denna kurs. Jag räknar m.a.o. med att ni är redan bekanta med motsvarande material och/eller kan lätt ta till er materialet själva via egen läsning. Specifikt handlar det om följande kapitel:
Mängdlära: Kapitel 2
Rekursion och Induktion: Kapitel 4
Logik och Boolesk algebra: Kapitel 7
Relationer och Funktioner: Kapitel 8
Dessutom ska man vara bekant med binära operationer. Dessa tas ej upp explicit i kursböckerna, men se här.
OBS 2: Jag har valt att lämna ut vissa delar av Vol. 2, vi har helt enkelt inte tid för allting. Specifikt kommer jag inte ta upp felrättande koder (3.1), och inte så mycket om algoritmer (4.1, 4.3, 4.4) förutom där dessa dyker upp i grafteori-delen av kursen. Spelteori (kap. 10) kommer vi troligen inte hinna med heller.
OBS 3: Det kommer att bli en hel del överlap mellan denna kurs och kursen MMG610 som jag har hållit för GU studenter de senaste åren. I synnerhet är föreläsningsanteckningarna delvis återvunna därifrån. Den stora skillnaden är Del 2 (Talteori och Gruppteori), dessa ämnen togs inte upp i GU-kursen ty GU-studenterna ser detta material i andra obligatoriska kurser.
Avklarat material markeras i grönt.
| Föreläsning | Avsnitt | Innehåll |
|---|---|---|
| 21/3, 13-17 |
Vol 1: 5 Videos: Fö-1, Fö-2 Text: Fö-1
|
Grundläggande räkningsprinciper: additions- och multiplikationsprinciperna, permutationer och kombinationer, val med/utan återläggning/ordning, bollar och lådor Multinomialsatsen Inklusion-Exklusion principen Dirichlets lådprincip (pigeonhole principle), Erdös-Szekeres satsen |
|
28/3, 13-15 31/3, 8-12 4/4, 13-15 |
Vol 2: 4.2, 6, 7.3 Videos: Fö-3, Fö-4, Fö-5, Fö-6 Text: Fö-3, Fö-4,
|
Rekursion. Linjära rekursionsformler. Binomialsatsen för negativa heltalsexponenter. Genererande funktioner. Catalantal. Stirlingtal och heltalspartitioner. |
|
7/4, 8-11 |
Vol 1: 3 Video: Fö-7 (2nd half only) Text: Fö-7 |
Primtal. Aritmetikens fundamentalsats. Euklides algoritm och linjära Diofantiska ekvationer. |
|
7/4, 11-12 21/4, 8-10 25/4, 13-17 28/4, 8-9 |
Vol 1: 3 Vol 2: 2, 3.2 Videos: Fö-8, |
Modulär aritmetik. Kinesiska Restsatsen. Euler/Fermat satsen. Gruppteoretisk formulering (inkl. Lagranges sats). RSA krypto. |
|
28/4, 9-10 2/5, 13-17, 9/5, 13-16 |
Vol 2: 5 Videos: Fö-13 (plus first half of Fö-14), Fö-14 (2nd half), Fö-15 Text: |
Permutationer. Gruppverkan på mängder och Burnsides Lemma. |
|
9/5, 16-17 12/5, 8-12, 16/5, 13-15, 19/5, 8-9 |
Vol 1: 6 Vol 2: 4.4, 7.1, 7.2, 7.4 |
Introduktion till grafer. Degree equation. Euler- och Hamiltoncyklar. P-NP problemet. Plana grafer (Eulers sats) Färgläggning av grafer. Träd. Minimala spännande träd: Kruskal och Prim algoritmer. Cayleys sats. |
|
19/5, 9-12 |
Vol 2: 8, 9 Text:
|
Matchningar och augmenting vägar. Halls äktenskapsats. Kant-färgläggning (utgår !). Flöden i nätverk (Ford-Fulkerson algoritmen) |
| 23/5, 13-15 |
Vol 2: 9.3 Video: Fö-21 Text: Fö-21 |
Stabila matchningar. Gale-Shapley algoritmen. |
| Utgår ! |
Egna anteckningar (ej i boken) | Den probabilistiska metoden: Ramseytal |
|
Utgår ! |
Vol 2: 10 (endast kombinatoriska spel) Egna anteckningar för Nash jämnvikt |
Kombinatoriska spel Generella spel: Nash jämnvikt |
| 3/6, 14-18 | Tentamen. Sista anmälan 11/5. Lokal meddelas senare. |
Övningsuppgifter
Jag avstår just nu från att ge listor av rekommenderade uppgifter. Jag tycker ni kan helt enkelt räkna igenom uppgifterna i er egen takt i de kapitel som vi går igenom (enligt innehållet ovan). Dessutom kommer ni säkert att ägna en hel del tid på inlämningsuppgifterna.
| Dag | Demoppgifter |
|---|---|
| 28/3 | Demo1.pdf |
| 4/4 | Demo2.pdf |
| 21/4 | Demo3.pdf |
| 28/4 | Demo4.pdf Figure D4 |
| 12/5 and 16/5 | Demo5.pdf Figures-to-problems Figures-to-solutions |
| 23/5 | Demo6.pdf Figures-to-problems Figure-to-solutions |
Datorlaborationer
Inga datorlaborationer i denna kurs
Referenslitteratur för Matlab:
- Material utvecklat av MV som ger en kortfattad introduktion till Matlab
- Programmering med Matlab, Katarina Blom. Ger en introduktion till Matlab och lär ut grunderna i programmering med Matlab. Rekommenderas varmt för dig som är nybörjare både vad gäller programmering och Matlab.
- Learning MATLAB, Tobin A. Driscoll. Ger en kortfattad introduktion till Matlab till den som redan kan programmera. Finns som e-bok på Chalmers bibliotek.
- Physical Modeling in MATLAB 3/E, Allen B. Downey
Boken är gratis att ladda ner från nätet. Boken ger en introduktion för dig som inte programmerat förut. Den täcker grundläggande MATLAB-programmering med fokus på modellering och simulation av fysikaliska system.
Inlämningsuppgifter
Tre st, som läggs upp som Uppgifter. Kan lämnas in antingen för hand på en föreläsning eller i Canvas. Man kan jobba med andra men varje person måste skriva egna lösningar. Man ska indikera vilka andra personer man har samarbetat med på varje uppgift.
Inlämningsuppgifterna är frivilliga men ger bonuspoäng till tentan. Se avsnittet "Examination" för fler detaljer.
Uppgift 1: Lades upp 31/3, lämnas in senast 18/4.
Uppgift 2: Läggs upp senast 24/4, lämnas in senast 8/5 (mer precision tillkommer)
Uppgift 3: Läggs upp senast 13/5, lämnas in senast 27/5 (mer precision tillkommer)