SF1630 Diskret matematik 9hp för D3, ht12 URL: http://www.math.kth.se/math/GRU/2012.2013/SF1630/CDATE/ Kursansvarig: Bengt Ek, 08-790 6951, bek@math.kth.se Kursstart: Måndagen den 27 augusti 2012 klockan 15.15 i sal Q1.

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

Aktuell information

• Omtentorna, TENB och TEN1, fredag 31 maj
  Skrivningar och lösningsförslag finns nu här.
  Rättningen är äntligen klar, men resultatet inte bra.
  Av de 25 som skrev TENB blev en godkänd och 4 fick FX, övriga inte godkända (trots att gränsen sänktes).
  Av de 10 som skrev TEN1 blev ingen godkänd.
  Den godkände och alla FX:en har nu meddelats med elpost.
  
  
• Tentorna, TENA och TEN1, måndag 7 januari
  Skrivningar och lösningsförslag finns nu här.
  Rättningen är klar och resultaten kommer att rapporteras in under början av vecka 3. De var tyvärr inte alls bra.
  Ladok-systemet för resultatadministration är delvis nere under vecka 3 i samband med årsbokslutet. Det betyder att resultaten kommer att bli synliga via "Mina sidor" tidigast måndag 21 januari.
  
  
• Kursenkät
  Nu finns en enkät om kursen att besvara.
  Gå bara in här, ange koden "diskDht12" (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!
  
  
• Tentan, TENB, tisdag 11 december
  Skrivningen och lösningsförslag finns nu här.
  Rättningen är klar. Resultaten bör (snart) finnas att läsa via "Mina sidor" och skrivningarna finns på expeditionen (som dock är stängd för terminen).
  Påfallande var att resultatet på uppgifterna 2, 3 och 4 var dåligt. De uppgifterna var inte svåra, men kanske oväntade som typ.
  Efter övervägande har bestämts att poänggränserna sänks med 3p för alla betyg, dvs gränserna blev: A 29, B 24, C 19, D 15, E 12, Fx 10.
  Ungefärliga procenttal med olika resultat blev då A 1%, B 3%, C 10%, D 19%, E 18%, FX 9%, F 39%.
  
  
• Jaha, nu blir det i alla fall en TEN1 den 7 januari för SF1631 (förstagångsregistrerade förra året)!
  Det skall gå att anmäla sig till TEN1 den 7 januari (samtidigt som omtentan TENA) nu.
  Ursäkta de virriga beskeden, men det har jag själv fått besked om nyss. Om jag vetat kunde jag ha sluppit göra en sådan skrivning till 11 december...
  Hursomhelst, det blir en TEN1 den 7 januari, anmäl er som vanligt, ni som berörs!
  
  
• Lappskrivning 3B, fredag 23 november
  Skrivningen och lösningsförslag finns nu här.
  Rättningen är klar. Skrivningarna delas ut på övningen den 30 november och lämnas sedan till expeditionen.
  
  
• Lappskrivning 2B, fredag 16 november
  Skrivningen och lösningsförslag finns nu här.
  Rättningen är klar. Skrivningarna delas ut på övningen den 30 november och lämnas sedan till expeditionen.
  
  
• Anmälan till tentan
  Om man skall skriva tentan den 11 december, 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älan sker som vanligt via "Mina sidor" och senaste tid för anmälan är torsdagen den 22 november, klockan 24.00.
  Om det inte går att anmäla sig den vägen beror det troligen på att man inte är registrerad på kursen (och inte skrev tenta A). Det i sin tur beror sannolikt på att man antingen inte skrivit upp sig på listan för registrering (skriv i så fall kurssekreteraren för att bli registrerad) eller på att det inte varit möjligt att registrera eftersom kursval inte är gjort (kontakta svl och skriv kurssekreteraren när det är klart).
  
  
• Lappskrivning 1B, fredag 9 november
  Skrivningen och lösningsförslag finns nu här.
  Rättningen är klar. Skrivningarna delades ut på övningen den 16 november. De skrivningar som inte hämtades ut då finns (snart) på expeditionen.
  
  
• Tentan, TENA, torsdag 18 oktober
  Skrivningen och lösningsförslag finns nu här.
  Rättningen är klar. Resultaten bör (snart) finnas att läsa via "Mina sidor" och skrivningarna finns på expeditionen.
  Ungefärliga procenttal med olika resultat: A 3%, B 6%, C 13%, D 16%, E 20%, FX 16%, F 24%.
  
  
• Upphittat under tentan, TENA
  Under skrivningen (TENA) den 18 oktober hittades en mobiltelefon på toaletten vid salarna L51 och L52.
  Den som tror sig vara ägaren bör höra av sig till kursledaren.
  
  
• Lappskrivning 3A, måndag 8 oktober
  Skrivningen och lösningsförslag finns nu här.
  Rättningen är klar. Skrivningarna kommer att delas ut vid övningen onsdag 10 oktober (i samma grupp man skrev i), de som inte hämtas då lämnas till elevexpeditionen.
  
  
• Lappskrivning 2A, tisdag 2 oktober
  Skrivningen och lösningsförslag finns nu här.
  Rättningen är klar. Skrivningarna kommer att delas ut vid övningen onsdag 10 oktober (i samma grupp man skrev i), de som inte hämtas då lämnas till elevexpeditionen.
  
  
• Lappskrivning 1A, tisdag 18 september
  Skrivningen och lösningsförslag finns nu här.
  Rättningen är klar. Skrivningarna delades ut vid övningen onsdag 26 september, finns nu på elevexpeditionen.
  
  
• Anmälan till tentan den 18 oktober
  Anmälningstiden har gått ut.
  Om man missat att anmäla sig, men ändå vill skriva, bör man vara vid skrivsalen i god tid och hoppas på en ledig plats. När de tar slut kan man vänta på en plats någon annan inte utnyttjar (efter 45 minuter av skrivtiden).
  
  
• Vi har en kursnämnd!
  Första föreläsningen utsågs Eric Hörberg och Thomas Sjöholm till kursnämndsrepresentanter, se här.
  
  
• Den som skall läsa SF1631
  Till och med förra året läste D kursen SF1631. Bortsett från uppsatsen är det samma kurs som den här och man kan skriva samma tentor. Om man förstagångsregistrerades på SF1631 förra läsåret skall man dock bara skriva en tenta, TEN1, som kommer att ges samtidigt som TENB, den 11 december. Det går bra att skriva lappskrivningar under hösten och få bonus för alla sex till TEN1-skrivningar under läsåret.
  För information om uppsatsmomentet, se förra årets kurssida. Uppsatser kan lämnas till föreläsaren. Om de lämnas senast den 16 november bör de kunna vara betygsatta före jul.
  
  
• Om registrering
  Den som följer kursen skall vara registrerad för denna termin (annars kan man inte få betyg och CSN inte veta att man läser).
  En registreringslista att skriva på fanns vid de första föreläsningarna, men har nu 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.
  
  

Viktiga tider

• Lappskrivningar (se nedan under lappskrivningar):
• Ls1A: tisdagen den 18 september kl. 15.15-15.40,
  
• Ls2A: tisdagen den 2 oktober kl. 15.15-15.40,
  
• Ls3A: måndagen den 8 oktober kl. 8.15-8.40,
  
• Ls1B: fredagen den 9 november kl. 13.15-13.40,
  
• Ls2B: fredagen den 16 november kl. 8.15-8.40,
  
• Ls3B: fredagen den 23 november kl. 8.15-8.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"):
• TENA, tentamen på första delen av kursen,
  ordinarie tentamen: torsdagen den 18 oktober 2012 kl. 8.00-13.00,
  omtentamen: måndagen den 7 januari 2013 kl. 14.00-19.00.
  
• TENB, tentamen på andra delen av kursen,
  ordinarie tentamen: tisdagen den 11 december 2012 kl. 8.00-13.00,
  omtentamen: fredagen den 31 maj 2013 kl. 8.00-13.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: Lars Svensson (larses@math.kth.se), tel. 790 8052, rum 3649.
Grupp 2: Anders Lundman (alundman@kth.se), tel. 790 6616, rum 3728.
Grupp 3: Jan Kristoferson ( janke@kth.se), nås säkrast i samband med undervisningen.
Grupp 4: Erik Aas (eaas@math.kth.se), tel. 790 6643, rum 3732.

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örsta föreläsningen):

