SF1688 Diskret matematik 6hp för D3, ht17

URL: http://www.math.kth.se/math/GRU/2017.2018/SF1688/

Kursansvarig: Bengt Ek, 08-790 6951, bek@math.kth.se
Kursstart: Onsdagen den 30 augusti 2017 klockan 13.15 i sal Q1.

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

Aktuell information

Omtenta, den 20 december 2017
Skrivningen och svarsförslag finns här nere.
Rättningen är äntligen klar.
Resultatet var inte alls bra, lite oklart varför. Så svår var den väl inte?
Skrivningarna skannas inom kort (om det inte redan är gjort), resultaten bör snart finnas på "Mina sidor".
Den som fått FX får göra en komplettering. Kontakta Bengt för besked om hur den går till (och för att meddela om du vill delta). När de flesta hört av sig skickas ett mejl med information.
Tentan den 24 oktober
Skrivningen och svarsförslag finns här nere.
Rättningen är (äntligen) klar.
Resultaten har rapporterats in och skrivningarna har lämnats för skanning.
Statistik: av 113 rättade skrivningar fick 5 (4%) betyg A, 5 (4%) B, 5 (4%) C, 16 (14%) D, 29 (26%) E, 17 (15%) FX och 36 (32%) F.
Den som fått FX får göra en komplettering. Kontakta Bengt för besked om hur den går till (och för att meddela om du vill delta). När de flesta hört av sig skickas ett mejl med information.
ks3, den 9 oktober
Skrivningen och svarsförslag finns nu här nere.
När rättningen är klar kommer skrivningarna att skannas och bli tillgängliga för er som vanligt.
ks2, den 25 september
Skrivningen och svarsförslag finns nu här nere (karakteristiska ekvationen i lösningen till uppgift 2a rättad em 25 september).
När rättningen är klar kommer skrivningarna att skannas och bli tillgängliga för er som vanligt.
ks1, den 11 september
Skrivningen och svarsförslag finns nu här nere.
När rättningen är klar kommer skrivningarna att skannas och bli tillgängliga för er som vanligt.
Några referenser
På föreläsningen ti 5 september talades kort om "nya cirkelns kvadratur". För att läsa på nätet om detta kan man t.ex. söka på "Tarski's circle-squaring problem" (finns bl.a. i Wikipedia).
För mer om problemet med getterna och vargarna (som behandlades på föreläsningen on 30 augusti) kan man läsa "River crossing puzzle" i Wikipedia och söka på de namn för problemen som finns där.
Första kursveckan har gått och vi har en kursnämnd!
Andra föreläsningen utsågs Cristian Osorio Bretti och Ludvig Kindberg till kursnämndsrepresentanter, se här.
Om registrering
Den som följer kursen skall vara registrerad för denna termins kurs (annars kan man inte skriva kontrollskrivningarna eller tentan och CSN inte veta att man följer kursen).
Vi använder egenregistrering, se Mattes studentexpeditions sida.
OBS! Registreringstiden gick ut redan to 31 augusti. Du som missat att registrera dig, gör som för omregistrering, se expeditionens sida.

Viktiga tider

Kontrollskrivningar (se nedan under kontrollskrivningar):

Ks1: måndagen den 11 september kl. 8.00-10.00, (anmälan 28 aug - 4 sep)
Ks2: måndagen den 25 september kl. 8.00-10.00, (anmälan 4 sep - 18 sep)
Ks3: måndagen den 9 oktober kl. 8.00-10.00. (anmälan 18 sep - 2 okt)

Tentamina (för information om salar och föranmälan se Studentexpeditionens sida):

Ordinarie tentamen: tisdagen den 24 oktober 2017 kl. 8.00-13.00, (anmälan 21 sep - 5 okt)
omtentamen: onsdagen den 20 december 2017 kl. 8.00-13.00. (anmälan 6 nov - 4 dec)

Lärare m.fl.

Föreläsare och kursledare:: Bengt Ek (bek@math.kth.se), tel. 790 6951, rum 3650.
Övningsledare:: Grupp 1: Eric Ahlqvist (ericahl@math.kth.se), tel. 790 7507, rum 3737.
Grupp 2: Magnus Carlsson (macarlso@math.kth.se), tel. 790 6488, rum 3748.
Grupp 3: Oliver Gäfvert (oliverg@math.kth.se), tel. 790 6581, rum 3419.
Grupp 4: Nima Amini (namini@math.kth.se), tel. 790 6616, rum 3728.

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

