SF1679 Diskret matematik 7,5hp för F3, ht17

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

Kursansvarig: Bengt Ek, 08-790 6951, bek@math.kth.se
Kursstart: Måndagen den 30 oktober 2017 klockan 10.15 i sal U31 (Brinellvägen 28A).

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

Aktuell information

Tentan den 5 april 2018
Skrivningen och svarsförslag finns nu här nere, ursäkta att de dröjt.
Rättningen är klar och resultaten och de skannade skrivningarna bör vara tillgängliga snart.
Tyvärr gick det inte särskilt bra.
Ett fel (kanske uppenbart) hade smugit sig in i lydelsen av uppgift 2 (rättat i filen nedan). Både A och B skulle vara delmängder till X. Det gjorde uppgifterna b och c enklare, men frågan verkar ha tolkats som avsett av de flesta. Hänsyn har tagits till misstaget vid rättningen.
Tentan den 11 januari
Skrivningen och svarsförslag finns nu här nere.
Rättningen är klar och resultaten och de skannade skrivningarna bör vara tillgängliga snart.
Tyvärr gick det sämre än väntat på skrivningen. Oklart vad det berodde på, även ganska lätta uppgifter visade sig vålla problem för flera.
Lösningsförslag till hemuppgifter omgång 2
Lösningar har kommit, finns nu att hämta här nere.
De (liksom resultaten) har dröjt, eftersom alstren kom fram sent.
Hemuppgiftsinlämningsproblem?
Det verkar inte (tvärtemot vad som påståtts) finnas någon låda att lämna uppgifterna i när huset Teknikringen 8 är låst.
Vi förlänger inlämnings/insändningstiden till to 4 januari.
Svar/anvisningar till problemen den 11 december
Lösningsbeskrivningar till sista lektionens uppgifter har kommit. Finns att hämta här nere.
Hemuppgifter!
Den andra omgången hemupgifter finns nu att hämta här nere.
Lösningar (enligt lydelsen) skall vara framme senast den 2 januari,
antingen i lådan för inlämning vid expeditionen, Teknikringen 8,
eller skickade med papperspost till:
Bengt Ek
Matematik
KTH
100 44 Stockholm.
Mycket nöje med uppgifterna!
Inför tentan 11 januari 2018
Tentan to den 11 januari kommer att ha samma allmänna format som förra årets tentor, se här nere.
Bestämmelser blir enligt de nya tentamensreglerna, så (bl.a.):
- Icke föranmälda får skriva i mån av plats, men måste för att släppas in visa upp ett giltigt kursregistreringsbevis (kan fås via "Personliga menyn")
- Fotoleg är obligatoriskt utan undantag (det räcker inte längre att någon känner igen en)
- Den som kommer för sent får vänta till 8.30 för att komma in (senare släpps ingen in - tidigare gällde 45 minuter)
Glöm inte registreringsbevis enligt ovan om du vill skriva utan att vara anmäld!
Skrivningen omfattar innehållet i alla lektioner som varit, dvs det som finns i litteraturen se här (Biggs och extra material) och sådant som bara behandlats vid undervisningen (se sammanfattningarna här nere), t.ex. ordningsrelationer och välordning (lektion 6), Cantor och Cantor-Bernsteins satser (le 8), ramseytal, Ramseys sats (le 10), (Dirichlet-)faltning (le12), normala delgrupper (le 15), namnen för hörnföljder i en graf (le 18), kromatiska polynom, Kuratowskis och Wagners satser (le 19), Königs oändlighetslemma, kromatiskt index (le 20). Om logik, modeller, bevis, oändligheter etc kommer på skrivningen blir det inte om mer än vad som finns tillgängligt i extramaterialet (i kurslitteraturlistan) den 15 december.
Några referenser
På lektionen ti 28 november 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å lektionen to 30 november) kan man läsa "River crossing puzzle" i Wikipedia och söka på de namn för problemen som finns där.
Problem till 11 december
Listan med uppgifter för övning 6 har kommit. Finns att hämta här nere.
Lösningsförslag till hemuppgifter omgång 1
Lösningar har kommit (för ett tag sedan). Finns nu att hämta här nere.
Om semantisk följd och bevis
Bladen om bevis mm har kommit. Finns nu att hämta här nere.
Ett fel rättades, några beteckningar ändrades och motivering för diagonallemmat lades till to 7 december.
Om modeller och teorier
Bladen om modeller mm har kommit (i en preliminärt klar version). Finns nu att hämta här nere.
Om induktion och rekursion
Bladen om induktion mm har fått en ny version, finns nu att hämta här nere.
Hemuppgifter!
Den första omgången hemupgifter finns nu (äntligen) att hämta här nere.
Om kedjebråk
Bladen om kedjebråk mm finns nu att hämta här nere.
Kursen har kommit igång och vi har en kursnämnd!
Första lektionen utsågs Gustaf Forsman och Viktor Nilsson till kursnämndsrepresentanter, se här.
Välkommen till kursen!
Under den här rubriken kommer efter hand viktig information om kursen.
Tag för vana att gå in och läsa regelbundet.
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 kursen).
Vi använder egenregistrering, se Mattes studentexpeditions sida.
Registreringstiden gick ut redan to 2 november. Den som missat att registrera sig kan skriva expeditionen på samma sätt som den som skall omregistreras.

