Inledande diskret matematik IT HT05


Kursansvarig: Docent Johan Jonasson

OBS! INGEN UNDERVISNING MÅNDAG DEN 24 OKTOBER. KURSEN INLEDS MED FÖRELÄSNINGEN KL 8.00 TISDAG DEN 25 OKTOBER.

DET ÄR AV STÖRSTA VIKT ATT MAN OFTA KOLLAR OCH TAR DEL AV DEN INFORMATION SOM FINNS PÅ DENNA SIDA FÖR ATT PÅ SÅ SÄTT KOMMA VÄL FÖRBEREDD TILL UNDERVISNINGEN.

  NYHETER

  Tider

Föreläsningar: Tisdagar kl 8-10 i HC1 och torsdagar kl 10-12 i HC3 samt onsdagar i lv 2, 4 och 6 i VA.
Övningar: Tisdagar kl 10-12 i ML 4,13,15 och torsdagar kl 13-15 i ML4-6.
Gruppövningar: Måndagar kl 13-16 i rum 5205-5211 och 6205-6215.

  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 5-8 och delavsnitten 1-4 av kapitel 9.

  Tryckfel

  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 gruppen som redovisar lösningen. Den som vid kursens slut har kryssat för minst 15 av de sammanlagt 21 kryssuppgifterna erhåller vid kursens slut 4 bonuspoäng på tentan. Under gruppö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. 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 8/11, tisdag den 22/11 respektive tisdag den 6/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 Stoff Avsnitt
25/10 Påståenden och logiska operationer. Tautologi och ekvivalens. 1.1-1.6
27/10 Argument och bevis. Predikatlogik. Mängder. 1.7-1.8, 2.1-2.4
1/11 Funktioner och relationer. 3.1-3.6
2/11 Temaföreläsning 1: Catarina Coquand: Om hård- och mjukvaruvalidering.  
3/11 Ekvivalensrelationer. Partiella ordningar. 3.7-3.8
8/11 Induktion. 6.1
10/11 Rekursion. Motsägelsebevis. 6.2-6.3
15/11 Delbarhet. Divisionsalgoritmen och Euklides algoritm. 7.1-7.2
16/11 Primtal och aritmetikens fundamentalsats. Diofantiska ekvationer. 7.2-7.3
17/11 Kongruensräkning. 7.4
22/11 Temaföreläsning 2: Björn von Sydow: Om kryptering.  
24/11 Kinesiska restsatsen. Eulers phi-funktion. 7.5-7.6
29/11 Temaföreläsning 3: Niklas Eriksen: Kombinatorik: Släktforskning för bakterier. 7.6, 8.1-8.2
30/11 RSA-krypto. Multiplikationsprincipen. Permutationer.  
1/12 Kombinationer. Binomialsatsen och Pascals triangel. Grafer 8.3, 9.1
6/12 Grafer och riktade grafer. Eulervägar och Eulercykler. 9.1-9.4
8/12 Sammanfattning.  
16/12 Tentamen, förmiddag i V-huset.  

  Schema för övningarna

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

Veckoblad:

  Gamla tentor

Dessutom finns det en samling övningsuppgifter inför tentan. Dessa kommer man åt genom att klicka här. Vill man se lösningar till (de flesta av) de uppgifterna kan man göra det genom att klicka här.

  Tentamina

Vid tentamen är inga hjälpmedel tillåtna. Tentamen kommer att omfatta 50 poäng och för betyget 3 krävs minst 25 poäng, för betyget 4 minst 35 poäng och för betyget 5 minst 45 poäng.
Rättade tentor återfås på Mottagningen för matematik i Matematiskt centrum. Öppettiderna är må-fr 12.00-13.00.
Kontrollera att Du har fått rätt betyg och att poängsumman stämmer. Eventuella klagomål på rättningen ska lämnas skriftligt.

  Lektionsledare och gruppindelning

Gruppövningar rum 5205-5211, 6205: Johan Jonasson
Gruppövningar rum 6207-6215: Carl-Henrik Fant, chf@math.chalmers.se
Övningsgrupp 1: Oscar Marmon, md0osmar@math.chalmers.se
Övningsgrupp 2: Johan Berglind, johanbe@math.chalmers.se
Övningsgrupp 3: Andreas Andreasson, andreas.andreasson@filosofi.gu.se

Johan Jonasson <jonasson@math.chalmers.se>
Last modified: Mon Oct 17 09:00:00 MET DST 2005