Diskret Matematik E3 (TMA 055) - HT06



Kursutvärederingen kan fyllas i här när den blir tillgängligt




   Kontaktinformation

Kursansvarig :   Peter Hegarty, Rum MV:L3032, Tel.: x5371, hegarty@math.chalmers.se

Övningsledare :   Vilhelm Adolfsson, Rum MV:H4014, Tel.: x5307, vilhelm@math.chalmers.se

Studieförtroendeman :   Lukas Sandström, lukass@etek.chalmers.se, 0730-210811.


   Schema

Finns här


   Kurslitteratur

OBS! Det finns ingen obligatorisk kurslitteratur. Jag kommer att skriva mina egna sammanfattningar av föreläsningarna och dela ut stenciler med övningar, främst från RG (se nedan). Dessutom av erfarenhet så tillbringar de flesta en hel del tid på hemuppgifterna, som är mer krävande än typuppgifter så att man lär sig mycket från att göra dem. Vill man ändå ha en bok att arbeta utifrån så rekommenderas i första hand

(RG) Ralph P. Grimaldi, Discrete and Combinatorial Mathematics, 5th edition, Addison Wesley. ISBN : 0-321-21103-0.

Boken är inte på Cremona och du måste alltså ordna köpet själv. Är det många som vill köpa boken så kanske det går att fixa en gruppköp.

En alternativ text är

(NB) Norman L. Biggs, Discrete Mathematics, 2nd edition, Oxford. ISBN : 0-19-850718-6.

Jag kollade på Cremona idag (4/9) och det finns ett 30-tal överlämnade exemplar av boken där. NB är något mer kortfattat än RG men i slutet på varje kapitel så finns det "Miscellaneous exercises" som oftast är ganska utmanande. Det är något av en smaksak vilken typ av bok man föredrar, men personligen så tycker jag att materialet ordnas på ett mer logiskt sätt i RG.

Jag tar med båda böckerna till 1:a föreläsningen så att ni kan själva bladdra igenom dem.


   Kursinnehåll

Talen hänvisar till kapitlen i RG. Utöver listan nedan så kan det förekomma stoff som jag väljer själv och som kommer att skrivas upp i föreläsningsanteckningarna.

Mängdlära och relationer : 3,7.

Kombinatorik : 1,5,8.

Algebraisk kombinatorik : 9,10.

Talteori och kryptering : 4,14,16.1-16.4.

Grafteori : 11,12,13.

Boolesk algebra (bara om tiden räcker) : 15.

Ändliga kroppar och felrättande koder (bara om tiden räcker) : 16,17.


   Program

Undervisningen består av föreläsningar och övningar. Under föreläsningarna går vi igenom den matematiska teorin och under övningarna löser vi uppgifter med anknytning till denna. Ca en tredjedel av tiden på övningarna förväntas bli ägnat åt demonstrationsräkning då handledaren går igenom en uppgift vid tavlan. Resten av tiden lämnas till egen verksamhet. Många studenter väljer att använda denna tid delvis till att jobba på sina hemuppgifter.


   Schema för läsveckorna

Allteftersom kursen framskrider markeras avklarat material med grönt. Längre ner kommer man att finna veckoblad med mer detaljerad information om de olika läsveckorna, med bland annat rekommenderade övningar. Dessa veckoblad kommer att uppdateras ständigt under kursens gång : information om uppdateringar skickas ut via email.

OBS! Följande schema är både ungefärligt och preliminärt.

Vecka Stoff Avsnitt
1 Enumerativ kombinatorik : Multiplikationsprincipen och dess konsekvenser. Additionsprincipen. Lådprincipen. RG : 1.1-1.4, 5.5.

NB : 6.1-6.4, 10 (utom 10.3), 11.1-11.3, 12.3.

2 Enumerativ kombinatorik (forts.) : Inklusion-Exklusion. Diskret sannolikhetslära. Stirlingtalen av 2:a typen och Heltalspartitioner. RG : 1.5, 3.1-3.6, 5.3, 8.1, 8.3, 9.3 (delvis).