Viktiga tider

Hemuppgifter (se nedan under hemuppgifter), senaste inlämning:

omgång 1: må 4 december, kl. 12.00 i sal K51,
omgång 2: må 2 januari 2017.

Tentamina (för information om föranmälan se Mattes studentexpeditions sida, om salar se här):

ordinarie tentamen: torsdagen den 11 januari 2018 kl. 14.00-19.00, (anmälan 20 nov - 18 dec)
omtentamen: torsdagen den 5 april 2018 kl. 8.00-13.00, (anmälan 20 feb - 20 mar).

Vem är vem?

Kursledare:: Bengt Ek (bek@math.kth.se), tel. 790 6951, rum 3650 (på planet över entréplanet, Lindstedtsvägen 25 (under klocktornet)).
För frågor om registrering, inrapportering av betyg och liknande, se Studentexpeditionens sida. Med frågor rörande kursens innehåll bör man vända sig till lärarna.
Kursnämndsrepresentanter (utsågs den första lektionen):: Gustaf Forsman (skriv honom),
Viktor Nilsson (skriv honom).

Kursbeskrivning

Kursens betydelse

Denna kurs är valfri för F3.

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 datalogi, 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 (ren eller tillämpad) 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.

Kursens mål och innehåll

Se studiehandboken.

Förkunskaper

SF1604 Linjär algebra, 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!

Annat kursmaterial (ingår i kurslitteraturen!)

Lite om kedjebråk pdf
Kinesiska restsatsen pdf
RSA-kryptering och primalitetstest pdf
Om induktion och rekursion pdf (lite förnyad 21 november)
Om planära grafer pdf
Om modeller och teorier pdf
Om semantisk följd och bevis pdf
Om urvalsaxiomet mm pdf
Om ordinaltal och kardinaltal (pdf) (ofullständig)
Problem för övningarna kan man finna i lektionsplanen, här (det kan bli lite ändringar under kursens gång).
Svar och anvisningar kommer att läggas ut efter övningen.
Sammanfattningar och kommentarer till lektionerna kommer att läggas ut i planen för lektionerna, här nere.
De kommer ibland att innehålla material som inte tas upp i kursboken eller det övriga materialet.

Ytterligare material

Här finns (förhoppningsvis) lösningar till övningsexemplen i Biggs.
Innan du tittar på lösningarna, försök verkligen själv!
Tänk på att det ger mycket mer att läsa en lösning om man har försökt ordentligt själv.

Examination

Tentamina

En skriftlig tentamen, TEN1, 7,5hp.

Årets tentor:
11 januari 2018 pdf,    lösningar pdf
5 april 2018 pdf,    lösningar pdf

Förra årets tentor:
12 januari 2017 pdf,    lösningar pdf
12 april 2017 pdf,    lösningar pdf

Denna kurs gavs första gången förra året, men tidigare fanns en kurs SF2736, som gavs på engelska, med till största delen samma innehåll.
Förrförra årets tentor i den kursen:
13 januari 2016 pdf,    lösningar pdf
16 mars 2016 pdf,    lösningar pdf

Några äldre tentor (i SF2736) finns här.

Hemuppgifter

