5B1305 Tillämpad kombinatorik 4p för D3, vt04
Institutionen för matematik	Kursansvarig: Johan Karlander, 08-790 9690, johank@nada.kth.se Kursstart: Måndagen den 15 mars 2004 klockan 15.15 i sal D35

Sidan revideras efter hand. Gå in då och då och se vad som har ändrats.

Aktuell information

Tentaanmälan: De som inte anmält sig till tentan via Ping-systemet och som vill anmäla sig skall kontakta mig.

En preliminär lista med redovisningstider finns nu:   Lista
Obs: Ingen vanlig föreläsning den 18 och den 19. Hemtalsredovisning istället!

04-01: En ny formulering av examinationen har gjorts.
Hemtal1 kommer att vara färdigställt den 2 april.

     04-02: Hemtal 1 finns nu. Skall vara inlämnat senast den 30 april.
 Några timmar senare har jag nu ändrat en formulering. Det skall vara triangulering av en konvex  med numrerade hörn.

05-02: Delar av Hemtal 2 finns nu.

05-05: Liten korrigering av första uppgiften på hemtal2 har gjorts.

05-06: Preliminära betygsgränser på hemtal.

05-07: Nya uppgifter på hemtal2.

05-10:  Ny hemtalsuppgift.
Schemaändring har gjorts. Två sista undervisningspassen ägnas åt hemtalsredovisningar.

05-11: Info om tentaanmälan. Se ovan.

05-13: De sista hemtalsuppgifterna har lagts ut.

05-17: Redovisningslista finns. (Se ovan.)

De första problemen i hemtal 2 finns nu. Fler problem kommer att delas ut.

 Hemtal 2 (ps)    Hemtal 2 (pdf)
 

Preliminärt gäller följande betygsgränser på hemtalen:
3:  15-19  4: 20-24  5: 25-30.

Lärare m.fl.

Föreläsare:

Johan Karlander (johank@nada.kth.se), tel. 790 9690.

 

 
 
 
 
 
 
 
 
 

---

Kursinnehåll

Kursen bygger vidare på kursen Diskret Matematik och ger en fördjupad insikt i kombinatoriska metoder. I kursen tar vi upp en del nya teoretiska begrepp men försöker visa på dessa begrepps relevans inom datalogi och matematisk problemlösning. Kursen inleds med en repetition och fördjupning av kunskaperna i grundläggande enumeration. Sedan görs en ingående studie av hur genererande funktioner kan användas för att räkna objekt. Tillämpningar på vissa speciella problem tas upp. Senare under kursen bygger vi vidare på dessa idéer och presenterar Polyas metod som ärr ett mycket sofistikerat verktyg i enumeration. Därefter följer en presentation av några nya begrepp: Enkel designteori och Ramseyteori. Vi kommer att se tillämpningar av dessa begrepp inom sannolikhetsteori. Vi tar upp ett fördjupat studium av grafteori. Framför allt kommer vi att studera graffärgning och planäritet. Kursen kommer också att innehålla en genomgång av viss teori om partialordningar. Alla dessa områden kommer i möjligaste mån beskrivas i anknytning till konkreta problem. 

---

Kurslitteratur

Kursbok

Cameron, Peter J. : "Combinatorics: Topics, Techniques, Algorithms" ; Cambridge University Press, 1994(ISBN 0 521 45761 0).  Övrigt kursmaterial Föreläsningsanteckningar kommer att delas ut under kursen.  Examination  Man kan bli examinerad på hemtal eller på tenta. Om man försöker båda kommer det bästa resultatet att räknas. Inlämningsuppgifter Kommer att delas ut i två omgångar. Den första delas ut vecka 14 och skall vara inlämnad vecka 18. Den andra delas ut vecka 18-20 och skall vara inlämnad senast vecka 21.  Man kan få maximalt 30 poäng på dem. Gränsen för godkänt vid examination på hemtal är 15 poäng. Hemtalen kommer att kombineras med ett muntligt förhör. Tentamen Tentamen är  den 24 maj. Man kommer att kunna få maximalt 30 poäng på tentan. Gränsen för godkänt är 15 poäng. Poäng från hemtalen kommer att få tillgodoräknas. Dock högst 8 poäng. Några extentor finns här:   www.math.kth.se/~hultman/5B1305.2002.2003.html Undervisning Undervisningen ges i form av föreläsningar. Några av dessa kommer att ägnas åt problemlösning och får då karaktär av räkneövning.     Föreläsningar (preliminärt) Tid Lokal Innehåll Avsnitt i litteraturen  M 15/3 15-17 D35  Introduktion, Grundläggande enumeration 3.1-3.6  O 17/3 8-10 D35  Grundläggande enumeration, forts. 3.7-3.10,3.12 F 19/3 10-12 E34 Sterlingtal, Belltal och liknande 3.11,5  M 22/3 15-17 D35 Genererande funktioner 4.1-4.4, Delar av 5  O 24/3 8-10 D35 Catalantal. Mer om gen funk 4.5-4.7  F 26/3 10-12 E34 Problemlösning Diverse uppgifter kap 3-5  M 29/3 15-17 D35 Sannolikhetstillämpningar av gen funk Föreläsningsanteckningar  O 31/3 8-10 D35 Sperners sats och Steinersystem 7.1,7.2,8.1,8.6  F 2/4 10-12 L43 Steinersystem forts. Designteori. 16.1-16.3. ev delar av 6  M26/415-17 D35 Ramseyteori 10  O 28/4 8-10 D35 Flöde och matchning 11.9,11.10  F 30/4 10-12 E34 Avancerad matchningar Föreläsningsanteckningar  M 3/5 15-17 D35 Problemlösning Uppgifter från 7,8,10,11 O 5/5 8-10 D35 Graffärgning 18.1-18.3 F 7/5 10-12 E32 Graffärgning forts. Planäritet. 18.5-18.7 M 10/5 15-17 D35 Partialordningar 12: framför allt 12.5,12.7 O 12/5 8-10 D35 Problemlösning Uppgifter från 12,18 F 14/5 10-12 E32 Polya-teori 15 M 17/5 15-17 D35 Polya-teori forts 15 T 18/5 8-10 D35 Hemtalsredovisning O 19/5 8-10 D35 Hemtalsredovisning

Föreläsningsanteckningar

 F1 (ps)     F1 (pdf)

F2 (ps)      F2 (pdf)

F3 (ps)      F3 (pdf)

F4  (ps)     F4 (pdf)

F5 (ps)      F5 (pdf)

F6 (ps)      F6 (pdf)

F7 (ps)   F7 (pdf)

 F8 (ps)   F8 (pdf)

F9  (ps)   F9 (pdf)

F10 (ps)  F10 (pdf)

F11  (ps)   F11 (pdf)

F12 (ps)  F12  (pdf)

F14  (ps)   F14 (pdf)

 F15 (ps)    F15 (pdf)

 F16 (ps)    F16 (pdf)

 F18 (ps)    F18 (pdf)

 F19 (ps)     F19 (pdf)