Inledande diskret matematik IT HT06


Kursansvarig:   Laura Fainsilber

Kolla denna sida då och då.  Den uppdateras under kursens gång.

  NYHETER

Kursens tenta 061221 finns att ladda ner här . Lösningar finns här.

Om du har allmänna frågor om kursen, avsnitt eller uppgifter du inte förstår, säg till, så försöker jag ta upp det vid sammanfattningen v.50.

En sida med fler elementära kombinatoriska principer

Julklappstips : Simon Singhs böcker: Fermats Enigma eller Kodboken

Allt om primtal: The prime Pages

Mer om kryptering och RSA hos företaget RSA Security

Björn von Sydows presentation om kryptering (stor pdf-fil)

Några enklare övningar om kapitel 6 och 7 : finns här (pdf) (ingen facit, tyvärr.)

En länk om att : skriva bevis (pdf)

Vad säger Google om Fibonacci?

Utvärderare för kursen är Fredrik Portström (epost: portstro) och Sofie Kores (kores) epostadressen domän student.chalmers.se

Instruktioner till måndagarna: Att hitta på egna uppgifter

Instruktiva och roliga logiklänkar: felaktiga bevis och att dra logiska slutsatser

 

  Tider

Föreläsningar: Tisdagar kl 13-15 i HC3, varannan torsdag kl 13-15 i  samt fredagar 13-15.
Övningar: Tisdagar kl 15-17  och fredagar kl 10-12.
Gruppövningar: Måndagar kl 13-16 i rum 3207, 3209, 3211, 3213, 5205, 5207, 5209.

  Litteratur och kursinnehåll

Johan Jonasson och Stefan Lemurell, Algebra och diskret matematik , Studentlitteratur, 2004. Kan köpas på Cremona.

I kursen ingår avsnitten 1-3 (utom 3.9) och 6--9 (inkl hela kap 9)

Referenslitteratur:
Det finns många kursböcker på engelska med namn "Discrete Mathematics" eller liknande. 
De kan ge andra infallvinklar på materialet. Följande finns till exempel på Chalmers e-bibliotek:
Hein "Discrete Structures, logic, and computability"
 
direkt länk

  Lektionsledare och gruppindelning

 

 Föreläsningar: Laura Fainsilber, laura@math.chalmers.se

Övningsgrupp 1: Oscar Marmon, oscar.marmon@math.chalmers.se

Övningsgrupp 2: Ragnar Freij, freij@math.chalmers.se

Övningsgrupp 3: Andreas Andreasson, andreas.andreasson@filosofi.gu.se

Måndagshandledning: Laura Fainsilber, Oscar Marmon

 
 

  Program

Tempot i matematikundervisningen är högt. Det är viktigt att du kommer igång med att studera teorin och lösa uppgifter genast. Det är ett misstag att tro att man klarar att läsa in kursen veckan före tentamen! Läs igenom de avsnitt som tas upp på föreläsningarna i förväg, så blir det betydligt enklare att följa med och veta vad som eventuellt behöver antecknas. Försök räkna igenom uppgifterna före övningstillfället och fråga på de uppgifter du inte klarar. Utnyttja övningsledarna!

Kursen byggs upp kring tre teman ; (1) Logik, mängdlära, funktioner och relationer, (2) Heltalsaritmetik, (3) Kombinatorik och grafer. Till varje tema hör en temaföreläsning där några tillämpningar och teorin bakom dem presenteras översiktlig av en inbjuden talare. Till detta läggs fyra ''vanliga'' föreläsningar där teorin gås igenom mer detaljerat. Under övningarna tränar vi på den matematiska teorin, dels genom att handledarna demonstrationsräknar vid tavlan, dels genom egen verksamhet. Den egna verksamheten kommer att ske i grupper om 4-5 studenter. Här arbetar man dels med uppgifterna i boken, dels med veckans veckoblad. På varje veckoblad finns tre så kallade kryssuppgifter specificerade. Vid sista övningstillfället varje vecka kryssar man individuellt, på en lista, för de kryssuppgifter man löst på ett sådant sätt att man anser sig kunna redovisa lösningen. Övningshandledaren kommer sedan för varje kryssuppgift att på måfå välja ut en i varje basgrupp som redovisar lösningen. Den som vid kursens slut har kryssat för minst 15 (resp. 11) av de sammanlagt 21 kryssuppgifterna erhåller vid kursens slut 4 (resp. 2) bonuspoäng på tentan. Under måndagsövningarna arbetar vi huvudsakligen med att konstruera egna uppgifter. Tanken med detta är man själv ska ikläda sig lärarrollen, vilket kräver en djup förståelse av kursinnehållet. Detta görs gruppvis i samma grupper som på övningarna. Varje grupp konstruerar två uppgifter per tema, inklusive lösningar, och testar dem på en annan grupp. Uppgifterna bedöms och poängsätts; en bra uppgift som gärna är av teoretisk karaktär ger höga poäng medan en ''vanlig'' övningsuppgift stulen ur en bok ger låga poäng. Deadlines för inlämning av de egenkonstruerade uppgifterna med lösning är tisdag den 14/11, tisdag den 28/11 respektive tisdag den 12/12. För detta arbete kan man sammanlagt erhålla upp till 4 bonuspoäng på tentan.

  Schema för föreläsningarna

  Allteftersom kursen framskrider markeras avklarat material med grönt.

Dag

Plan (approximativ)

Avsnitt

30/10

Kursintroduktion. Argument och bevis.

1.1-1.6, 2.1-2.4

31/10

Predikatlogik.  Funktioner.  Variabler

1.7-1.9, 3.1-3.4

3/11

Relationer.

3.6-3.9

7/11

Ekvivalensrelationer. Partiella ordningar,

 6.1-6.2

9/11

Motsägelsebevis, Induktion, rekursion

 6.3-6.4

10/11

Temaföreläsning 1: Catarina Coquand: Om hård- och mjukvaruvalidering.  

 

14/11

  Heltalsaritmetik börjar, delbarhet, division med rest

 Kap 7.1

17/11

Euklides algoritm, diofantiska ekvationer, primtal

7.2, 7.3

21/11

Temaföreläsning 2: Björn von Sydow: Om kryptering

 

23/11

primtal, kongruensräkning

7.2, 7.4

24/11

Kinesiska restsatsen, Eulers phi-funktion

7.5, 7.6

28/11

Mer om primtal och algoritmer

Kap 7

1/12

Kombinatorik börjar:multiplikationsprincipen, permutationer

Kap 8

5/12

Temaföreläsning 3: Niklas Eriksen Kombinatorik: Släktforskning för bakterier

 

7/12

Additionsprincip, lådprincip

Kap 8, stencil

8/12

grafer och träd

9.1-9.4

12/12

grafer och träd -- Sammanfattning

Kap 9

15/12

Sammanfattning.

 

21/12

Tentamen, förmiddag i M-huset.

 

  Schema för övningarna : se veckoblad för varje vecka

Boken innehåller inte fler övningar än att man under kursens gång bör kunna räkna igenom dem alla.

Veckoblad:

  Gamla tentor