Under kursen ges möjlighet att lämna in hemuppgifter vid två tillfällen. Problemen finns här:
hemuppgifter omgång 1, till 4 december: (pdf), (svar och anvisningar: (pdf))
hemuppgifter omgång 2, till 2 januari 2018: (pdf). (svar och anvisningar: (pdf)).
Hemuppgifterna kan ge högst 4 bonuspoäng (2 poäng per omgång), vilka läggs till resultatet av del I på tentan i januari och omtentan i april 2018. Det totala antalet poäng på del I kan emellertid inte överstiga 15.
Sista inlämningstid (och -plats) för lösningar till hemuppgifterna anges här. Glöm inte att ange dina namn, personnummer och mejladress på lösningarna!
Det är tillåtet att diskutera problemen med andra deltagare i kursen, men inte att söka hjälp från andra håll (som t.ex. fora på internet). Var och en måste göra sina egna lösningar, avskrivning är inte tillåten och skulle betraktas som fusk.
Lösningarna skall lämnas in i handskriven form.

Betygsättning

Betyget på kursen ges av betyget på tentan (A, B, C, D, E eller F).

Lektioner

Lektionerna kommer dels att vara i form av föreläsningar, där teori och illustrerande exempel presenteras, och dels som övningar, där problem löses och diskuteras.
Övningar blir måndagar från 6 november - 11 december plus en halvövning onsdag 13 december, totalt sex stycken och en halv.
Problemen för varje övning finns i planen nedan. Kursdeltagarna bör studera problemen i förväg.

Plan för lektionerna (provisorisk)
Nr	Tid	Lokal	Innehåll	Att studera före lektionen	Samman- fattning
1	Må 30/10 10-12	U31	Inledning till kursen. Heltal, talbaser, delbarhet, sgd, Euklides algoritm, mgm. Kedjebråk och bästa approximation med rationella tal. rubriker	Biggs 8.1-5, Lite om kedjebråk (pdf)	pdf
2	Ti 31/10 15-17	E32	Den diofantiska ekvationen ax+by=c. Primtalsfaktorisering av positiva heltal. Modulär aritmetik, Z_m. rubriker	Biggs 8.5-6, 13.1-3	pdf
3	On 1/11 10-12	E53	Linjära ekvationer i Z_m, Kinesiska restsatsen. Ett kaninexempel lösning Eulers ϕ-funktion, Fermats och Eulers satser. rubriker om Z₁₅	Kinesiska restsatsen (pdf), Biggs 13.3	pdf
4	To 2/11 8-10	D34	RSA-kryptering. Felrättande koder. rubriker	Om RSA (pdf) Biggs 24.1-4	pdf
5	Må 6/11 10-12	U31	Övning 1.	Problem pdf	Svar pdf
6	Ti 7/11 15-17	M35	Mängder. Ekvivalensrelationer, partitioner. Partialordningar. Välordningar, ordinaltal. rubriker	Biggs 4.7, 7.2-3, 12.1-2	pdf
7	To 9/11 8-10	E31	Välgrundade relationer. Induktion och rekursion. Kungar och narrar. rubriker	Biggs 4.3-6, Om induktion (pdf)	pdf
8	Fr 10/11 8-10	M35	Funktioner, injektioner, surjektioner, bijektioner. Postfacksprincipen. Mängders kardinalitet. rubriker	Biggs 5, 6, 9.7	pdf
9	Må 13/11 10-12	U31	Övning 2.	Problem pdf	Svar pdf
10	Ti 14/11 15-17	E33	Kombinatorik: additions- och multiplikationsprinciperna. Ramseys sats och ramseytal. Ordnat urval. Binomialtal. Multinomialtal. rubriker	Biggs 10.1-2, 10.4-5, 11.1, 11.3	pdf
11	To 16/11 8-10	D41	Oordnat urval med upprepning. Stirlingtal (av andra slaget). Sållprincipen (principen om inklusion/exklusion). Funktionerna ϕ(n) och μ(n). rubriker	Biggs 10.3, 11.2, 11.4-5, 12.1, 12.3	pdf
12	Fr 17/11 13-15	U61	Möbius inversionsformel. Permutationer, permuterade skurkar. rubriker	Biggs 10.6, 11.5, 12.4-6	pdf
13	Må 20/11 10-12	E53	Övning 3.	Problem pdf	Svar pdf
14	Ti 21/11 15-17	E31	Grupper. Definition, exempel. Grundläggande egenskaper. Cykliska grupper. rubriker	Biggs 20.1-6	pdf
15	On 22/11 15-17	U21	Delgrupper. Sidoklasser och Lagranges sats. rubriker	Biggs 20.7-8	pdf
16	To 23/11 8-10	L51	Grupper som verkar på mängder. Burnsides lemma. rubriker	Biggs 21.1-6	pdf
17	Må 27/11 10-12	U31	Övning 4.	Problem pdf	Svar pdf
18	Ti 28/11 15-17	E52	Grafer, ex. om vargar och getter. Definitioner. Grundläggande egenskaper. Euler- och hamiltongrafer. Träd. rubriker	Biggs 15.1-5	pdf
19	On 29/11 10-12	E31	Graffärgningar. Planära grafer. Kromatiska polynom. rubriker	Biggs 15.6-7, Planära grafer (pdf)	pdf
20	To 30/11 8-10	D34	Kőnigs (oändlighets)lemma. Bipartita grafer, matchning i grafer. rubriker	Biggs 17.1-6	pdf
21	Må 4/12 10-12	K51	Övning 5.	Problem pdf	Svar pdf
INL1	Må 4/12 12.00	(K51)	Sista inlämning/-sändande av hemuppgifter, omgång 1.
22	Ti 5/12 15-17	E31	Genererande funktioner (formella potensserier). Antalet partitioner av ett positivt heltal. rubriker	Biggs 25.1, 25.4, 26.1-4	pdf
23	On 6/12 15-17	U21	Lite om matematisk logik. Språk, strukturer, axiomatisering, modeller. Ultrafilter och ultraprodukter. rubriker	Om modeller (pdf)	.
24	To 7/12 8-10	D34	Semantisk följd. Formella bevis. Gödels fullständighetssats. Gödels ofullständighetssats. rubriker	Om bevis (pdf)	.
25	Må 11/12 10-12	U31	Övning 6.	Problem pdf	Svar pdf
26	Ti 12/12 15-17	E35	Urvalsaxiomet, välordning, Zorns lemma. Kompakthetssatsen. Löwenheim-Skolems sats. rubriker	Om urvalsaxiomet mm (pdf)	.
27	On 13/12 15-17	E35	Ordinaltal, goodsteinföljder. Kardinaltal. Exempel på transfinit rekursion. rubriker	Om ordinaltal och kardinaltal (pdf) (ofullständig) Problem pdf	. Svar pdf
INL2	Ti 2/1-18		Sista inlämning/-sändande av hemuppgifter, omgång 2.
TEN1	To 11/1-18 14.00-19.00	Q36	Tenta
TEN1	To 5/4-18 8.00-13.00	Q15,17	Omtenta

