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

URL: http://www.math.kth.se/~bek/diskret03.html

Institutionen för matematik
Kursansvarig: Bengt Ek, 08-790 6951, bek@math.kth.se
Kursstart: Tisdagen den 14 januari 2003 klockan 11.15 i sal M1.

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

Aktuell information

Viktiga tider

Lärare m.fl.

Föreläsare:
Bengt Ek (bek@math.kth.se), tel. 790 6951, rum 3549.
Kommentarer och frågor från kursdeltagare är välkomna vid föreläsningarna eller via elpost, telefon eller personligt besök.
Säkraste tider är måndagar kl. 11-12 och torsdagar kl. 10-11.
 
Övningslärare:
Grupp 1: Jan Kristoferson ( janke@math.kth.se), tel. 790 7287, rum 3550.
Grupp 2: Andreas Enblom ( enblom@math.kth.se), tel. 790 6582, rum 3651.
Grupp 3: Lars H. Halle ( halle@math.kth.se), tel. 790 6694, rum 3524.
Grupp 4: Jonas Bergström ( jonasb@math.kth.se), tel. 790 6645, rum 3524.
Rum 3xyz ovan finns på plan x, Lindstedtsvägen 25 (dvs under klocktornet), där entréplanet räknas som plan 5.
Kursutvärderare:
Alan Abdulrahman ( alan82@kth.se)
David Johansson ( d01david@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" (Revised edition); Oxford University Press, 1989 (ISBN 0-19-853427-2). (THS)
En ganska tjock bok (nästan 500 sidor), men den är trevligt och klart skriven. Kom igång med läsningen så snart som möjligt!

I denna kurs ingår kapitlen 1-6 (utom 4.6, 4.7, 6.4, 6.5), kapitel 8, kapitel 10, 12.2, kapitel 13, 14.1-14.4, kapitel 15, 16.1-16.4 och 17.1-17.4.
Det kommer en ny upplaga av boken, men eftersom det inte är klart om den finns till kursstarten kommer vi att använda ovanstående.

För dem som har den nya upplagan finns här en kort beskrivning av skillnaderna.
Kapitel 1-9 ä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. Kapitel 4 ersätter avsnitten 1.1-4, men eftersom framställningen är förändrad kan det vara vettigt att låna ett exemplar av den gamla och läsa 1.1-2 där (det är bara 6 sidor).
För kapitel 10-27 i den nya upplagan gäller att kapitel n i stort sett exakt överensstämmer med kapitel n-7 i den gamla.

Övrigt kursmaterial

Övrigt material

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 tredje 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 3 mars (24.00), då en pappersversion skall ha kommit in. Elektroniskt insändande godtas alltså inte. Uppsatser som lämnas in efter den 3 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.

Årets tentor:
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örra årets tentor:
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

Förrförra årets tentor:
9 mars 2001, tentan  ps-fil   pdf-fil,    lösningar  ps-fil   pdf-fil
25 april 2001, tentan  ps-fil   pdf-fil,    lösningar  ps-fil   pdf-fil
22 augusti 2001, tentan  ps-fil   pdf-fil,    lösningar  ps-fil   pdf-fil

Lappskrivningar

Vid fem räknestugetillfällen (tisdagar 28 januari till 25 februari) 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:
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

Fö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

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)
Tid Lokal Innehåll Avsnitt i litteraturen
 Ti 14/1 11-13 M1  Inledning. Rekursionsekvationer. Rekursionsstencil, Biggs 12.2
 To 16/1 12-15 F2  Inledning grafer, Eulervägar, Hamiltoncykler. Biggs 8.1-4
 Fr 17/1 10-12 D1  Om uppsatsskrivning. Träd. Hörnfärgning. Biggs 8.5-7
 Må 20/1 13-16 D1  Bipartita grafer. Kantfärgning.  Biggs 10.1-3
 Ti 21/1 10-12 Q1  Matchning i bipartita grafer.  Biggs 10.4-6
 To 23/1 12-15 F2  Inledande aritmetik. Delbarhet, största gemensam delare.  Biggs 1.1-6
 Fr 24/1 10-12 D1  Euklides algoritm. Entydig faktorisering.  Biggs 1.7-8
 Må 27/1 13-16 D1  Funktioner, räkning. Postfacksprincipen.  Biggs 2
 Ti 28/1 10-12 Q1  Grundläggande kombinatorik. Ord, urval.  Biggs 3.1-2, 3.4-5
 To 30/1 12-15 F2  Permutationer.  Biggs 3.6
 Fr 31/1 10-12 D1  Delmängder, binomialtal. Binomialsatsen.  Biggs 4.1, 4.3
 Må 3/2 13-16 D1  Oordnat urval med upprepning. Sållprincipen.  Biggs 4.2, 4.4
 Ti 4/2 10-12 Q1  Partitioner. Ekvivalensrelationer.  Biggs 5.1-3
 To 6/2 12-15 F2  Partitioner av naturliga tal. Mer om permutationer.  Biggs 5.4-6
 Fr 7/2 10-12 D1  Eulers funktion och möbiusfunktionen.  Biggs 3.3, 4.5
 Må 10/2 13-16 D1  Modulär aritmetik.  Biggs 6.1-3
 Ti 11/2 10-12 Q1  Kinesiska restsatsen.  Kinesisk reststencil
 To 13/2 12-15 F2  Grupper.  Biggs 13.1-3, 13.5
 Fr 14/2 10-12 D1  Cykliska grupper. Delgrupper.  Biggs 13.4, 13.6-7
 Må 17/2 13-16 D1  Lagranges sats.  Biggs 13.8-9
 Ti 18/2 10-12 Q1  Gruppers verkan på mängder.  Biggs 14.1-4
 To 20/2 12-15 F2  Ringar, kroppar. Polynom, polynomdivision.  Biggs 15.1-6
 Fr 21/2 10-12 D1  Polynomfaktorisering, irreducibla polynom.  Biggs 15.7-8
 Må 24/2 13-16 D1  Ändliga kroppar.  Biggs 16.1-4
 Ti 25/2 10-12 Q1  Felrättande koder, början.  Biggs 17.1-2
 To 27/2 12-15 F2  Felrättande koder, avslutning. Kryptografi, början. Biggs 17.3-4, Kryptografistencil
 Fr 28/2 10-12 D1  Kryptografi, avslutning. Repetition. Kryptografistencil
 Må 3/3 13-16 D1  Repetition. Problemgenomgång, bl.a. 10.7:9, 13.10:23, 1.9:19 i Biggs. Allt möjligt
 Ti 4/3 10-12 F1  Repetition. Problemgenomgång, bl.a. 13.8:4,5, 13.10:10 i Biggs. Allt möjligt

 
