Tillämpad Kombinatorik 5B1305

Skriv era synpunkter/utvärdering här!

Vi har gått genom följande moment: uppdateras ständigt

• D31 12/3 I boken: 2.2, 2.6, 3.1, 3.2, 3.3, 3.5, 3.7, 3.8, 3.11, 5.3(del). Induktion. Dubbelräkning. Binomialkoefficienter. Selektioner. Ekvivalensrelationer. Partitioner. Permutationer. Belltal. Stirlingtal av typ I och II.
• E36 15/3* I boken: 3.12 (Generering av kombinatoriska objekt). 3.13.26 (Cayley sats via Prüferkod). De olika beskrivnigar av Katalantal som jag gick genom finns tyvärr inte med i boken. Övningar: 3.13.3, 3.13.4, 3.13.9.
• Q14 16/3 I boken: 3.6 (Stirling formel, bevis av en enklare version mha integralmetoden). Övningar: 3.13.10, 3.13.21, 3.13.14, 3.13.15. 3.13.22, 3.13.27 (bara rekursionsformel), 3.13.16(a,b).
• D41 19/3* I boken: 4.1, 4.2, 4.3, 4.5 (Katalantal), 4.7 (Quicksort, början). Introduktion till genererande funktioner. Formella beräkningsregler för potensserier. Formler för Fibonacci och Katalantal. Linjära homogena rekursioner. Komplexitetsanalys av Quicksort.
• D41 20/3 I boken: 4.5 (Belltal), 4.7 (Quicksort, avslutning). Exponentiella genererande funktioner. Övningar 4.8.9 (i), 4.8.10. Övningar från Biggs 18.7.15, 18.7.16. Övriga övningar.
• Q14 22/3* I boken: 5.1, 5.2, 5.3, 5.4. PIE, generaliseringar. Stirlingtal och exponenter. Övningar 4.8.19, 5.6.6. Övningar från Biggs 18.7.9, 18.6.2. Övriga övningar.
• D41 26/3* I boken: Kapitel 15. Även Kapitlar 14 och 20 i Biggs är en bra referens. Gruppverkan, banor och stabilisatorer. Orbit-counting lemma med exempel. Cykelindex. Polya sats formulering.
• D41 27/3 I boken: Kapitel 15. Även Kapitlar 14 och 20 i Biggs är en bra referens. Cykelindex, bevis av Polya sats med exempel : räkna antalet av grafer (avslutning).
• D31 30/3 I boken: 11.1-11.8, 11.12 (bara definitionen). Grafer (repetition). Generalisering av Eulers sats (ej med i boken). Ore sats om Hamiltonska cykler (del [b] är ej med i boken). Hamiltonska cykler på kantmängder av kuber. Resande handelsman algoritmer: "Twice-round-the-tree" (fel x2) och Christofides (fel x1.5) (ej med i boken). Moore grafer (d=2, k=57, n=3250 är en hemuppgift).
• D41 2/4* I boken: 11.9, 11.10, 6.1, 6.2, 6.3. Flöden i nätverk. Integritetssatsen. Min Cut - Max Flow satsen. Mengersatsen. Hallsatsen. Latinska kvadrater. Königssatsen. Birkhoff-von Neumann satsen om dubbelstokastiska matriser med tillämpningar i optimering och sannolikhetslära (obs finns inte i boken).
• Q11 6/4 I boken: 18.1-18.5. Hörn- och kantfärgningar av grafer. Det kromatiska polynomet och olika sätt att beräkna det (delvis finns i boken). Brooks sats.
• PÅSKLOV
• Q11 4/5 I boken: 18.6, 18.7. Topologisk grafteori. Eulerssats (V-E+F=2). Formuleringar av Kuratowski sats, Robertson-Seymour sats, Ringel-Young sats. Formuleringen av Appel-Haken sats, även känd som 4-färgsatsen. Bevis för 5-färgsatsen.
• D41 7/5* Gale-Ryser satsen. Perfekta grafer. Övningar från Kapitlar 11 och 18, samt från Biggs.
• D31 10/5 I boken: Kapitel 17, samt 11.6. Felrättande koder.
• D31 11/5 I boken: Kapitlar 8 och 16. Designs.
• D41 14/5 I boken: Kapitel 12. Pomängder, lattice, matroider. Generalisering av PIE.
• D31 15/5 Övningar från Kapitlar 8,12,16,17.
• D31 18/5 Repetition. Frågor. Genomgång av gamla tentor.

Kursens mål

Kursens ansvarig

Kursen går under period 4, 2001 och vi träffades första gången på Måndag 12/3, kl. 15.15 i D31, då även kursens uppläggning diskuterades.

Kurslitteratur

OBS: Kursen avslutas med en hemtentamen. Den kommer att bestå av 6 problem, högst 5 poäng för varje problem (totalt högst 30 poäng). Betygsfördelningen kommer att vara 12 - 18 - 24 för 3 - 4 - 5. De 4 första problemen skall vara lättare än de 2 sista. Problem 6 skall vara svårast.

Klicka här för att ladda hem gamla tentor

TENTAN

OMTENTAN

Detaljschema

• Fördjupning av grundläggande enumeration; Stirlings formel;
• Enumeration under gruppverkan;
• Genererande funktioner och deras tillämpningar i komplexitetsanalys;
• Fördjupning av allmänn grafteori; Matchningsteori; Flöden i nätverk;
• Vissa aspekter av kodteori;
• Pomängder, Möbius inversion;
• Vissa aspekter av designteori.

OBS: BARA preliminär KURSPLAN