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 preliminärt av 19 föreläsningar och 9 övningar. Varje vecka förutom v.14 har vi 2 föreläsningar följd av en övning. Sista föreläsningen den 24/5 är en reserv tid, alt. ägnas åt repitition.
Föreläsningarna kommer inte att ges i hybrid form i år, m.a.o. man måste vara på plats.
Heltäckande föreläsningsanteckningar kommer också att läggas upp i Canvas. Anteckningar som först skrevs 2022 kommer att finnas med redan från början av kursen men kommer att justeras under kursens gång beroende på hur det fortskrider. I synnerhet blir det vissa justeringar till materialet om Del 2: detta material bantades något 2023 och jag förväntar mig ungefär samma innehåll i år.
Övningarna kommer inte heller att livestreamas. 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)
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, inkl. rekursion (ca 6 föreläsningar)
Del 2: Aritmetik och algebra (ca 6 föreläsningar, OBS! viss bantning jämfört med anteckningarna nedan, upplägget förväntas bli ungefär som i fjol)
Del 3: Grafteori (ca 7 föreläsningar)
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 man kan ha fördel av att läsa in själv (ej nödvändigt, men kanske fördelaktigt). Specifikt handlar det om följande kapitel:
Mängdlära: Kapitel 2
Logik och Boolesk algebra: Kapitel 7
Relationer och Funktioner: Kapitel 8
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 (Aritmetik och Algebra), 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 |
|---|---|---|
|
18/3, 13-15 20/3, 10-12, 25/3, 13-15
|
Vol. 1: 5, Vol. 2: 6.1 Gamla 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 |
|
26/3, 8-10 8/4, 13-15 10/4, 10-12 15/4, 13-14 |
Vol. 1: 5.4.1, Vol. 2: 4.2, 6.2, 6.3, 6.5, 6.6, 6.7, 7.3 Gamla 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. |
|
15/4, 14-15 17/4, 10-12 |
Vol. 1: 3 Gammal Video: Fö-7 (2nd half only) Text: Fö-7 |
Primtal. Aritmetikens fundamentalsats. Euklides algoritm och linjära Diofantiska ekvationer. |
|
22/4, 13-15 24/4, 10-12 29/4, 13-15 2/5, 15-17 |
Vol. 1: 3 Vol. 2: 2, 3.2 Gamla Videos: Fö-8, |
Modulär aritmetik. Kinesiska Restsatsen. Euler/Fermat satsen. Gruppteoretisk formulering, inkl. Lagranges sats. (ej gjort) RSA krypto.
Här är ett "direkt" bevis av Sats 11.7 som inte explicit hänvisar till Lagranges Sats. |
|
2/5, 15-17 (om vi hinner !) Vi hann inte, detta material UTGÅR ! |
Vol. 2: 5 Gamla Videos: Fö-13 (plus first half of Fö-14), Fö-14 (2nd half), Fö-15 Text: |
Permutationer. Gruppverkan på mängder och Burnsides Lemma. |
|
6/5, 13-15 7/5, 8-10 13/5, 13-15 15/5, 10-12 20/5, 13-14 |
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. |
|
20/5, 14-15 22/5, 10-12 |
Vol. 2: 8, 9 Text:
|
Matchningar och augmenting vägar. Halls äktenskapsats. Flöden i nätverk (Ford-Fulkerson algoritmen) |
| 24/5, 8-10 |
Vol. 2: 9.3 Gammal Video: Fö-21 Text: Fö-21 |
Stabila matchningar. Gale-Shapley algoritmen. |
| 31/5, 14-18 | Tentamen. Anmälan 26/2 - 12/5. Lokal meddelas senare. |
Rekommenderade övningssuppgifter från böckerna
| Block | Uppgifter |
| 1 |
Vol. 1, Kap. 5: 3, 4, 7, 10, 11, 13, 24, 32, 35, 36, 47, 50, 52, 55, 56, 57, 62, 64, 65, 73, 74, 76, 80, 83, 84, 85, 88, 89, 90. Vol. 2, Kap. 6: 1, 2, 3. |
| 2 |
Vol. 1, Kap. 5: 58, 60 (mer precis: uttrycka k^n i termer av Stirlingtal). Vol. 2, Kap. 4: 5ab, 6ab, 8, 37ab, 38. Vol. 2, Kap. 6: 4a, 11, 15, 18, 19, 20, 25a, 26 (se ovan), 28, 29, 32, 37. Vol. 2, Kap. 7: 48, 50, 51, 71, 72. |
| 3 | Vol. 1, Kap. 3: 5, 9, 10, 15, 16, 19, 22, 26, 51, 52, 54ab, 55av, 58, 60, 71 |
| 4 |
Vol. 1, Kap. 3: 30, 38, 42, 46, 49, 61, 63, 65, 75. Suppl4: 1-23. |
| 5 | Preliminärt ingenting, kan justeras ! |
| 6 |
Vol. 1, Kap. 6: 8, 11, 15, 16, 17, 29, 30, 31, 39, 41, 42, 44, 45, 46, 47, 48, 48, 50, 51, 63, 64, 68, 69, 98, 101, 103, 104, 105, 113, 114, 116, 119. Vol. 2, Kap. 4: inget. Vol. 2, Kap. 7: 1, 2, 6, 7, 10, 22, 25, 64, 67, 68, 71, 72, 74. |
| 7 |
Vol. 2, Kap. 8: 6, 8, 18, 19. Vol. 2; Kap. 9: 1, 2, 3, 4, 5, 6, 8, 9, 10, 24, 30, 33, 34. |
| 8 | Vol. 2, Kap. 9: 14, 15, 16, 18, 19, 36. |
Demonstrationsuppgifter
| Dag | Demouppgifter |
|---|---|
| 21/3, 13-15 | Demo1.pdf (med lösningar) |
|
27/3, 10-12 OBS! Flyttad till 28/3, 10-12, sal: MV:H12. |
Demo2.pdf (med lösningar) |
| 12/4, 10-12 | Demo3.pdf (med lösningar) |
| 18/4, 13-15 | Demo4.pdf (med lösningar) |
| 26/4, 8-10 | Demo5.pdf (med lösningar) |
| 3/5, 13-15 | Demo6.pdf (med lösningar) |
| 8/5, 10-12 | Demo7.pdf (med lösningar) Figures-D7 Figures-D7(S) |
| 17/5, 13-15 | Demo8.pdf Figures-D8 Figures-D8(S) |
| 23/5, 10-12 | Demo9.pdf Figures-D9 Figures-D9(S) |
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: Öppnar 27/3 kl 18.00, lämnas in senast 17/4 kl 23.59.
Uppgift 2: Läggs upp senast 19/4, lämnas in senast 3/5.
Uppgift 3: Läggs upp senast 10/5, lämnas in senast 24/5.