NB : 10.3, 11.4-11.5, 12.1, 12.4 (se också 26).

3 Algebraisk kombinatorik : Linear recurrence relations with constant coefficients.

Grafteori : Grundläggande definitioner, Eulercyklar.

RG : 10.1-10.3, 11.

NB : 19.1-19.2, 25.5-25.6, 15.

4 Grafteori (forts.) : Hamiltoncyklar, Färgläggning, Plan grafer, Träd och sortering. RG : 11, 12.1-12.3.

NB : 15, 16.1.

5 Grafteori (forts.) : MST (Kruskal/Prim alg.), Kortaste Väg (Dijkstra alg.), Maximalt flöde (Ford-Fulkerson alg.). Bipartite grafer och matchningar. RG : 13.

NB : 16.3-16.6, 17, 18.

6 Talteori : Relationer och modulär aritmetik. Gruppar, ringar och kroppar.

Euklides algoritm och linjära Diofantiska ekvationer. Aritmetikens Fundamentalsats. Fermat/Eulersatsen,

RG : 4, 5.1, 7.1, 7.3, 7.4, 14, 16.1-16.3.

NB : 8, 13.1-13.3, 20, 22.1-22.3.

7 RSA kryptosystemet (ej examinerbart !!).

Repetition.

RG : 16.4.
23/10 Tentamen  

OBS! : Om tiden räcker så kanske gör vi lite extra material. Möjligheter är (i) diskret Fouriertransformen (ii) probabilistiska metoder inom kombinatoriken (iii) felrättande koder (iv) Boolesk algebra.

OBS! Tiden kommer, som väntat, inte att räcka för sådant extra stoff.


   Vecka 1

5/9 Föreläsning RG : 1.1, 1.2, 1.3. NB : 10.4-10.6, 11.1.

Additions och multiplikationsprinciperna. Ordnade och oordnade val utan repitition (permutationer och kombinationer).

7/9 Lektion : Demonstrationsuppgifter hittas nedan. OBS! Avsnitt 5.5 ur RG, motsv. 6.2-6.4 i NB, (Dirichlet lådprincipen) görs i samband med dessa demonstrationer.

Följande övningar ur RG rekommenderas för självstudier :

1.1/1.2 : Borde räcka med att göra vart 4:e uppgift, t.ex. 1,5,9,13,...

1.3 : 1,3,5,7,9,11,13,15,19,21.

5.5 : 1,2,3,... until you get fed up.

8/9 Föreläsning RG : 1.3 (forts), 1.4. NB : 11.1-11.3.

Binomialsatsen. Binomial och multinomialkoefficienter. Oordnat val med repitition tillåten.

8/9 Lektion : Demonstrationsuppgifter hittas nedan.

Följande uppgifter ur RG rekommenderas för självstudier :

1.3 : 23,25,27,29,30.

1.4 : 1,3,5,7,9,10,13,14,23,25,27,28.


   Vecka 2

12/9 Föreläsning RG : 8.1, 8.3. NB : 10.3, 11.4-11.5.

Bollar och lådor I (omformulering av MP och oordnade val med repitition). Inklusion-Exklusion med tillämpningar : Derangements, Eulerfunktionen.

14/9 Lektion : Demonstrationsuppgifter hittas nedan. Följande övningar ur RP rekommenderas för självstudier :

8.1 : 4,5,6,9,10,13,15,21,23,24,29,30.

8.3 : 1,3,5,7,9,11,13.

15/9 Föreläsning RG : 3.1-3.6, 5.3, 9.3 (delvis). NB : 12.1, 12.4 (se också 26). OBS! Diskret sannolikhetslära finns inte alls med i Biggs.

Diskret sannolikhetslära. Bollar och lådor II : Stirlingtalen och Heltalspartitioner.

15/9 Lektion : Demonstrationsuppgifter hittas nedan. Följande övningar ur RG rekommenderas för självstudier :

3.1-3.6 : Inga övningar ska delas ut för detta material, eftersom det finns egentligen ingenting nytt här, bara omformuleringar av det som kommit innan i termer av sannolikheter.

