5B1204 Diskret matematik 8p för D2, vt05

URL: http://www.math.kth.se/math/student/courses/5B1204/D/200405/

Kursansvarig: Bengt Ek, 08-790 6951, bek@math.kth.se
Kursstart: Måndagen den 17 januari 2005 klockan 13.15 i sal D1.

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

Aktuell information

Tentan den 26 augusti
Skrivningen och ett lösningsförslag finns här nere.
Rättningen är nu klar och resultatet anslaget.
Statistik (korrigerad 16 sep sedan en borttappad tenta kommit till rätta):
Av 34 skrivande fick 2 (6%) betyg 4, 11 (32%) betyg 3 och övriga 21 (62%) blev inte godkända.
Skrivningarna finns på elevexpeditionen.
Kursutvärderingen
Kursutvärderingen är nu klar. Den kan hämtas som pdf-fil.
Tack Ingmar Bäckström och Henrik Ygge, som gjort utvärderingen!
Några uppsatsresultat till
Ytterligare resultat på uppsatser (inlämnade "28 mars") anslås idag, den 10 maj.
Tentan den 31 mars
Skrivningen och ett lösningsförslag finns nu här nere.
Rättningen är nu klar och resultatet finns anslaget. Skrivningarna finns på elevexpeditionen.
Tyvärr var resultatet inte alls bra.
Statistik: Av 66 skrivande fick 2 (3%) betyget fyra, 10 (15%) fick betyg 3 och hela 54 stycken (85%) blev underkända.
Uppsatserna, andra omgången (28 mars)
Tidsgränsen är passerad.
Uppsatserna, första omgången (4mars)
Resultaten finns nu anslagna och uppsatserna på elevexpeditionen.
Tentan den 9 mars
Skrivningen och ett lösningsförslag finns här nere.
Rättningen är nu klar. Resultatet finns anslaget och skrivningarna på elevexpeditionen.
Statistik: Av 116 skrivande fick 3 st (3%) betyg 5, 27 st (23%) betyg 4, 45 st (39%) betyg 3 och 41 st (35%) blev inte godkända.
Nu har vi kursutvärderare!
Ingmar Bäckström och Henrik Ygge har utsetts till kursutvärderare.
De avstår från foton på kurssidan, men kontakta dem om du har synpunkter på kursen (eller gå till läraren direkt).
Registrering
Listan har nu lämnats till kurssekreteraren.
Om du ännu inte registrerat dig, men skall följa kursen, skriv till henne.
Meddela dina namn, personnummer och program samt kursens nummer (5B1204) och namn.
Undervisningen är slut
(Länkar till) korta sammanfattningar av föreläsningarna finns här nere.

Viktiga tider

Lappskrivningar (se nedan under lappskrivningar):

Tentamina (för information om salar och föranmälan se här , anmälan senast två veckor före tentamensperiodens början):

Inlämning av uppsatsen (se nedan under uppsats)

Lärare m.fl.

Föreläsare:: Bengt Ek (bek@math.kth.se), tel. 790 6951, rum 3549.
Övningslärare:: Grupp 1: Jan Kristoferson ( janke@math.kth.se), tel. 790 7287, rum 3550.
Grupp 2: Jonas Bergström ( jonasb@math.kth.se), tel. 790 6645, rum 3524.
Grupp 3: Andreas Enblom ( enblom@math.kth.se), tel. 790 7208, rum 3752.
Grupp 4: Jonas Sjöstrand ( jonass@kth.se), tel. 790 6659, rum 3734.

Rum 3xyz ovan finns på plan x, Lindstedtsvägen 25 (dvs under klocktornet), där entréplanet räknas som plan 5.

Kurssekreterare:: Rose-Marie Jansson (jansson@math.kth.se).
Kursutvärderare:: Ingmar Bäckström (ingmarba@kth.se),
Henrik Ygge (ygge@kth.se).

Kursbeskrivning

Kursens mål och betydelse

Denna kurs är obligatorisk för D2. Den diskreta matematiken (kombinatorik, grafteori, talteori, abstrakt algebra) har under andra halvan av nittonhundratalet ökat explosionsartat i betydelse, både som forskningsområde och för tillämpningar inom framförallt datalogi men även inom fysik, kemi, bioteknik och ekonomisk modellering.

