5B1204 Diskret matematik 8p för D2, vt06 URL: http://www.math.kth.se/math/student/courses/5B1204/D/200506/ Kursansvarig: Svante Linusson, 08-790 9444, linusson@math.kth.se Kursstart: Onsdagen den 18 januari 2006 klockan 8.15 i sal E1.

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

Aktuell information

• Rättningen av omtenta del B den 23 augusti är klar. Av 21 skrivande fick 1 betyg 5, 1 betyg 4, 8 betyg 3 och 11 fick underkänt. De uppsatser som lämnades in 17 augusti är också rättade. Tentor och uppsatser finns att avhämta på expeditionen.
  
  
• Svar på tenta B den 23 augusti, som pdf.
  
  
• Rättningen av omtenta del A den 7 juni är klar. 13 blev underkända, 28 godkända. 15 fick betyg 3 (gräns 13p), 9 fick betyg 4 (gräns 17 p) och 4 fick betyg 5 (gräns 22p).
  
  
• Omtentan för tenta B blir den 23 augusti 14.00-19.00.
  
  
• Svar på tenta A den 7 juni, som pdf.
  
  
• Rättningen av Tenta B den 16 maj är klar. 29 blev underkända, 57 godkända. 20 fick betyg 3 (gräns 10p), 19 fick betyg 4 (gräns 14 p) och 18 fick betyg 5 (gräns 18p). De två (vars efternamn börjar på Sä resp. Sö) som fick 9 poäng ombeds kontakta mig för instruktioner om kompleteringsmöjlighet den 12 juni.
  
  
• Svar på tenta B den 16 maj, som pdf.
  
  
• Uppsatserna är färdigrättade. De rättade uppsatserna finns att hämta på expeditionen. De som inte har lämnat in sin uppsats ännu får en andra chans om de lämnar in den före 16.00 de 17 augusti. Skicka till mig per brev eller lämna i svarta lådan till vänster i mattes huvudentré.
  
  
• Stencilen om kryptografi och primalitet finns nu att ladda ner, se under kurslitteratur nedan.
  
  
• Det finns nu en lista med de satser vars bevis kan komma på Tenta B, se under Examination nedan.
  
  
• En fråga om referenser i uppsatsen: För några av uppgifterna har ni fått utdelat material. För några upppgifter är detta inte samma som den literatur som tipsas om på hemsidan. Om ni inte kan lista ut var stencilen kommer ifrån så accepterar jag en referens till "sid xx eller sats yy i det för uppgiften utdelade materialet".
  
  
• Efter inlämningen av uppsatsen skall man också skicka in sitt elektroniska orginal, se under Uppsats
  
  
• Lappskrivning 4 är enda lappskrivningen inför Tenta B. Godkänt på lappskrivning 4 ger 2 bonuspoäng på Tenta B.
  
  
• Rättningen av Tenta A den 29 mars är klar. 69 blev underkända, 58 godkända. 22 fick betyg 3, 22 fick betyg 4 och 14 fick betyg 5. Gränsen för godkänt var 12 poäng, gränsen för betyg 4 var 16 poäng och för betyg 5 var gränsen 21 poäng. De som fick 11 poäng ombeds kontakta mig snarast för instruktioner om kompleteringsmöjlighet.
  
  

Viktiga tider

