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. Alla övningspass sker på torsdagar 10-12.

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 och EE.

Heltäckande föreläsningsanteckningar kommer också att läggas upp i Canvas. Vanligtvis fastställs dessa efter respektive föreläsning, men det kan bli så att preliminära anteckningar ibland läggs upp innan.

Övningarna ämnas att ges endast på plats (ingen livestreaming). Detta kan ändras beroende på smittspridningsläget. 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.

Kursen kan delas upp grovt i fyra delar.

Del 1: (Enumerativ) kombinatorik (ca 5 föreläsningar)

Del 2: Talteori och gruppteori (ca 6 föreläsningar)

Del 3: Grafteori (ca 7 föreläsningar)

Del 4: Några särkilda ämnen (ca 3 föreläsningar)

OBS 1: Eftersom detta är första gången jag ger kursen är chansen stor att planen som skisskas ovan och nedan kommer visa sig vara för amibitiös och att vi blir tvungna att stryka vissa ämnen. Ni kommer således att hållas uppdaterade om vart vi ligger och om något ska strykas.

OBS 2: 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 3: 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.

OBS 4: 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 kommer jag att återvinna föreläsningsanteckningar 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. Men om man vill ha lite hum redan nu om vad som kommer, kan man kolla filerna med föreläsningsanteckningar på 2020-års upplaga av MMG610. Eftersom jag måste göra plats för Del 2, kommer naturligtvis en del av innehållet där att skäras bort för oss.

Avklarat material markeras i grönt.

 

Föreläsning	Avsnitt	Innehåll
18/1, 13-17	Vol 1: 5 Videos: Fö-1-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
20/1, 8-10 25/1, 13-17, 27/1, 8-10	Vol 2: 4.2, 6, 7.3 Videos: Fö-3, Fö-5, Fö-6 Första halvan av Fö-3 glömde jag spela in. Fö-4 spelades inte in pga teknikstrul. 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.
3/2, 8-11	Vol 1: 3 Video: Fö-7 Text: Fö-7	Primtal. Aritmetikens fundamentalsats. Euklides algoritm och linjära Diofantiska ekvationer.
3/2, 11-12 10/2, 8-10 15/2, 13-17 17/2, 8-9	Vol 1: 3 Vol 2: 2, 3.2 Videos: Fö-8, Fö-9  Fö-10, Fö-11 Fö-12 Första halvan av Fö-11 glömde jag spela in Text: Fö-8, Fig8;  Fö-9, Fö-10, Fö-11  Fö-12	Modulär aritmetik. Kinesiska Restsatsen. Euler/Fermat satsen. Gruppteoretisk formulering (inkl. Lagranges sats). RSA krypto.
17/2, 9-10 23/2, 13-17, 24/2, 8-9	Vol 2: 5 Videos: Fö-13-14, Fö-15 Text: Fö-13, Fö-14, Fö-15  Figs15	Permutationer. Burnsides Lemma.
24/2, 9-10 2/3, 13-17, 3/3, 8-10	Vol 1: 6 Vol 2: 4.4, 7.1, 7.2, 7.4 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.
8/3, 13-17	Vol 2: 8, 9 Videos: Jag glömde spela in 8/3 Text: Fö-19, Fö-20	Matchningar och augmenting vägar. Halls äktenskapsats. Kant-färgläggning (utgår pga tidsbrost !). Flöden i nätverk (Ford-Fulkerson algoritmen)
10/3, 8-10	Vol 2: 9.3 Video: Fö-21 Text: Fö-21 Gale-Shapley paper	Stabila matchningar. Gale-Shapley algoritmen.
Utgår ! Tid räcker ej	Egna anteckningar (ej i boken)	Den probabilistiska metoden: Ramseytal
Utgår ! Tid räcker ej	Vol 2: 10 (endast kombinatoriska spel) Egna anteckningar för Nash jämnvikt	Kombinatoriska spel Generella spel: Nash jämnvikt
15/3, 14-18		Tentamen. Sista anmälan 25/2. Lokal meddelas senare.

 

Tillbaka till toppen

Ö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
20/1	Demo1.pdf
27/1	Demo2.pdf
10/2	Demo3.pdf   FigD3
17/2	Demo4.pdf
3/3	Demo5.pdf     Figures-to-problems     Figures-to-solutions
10/3	Demo6.pdf     Figures-to-problems     Figure-to-solutions

 

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 under v.3, lämnas in under v.5 (mer precision tillkommer)

Uppgift 2: Läggs upp under v.5, lämnas in under v.8 (mer precision tillkommer)

Uppgift 3: Läggs upp under v.8, lämnas in under v.10 (mer precision tillkommer)

Tillbaka till toppen