För hemarbete rekommenderas

Biggs 4.3:2; 4.4:2; 4.5:3; 4.6:3; 4.7:1;
Biggs 5.2:1,2; 5.3:1; 5.4:2,3; 5.5:4;
Biggs 6.2:3; 6.4:2,3,5; 6.5:2,3; 6.6:3; 6.7:2;
Biggs 8.4:1,2,4 (finn alla sådana x,y); 8.6:3,5; 8.7:5,14;
Biggs 10.1:1,2; 10.2:1,3; 10.3:2; 10.4:2,3; 10.5:1,2,4; 10.6:1,2,3,4; 10.7:4,5,7;
Biggs 11.1:3,4,5,6,7; 11.2:2,3; 11.3:2,3; 11.4:1,2,5; 11.5:1,2,3,4; 11.8:3,5,6;
Biggs 12.1:1,2; 12.2:2,5; 12.3:1,2,5,6; 12.5:1,2,3,4; 12.6:1,2,3,4; 12.7:19;
Biggs 13.1:1,2,3; 13.2:1,3,4; 13.3:1,4,5,7,8;
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 mittenkuben?); 15.5:1,2,4; 15.6:1,2; 15.7:1,2,3; 15.8:8;
Biggs 17.1:2,3; 17.2:1,2,4; 17.4:1,2,3; 17.5:1; 17.6:1,3,4; 17.7:1(,9);
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; 20.8:1,2,3,4,5; 20.10:5,13;
Biggs 21.1:2,5; 21.2:2,4; 21.3:3; 21.4:1,2,3,4; 21.5:1,3,4; 21.6:2,3,4;
Biggs 24.1:1,2; 24.2:1,2,3,4; 24.3:1,2,3; 24.4:1,2,3,4;
Biggs 25.1:3,4; 25.4:2,3,4;
Biggs 26.1:4; 26.2:1,2,3; 26.3:1,2,3; 26.4:2,3;
Övningarna i extramaterialet (Kinesiska restsatsen etc.).