Kursnämndsrepresentanter (utsågs vid andra föreläsningen):: Ludvig Kindberg (skriv honom).
Cristian Osorio Bretti (skriv honom),

Kursbeskrivning

Kursens betydelse

Denna kurs är obligatorisk för D3 och är en fortsättning på den diskreta matematik som lästes i första årskursen.

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

Se studiehandboken.

Förkunskaper

SF1624 Algebra och geometri och SF1671 Matematik, baskurs, med diskret matematik (eller motsvarande).

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!

Övrigt kursmaterial (ingår i kurslitteraturen!)

K. Eriksson: A summary of recursion solving techniques pdf-fil
Om planära grafer pdf-fil
Om kinesiska restsatsen pdf-fil
Alternativt kan man läsa följande:
A. Björner: Kinesiska restsatsen och struktursatser (Avsnitt 3 ingår inte i vår kurs och i avsnitt 2 är delen "Tillämpad aspekt" på sidan 4-5 viktigast) pdf-fil (Hänvisningarna till Biggs bok gäller gamla upplagan. För den nya, ersätt 13... med 20...)
Om RSA-kryptering och primalitet pdf-fil
Alternativt kan man läsa följande:
A. Björner: Kryptografi och primalitet pdf-fil ("Biggs (sid. 121)" på sid. 5 ersätts med "Biggs (sid. 149)" för nya upplagan.)
En lista med extra övningsexempel 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 helt ersätta annat kursmaterial. I vissa fall kan de innehålla material som inte täcks i den övriga litteraturen (t.ex. kromatiska polynom).
Här finns lösningar till exemplen i Biggs bok.
(Svaret till uppgift 19.2.1 (i) är fel. Rätt i bokens facit.
Också i facit för uppgift 20.1:1 finns ett fel. Subtraktion på heltalen har inget identitetselement (bara en högeridentitet, 0), därmed egentligen ingen invers.)
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!!

Examination

Tentamen

En tentamen: TEN1, 6hp, ges efter period 1.
En beskrivning av betygskriterier och av tentamens utformning (samma som i extentorna nedan) finns här.

Årets tentor:
24 oktober 2017 pdf-fil,    lösningar pdf-fil
20 december 2017 pdf-fil,    lösningar pdf-fil

Eftersom denna kurs ges för första gången i år, finns inga gamla tentor att studera, men nedan finns tentor för den tidigare kursen SF1630, vars innehåll i stort sett var unionen av vår kurs och diskretmattedelens i SF1671.
I listan står efter varje skrivning angivet vilka av uppgifterna som kunde ingått i vår tenta.

Förra årets tentor:
25 oktober 2016, TENA pdf-fil,    lösningar pdf-fil   (1, 4, 5, 6, 8, 10, 11, 12, 13)
21 december 2016, TENA pdf-fil,    lösningar pdf-fil   (1, 4, 5, 6, 8, 9, 12, 13)
12 januari 2017, TENB pdf-fil,    lösningar pdf-fil   (alla)
12 april 2017, TENB pdf-fil,    lösningar pdf-fil   (alla)

Förrförra årets tentor:
27 oktober 2015, TENA pdf-fil,    lösningar pdf-fil   (1, 2c, 4, 5, 6, 8, 9, 11, 13)
8 januari 2016, TENA pdf-fil,    lösningar pdf-fil   (1, 4, 5, 6, 8, 9, 11, 12, 13)
13 januari 2016, TENB pdf-fil,    lösningar pdf-fil   (alla)
16 mars 2016, TENB pdf-fil,    lösningar pdf-fil   (alla)

Fler gamla tentor för kurs SF1630 finns här.

Kontrollskrivningar

Vid tre tillfällen (se ovan för tider), ges kontrollskrivningar med fem uppgifter. De omfattar stoff som anges i undervisningsschemat nedan. Kontrollskrivningarnas ungefärliga utformning framgår av de fiktiva exempelskrivningarna nedan.
Kontrollskrivningarna kan ge bonus till tentan, som beskrivs i bladet om betygskriterier.

Årets kontrollskrivningar:
Ks1, 11 september 2017: Skrivningen pdf-fil    Lösningar pdf-fil
Ks2, 25 september 2017: Skrivningen pdf-fil    Lösningar pdf-fil
Ks3, 9 oktober 2017: Skrivningen pdf-fil    Lösningar pdf-fil

