SF1610 Diskret matematik 7,5hp
för CL2, Media2 vt10

Tidigare kursnummer: 5B1118

URL: http://www.math.kth.se/math/GRU/2009.2010/SF1610/CL

Kursansvarig: Bengt Ek, 08-790 6951, bek@math.kth.se
Kursstart: Måndagen den 18 januari 2010 klockan 15.15 i sal Q36.

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

Aktuell information

Tentan den 18 augusti
Skrivningen och lösningsförslag finns nu här nere.
Där finns nu också resultatlistan. Skrivningarna finns på expeditionen.
Den som inte kan sin kod kan se på "Mina sidor" (eller skriva mig).
Du som fått "Fx", dvs rätt att komplettera, skriv föreläsaren och meddela om du vill delta i kompletteringen. Information om tid och plats för den delges senare dem som hört av sig.
Komplettering av tentan 29/31 maj
Nu har meddelande skickats till dem som får komplettera, i vissa fall till u1...-adresserna. Glöm inte att svara på meddelandet, så vi vet om ni nåtts av informationen och om ni vill delta.
Kompletteringen blir redan på fredag, den 11 juni.
Kursenkät!!
Nu finns en enkät om kursen att besvara.
Gå bara in här, ange koden "diskCLvt10" (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!
Den som inte besvarar enkäten deltar inte i en utlottning av en kryssning för två i Karibien!
Tentan den 31 maj
Skrivningen (med tryckfelet rättat) och lösningsförslag finns nu här nere.
Nu finns där en preliminär resultatlista också. Listan avses bli definitiv nästa vecka.
De som inte finns med på listan kan kontakta föreläsaren.
Tid för komplettering blir fredag 11 juni 15-17. Mer info kommer.
Extratentan den 29 maj
Skrivningen, lösningsförslag och resultat finns nu här nere.
Skrivningarna finns på expeditionen.
Meddelande om tid och plats för komplettering kommer senare till dem det berör och som skriver föreläsaren.
Ks5 den 19 maj
Skrivningen, lösningsförslag och resultat finns nu här nere.
Alla ks:ar finns på elevexpeditionen.
Ks4 den 3 maj
Skrivningen, lösningsförslag och resultat finns nu här nere.
Av 37 skrivande blev 19 godkända.
Nytt om tiden för tentan!
Den nya tiden för tentan, måndagen den 31 maj, klockan 9.00-14.00, står fast. Den tiden verkar passa bättre för de flesta.
Men eftersom den nya tiden inte alls passar för en del, kommer det att finnas möjlighet att skriva lördagstiden i stället (inte samma skrivning). Det blir inte tillåtet att skriva båda skrivningarna, man måste välja endera.
Till skrivningen på måndagen (den nya tiden) anmäler man sig som vanligt via "Mina sidor", medan den som vill skriva på lördagen (den gamla tiden) ombeds att skriva föreläsaren och meddela det. Du som redan anmält dig via "Mina sidor", men vill skriva på lördagen, var snäll och tag bort din anmälan och skriv föreläsaren!
Ks3 den 12 april
Skrivningen, lösningsförslag och resultat finns nu här nere.
Den som inte skrev ks1 och ks2 (och därför inte vet sin kod) eller har glömt koden, kan skriva föreläsaren för att få besked.
Tentaanmälan!
Anmälan till tentan kan ske (som vanligt via "Mina sidor") från må 12 april (dvs genast efter påskuppehållet) till och med sö 16 maj.
Det är viktigt att vara anmäld om man vill skriva, den som inte är det riskerar att inte få plats eller få börja senare.
Kursnämndsmöte den 29 mars
Kursnämnden sammanträder på måndag, den 29 mars.
Den som vill ha något framfört kan kontakta en av representanterna.
Ks2 den 8 mars
Skrivningen, lösningsförslag och resultat finns nu här nere.
Den som inte skrev ks1 (och därför inte vet sin kod) eller har glömt koden, kan skriva föreläsaren för att få besked.
Ett "tryckfel" i lösningen till uppgift 4 rättades samma dag som skrivningen var. Tack Henrik Lindberg för påpekandet.
Ks1 den 15 februari
Skrivningen, lösningsförslag och resultat finns nu här nere.
Terminsregistrering
Den som inte redan terminsregistrerat sig, men följer kursen, bör skriva kurssekreteraren. Ange kursens och dina namn och nummer.
Mattejour
Som tidigare år finns en mattejour för den som kört fast, se här.
En liten schemaändring!
Uppmärksamma läsare har observerat att en del av stoffet för ks1 skall tas upp på Ö3, efter ks:en. Tack för påpekandet!
För att undvika problemet, delar vi upp Ö3 och F6, så som det nu står i planeringen.
Tiderna skall vara desamma som i schemat på nätet, men det stod tidigare fel veckodag för ks:en i planeringen. Den är på måndagen, den 15 februari.

Viktiga tider

Tentamina (för information om salar och föranmälan se här, anmälan "minst 14 dagar före tentamensperioden"):
ordinarie tentamen: måndagen den 31 maj kl. 09.00-14.00 (ändrad tid!)
(alternativt kan man skriva den ursprungliga tiden, lö 29 maj kl. 09.00-14.00, se ovan!),
kompletteringsskrivning vid behov, tid meddelas senare.
omtentamen: onsdagen den 18 augusti kl. 14.00-19.00,
kompletteringsskrivning vid behov, tid meddelas senare.
Kontrollskrivningar:
KS1: Måndagen den 15 februari kl. 15.10-16.00 i Q34, Q36
KS2: måndagen den 8 mars kl. 9.00-10.00 i Q34, Q36
KS3: måndagen den 12 april kl. 9.00-10.00 i Q34, Q36
KS4: måndagen den 3 maj kl. 9.00-10.00 i Q34, Q36
KS5: onsdagen den 19 maj kl. 11.00-12.00 i Q31, Q33

Lärare m.fl.

Kursledare och lärare:: Bengt Ek (bek@math.kth.se), tel. 790 6951, rum 3549.
Kurssekreterare:: Rose-Marie Jansson (jansson@math.kth.se).
Rum 3549 finns på plan 5 (entréplanet), Lindstedtsvägen 25.
Kursnämndsrepresentanter (utsedda första lektionen):: Joel Dahl, (skriv honom).
Tony Hay Werner, (skriv honom).

Kursbeskrivning

Bakgrund och betydelse

Denna kurs läses av CL2 och Media2 (och IT2 på hösten).

Den diskreta matematiken (talteori, kombinatorik, abstrakt algebra, grafteori) har ökat explosionsartat i betydelse sedan mitten av förra århundradet, både som forskningsområde och för tillämpningar inom framför allt datalogi men även inom fysik, kemi, bioteknik och ekonomisk modellering.

Diskret matematik ger 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. Dessutom är vissa kunskaper i diskret matematik nödvändiga för att kunna förstå, analysera och konstruera algoritmer och datastrukturer.

Kursens söker ge grundläggande kunskaper, insikter och färdigheter i diskret matematik. 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

Se studiehandboken.

Förkunskaper

En kurs i linjär algebra eller liknande.
(Vi behöver inte så mycket från tidigare kurser, men en vana vid och vilja till abstrakta resonemang är bra att ha.)

Kurslitteratur

Kursböcker

Vi använder liksom förra året dessa böcker.

Eriksson, Kimmo och Gavel, Hillevi: "Diskret Matematik och diskreta modeller" Studentlitteratur, 2002 (ISBN 91-44-02465-7).
I vår kurs ingår följande delar:: kapitlen (1) och 2-5,
kapitel 6 (utom avsnitten 6.3, 6.5.2, 6.6.1),
kapitel 8 (utom avsnitt 8.1.3),
avsnitt 7.4.

Eriksson, Kimmo och Gavel, Hillevi: "Diskret Matematik Fördjupning" Studentlitteratur, 2003 (ISBN 91-44-02878-4).
I vår kurs ingår följande delar:: kapitlen (1) och 3,
kapitel 2 (utom avsnitt 2.2),
avsnitten 5.1, 7.1-7.2.3 och 9.1-9.2.

Material som kan komplettera kursböckerna (inte kurslitteratur)

A. Björner: Kryptografi och primalitet pdf-fil
Om plana och planära grafer pdf-fil

Övrigt material

Exempel för övningarna, finns länkar till i planen för övningarna.
Kortfattade lösningar kommer att läggas ut efter övningen.
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 undervisningsplanen.
Observera att bilderna är avsedda som stöd vid inlärning och repetition, de garanteras inte täcka kursinnehållet och kan absolut inte ersätta annat kursmaterial.

Examination

Dels kontrollskrivningar under kursens gång, dels en skriftlig tentamen vid kursens slut.
Lyckade kontrollskrivningar kommer att räcka för betyg E på kursen (utan tenta).
Tentamen
Skrivningen kommer att omfatta tre delar, I, II och III.
Del I består av 5 uppgifter, som vardera kan ge högst 3p. Godkänd kontrollskrivning nr i ger automatiskt 3p på uppgift nr i (i=1,2,3,4,5).
Del II består av 3 uppgifter, som vardera kan ge högst 4p.
Del III består av 2 uppgifter, som vardera kan ge högst 5p. För att lösa dessa behövs en djupare insikt i kursinnehållet och för full poäng krävs väl strukturerade och presenterade lösningar.
Från kontrollskrivningarna kan man också få ett extra bonuspoäng per skrivning (se nedan).
Totalt blir det alltså möjligt att få 42p på skrivningen.

För godkänt, dvs minst betyget E, på tentamen krävs dels minst 12p på del I, dels totalt på skrivningen (inklusive poäng från kontrollskrivningar) poäng som följer:
betyg E: 15p,
betyg D: 18p,
betyg C: 22p,
betyg B: 27p,
betyg A: 32p.

Minst 13p totalt, men inte godkänt, ger resultat Fx, som innebär rätt till komplettering.

De som varit registrerade vt07 eller tidigare (med kursnummer 5B1118) får betyg 5, 4, 3, K (rätt till komplettering) eller U. Kraven för de fyra första är som för A, C, E respektive Fx ovan.

Årets tentor:
Extraskrivningen 29 maj 2010: Tentan pdf-fil    Lösningar pdf-fil    Resultat pdf-fil
31 maj 2010: Tentan pdf-fil    Lösningar pdf-fil    Resultat pdf-fil
18 augusti 2010: Tentan pdf-fil    Lösningar pdf-fil    Resultat pdf-fil

Förra årets tentor:
21 oktober 2008: Tentan pdf-fil    Lösningar pdf-fil
27 maj 2009: Tentan pdf-fil    Lösningar pdf-fil
19 augusti 2009: Tentan pdf-fil    Lösningar pdf-fil

Förrförra årets tentor:
20 december 2007: Tentan pdf-fil    Lösningar pdf-fil
5 maj 2008: Tentan pdf-fil    Lösningar pdf-fil
20 augusti 2008: Tentan pdf-fil    Lösningar pdf-fil

Kontrollskrivningar

Fem kontrollskrivningar under kursens gång kommer att ges. Klarad ks kommer att ersätta varsin uppgift på skrivningen och den som klarat alla ks:ar har redan betyg E på kursen klart.
Dessutom ger 13p eller mer (av 15 möjliga) vid ks ett extra bonuspoäng som läggs till den totala poängen på tentan.
Skrivningarna omfattar följande material
KS1: Aritmetik och mängder, DM2-4, 8 (utom 8.2.2.2) (F1-4),
KS2: Kombinatorik, DM5, 8.2.2.2 (F5-8),
KS3: Algebra, DMF2.1, 5.1 (F9-12),
KS4: Tillämpad algebra, DMF3, DM7.4 (F13-15),
KS5: Grafer, DM6 (utom 6.5.2, 6.6.1 och 6.3), DMF7.1-7.2.3, DMF9.1-9.2 (F16-20).

Årets kontrollskrivningar:
KS1, 15 februari 2010: Skrivningen pdf-fil    Lösningar pdf-fil    Resultat pdf-fil
KS2, 8 mars 2010: Skrivningen pdf-fil    Lösningar pdf-fil    Resultat pdf-fil
KS3, 12 april 2010: Skrivningen pdf-fil    Lösningar pdf-fil    Resultat pdf-fil
KS4, 3 maj 2010: Skrivningen pdf-fil    Lösningar pdf-fil    Resultat pdf-fil
KS5, 19 maj 2010: Skrivningen pdf-fil    Lösningar pdf-fil    Resultat pdf-fil

Förra årets kontrollskrivningar:
KS1, 10 februari 2009: Skrivningen pdf-fil    Lösningar pdf-fil
KS2, 2 mars 2009: Skrivningen pdf-fil    Lösningar pdf-fil
KS3, 30 mars 2009: Skrivningen pdf-fil    Lösningar pdf-fil
KS4, 28 april 2009: Skrivningen pdf-fil    Lösningar pdf-fil
KS5, 14 maj 2009: Skrivningen pdf-fil    Lösningar pdf-fil

Förrförra årets kontrollskrivningar:
KS1, 13 februari 2008: Skrivningen pdf-fil    Lösningar pdf-fil
KS2, 27 februari 2008: Skrivningen pdf-fil    Lösningar pdf-fil
KS3, 25 mars 2008: Skrivningen pdf-fil    Lösningar pdf-fil
KS4, 9 april 2008: Skrivningen pdf-fil    Lösningar pdf-fil
KS5, 23 april 2008: Skrivningen pdf-fil    Lösningar pdf-fil

Undervisning

Kursen har lektionsundervisning, men var tredje lektion kommer att kallas övning och de övriga föreläsningar.
På föreläsningarna varvas teori och illustrerande problemgenomgångar, medan övningarna ägnas problemlösning av lärare och/eller studenter.
I listan betyder "DMx" avsnittet x i den första kursboken och "DMFx" motsvarande i den andra.
Kontrollskrivningarna sker på särskilda tider, se ovan.

Föreläsningar (preliminärt)
Nr	Tid	Lokal	Innehåll	Avsnitt i litteraturen	Samman- fattning
F1	Må 18/1 15-17	Q36	Presentation av kursen. Heltalsaritmetik, divisionsalgoritmen. Talbaser. Delbarhet. Delargrafer. Största gemensam delare.	DM3.1-3.3	pdf-fil
F2	To 21/1 8-10	Q36	Euklides algoritm, vissa diofantiska ekvationer. Primtal. Aritmetikens fundamentalsats. Modulär aritmetik, början.	DM3.3-3.4	pdf-fil
F3	To 28/1 10-12	Q36	Mer modulär aritmetik, linjära ekvationer i modulär aritmetik. Mängdlära: union, snitt, komplement, räkneregler.	DM3.4, 2.1-2.4	pdf-fil
F4	On 3/2 10-12	Q36	Rekursion, induktion. Produktmängder. Funktioner, relationer. Kardinalitet.	DM2.5-6, 4, 8.2	pdf-fil
F5	On 10/2 10-12	Q36	Binära relationer. Ekvivalensrelationer, partialordningar. Inledning kombinatorik. Additionsprincipen.	DM5.3, 8.1	pdf-fil
F6 A	To 11/2 13-14	Q36	Additions- och multiplikationsprinciperna. Övningsks1 svar	DM5.3	.
KS1	Må 15/2 15.10-16.00	Q34, Q36	KONTROLLSKRIVNING 1 på DM2, 3, 4, 8 (utom 8.2.2.2).
F6 B	On 17/2 10-11	Q36	Lite sannolikhetslära. Ordnade urval och permutationer. Icke-ordnat urval utan upprepning, binomialtal.	DM5.1-5.5, 8.2.2.2	pdf-fil
F7	To 18/2 10-12	Q33	Icke-ordnat urval med upprepning. Postfacksprincipen. Exempel med genererande funktion.	DM5.6, 5.8.2	pdf-fil
F8	On 24/2 10-12	Q36	Principen om inklusion/exklusion (sållprincipen). Uppdelningar av mängder, stirlingtal.	DM5.7, 5.8.1	pdf-fil
F9	On 3/3 10-12	Q36	Grupper. Introduktion, exempel. Övningsks2 svar	DMF2.1.1, 2.1.3	pdf-fil
KS2	Må 8/3 9.00-10.00	Q34,Q36	KONTROLLSKRIVNING 2 på DM5, 8.2.2.2.
F10	On 10/3 10-12	Q36	Cykliska grupper. Delgrupper, sidoklasser. Lagranges sats. Gruppisomorfi.	DMF2.1.2, 2.1.4-2.1.7	pdf-fil
F11	Må 22/3 15-17	Q36	Direkta produkter av grupper. Normala delgrupper. Lite om ringar och kroppar. Permutationsgrupper.	DMF2.1.8 DMF5.1.1	pdf-fil
F12	To 25/3 8-10	Q36	Ex med permuterade skurkar. Permutationers ordning. Konjugering. Udda och jämna permutationer.	DMF5.1.2-5.1.4	pdf-fil
F13	To 1/4 8-10	Q36	Avslutning udda och jämna permutationer. Felrättande koder. Övningsks3 svar	DMF3.1	pdf-fil
KS3	Må 12/4 9.00-10.00	Q34,Q36	KONTROLLSKRIVNING 3 på DMF2.1, 5.1.
F14	On 14/4 8-10	Q36	Avslutning felrättande koder Kryptering. Fermats lilla sats. RSA-kryptering. Primalitetstest.	DMF(3.1,) 3.2	pdf-fil
F15	Ti 20/4 8-10	Q36	Lite om satslogik. Boolesk algebra. Disjunktiv och konjunktiv normalform. Karnaughdiagram.	DM7.4	pdf-fil
F16	To 22/4 10-12	Q36	Karnaughdiagram, lite till. Grafer, allmänt. Grafisomorfi. Eulerkretsar, hamiltoncykler.	DM6.1-6.2, 6.4	pdf-fil
F17	On 28/4 10-12	Q36	Träd. Planära grafer. Övningsks4 svar	DM6.2, 6.5-6.6 DMF7.1	pdf-fil
KS4	Må 3/5 9.00-10.00	Q34,Q36	KONTROLLSKRIVNING 4 på DMF3, DM7.4.
F18	Ti 4/5 8-10	Q36	Planära grafer, avslutning. Graffärgning. Fyrfärgssatsen.	DMF7.1-7.2.3	pdf-fil
F19	Må 10/5 8-10	Q36	Kromatiska polynom. Matchning i bipartita grafer. Halls giftermålssats.	DMF7.2.1 DMF9.1	pdf-fil
F20	Ti 11/5 15-17	Q36	Maximala matchningar i bipartita grafer. Reservtid. Repetition. Övningsks5 svar	DMF9.2 DM, DMF	pdf-fil
KS5	On 19/5 11.05-12.00	Q31, Q33	KONTROLLSKRIVNING 5 på DM6 (utom 6.3, 6.5.2, 6.6.1), DMF7.1-7.2.3, DMF9.1-9.2.

Övningar (preliminärt)
Nr	Tid	Lokal	Att välja bland	Att göra själv
Ö1	Må 25/1 10-12	Q36	uppgifter (pdf) svar (pdf)	DM3: 2, 6, 7, 11, 12, 13, 14, 17, 18, 22, 29, 30, 31, 47, 48, 54
Ö2	To 4/2 10-12	Q36	uppgifter (pdf) svar (pdf)	DM3: 35, 45, 46, 49 DM2: 9, 11, 13, 17, 18, 31, 33, 34, 37
Ö3 A	To 11/2 14-15	Q36	uppgifter (pdf) (svar vid Ö3B)	DM4: 5, 9, 10, 11, 16, 17, 18, 19, 20, 45, 46, 47, 66 DM8: 4, 5, 21, 29, 32, 34, 36, 41, 58, 63, 69, 79 DM5: 3, 4, 7, 9, 10, 13, 14, 16, 25, 28, 29, 30, 31, 32, 33, 34, 35, 36
KS1	Må 15/2 15.10-16.00	Q34, Q36	KONTROLLSKRIVNING 1 på DM2, 3, 4, 8 (utom 8.2.2.2).
Ö3 B	On 17/2 11-12	Q36	(uppg. vid Ö3A) svar (pdf)	DM5: 37, 41, 43, 46
Ö4	Må 1/3 8-10	Q36	uppgifter (pdf) svar (pdf)	DM5: 52, 54, 67, 68, 70, 71, 72, 73 DM8: 55, 56, 57
KS2	Må 8/3 9.00-10.00	Q34,Q36	KONTROLLSKRIVNING 2 på DM5, 8.2.2.2.
Ö5	To 11/3 10-12	Q36	uppgifter (pdf) svar (pdf)	DMF2: 1, 3, 5, 6, 8, 9, 10, 12, 13, 16, 17, 34, 35, 38, 39, 40
Ö6	Ti 30/3 8-10	Q36	uppgifter (pdf) svar (pdf)	DMF2: 21, 22, 36 DMF5: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 16, 17, 20, 21, 51
KS3	Må 12/4 9.00-10.00	Q34,Q36	KONTROLLSKRIVNING 3 på DMF2.1, 5.1.
Ö7	To 15/4 10-12	Q36	uppgifter (pdf) svar (pdf)	DMF3: 4, 5, 8, 9, 14, 17, 18, 19, 20, 23, 29, 31, 34, 35, 37, 38, 40
Ö8	Ti 27/4 8-10	Q36	uppgifter (pdf) svar (pdf)	DM7: 53, 54, 55, 56, 61, 66, 67, 69, 83, 91 DM6: 9, 10, 11, 12, 24, 31, 33, 34, 47, 48, 49
KS4	Må 3/5 9.00-10.00	Q34,Q36	KONTROLLSKRIVNING 4 på DMF3, DM7.4.
Ö9	On 5/5 10-12	Q36	uppgifter (pdf) svar (pdf)	DM6:55, 56, 62, 67, 92 DMF7: 1, 2, 7, 14, 15, 22, 23, 28, 29
Ö10	Ti 18/5 10-12	Q36	OBS! Tag med en kortlek till övningen. uppgifter (pdf) svar (pdf)	DMF9: 1, 2, 3, 4, 5, 7, 10
KS5	On 19/5 11.00-12.00	Q31, Q33	KONTROLLSKRIVNING 5 på DM6 (utom 6.3, 6.5.2, 6.6.1), DMF7.1-7.2.3, DMF9.1-9.2.

För hemarbete rekommenderas dels de som står under rubriken "Att göra själv", dels de uppgifter som inte hunnits med på övningarna.

SF1610 Diskret matematik 7,5hp för CL2, Media2 vt10

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