SF1631 Diskret matematik 12hp för D3, ht11 URL: http://www.math.kth.se/math/GRU/2011.2012/SF1631/CDATE/ Kursansvarig: Bengt Ek, 08-790 6951, bek@math.kth.se Kursstart: Måndagen den 29 augusti 2011 klockan 15.15 i sal Q1.

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

Aktuell information

• Tentan onsdagen den 15 augusti
  Skrivningen och lösningsförslag finns här.
  Rättningen är nu klar. Resultaten kan (nu eller snart) nås via "Mina sidor" och skrivningarna finns på mattes elevexpedition.
  Skrivningen tycks ha varit svår och poängen var oväntat låga. Gränsen för betyg E sänktes till 18p och den för komplettering till 13p. De som fått Fx, skriv kursledaren för besked om hur, var och när komplettering (för den som önskar) kommer att gå till.
  
  
• Om tentan (TENB) den 8 juni
  Skrivningarna och lösningsförslag finns nu här nere.
  Rättningen är klar.
  Resultaten beräknas rapporteras in på måndag. De var inte bra, av 10 skrivande fick en D, en Fx och övriga F.
  Den som har Fx, kontakta kursledaren om eventuell komplettering.
  
  
• En tenta (TEN1) i augusti!
  Tvärtemot vad som tidigare meddelats den som frågat, kommer det i augusti ett tentatillfälle för dem som skall skriva TEN1, på hela kursen (dvs de som läste kursen för första gången ht11).
  Tid: on 15 augusti, 14.00-19.00. Glöm inte anmälan!
  Liksom tidigare TEN1-skrivningar under året kommer äldre också att kunna räkna denna tenta som TENA och TENB (endera eller båda).
  Den skrivningen som går fredag den 8 juni är dock bara för TENB.
  
  
• Om uppsatsrättningen
  Äntligen är alla inlämnade uppsatser bedömda och inrapporterade.
  Resultaten för alla uppsatser har nu rapporterats in i systemet. Om någon saknar sitt resultat kan det bero på att vi inte kunnat rapportera in det eftersom terminsregistrering saknas. Om du saknar ditt resultat, kontakta kurssekreteraren för att få veta om det gäller dig.
  
  
• Om (om)tentan lördag 18 februari
  Skrivningarna och lösningsförslag finns nu här nere.
  Rättningen är äntligen klar.Resultaten är eller kommer snart att vara inrapporterade.
  Tyvärr var resultatet inte bra.
  Skrivningarna finns på elevexpeditionen, Lindstedtsvägen 25.
  Den som fått resultat FX bör kontakta kursledaren och meddela om hon/han vill använda möjligheten till komplettering. Då fås också info om hur den kommer att gå till.
  
  
• Om (om)tentan lördag 28 januari
  Skrivningarna och lösningsförslag finns nu här nere.
  Rättningen är klar.Resultaten är eller kommer snart att vara inrapporterade.
  Tyvärr var resultatet inte bra.
  Skrivningarna finns på elevexpeditionen, Lindstedtsvägen 25.
  Den som fått resultat FX bör kontakta kursledaren och meddela om hon/han vill använda möjligheten till komplettering. Då fås också info om hur den kommer att gå till.
  
  
• Inlämnade uppsatser
  Tackar för alla uppsatser som kommit in, hela 94 stycken (ungefär?). Nu har ni gjort ert och det blir min tur att läsa.
  Bedömningen av uppsatserna kommer nog att ta ett tag. Jag går igenom dem ämnesvis med ordningen bestämd med lottning och rapporterar resultat lite efterhand. Meddelande kommer i denna spalt. (Inget kommer tyvärr att rapporteras in före nyår.)
  
  
• Vad är "vardagligt" i en diskretuppsats?
  Det har kommit frågor om vad som skall menas med ett "vardagligt problem" att behandla i uppsatsen.
  Med "vardagligt" menar vi här något som kan (tänkas) dyka upp i konkreta vardagliga situationer. Konkreta, så att inte alla problem i en mattebok är vardagliga problem, även om man kan syssla med matematik till vardags. För mer abstrakta problem kan det förstås vara möjligt att finna konkretare problem som kan formuleras så. I praktiken blir det ibland lite långsökta problem, men det får passera.
  Inte sällan är lösningen på ett (litet) vardagsproblem rätt uppenbar, men det kan ändå illustrera och klargöra hur man kan använda diskret matte för att lösa (större och) svårare problem av samma typ.
  Bäst är förstås om man finner ett problem som känns vardagligt, inte har en självklar lösning och passar bra att lösa med diskret matte.
  
  