5.3 : 4,6,8,10,11,13,15,17.


   Vecka 3

19/9 Föreläsning RG : 10.1-10.2. NB : 19.1-19.2.

Fibonaccitalen. Algebraiska metoder för linjära rekursionsformler med konstanta koefficienter : homogena fallet.

21/9 Lektion : Demonstrationsuppgifter hittas nedan. Följande uppgifter ur RG rekommenderas för självstudier :

10.1 : 2,5,7,10.

10.2 : 1,4,5,9,11,12,13,16,17,23,24,33.

22/9 Föreläsning RG : 10.3, 11.1, 11.3. NB : 25.5-25.6, 15.1, 15.3. OBS! Eulercyklar diskuteras knappt alls i Biggs.

Linjära rekursionfsformler med konstanta koefficienter : icke-homogena fallet. Introduktion till grafer : Königsbergproblemet och Eulercyklar.

22/9 Lektion : Demonstrationsuppgifter hittas nedan. Följande övningar ur RP rekommenderas för självstudier :

10.3 : 1,3,5,8,12.

11.1 : 5,6,8,10,12.


   Vecka 4

26/9 Föreläsning RG : 11.2-11.3, 11.5-11.6 (ej kromatiska polynom). NB : 15.2-15.4, 15.6-15.7.

Hamitloncyklar och TSP. NP-kompletta problem. Färgläggning av grafer. Den giriga färgläggningsalgoritmen.

28/9 Lektion : Demonstrationsuppgifter hittas nedan. Följande övningar ur RG rekommenderas för självstudier :

11.2 : 9,10,14.

11.3 : 1,3,5,6,13,18,19,20,21,22,26,30.

11.5 : 1,3,6,7,8,15,18,19,20.