Övningar (preliminärt)
Tid: 13-16
Salar:   Ti Q24,(grupp 2 lite olika),32,33    Fr Q33-36
Dag Uppgifter att välja bland
 Fr 17/1 rek 4,5,6,8; Biggs 8.1:3,4; 8.2:1,2; 8.3:1,3; 8.4:1,3,4,5 (i vilka kuber kan musen starta om han vill sluta i mitten?)
 Ti 21/1 8.5:1,4; 8.6:1,2; 8.7:4; 10.1:2,3; 10.2:1,4; 10.3:1; 10.4:1,2; 10.5:1; 10.6:1
 Ti 28/1 Ls 1; 1.5:2,3; 1.6:4; 1.7:1,5(finn alla x,y); 1.8:4,7; 2.1:1; 2.2:1; 2.3:3; 2.4:2,3; 2.5:4; 3.1:1,2; 3.2:1; 3.4:3,4; 3.5:2
 Ti 4/2 Ls 2; 3.6:1,2,3; 4.1:3,5,6; 4.3:2; 4.2:2; 4.4:1; 5.1:1,2; 5.2:1,2,6; 5.3:1,2,5,6
 Ti 11/2 Ls 3; 5.4:2; 5.5:2,4; 5.6:1,4; 3.3:1; 4.5:1; 6.1:1-3; 6.2:1,3; 6.3:1,4-5; kin 2,3
 Ti 18/2 Ls 4; 13.1:1; 13.2:1,3; 13.3:1,5; 13.4:1; 13.5:1; 13.6:1; 13.7:1,3; 13.8:1; 13.9:1,2; 14.1:5; 14.2:2,4; 14.3:3; 14.4:1,2
 Ti 25/2 Ls 5; 15.1:2; 15.2:1; 15.3:2; 15.4:1; 15.5:4; 15.6:1; 15.7:6; 15.8:1; 16.2:2 [bör stå: "finite field"]; 16.3:1; 16.4:1,3; 17.1:1,2; 17.2:1,3; 17.3:1,2; 17.4:1,2
 Ti 4/3 krypto 1,3,5,7,8; 1.9:3,7; 3.3:2; 4.2:3; 4.3:3; 5.5:6; 6.2:4; 6.3:6; 13.4:2; 13.7:4; 15.3:3; 15.5:2,3
För hemarbete rekommenderas de uppgifter av ovanstående som inte hunnits med på övningarna, samt övriga exempel från relevanta avsnitt i Biggs.