• Om uppsatsen
  Förhoppningsvis går arbetet med uppsatsskrivandet framåt.
  Här nere finns nu som vägledning en beskrivning av kriterierna vid betygssättningen.
  
  
• Rättningen av tentan 20 oktober är klar
  Resultaten kan läsas via "Mina sidor".
  För två personer har inget kunnat rapporteras in, eftersom det inte varit möjligt att kursregistrera dem. De bör kontakta svl för kursval eller terminsregistrering och sedan meddela kurssekreteraren.
  Statistik (äldre sifferbetyg översatta till bokstäver): av 110 skrivande fick 2 betyg A (2%), 5 betyg B (5%), 15 betyg C (14%), 21 betyg D (19%) och 14 betyg E (13%). 14 fick FX (13%), dvs rätt att komplettera (se nedan), och 39 skrivningar (35%) blev tyvärr underkända.
  Skrivningarna finns på elevexpeditionen, Lindstedtsvägen 25.
  Den som fått resultat FX (eller K, vilket på "Mina sidor" syns som ett "U"!) bör kontakta kursledaren och meddela om hon/han vill använda möjligheten till komplettering. Då fås också info om hur den kommer att gå till.
  
  
• Kursenkät
  Nu finns en enkät om kursen att besvara.
  Gå bara in här, ange koden "diskDht11" (utan citattecken).
  Det är mycket viktigt för att vi skall kunna förbättra kursen till nästa år att så många som möjligt svarar (men inte mer än en gång per person, förstås).
  Snälla, gör det!
  
  
• Kursnämndsmöte den 30 september
  För ett bra tag sedan sammanträdde kursnämnden.
  Här finns ett protokoll från mötet.
  
  
• Tentan 20 oktober
  Skrivningen och lösningsförslag finns nu här nere.
  Meddelande kommer här när rättningen är klar.
  
  
• Gamla tentor
  Här nere finns nu en länk till fler gamla tentor.
  
  
• Uppsatsmaterial
  Material till uppsatserna delades ut på sista övningen.
  Du som inte fått material, men vet vad du vill skriva om, kontakta Bengt (eller ring).
  
  
• Lappskrivning 5, 11 oktober
  Skrivningen och lösningsförslag finns nu här.
  
  
• Inför uppsatsskrivningen under period 2
  Listor för val av uppsatsämne kommer att finnas vid föreläsning 26 (to 6 oktober) och övningarna 13 och 14 (fr 7 och ti 11 oktober).
  Att skriva upp sig innebär att man beställer ett exemplar av det material som finns för inläsning till det ämnet. Det kommer att gå att byta ämne senare.
  För dem som skrivit upp sig kommer materialet att finnas vid sista övningen (fr 14 oktober).
  
  
• Lappskrivning 4, 4 oktober
  Skrivningen och lösningsförslag finns nu här.
  
  
• Lappskrivning 3, 27 september
  Skrivningen och lösningsförslag finns nu här.
  
  
• Anmälan till tentan
  Om man skall skriva tentan den 20 oktober, måste man vara anmäld. Om man inte är det finns risken att man inte får skriva (om det inte finns plats) eller (troligare) att man får en timme kortare skrivtid!
  Anmälningstiden har gått ut.
  
  
• Lappskrivning 2, 20 september
  Skrivningen och lösningsförslag finns nu här.
  
  
• Lappskrivning 1
  Skrivningen och lösningsförslag finns nu här (ett "tryckfel" i lösningen till A1 rättat on 14 september).
  
  
• Om registreringen
  Den som föjer kursen skall vara registrerad för denna termin (annars kan man inte få betyg).
  Den registreringslista som funnits vid föreläsningarna har lämnats till kurssekreteraren.
  Den som skrivit på listan men inte hittar kursen i "Mina sidor" har förmodligen inte gått att registrera. Kontakta svl för kursval.
  Om man glömt skriva upp sig för registrering får man skriva kurssekreteraren, se här. Ange ditt namn, ditt pnr och kursens namn och nummer.
  
  
• Extraexemplen klara (preliminärt)!
  Listan med extraexempel har kompletterats. Den nya (7 sep) versionen finns här nere.
  
  