11.6 : Most of the exercises are about chromatic polynomials, so forget about them. Instead do homework exercises and questions on old exam papers (of course, you'll need the graphs, though it is usually possible to reconstruct them from the solutions).

29/9 Föreläsning RG : 11.4, 12.1, 12.2. NB : 15.5, 16.1. OBS! Planar graphs are not mentioned at all in Biggs.

Plangrafer. Träd och tillämpningar : förgreningsprocesser och sorteringsproblem.

29/9 Lektion : Demonstrationsuppgifter hittas nedan. Följande övningar ur RG rekommenderas för självstudier :

11.4 : 2,8,14,15,17,18,21,22,23.

12.1 : 8,10,11,13,14,21.

12.2 : 1,13,18.


   Vecka 5

3/10 Föreläsning RG : 13.1-13.3. NB : 16.3, 16.6, 18. OBS! Ford-Fulkerson algoritmen blev framflyttad till lektionen på torsdag pga brandövningen.

Tre optimiseringsproblem i viktade grafer : (i) minimal spanning tree (MST), Kruskal och Prim algoritmerna. (ii) kortaste väg, Dijkstras algoritm. (iii) maximalt flöde i ett nätverk, Ford-Fulkerson algoritmen.

5/10 Lektion : : Demonstrationsuppgifter hittas nedan. Följande övningar ur RG rekommenderas för självstudier :

13.1 : 2.

13.2 : 1,4.

13.3 : 1,3,6,7.

OBS! Det finns många gamla tentamensuppgifter om detta material.

6/10 Föreläsning RG : 13.4. NB : 17.1-17.2, 17.4-17.5. OBS! Bigga does this material much better.

Bipartite grafer : "Augmenting path" algoritmer för kantfärgläggning och matchning. Halls Äktenskapsats.

6/10 Lektion Inga demonstrationsuppgifter idag. Följande övningar ur NB rekommenderas för självstudier :

Kap. 17 : 1.1, 1.2, 1.3, 2.1, 2.2, 2.3, 2.4, 2.5, 4.1, 4.2, 4.3, 5.1, 5.3. The miscellaneous exericses in Section 7 are in general significantly more challenging, and are optional.


   Vecka 6

10/10 Föreläsning RG : 14.1 - 14.3 (see also 5.1, 7.1, 7.3, 7.4). NB : 13.1 - 13.3 (see also Chs. 20,22,23).

Grupper, ringar och kroppar. Heltalen modulo n.

12/10 Lektion : Demonstrationsuppgifter hitta nedan. Följande övningar ur RG rekommenderas för självstudier :

14.3 : så många du orkar.

13/10 Föreläsning RG : 4.3 - 4.5, 16.3. NB : 8.1 - 8.6, 13.3.

Inverterbara element i Z_n : linjära Diofantiska ekvationer och Euklides algoritm. Primtal och Aritmetikens Fundamentalsats. Fermat/Eulersatsen och Lagranges sats för allmänna ändliga grupper.

13/10 Lektion : Demonstrationsuppgifter hittas nedan. Följande övningar ur RG rekommenderas för självstudier :

4.3 : 2,7,10,11,13.

4.4 : 1(b),6,8,10,13,17,19.

4.5 (optional !!) : 1(b),6,8,13,14,18,19,21,26,27.


   Vecka 7

17/10 Föreläsning RG : 16.4. OBS! Detta material finns ej i NB. Materialet är inte heller examinerbart.

RSA Public Key Cryptosystem.

19/10 och 20/10 Resterande tiden ägnås åt repitition.


   Föreläsningsanteckningar

Finns här (senast uppdaterad 14/10) ps pdf


   Demonstrationsuppgifter

Finns här (senast uppdaterad 12/10) ps pdf


   Gamla grejer (inkl. tentor)

Hemsidan för förra årets kurs finns här. Där finns bl.a. gamla tentor. Du kan också länka vidare till hemsidorna för tidigare år. Kursens upplägg och innehåll ändrades avsevärt från 2003 till 2004. Det är alltså materialet från 2004 och framåt som är mest relevant.


   Tentamina

Examinationen består av tre st hemuppgifter och en skriftlig tenta. Det hela omfattar 100 poäng av vilka 34 går till hemuppgifterna och 66 till tentan. För att bli godkänd på kursen krävs

(i) minst 26 poäng på tentan.

(ii) minst 50 poäng totalt.

Klarar man krav (ii) men inte krav (i) ska måste man göra en omtenta. Klarar man krav (i) men inte krav (ii) så får man också möjligheten att komplettera med extra hemuppgifter. Hur detta ska gå till berättar jag senare.

Hemuppgifterna är i allmänhet mer krävande än tentamensuppgifterna. Man får samarbeta med vem man vill men alla ska lämna in sina egna lösningar och dessutom skriva på 1:a bladet vem man har samarbetat med.

Hemuppgifterna läggs ut på denna sida i slutet på Veckor 1,3 och 5 och ska lämnas in senast på tisdagen i Vecka 3,5 resp. 7.


Tenta 23/10/06   PS    PDF och lösningar   PS    PDF Tenta 20/01/07   PS    PDF och lösningar   PS    PDF Tenta 21/08/07   PS    PDF och lösningar   PS    PDF


   Hemuppgifter

Uppgift 1 (att lämnas in senast 22/9, kl 1700) :   PS    PDF    Solutions :   PS    PDF Uppgift 2 (att lämnas in senast 9/10, kl 1700) :   PS    PDF    Solutions :   PS    PDF Uppgift 3 (att lämnas in senast 18/10) :   PS    PDF    Solutions :   PS    PDF

   Other supplementary stuff (entirely optional)

Lecture notes for a course in Probabilistic Combinatorics given at TU München, May 2006

PDF file


   Något om LaTeX

Anvisningar En svensk manual (LTH) Manualer LaTeX för Windows LaTeX hemsida

   Andra länkar

Intressant länk om bevisteknik (PDF) Att skriva matematik Sloane's On-Line Encyclopedia of Integer Sequences


Om du har kommentarer, påpekanden eller annat att säga om kursen, tryck   här

Peter Hegarty <hegarty@math.chalmers.se>
Last modified: Tue Oct 7 18:24:07 MET DST 2003