Eric Hörberg (skriv honom),
Thomas Sjöholm (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 per period 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. 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.

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.

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 (ingår i kurslitteraturen!)

• 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

Ö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.
  

Examination

Tentamina

Lappskrivningar

Betygssättning

Undervisning

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

 

Ö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, "extra" står för stencilen med extra uppgifter, finns här)
1	Fr 31/8 10-12	Q17,Q21, Q22,Q24	rek 4,5,6,8; Biggs 15.1:4; 15.2:1,2,3; 15.3:1,2,3,4,5; extra svar
2	Fr 7/9 13-15	D33,D34, E31,E33	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 svar
3	On 12/9 8-10	D34,D35, D41,D42	plan 1,2,3; Biggs 17.1:2,3; 17.2:1,2,4; 17.4:1,2,3; extra svar
4	To 13/9 15-17	Q11,Q13, Q15,Q31	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 svar
5	Ti 18/9 15-17	Q15,Q17, Q21,Q24	Ls 1A, 15.15-15.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 svar
6	On 26/9 15-17	D41,D42, E31,E33	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 svar
7	Ti 2/10 15-17	D41,D42, E31,E33	Ls 2A, 15.15-15.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 svar
8	Må 8/10 8-10	Q34,Q36, V01,V11	Ls 3A, 8.15-8.40, om kombinatorik (Biggs 7.2-3, 10.1-2, 10.4-5, 11.1-4 och 12.3) Biggs 10.3:2; 10.7:4,5,7; 11.5:1,2,3,4; 12.1:1,2; extra svar
9	On 10/10 15-17	Q15,Q17, Q22,Q26	Biggs 10.6:1,2,3,4; 12.5:1,2,3,4; 12.6:1,2,3,4; 12.7:19; extra svar
TENA	To 18/10 8.00-13.00	L,Q	Tentamen (TENA, 6hp) på innehållet i F1-F18.
10	Fr 26/10 15-17	Q15,Q17, Q22,Q26	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 svar
11	Fr 2/11 10-12	Q15,Q17, Q22,Q26	Biggs 20.8:1,2,3,4,5; 20.9:1,2,3; 20.10:5,13
12	Fr 9/11 13-15	D34,D35, E35,E36	Ls 1B, 13.15-13.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 16/11 8-10	D35,D41, E35,E36	Ls 2B, 8.15-8.40, om gruppers verkan på mängder, ringar och kroppar (Biggs 21.1-4, 22.1-3) 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	Fr 23/11 8-10	D34,D35, D41,E36	Ls 3B, 8.15-8.40, om polynom, ändliga kroppar (Biggs 22.4-8 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 30/11 8-10	Q17,Q21, Q22,Q26	krypto 1,3,5,7,8; Repetition
TENB	Ti 11/12 8.00-13.00	L,Q	Tentamen (TENB, 3hp) på innehållet i F19-F30.