För att kunna förstå, analysera och konstruera algoritmer och datastrukturer är vissa kunskaper i diskret matematik nödvändiga. Dessutom ger diskret matematik tillfälle att öva tankens skärpa på ett kanske tillgängligare sätt än differentialkalkyl och geometri, samtidigt som den kan användas för att modellera många vardagsnära problem som kan vara både viktiga och underhållande.

Kursens mål är att ge kunskaper, insikter och färdigheter i diskret matematik som kan vara nyttiga för en datalog samt att träna förmågan att skriva om matematiskt stoff för icke-matematiker. Med "insikter och färdigheter" menas bland annat förståelse av begreppen, förmåga att göra korrekta matematiska resonemang och att kunna redogöra för dem muntligt och skriftligt.

Kursinnehåll

Bijektioner, injektioner, surjektioner. Principer för räkning. Pascals triangel. Linjär rekursion. Partitioner, ekvivalensrelationer. Modulär aritmetik. Kryptografi. Kinesiska restsatsen. Grafer. Grundläggande gruppteori. Ringar, kroppar, polynom. Ändliga kroppar. Felrättande koder. Fördjupning inom något område av grafteori.

Förkunskaper

5B1109 Linjär algebra II eller motsvarande.

Kurslitteratur

Kursbok

Biggs, Norman L.: "Discrete Mathematics" (Second edition); Oxford University Press, 2002 (ISBN 0-19-850717-8). (THS): En ganska tjock bok (drygt 400 sidor), men den är trevligt och klart skriven. Kom igång med läsningen så snart som möjligt!

Gamla upplagan av boken

Så här ser en äldre upplaga av boken ut.
Man kan nog klara sig med den, men det är förstås bättre med den nya. Det är i början av texten de stora skillnaderna finns.
Kapitel 1-9 i den nya upplagan är till största delen nya. Av dem motsvarar kap. 5 och 6 den gamla upplagans kap. 2, medan kapitel 8 motsvarar de gamla avsnitten 1.5-8. Kapitlen 4 och 7 ersätter de gamla avsnitten 1.1-4, men framställningen är förändrad, så man bör låna ett exemplar av den nya upplagan och läsa de kapitlen där.
För kapitel 10-27 i den nya upplagan gäller att kapitel n i stort sett exakt tycks överensstämma med kapitel n-7 i den gamla.

Övrigt kursmaterial

K. Eriksson: A summary of recursion solving techniques ps-fil pdf-fil
A. Björner: Kinesiska restsatsen och struktursatser (Avsnitt 3 ingår inte i denna kurs och i avsnitt 2 är delen "Tillämpad aspekt" på sidan 4-5 viktigast) ps-fil pdf-fil
A. Björner: Kryptografi och primalitet ps-fil pdf-fil
Om planära grafer ps-fil pdf-fil
Uppsatsämnen

Övrigt material

Korta sammanfattningar av föreläsningarna, motsvarande de OH-bilder som visas efterföljande gång, kommer det (förhoppningsvis) att finnas länkar till i föreläsningslistan.
Observera att bilderna är avsedda som stöd vid repetition, de garanteras inte täcka kursinnehållet och kan absolut inte ersätta annat kursmaterial.
Här finns lösningar till exemplen i Biggs bok.
Tänk på att det ger mest utbyte att läsa en färdig lösning om man först verkligen försökt själv!

Uppsats

I en uppsats ska ni träna er att skriva om matematik för icke-specialister.

Uppgiften består av tre delar. I inläsningsdelen skall ni läsa in er på något område med anslutning till kursen. I problemdelen skall ni formulera och lösa ett "vardagligt" problem som kan lösas med resultat inom det aktuella området. I redovisningsdelen skall ni formulera detta i en uppsats som riktar sig till läsare med kunskaper motsvarande era egna innan ni började läsa den här kursen.
Det är mycket svårare att skriva lättbegripligt än att beskriva någonting på ett tekniskt sätt och detta är därför nyttigt att träna på. Sjutton uppsatsämnen finns att välja bland. För flera av de föreslagna ämnena kommer det att finnas stenciler med material att läsa in. Mer om detta fjärde föreläsningen!