Exempelskrivningar: ks1 pdf-fil,   lösningar pdf-fil;    ks2 pdf-fil,   lösningar pdf-fil;    ks3 pdf-fil,   lösningar pdf-fil.

Betygssättning

Slutbetyget på kursen är samma som betyget på tentan.

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.

Föreläsningar (preliminärt)
Nr	Tid	Lokal	Innehåll	Avsnitt i litteraturen	Samman- fattning
1	On 30/8 13-15	Q1	Inledning till kursen. Inledning grafer, ex. om vargar och getter (pdf). Valens, isomorfi. rubriker(pdf) färgfrågor(pdf).	Biggs 15.1-3	pdf-fil OH(pdf)
2	To 31/8 8-10	Q1	Eulerkretsar. Hamiltoncykler. Antalet vandringar mellan givna hörn. rubriker(pdf) färgfrågor(pdf)	Biggs 15.4	pdf-fil OH(pdf)
3	Fr 1/9 8-10	Q1	Träd. Hörnfärgning. Bipartita grafer. Kromatiska polynom. rubriker(pdf) färgfrågor(pdf)	Biggs 15.5-7, 17.1	pdf-fil OH(pdf)
4	Må 4/9 8-10	Q1	Planära grafer. rubriker(pdf) färgfrågor(pdf)	Planaritetsstencil	pdf-fil OH(pdf)
5	Ti 5/9 15-17	D1	Kantfärgning. Latinska kvadrater. Alternerande stigar. Halls bröllopssats. rubriker(pdf) färgfrågor(pdf)	Biggs 17.2-4	pdf-fil OH(pdf)
6	On 6/9 13-15	D1	Maximala matchningar. Transversaler. rubriker(pdf) färgfrågor(pdf)	Biggs 17.5-6	pdf-fil OH(pdf)
Ks1	Må 11/9 8.00-10.00	Q22,Q26,Q31, Q33,Q34,Q36	Kontrollskrivning 1 på innehållet i F1-F6.
7	Må 11/9 10-12	D1	Rekursionsekvationer, Mästarsatsen. rubriker(pdf) färgfrågor(pdf)	Rekursionsstencil, Biggs 4.5, 19.2	pdf-fil OH(pdf)
8	Ti 12/9 10-12	D1	Permutationer. Ett ex. "permuterade skurkar" (pdf-fil). rubriker(pdf) färgfrågor(pdf)	Biggs 10.6, 12.4	pdf-fil OH(pdf)
9	Fr 15/9 8-10	D1	Mer om permutationer. rubriker(pdf) färgfrågor(pdf)	Biggs 12.4-6	pdf-fil OH(pdf)
10	Må 18/9 13-15	D1	Grupper, ordning av element. rubriker(pdf) färgfrågor(pdf)	Biggs 20.1-4	pdf-fil OH(pdf)
11	Ti 19/9 8-10	D1	Cykliska grupper. Delgrupper. Lite om cayleygrafer. rubriker(pdf) färgfrågor(pdf)	Biggs 20.5-7	pdf-fil OH(pdf)
12	On 20/9 15-17	D1	Lagranges sats. Exempel. rubriker(pdf) färgfrågor(pdf)	Biggs 20.8	pdf-fil OH(pdf)
Ks2	Må 25/9 8.00-10.00	Q26,Q31,Q33 Q34,Q36	Kontrollskrivning 2 på innehållet i F7-F12.
13	Ti 26/9 8-10	F1	Grupper som verkar på mängder. Burnsides lemma. rubriker(pdf) färgfrågor(pdf)	Biggs 21	pdf-fil OH(pdf)
14	On 27/9 13-15	Q1	Modulär aritmetik. Kinesiska restsatsen. Ett gammalt tentatal (pdf-fil), lösning. Eulers och Fermats satser. rubriker(pdf) färgfrågor(pdf)	Biggs 13.1-3 Kinesisk reststencil	pdf-fil OH(pdf)
15	Fr 29/9 13-15	E1	Eulers funktion ϕ och Möbiusfunktionen μ. Mer om cykliska grupper. rubriker(pdf) färgfrågor(pdf)	Biggs 10.3, 11.5, 20.9	pdf-fil OH(pdf)
16	Må 2/10 8-10	E1	Ringar och kroppar. rubriker(pdf) färgfrågor(pdf)	Biggs 22.1-3	pdf-fil OH(pdf)
17	Ti 3/10 13-15	F1	Polynomfaktorisering. Irreducibla polynom. rubriker(pdf) färgfrågor(pdf)	Biggs 22.4-8	pdf-fil OH(pdf)
18	On 4/10 10-12	F1	Ändliga kroppar. rubriker(pdf) färgfrågor(pdf)	Biggs 23.1-4	pdf-fil OH(pdf)
Ks3	Må 9/10 8.00-10.00	Q26,Q31,Q33, Q34,Q36	Kontrollskrivning 3 på innehållet i F13-F18.
19	Ti 10/10 13-15	D1	Felrättande koder. rubriker(pdf) färgfrågor(pdf)	Biggs 24.1-4	pdf-fil OH(pdf)
20	On 11/10 10-12	E1	RSA-kryptering. Primalitetstest. rubriker(pdf) färgfrågor(pdf)	Kryptografistencil	pdf-fil OH(pdf)
21	Fr 13/10 8-10	E1	Repetition. Problemgenomgång. Exempel(pdf)	Allt möjligt	pdf-fil
TEN1	Ti 24/10-17 8.00-13.00	B21-24,D36, M36-38	TENTAMEN.
TEN1	On 20/12-17 8.00-13.00	Q-salar	OMTENTAMEN.