• Lappskrivningar (se nedan under lappskrivningar):2/2, 23/2, 15/3, 20/4.
• Uppsatsen (se nedan under Uppsats) skall vara inlämnad i pappersversion senast 4 maj klockan 8.15. Även elektronisk version inskickad senast den 4 maj (midnatt). Andra dödlinjen för inlämnandet av uppsatser blir den 17 augusti klockan 16.00. Emaila även en elektronisk kopia. Skicka papperskopian med brev eller lämna i svarta lådan till vänster i mattes huvudentré i ett kuvert med mitt namn på.
• Tentamina (för information om salar och föranmälan se här :
• Ordinarie tenta A: onsdagen den 29 mars 2006 kl. 8.00-13.00.
• Kompleteringsmöjlighet preliminärt 25 april 10.15-15.00 Kan ändras beroende på antal som skall försöka kompletera.
• Omtenta A: onsdagen den 7 juni 2006 kl. 8.00-13.00,
• Ordinarie tenta B: tisdagen den 16 maj 2006, kl. 8.00-13.00.

Lärare m.fl.

Föreläsare:

Svante Linusson (linusson@math.kth.se), tel. 790 9444, rum 3437.

Ni är välkomna med frågor om kursen till mig. Helst i anslutning till föreläsningarna.
Jag har mottagning och svarar på frågor på mitt rum en gång i veckan. Vecka 5,6,13,14,16,17,18,19 är det tisdag 13.15-15.00. Vecka 4,7,10,12 är det fredag 13.15-15.00. Även torsdagen den 2 mars 10.15-12.00. Rummet ligger på avd. Matematisk Statistik.

Övningslärare:

Grupp 1: Jonas Bergström ( jonasb@math.kth.se), tel. 790 6645, rum 3524.
Grupp 2: Jonas Gustavsson ( jonasgu@math.kth.se), tel. 790 8457, rum 3750.
Grupp 3: Jonas Sjöstrand ( jonass@kth.se), tel. 790 6659, rum 3734.
Grupp 4: Johan Karlander ( johank@nada.kth.se), ntel. 790 6340, rum 1434 på NADA.

Kurssekreterare:

Rose-Marie Jansson (jansson@math.kth.se).

Kurssekreteraren kan besvara frågor om registrering, inrapportering av betyg och anmälan till tentor om PING krånglar.
Med frågor om kursens innehåll bör man vända sig till lärarna.

---

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! I denna kurs ingår kapitlen 4-8, kapitlen 10-13 (utom 11.6-7 och 13.4-5), kapitel 15, kapitel 17, avsnitt 19.2, kapitel 20, 21.1-4, kapitel 22, 23.1-4 och 24.1-4.

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

Fem kompleterande stenciler (Linjär rekursion, Planära grafer, Partitioner och träd, Kinesiska restsatsen, samt Kryptografi och primalitet) ingår i kursmaterialet. Stencilen om Partitioner och träd har utgått ur kursen. De läggs ut efterhand här.

• K. Eriksson: A summary of recursion solving techniques ps-fil pdf-fil
• Om plana och planära grafer 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
•  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å. Det finns 11 uppsatsämnen  att välja bland. 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 maj klockan 8.15, då en pappersversion skall ha kommit in. Antingen direkt till respektive övningslärare eller till mig. Elektroniskt insändande godtas alltså inte. Uppsatser som lämnas in efter detta kommer att bedömas först i samband med omtentan (se nedan under betygssättning).
För att uppsatsen skall bli bra är det viktigt att börja skriva på den i god tid. Alla skall också skicka in sin uppsats i elektronisk form senast den 4 maj (midnatt). Skicka till linusson@math.kth.se. Det kommer att användas för stickprovskontroller för att undvika plagiat. OBS: Det är pappersversionen som vi kommer att rätta. Inga ändringar kan göras till den elektroniska versionen och vi kommer inte att skriva ut någons elektroniska version.

---

Examination

Tentamen

Det kommer att vara två tentor, Tenta A om 4 poäng och Tenta B om 2 poäng.
Tenta A omfattar de delar av kursen som motsvarar föreläsning 1-20.
Tenta B omfattar de delar av kursen som motsvarar föreläsning 21-30.
Litteratur som svarar mot en viss föreläsning beskrivs nedan .
Inga hjälpmedel är tillåtna vid tentamen.

Årets tentor:
Tenta A
Övningstenta A,  ps-fil   pdf-fil,    lösningsförslag  ps-fil   pdf-fil
29 mars 2006, tentan  ps-fil   pdf-fil,    lösningsförslag  ps-fil   pdf-fil
7 juni 2006, tentan  ps-fil   pdf-fil,    lösningsförslag  ps-fil   pdf-fil

Tenta B
Övningstenta B,  ps-fil   pdf-fil,    lösningsförslag  ps-fil   pdf-fil
16 maj 2006, tentan  ps-fil   pdf-fil,    lösningsförslag  ps-fil   pdf-fil


Tidigare års tentor. (OBS: Det var då en 6-poängs tenta!)

Kompletering För de som var nära att klara tentan kommer det att finnas möjlighet till kompletering. Vad "nära" betyder kommer att stå på tentan.

Bevis på tentan

I diskret matematik är ofta själva bevismetoden som använts för att resonera sig fram till en sats lika viktig som satsen själv. Det har ni säkert märkt av de många bevisuppgifterna på föreläsningar och övningar. På tentamen kommer det att förekomma ett par rena bevisfrågor. För att underlätta för er har jag sammanställt en lista på satser där jag tycker att bevisen är intressanta och lagom svåra för att komma på tentan.
Observera att andra satser fortfarande är mycket viktiga och att det säkert kommer att komma uppgifter där man använder andra satser för att kunna lösa uppgiften.

Inför Tenta A gäller:
Sats 15.3 (även kallat handskakningslemmat)
Sats 15.5 (T3)
Sats 15.7 (i)
Följdsats 1 i planäritetsstencilen
Sats 17.4 (Halls sats)
Sats: Det finns oändligt många primtal, se Exempel på sid. 52 i boken.
Sats 5.3
Sats 10.5
Sats 11.1.1
Sats 11.3 (Binomialsatsen)
Sats 11.2
Sats 12.1
Sats 12.5
Sats 11.5.1
Sats 13.1

Inför Tenta B gäller:
Sats 20.3.2
Burnsides Lemma (Sats 21.4)
Faktorsatsen (sats 22.8.1)
Sats 24.1
Sats 1 i häfte om Kryptografi

Lappskrivningar

Vid fyra räknestugetillfällen (2/2, 23/2, 15/3, 20/4) ges korta (20 minuter) lappskrivningar med korta frågor av teoretisk art.
Ls1 omfattar föreläsning 1-5.
Ls2 omfattar föreläsning 6-10.
Ls3 omfattar föreläsning 11-16.
Ls4 omfattar föreläsning 21-24.

Godkänt resultat på lappskrivning 1, 2 och 3 ger (var för sig) en bonuspoäng på Tenta A. Godkänt på lappskrivning 4 ger 2 bonuspoäng på Tenta B. Bonusen gäller i båda fallen ordinarie tentan och första omtentan.

Uppsatsen

Uppsatsen (se ovan) bedöms med något av betygen tre, fyra och fem. Betyget 5 kan inte fås om uppsatsen lämnas in för sent (d.v.s. efter 4 maj 08.15). Uppsatsmomentet motsvarar 2 av kursens 8 poäng.

Betygssättning

Kursens slutbetyg fås som en sammanvägning av betygen på Tenta A, Tenta B och Uppsatsen som lika mycket värda. D.v.s. om A=Betyg Tenta A, B=Betyg Tebta B och C=Betyg Uppsats, så blir slutbetyget (A+B+C)/3. Enda undantaget är kombinationen A=5, B=4, C=4 som ger 5:a.

---

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

 

Övningar Fylls i varje vecka.
Nr	Tid	Uppgifter att välja bland
1	Fr 20/1 8-10	rek 4,5,6,8; Biggs 15.1:1,3,4; 15.2:1,3; 15.3:1,3,5
2	On 25/1 13-15	Biggs 15.4:1,3,4,5 (i vilka kuber kan musen sluta om han startar i ett hörn?); 15.5:1,3,4; 15.6:1,2; 15.7:1,3; 15.8:8,22; 17.1:2,3; Ge en tolkning av grannmatrisen upphöjt till ett heltal k
3	To 2/2 8-10	Ls 1 8.15-8.35; Biggs 17.2:1,2,4; 17.3:1,2; plan 1,2,3; Biggs 17.4:1,2; 17.5:1; 17.6:1,3,4
4	To 9/2 8-10	Biggs 17.7:1; 4.2:5; 4.6:4,5; 4.7:3; 7.3:4; 7.7:2; 8.3:1; 8.4:1,4(finn alla x,y); 8.6:3,5; 8.7:11,14
5	On 15/2 13-15	5.2:1,2; 5.3:1; 5.4:2,3; 5.5:4; 6.2:3; 6.4:2,3,5; 6.5:2,5; 10.1:1,2; 10.2:1,3; 10.4:2,3; 10.5:2,4
6	To 23/2 8-10	Ls 2 8.15-8.35; 10.6:1,2,3; 10.7:4,5,7,8; 11.1:3,4,6,7; 11.3:2,3; 12.3:1,2,5,6; 11.8:3
7	On 1/3 13-15	11.2:2,3; 11.4:1,2,5; 12.1:1,2; 12.2:1,2,5; 11.8:5,6,15 (skall stå "fel rock eller fel paraply")
8	Ti 7/3 13-15	12.4:1,2,3; 12.5:1,2,3,4,5; 12.6:1,3,4; 12.7:12,13,19
9	On 15/3 13-15	Ls 3 13.15-13.35; 10.3:2; 11.5:1,2,3,4; 13.1:1-3; 13.2:1,3; 13.3:1,4,5
10	Ti 21/3 13-15	kin 2,3; repetition
11	Må 3/4 15-17	20.1:1; 20.2:1,3; 20.3:1-3,5; 20.4:1,3; 20.5:1,2; 20.6:1,4; 20.7:1,4;
12	To 6/4 8-10	20.8:1,3,4; 20.9:1,2; 21.1:2,5; 21.2:2,4; 21.3:3; 21.4:1,2,3,4;
13	To 20/4 8-10	Ls 4 8.15-8.35; 22.1:2; 22.2:1,3; 22.3:2,3; 22.4:1,2,4; 22.5:1,3,4; 22.6:1,3;
14	To 27/4 8-10	22.7:6; 22.8:1; 22.9:1,4,5,16; 23.2:1,2 [bör stå: "finite field"]; 23.3:1; 23.4:1,3;
15	To 4/5 8-10	24.1:1,2; 24.2:1,3; 24.3:1,2,4; 24.4:1,2,4; krypto 1,3,5,7,8;

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.

---