Ni får själva välja språk, svenska eller engelska. Uppsatsen ska vara 2000-3000 ord och skrivas i Word eller TEX. Uppgiften är individuell. Plagiat (av källtext eller av annan uppsats) betraktas som fusk.

Uppsatsen kommer att bedömas efter innehåll (är den presenterade matematiken korrekt, relevant för problemet, begripligt beskriven, är problemet vettigt och "lagom" för detta format?), form (är fördelningen mellan problempresentation och teori lagom, finns en lagom lång inledning och sammanfattning med slutsatser, en tydlig röd tråd?), stil och språklig korrekthet (rätt stilnivå, inte för lätt/svårt, stavning, meningsbyggnad, medryckande/tråkigt?).

En tidsgräns för inlämning av uppsatsen är satt till den 4 mars (24.00), då en pappersversion skall ha kommit in. Elektroniskt insändande godtas alltså inte. Uppsatser som lämnas in efter den 4 mars kommer att bedömas först i samband med nästa omtenta och bara att ge betyget tre kombinerad med ordinarie tentamen (se nedan under betygssättning).

Examination

Tentamen

Tentamen kommer att bestå av två delar: en teoridel (20 poäng) med fem uppgifter av resonerande karaktär som går att ersätta med godkända lappskrivningar, och en andra del (30 poäng) med fem problem av varierande svårighetsgrad. För godkänt betyg krävs 25 poäng. För betyg fyra krävs 33 poäng. För betyg fem krävs 42 poäng.
Inga hjälpmedel är tillåtna vid tentamen (detta till skillnad mot förra året, då BETA var tillåtet hjälpmedel).

Årets tentor:
9 mars 2005, tentan ps-fil   pdf-fil,    lösningar ps-fil   pdf-fil
31 mars 2005, tentan ps-fil   pdf-fil,    lösningar ps-fil   pdf-fil
26 augusti 2005, tentan ps-fil   pdf-fil,    lösningar ps-fil   pdf-fil

Förra årets (OBS! Kursen var då delvis annorlunda upplagd än i år):
10 mars 2004, tentan pdf-fil,    lösningar pdf-fil
14 april 2004, tentan pdf-fil,    lösningar pdf-fil

Förrförra årets:
7 mars 2003, tentan ps-fil   pdf-fil,    lösningar ps-fil   pdf-fil
23 april 2003, tentan ps-fil   pdf-fil,    lösningar ps-fil   pdf-fil
20 augusti 2003, tentan ps-fil   pdf-fil,    lösningar ps-fil   pdf-fil

Förrförrförra årets:
7 mars 2002, tentan ps-fil   pdf-fil,    lösningar ps-fil   pdf-fil
11 april 2002, tentan ps-fil   pdf-fil,    lösningar ps-fil   pdf-fil
14 augusti 2002, tentan ps-fil   pdf-fil,    lösningar ps-fil   pdf-fil

Lappskrivningar

Vid fem räknestugetillfällen (tisdagar 25 januari, 1, 15, 22 februari och 1 mars) ges korta (20 minuter) lappskrivningar med fem korta frågor av teoretisk art. De omfattar det stoff som behandlats t.o.m. veckan innan.
För godkänt på lappskrivningen krävs fyra uppgifter rätt. Godkänd lappskrivning 'i' ger 4 poäng på uppgift 'i' vid ordinarie tentamen och de två första omtentamenstillfällena fram till (men inte med) nästa ordinarie tentamen.

Årets lappskrivningar:
1A ps pdf 1B ps pdf
2A ps pdf 2B ps pdf (ett fel i uppgift 3 är rättat)
3A ps pdf 3B ps pdf
4A ps pdf 4B ps pdf
5A ps pdf 5B ps pdf

Förrförra årets:
1A ps pdf 1B ps pdf
2A ps pdf 2B ps pdf
3A ps pdf 3B ps pdf
4A ps pdf 4B ps pdf
5A ps pdf 5B ps pdf

Uppsatsen

Uppsatsen (se ovan) bedöms med något av betygen tre, fyra och fem. Uppsatsmomentet ger 2 av kursens 8 poäng.

Betygssättning