• Det finns nu en kursnämnd
  Första föreläsningen valdes Andreas Lindström och Alexander Solsmed in i kursnämnden.
  Dem kan man kontakta om man har synpunkter på kursen, se här nere.
  
  

Viktiga tider

• Lappskrivningar (se nedan under lappskrivningar):
tisdagarna 13, 20, 27 september och 4, 11 oktober kl. 10.15-10.40.

• Tentamina (för information om salar och föranmälan se här , anmälan "i god tid före tentamen", se "Mina sidor"):
ordinarie tentamen: torsdagen den 20 oktober 2011 kl. 8.00-13.00,
omtentamen: lördagen den 28 januari 2012 kl. 9.00-14.00,
omtentamen: onsdagen den 15 augusti 2012 kl. 14.00-19.00.
(Omtentamina enligt det gamla systemet med två tentor (för dem som läst kursen tidigare):
Tenta A: lördagen den 28 januari 2012 kl. 9.00-14.00,
tenta B: lördagen den 18 februari 2012 kl. 9.00-14.00,
tenta B: fredagen den 8 juni 2012 kl. 8.00-13.00.)
• Inlämning av uppsatsen (se nedan under uppsats)
Senaste tid för inlämning: under måndagen den 12 december (vilket innebär att den skall ha nått Bengt senast tisdagen den 13:e, klockan 8.00).

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.
För besök, ring eller mejla gärna innan för säkerhets skull.

Övningsledare:

Grupp 1: Thomas Westerbäck (thowest@math.kth.se), tel. 790 6509, rum 3747.
Grupp 2: Jan Kristoferson ( janke@kth.se), nås säkrast i samband med undervisningen.
Grupp 3: Sarah Alsaadi ( sarah.alsaadi@gmail.com), nås säkrast i samband med undervisningen.
Grupp 4: Lars Svensson (larses@math.kth.se), tel. 790 8052, rum 3649.

Kurssekreterare:

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

Kurssekreteraren kan besvara frågor om registrering, inrapportering av betyg och anmälan till tentor om det inte fungerar via "Mina sidor".
Med frågor om kursens innehåll bör man vända sig till lärarna.

Kursnämndsrepresentanter (utsågs på föreläsningen den 29 augusti):

Andreas Lindström (skriv honom),
Alexander Solsmed (skriv honom).

Till dem kan man framföra synpunkter på kursen och undervisningen (man kan förstås också själv tala med lärarna).
Kursnämnden planeras ha minst ett möte i samband med kursen.

Kursbeskrivning

Kursens betydelse

Denna kurs är obligatorisk för D3. Den diskreta matematiken (kombinatorik, grafteori, talteori, abstrakt algebra) har sedan mitten 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.

Kursens mål och innehåll

Förkunskaper

Kurslitteratur

Kursbok

Biggs, Norman L.: "Discrete Mathematics" (Second edition); Oxford University Press, 2002 (ISBN 9780198507178). (THS) En ganska tjock bok (drygt 400 sidor, men vi läser inte alls hela), men den är trevligt och klart skriven. Kom igång med läsningen så snart som möjligt! I denna kurs ingår avsnitt 4.5, kapitlen 5, 6, avsnitt 7.2-3, kapitel 8, kapitlen 10-13 (utom 11.6-7 och 13.4-5), kapitel 15, kapitel 17, avsnitt 19.2, kapitel 20, avsnitt 21.1-4, kapitel 22, avsnitten 23.1-4 och 24.1-4.

Övrigt kursmaterial

• K. Eriksson: A summary of recursion solving techniques 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) pdf-fil
• A. Björner: Kryptografi och primalitet pdf-fil
• Om planära grafer pdf-fil
• En lista med extra övningsexempel finns här pdf-fil (preliminärt klar)
• En lista med föreslagna uppsatsämnen. Se även nedan om uppsatsen.

Ö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

Arbetet med uppsatsen avses huvudsakligen utföras under period 2. Nedan beskrivs lite vad som förväntas av era uppsatser. Mer information gavs på föreläsningen den 23 september.

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å. 13 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.

Ni får själva välja språk, svenska eller engelska. Uppsatsen ska vara 2000-3000 ord och skrivas i Word, TEX eller motsvarande. 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?).
Vid betygsättningen av uppsatsen kommer vi att försöka följa samma kriterier som användes förra året.

