MVE505 Diskret matematik

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.

OBS! Jag ska undersöka möjligheten till att flytta vissa pass så att (i) det blir färra 4-timmars pass (ii) ett par föreläsningar kan göras om till övningar.

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. Anteckningarna från förra året 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 juteringar till materialet om Del 2, som kommer att bantas något jämfört med förra året.

Ö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 från 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

20/3, 13-17

29/3, 13-15

Vol. 1: 5,

Vol. 2: 6.1

Gamla Videos: Fö-1, Fö-2

Text: Fö-1

Fö-2

 

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

 

30/3, 10-12

12/4, 13-15

13/4, 10-12

19/4, 10-12

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,

Fö-5, Figs5

Fö-6, Fig6

 

Rekursion. Linjära rekursionsformler.

Binomialsatsen för negativa heltalsexponenter.

Genererande funktioner. Catalantal.

Stirlingtal och heltalspartitioner.

20/4, 10-12

24/4, 13-14

Vol. 1: 3

Gammal Video: Fö-7 (2nd half only)

Text: Fö-7

Primtal. Aritmetikens fundamentalsats. Euklides algoritm och linjära Diofantiska ekvationer.

24/4, 14-15

26/4, 10-12

27/4, 13-15

3/5, 10-12

Vol. 1: 3

Vol. 2: 2, 3.2

Gamla Videos: Fö-8,

Fö-9, Fö-10, Fö-11, Fö-12

Text: Fö-8, Fig8; 

Fö-9,

Fö-10, Fö-11 

Fö-12 

Suppl4.pdf

Modulär aritmetik. Kinesiska Restsatsen. Euler/Fermat satsen. Gruppteoretisk formulering (inkl. Lagranges sats).

RSA krypto.

 

Här är ett "direkt" bevis av Sats 11.7 som inte explicit hänvisar till Lagranges Sats.

 

UTGÅR !

Vol. 2: 5

Gamla Videos: Fö-13 (plus first half of Fö-14), Fö-14 (2nd half),  Fö-15

Text:

Fö-13, Fö-14, Fö-15  Figs15

Permutationer.

Gruppverkan på mängder och Burnsides Lemma.

9/5, 15-17

10/5, 8-10

15/5, 13-15

17/5, 8-10

Vol. 1: 6

Vol. 2: 4.4, 7.1, 7.2, 7.4

Gamla Videos: Fö-16, Fö-17, Fö-18

Text:

Fö-16, Figs16

Fö-17, Fö-18

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.

22/5, 13-15

24/5, 8-10

Vol. 2: 8, 9

Gamla Videos: Fö-19, Fö-20

Text:

Fö-19, Fö-20

 

Matchningar och augmenting vägar.

Halls äktenskapsats.

Flöden i nätverk (Ford-Fulkerson algoritmen)

26/5, 8-10

Vol. 2: 9.3

Gammal Video: Fö-21

Text: Fö-21

Gale-Shapley paper

Stabila matchningar. Gale-Shapley algoritmen.
2/6, 14-18 Tentamen. Sista anmälan 10/5. Lokal meddelas senare.

 

Tillbaka till toppen

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 UTGÅR !
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
27/3 Demo1.pdf
31/3 Demo2.pdf
17/4 Demo3.pdf  
20/4 Demo4.pdf
27/4 Demo5.pdf   
4/5 Demo6.pdf    
11/5 Demo7.pdf   Figures-D7   Figures-D7(S)
17/5 Demo8.pdf   Figures-D8   Figures-D8(S)
25/5 Demo9.pdf   Figures-D9   Figures-D9(S)

 

Tillbaka till toppen

Datorlaborationer

Inga datorlaborationer i denna kurs

Referenslitteratur för Matlab:

  1. Material utvecklat av MV som ger en kortfattad introduktion till Matlab
  2. 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.
  3. Learning MATLAB, Tobin A. Driscoll. Ger en kortfattad introduktion till Matlab till den som redan kan programmera. Finns som e-bok på Chalmers bibliotek.
  4. 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.

 

Tillbaka till toppen

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: Läggs upp 31/3, lämnas in senast 18/4.

Uppgift 2: Läggs upp 21/4, lämnas in senast 3/5.

Uppgift 3: Läggs upp senast 5/5, lämnas in senast 19/5.

Tillbaka till toppen