Kursens slutbetyg fås som medelvärdet (höjt om medelvärdet blir halvtaligt) av betygen på tentamen och uppsatsen, med ett undantag: betyg tre på tentamen och fyra på uppsatsen ger slutbetyget tre.
Uppsatser som lämnas in senare än bestämt datum knappt en vecka före en viss tentamen ger dock högst betyg tre då den räknas ihop med denna tentamen.

Undervisning

Undervisningen ges i form av föreläsningar och räkneövningar. På föreläsningarna varvas teori och illustrerande problemgenomgångar, medan övningarna ägnas problemlösning av lärare och/eller studenter.
På övningarna kommer också lappskrivningarna att ges.

Föreläsningar (preliminärt)
Nr	Tid	Lokal	Innehåll	Avsnitt i litteraturen	Samman- fattning
1	Må 17/1 13-15	D1	Inledning. Rekursionsekvationer.	Rekursionsstencil, Biggs 4.5, 19.2	ps-fil pdf-fil
2	Ti 18/1 10-12	D1	Inledning grafer. Valens, isomorfi.	Biggs 15.1-3	ps-fil pdf-fil
3	On 19/1 10-12	F1	Eulervägar, Hamiltoncykler. Träd.	Biggs 15.4-5	ps-fil pdf-fil
4	Fr 21/1 10-12	E1	Hörnfärgning. Bipartita grafer. Om uppsatsskrivning.	Biggs 15.6-7, 17.1	ps-fil pdf-fil
5	Må 24/1 13-15	D1	Kantfärgning. Latinska kvadrater. Planära grafer.	Biggs 17.2-3, Planaritetsstencil	ps-fil pdf-fil
6	Ti 25/1 10-12	D1	Matchning i bipartita grafer.	Biggs 17.4-6	ps-fil pdf-fil
7	On 26/1 10-12	F1	Inledande aritmetik. Naturliga tal, induktion. Heltal. Ekvivalensrelationer.	Biggs 4.1-3, 4.6-7, 7	ps-fil pdf-fil
8	Fr 28/1 10-12	E1	Delbarhet, största gemensam delare. Euklides algoritm. Entydig faktorisering.	Biggs 8	ps-fil pdf-fil
9	Må 31/1 13-15	D1	Funktioner, räkning. Postfacksprincipen.	Biggs 5, 6	ps-fil pdf-fil
10	Ti 1/2 10-12	D1	Grundläggande kombinatorik. Ord, urval.	Biggs 10.1-2, 10.4-5	ps-fil pdf-fil
11	On 2/2 10-12	F1	Permutationer.	Biggs 10.6	ps-fil pdf-fil
12	Fr 4/2 10-12	E1	Delmängder, binomialtal. Binomialsatsen. Multinomialtal.	Biggs 11.1, 11.3, 12.3	ps-fil pdf-fil
13	Må 7/2 13-15	D1	Oordnat urval med upprepning. (Ett ex. "permuterade skurkar" (pdf-fil).)	Biggs 11.2	ps-fil pdf-fil
14	Ti 8/2 10-12	D1	Sållprincipen. Partitioner och ekvivalensrelationer. Stirlingtal.	Biggs 11.4, 12.1-2	ps-fil pdf-fil
15	On 9/2 10-12	F1	Mer om Stirlingtal. Partitioner av naturliga tal.	Biggs 12.3-4	ps-fil pdf-fil
16	Fr 11/2 10-12	E1	Mer om permutationer.	Biggs 12.5-6	ps-fil pdf-fil
17	Må 14/2 13-15	F1	Eulers funktion och möbiusfunktionen.	Biggs 10.3, 11.5	ps-fil pdf-fil
18	Ti 15/2 10-12	D1	Modulär aritmetik.	Biggs 13.1-3	ps-fil pdf-fil
19	On 16/2 10-12	F1	Kinesiska restsatsen. ("Ex 8, 22 aug 2001" (pdf-fil).)	Kinesisk reststencil	ps-fil pdf-fil
20	Fr 18/2 10-12	E1	Grupper.	Biggs 20.1-3, 20.5	ps-fil pdf-fil
21	Må 21/2 13-15	D1	Gruppelements ordning. Cykliska grupper. Delgrupper.	Biggs 20.4, 20.6-7	ps-fil pdf-fil
22	Ti 22/2 10-12	D1	Lagranges sats. Mer om cykliska grupper.	Biggs 20.8-9	ps-fil pdf-fil
23	On 23/2 10-12	F1	Gruppers verkan på mängder. Burnsides lemma.	Biggs 21.1-4	ps-fil pdf-fil
24	To 24/2 10-12	D1	Ringar, kroppar.	Biggs 22.1-3	ps-fil pdf-fil
25	Fr 25/2 13-15	D1	Polynom, polynomdivision.	Biggs 22.4-6	ps-fil pdf-fil
26	Må 28/2 13-15	D1	Polynomfaktorisering, irreducibla polynom.	Biggs 22.7-8	ps-fil pdf-fil
27	Ti 1/3 13-15	D1	Ändliga kroppar.	Biggs 23.1-4	ps-fil pdf-fil
28	On 2/3 10-12	F1	Felrättande koder.	Biggs 24.1-4	ps-fil pdf-fil
29	To 3/3 10-12	D1	RSA-kryptering. Primalitetstest.	Kryptografistencil	ps-fil pdf-fil
30	Fr 4/3 10-12	E1	Repetition. Problemgenomgång.	Allt möjligt	ps-fil pdf-fil