Tidsgräns för inlämning av uppsatsen är måndagen den 12 december 2011. Då skall en pappersversion ha kommit in. Elektroniskt insändande godtas alltså inte.

Examination

Tentamen

Lappskrivningar

Uppsatsen

Betygssättning

Undervisning

Föreläsningar (preliminärt)
Nr	Tid	Lokal	Innehåll	Avsnitt i litteraturen	Samman- fattning
1	Må 29/8 15-17	Q1	Inledning. Rekursionsekvationer.	Rekursionsstencil, Biggs 4.5, 19.2	pdf-fil
2	On 31/8 15-17	D1	Mästarsatsen. Inledning grafer. Valens, isomorfi.	Rekursionsstencil, Biggs 15.1-3	pdf-fil
3	To 1/9 13-15	Q1	Eulerkretsar. Hamiltoncykler.	Biggs 15.4	pdf-fil
4	Fr 2/9 8-10	M1	Träd. Hörnfärgning. Bipartita grafer.	Biggs 15.5-7, 17.1	pdf-fil
5	Må 5/9 15-17	Q1	Planära grafer.	Planaritetsstencil	pdf-fil
6	Ti 6/9 8-10	D1	Kantfärgning. Latinska kvadrater. Alternerande stigar. Halls bröllopssats.	Biggs 17.2-4	pdf-fil
7	On 7/9 15-17	D1	Maximala matchningar. Transversaler.	Biggs 17.5-6	pdf-fil
8	To 8/9 13-15	Q1	Delbarhet, sgd. Euklides algoritm. Entydig faktorisering.	Biggs 8	pdf-fil
9	Må 12/9 15-17	F2	Modulär aritmetik.	Biggs 13.1-3	pdf-fil
10	Ti 13/9 8-10	D1	Kinesiska restsatsen. Ett gammalt tentatal (pdf-fil).	Kinesisk reststencil	pdf-fil
11	On 14/9 15-17	F1	Funktioner, räkning. Kardinalitet. Postfacksprincipen.	Biggs 5, 6	pdf-fil
12	To 15/9 13-15	Q1	Multiplikationsprincipen och binomialtal. Binomialsatsen.	Biggs 10.1-2, 10.4-5, 11.1	pdf-fil
13	Må 19/9 13-15	F1	Multinomialtal. Urval med upprepning.	Biggs 11.2-3, 12.3	pdf-fil
14	Ti 20/9 8-10	Q1	Principen om inklusion och exklusion (sållprincipen). Exempel kombinatorik-grafteori.	Biggs 11.4-5	pdf-fil
15	On 21/9 8-10	D1	Stirlingtal och ekvivalensrelationer.	Biggs 7.2-3, 12.1-3	pdf-fil
16	On 21/9 15-17	D1	Eulers funktion och Möbiusfunktionen.	Biggs 10.3, 11.5	pdf-fil
17	To 22/9 13-15	Q1	Permutationer. Ett ex. "permuterade skurkar" (pdf-fil).	Biggs 10.6	pdf-fil
18	Fr 23/9 8-10	D1	Mer om permutationer. Om uppsatsskrivning.	Biggs 12.4-6	pdf-fil
19	Må 26/9 15-17	F2	Grupper, ordning av element.	Biggs 20.1-4	pdf-fil
20	Ti 27/9 8-10	Q1	Cykliska grupper. Delgrupper.	Biggs 20.5-7	pdf-fil
21	On 28/9 15-17	F1	Lagranges sats. Exempel.	Biggs 20.8	pdf-fil
22	To 29/9 13-15	Q1	Mer om cykliska grupper mm.	Biggs 20.9	pdf-fil
23	Må 3/10 13-15	E1	Grupper som verkar på mängder. Burnsides lemma.	Biggs 21.1-4	pdf-fil
24	Ti 4/10 8-10	Q1	Ringar och kroppar.	Biggs 22.1-3	pdf-fil
25	On 5/10 15-17	D1	Polynomfaktorisering. Irreducibla polynom.	Biggs 22.4-8	pdf-fil
26	To 6/10 13-15	Q1	Ändliga kroppar.	Biggs 23.1-4	pdf-fil
27	Må 10/10 15-17	Q1	Mer om ändliga kroppar.	Biggs 23.1-4	pdf-fil
28	Ti 11/10 8-10	Q1	Felrättande koder.	Biggs 24.1-4	pdf-fil
29	On 12/10 15-17	F1	RSA-kryptering. Primalitetstest.	Kryptografistencil	pdf-fil
30	To 13/10 13-15	Q1	Repetition. Problemgenomgång.	Allt möjligt	pdf-fil

 