Ö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, den finns här)
1	To 31/8 10-12	Q22,Q26, Q31,Q33	Biggs 15.1:4; 15.2:1,2,3; 15.3:1,2,3,4,5; 15.4:1,3,4,5 (i vilka kuber kan musen starta om hon vill sluta i mitten?); extra svar
2	Ti 5/9 10-12	Q22,Q26, Q31,Q33	Biggs 15.5:1,2,4; 15.6:1,2; 15.7:1,2,3; 15.8:8; 17.1:2,3; plan 1,2,3; extra svar
3	To 7/9 10-12	Q22,Q26, Q31,Q33	Biggs 17.2:1,2,4; 17.4:1,2,3; 17.5:1; 17.6:1,3,4; 17.7:1(,9); extra svar
Ks1	Må 11/9 8.00-10.00	Q22,Q26,Q31, Q33,Q34,Q36	Kontrollskrivning 1 på innehållet i F1-F6.
4	On 13/9 10-12	Q15,Q17, Q34,Q36	rek 4,5,6,8; Biggs 10.6:1,2,3,4; extra svar
5	Må 18/9 15-17	Q17,Q22, Q33,Q34	Biggs 12.5:1,2,3,4; 12.6:1,2,3,4; 12.7:19; 20.2:1,3,4; 20.3:1,2,3,5; 20.4:1,3; extra svar
6	To 21/9 10-12	Q11,Q13 Q31,Q33	Biggs 20.5:1,4; 20.6:1,4; 20.7:1,2,3,4; 20.8:1,2,3,4,5; 20.10:5,13; extra svar
Ks2	Må 25/9 8.00-10.00	Q26,Q31,Q33 Q34,Q36	Kontrollskrivning 2 på innehållet i F7-F12.
7	Fr 29/9 8-10	L51,L52, Q22,Q26	Biggs 21.1:2,5; 21.2:2,4; 21.3:3; 21.4:1,2,3,4; 21.5:1,2,4; 21.6:1,2,4; 13.1:1,2,3; 13.2:1,3,4; 13.3:1,4,5,7,8; kin 1,2,3; extra svar
8	Ti 3/10 10-12	Q15,Q17, Q31,Q33	Biggs 10.3:1,2,3; 11.5:1,2,3,4; 11.8:16,17; 20.9:1,2,3; 22.1:2; 22.2:1,3; 22.3:2,3; extra svar
9	Fr 6/10 10-12	Q15,Q17, Q33,Q34	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 extra svar
Ks3	Må 9/10 8.00-10.00	Q26,Q31,Q33, Q34,Q36	Kontrollskrivning 3 på innehållet i F13-F18.
10	On 11/10 13-15	Q15,Q17, Q31,Q33	Biggs 24.1:1,2; 24.2:1,2,3,4; 24.3:1,2,3; 24.4:1,2,3,4; krypto 1,2,3,4,5; extra svar
TEN1	Ti 24/10-17 8.00-13.00	B21-24,D36, M36-38	TENTAMEN.
TEN1	On 20/12-17 8.00-13.00	Q-salar	OMTENTAMEN.

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.