Övningar (preliminärt)
Salar: Q25, Q31, Q32, Q33
Nr	Tid	Uppgifter att välja bland
1	Ti 18/1 13-15	rek 4,5,6,8; Biggs 15.1:1,3,4; 15.2:1,2; 15.3:1,3,5
2	Fr 21/1 13-15	Biggs 15.4:1,3,4,5 (i vilka kuber kan musen starta om han vill sluta i mitten?); 15.5:1,4; 15.6:1,2; 15.7:1,4; 17.1:2,3
3	Ti 25/1 13-15	Ls 1 13.15-13.35; Biggs 17.2:1,2,4; 17.3:1; plan 1,2; Biggs 17.4:1,2; 17.5:1
4	Fr 28/1 13-15	Biggs 17.6:1; 17.7:1(,9); 4.2:5; 4.6:4,5; 4.7:4; 7.3:4; 7.4:1; 7.5:3; 8.3:1; 8.4:1,4(finn alla x,y); 8.6:3,5
5	Ti 1/2 13-15	Ls 2 13.15-13.35; 5.2:2; 5.3:1; 5.4:4; 5.5:4; 6.4:2,3,5; 6.5:2; 10.1:1,2; 10.2:1; 10.4:3,4; 10.5:2,4
6	Fr 4/2 13-15	10.6:1,2,3; 10.7:5,7; 11.1:3,5,6; 11.3:2; 12.3:1,2,5,6; 11.8:3
7	Ti 8/2 13-15	11.2:2,3; 11.4:1,2; 12.1:1,2; 12.2:1,2,5; 11.8:5,6
8	Fr 11/2 13-15	12.4:1,2,3; 12.5:2,3,4,6; 12.6:1,4; 12.7:12,13
9	Ti 15/2 13-15	Ls 3 13.15-13.35; 10.3:1,2; 11.5:1,4; 13.1:1-3; 13.2:1,3; 13.3:1,4,5
10	Fr 18/2 13-15	kin 2,3; 20.1:1; 20.2:1,3; 20.3:1-3,5; 20.5:1,2
11	Ti 22/2 13-15	Ls 4 13.15-13.35; 20.4:1,3; 20.6:1,3; 20.7:1,3; 20.8:1,4,5
12	Fr 25/2 10-12	20.9:1,2; 21.1:5; 21.2:2,4; 21.3:3; 21.4:1,2; 22.1:2; 22.2:1,3; 22.3:2
13	Ti 1/3 10-12	Ls 5 10.15-10.35; 22.4:1,4; 22.5:1,3,4; 22.6:1; 22.7:6; 22.8:1; (22.9:16)
14	On 2/3 13-15	23.2:2 [bör stå: "finite field"]; 23.3:1; 23.4:1,3; 24.1:1,2; 24.2:1,3; 24.3:1,2; 24.4:1,2
15	Fr 4/3 13-15	krypto 1,3,5,7,8; 8.7:5,14; 10.7:13,14; 13.2:4; 17.7:13; 20.10:23

För hemarbete rekommenderas de uppgifter av ovanstående som inte hunnits med på övningarna, samt övriga exempel från relevanta avsnitt i Biggs bok.