Övningar (preliminärt)
Nr	Tid	Salar	Uppgifter att välja bland ("rek", "plan", "kin" och "krypto" står för stencilerna om rekursion, planaritet, kinesiska restsatsen och kryptografi)
1	To 1/9 10-12	Q15,Q17, Q24,Q33	rek 4,5,6,8; Biggs 15.1:4; 15.2:1,2,3; 15.3:1,2,3,4,5; extra
2	Fr 2/9 10-12	Q11,Q13, Q31,Q33	Biggs 15.4:1,3,4,5 (i vilka kuber kan musen starta om han vill sluta i mitten?); 15.5:1,2,4; 15.6:1,2; 15.7:1,2,3; 15.8:8; extra
3	Ti 6/9 10-12	E31-34	plan 1,2,3; Biggs 17.1:2,3; 17.2:1,2,4; 17.4:1,2,3; extra
4	Fr 9/9 10-12	D35,D41, E31,E32	Biggs 17.5:1; 17.6:1,3,4; 17.7:1(,9); 8.4:1,2,4(finn alla x,y); 8.6:3,5; 8.7:5,14; extra
5	Ti 13/9 10-12	E31-34	Ls 1, 10.15-10.40, om grafer (Biggs 15 och 17; planaritetsstencilen) Biggs 13.1:1,2,3; 13.2:1,3,4; 13.3:1,4,5,7,8; kin 1,2,3; extra
6	Fr 16/9 10-12	Q11,Q13, Q15,Q17	Biggs 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,3; 10.1:1,2; 10.2:1,3; 10.4:2,3; 10.5:1,2,4; 11.1:3,4,5; extra
7	Ti 20/9 10-12	Q21,Q22, Q31,Q33	Ls 2, 10.15-10.40, om heltal mm (Biggs 5, 6, 8 och 13.1-3; kinesiska reststencilen) Biggs 11.1:6,7; 11.2:2,3; 11.3:2,3; 11.4:1,2,5; 11.8:3,5,6; 12.3:1,2,5,6; extra
8	To 22/9 10-12	Q21,Q22, Q24,Q26	Biggs 10.3:2; 10.7:4,5,7; 11.5:1,2,3,4; 12.1:1,2; extra
9	Fr 23/9 10-12	Q15,Q17, Q31,Q33	Biggs 10.6:1,2,3,4; 12.5:1,2,3,4; 12.6:1,2,3,4; 12.7:19; extra
10	Ti 27/9 10-12	Q15,Q17, Q21,Q22	Ls 3, 10.15-10.40, om kombinatorik (Biggs 7.2-3, 10, 11.1-5 och 12) Biggs 20.2:1,3,4; 20.3:1,2,3,5; 20.4:1,3; 20.5:1,4; 20.6:1,4; 20.7:1,2,3,4; extra
11	Fr 30/9 10-12	Q11,Q13, Q31,Q33	Biggs 20.8:1,2,3,4,5; 20.9:1,2,3; 20.10:5,13
12	Ti 4/10 10-12	L51,L52, Q15,Q17	Ls 4, 10.15-10.40, om grupper (Biggs 20) Biggs 21.1:2,5; 21.2:2,4; 21.3:3; 21.4:1,2,3,4; 22.1:2; 22.2:1,3; 22.3:2,3
13	Fr 7/10 10-12	Q22,Q26, Q31,Q33	Biggs 22.4:1,4; 22.5:1,2,3,4; 22.6:1,3; 22.7:6; 22.8:1,3; 22.9:1,4,5,16; 23.1:1,2,3,4; 23.2:1; 23.3:1; 23.4:1,2,3,4
14	Ti 11/10 10-12	Q11,Q13, Q15,Q17	Ls 5, 10.15-10.40, om gruppverkan, ringar, polynom, kroppar (Biggs 21.1-4, 22 och 23.1-4) Biggs 24.1:1,2; 24.2:1,2,3,4; 24.3:1,2,3; 24.4:1,2,3,4
15	Fr 14/10 10-12	Q21,Q22, Q31,Q33	krypto 1,3,5,7,8; Repetition