Diskret Matematik 7,5 hp, VT 2012

Föreläsare/Examinator

Johan Andersson , epost: jander@dsv.su.se.

Nyheter Maj-Juni

Tentamina

Första tentamen gick bra för de flesta som skrev. 20 studenter skrev och 16 blev godkända (2 A, 3 B, 3 C, 6 D, 2 E). Poänggränser för betyg var följande F:0-13, Fx:14-16, E:17-20, D:21-24, C:25-28, B:29-32, A:33-36. Detta motsvarar ungefär (för några betygsgränser mindre justering) Fx:40%, E:50%, D:60%, C:70%, B:80%, A:90%. Jag har skrivit ett Lösningsförslag . Första omtentamen som skrevs gick även bra för er som skrev den.

Angående omtentamen i Augusti.

För er som ännu inte klarat tentamen kursen så kommer det finnas en andra omtentamen och en ny möjlighet i Augusti. Exakt datum verkar inte vara bokat. Jag återkommer.

Angående ny deadline för inlämningsuppgifter.

Jag kommer även att ha ytterligare en deadline för inlämningsuppgifterna (restuppgifterna) för er som ännu inte fått godkänt på inlämningsuppgiftsdelen av kursen i samband med omtentan i Augusti. En muntlig presentation kommer då också att inplaneras. Exakt datum för deadline och presentation meddellas senare.

Restuppgifterna som ni behöver göra är följande: Inlämning 1, rest , Inlämning 2, rest , Inlämning 3, rest . Inlämningsuppgifterna skall skickas till min epost address jander@dsv.su.se. Det går dock bra att skriva för hand och scanna in eller ta bilder av uppgifterna med digitalkamera.

Notera att om ni redan klarat motsvarande ordinarie omgång inlämningsuppgifter så behöver ni inte göra den omgången restuppgifter. Ni som har klarat en omgång vet om det. Ni har redan gjort en muntlig presentation och fått godkänt av mig.

Nyheter Tisdagen den 13:e Mars

Jag har samlat en del gammalt och nytt kursmaterial (egen exempeltenta + lösningsförslag omgång 1) nedan:

Inlämningsuppgifter + Lösningsförslag

Inlämning 1 , med lösningsförslag . Inlämning 2 , med lösningsförslag . Inlämning 3 . med lösningsförslag .

Tentor

Här ligger förra årets tentamen på kursen , med Thorbiörnsons lösningsförslag . Jag har också skrivit en egen exempeltenta, med svar/ledningar på vissa av uppgifterna. För fullständiga lösningsförslag rekommenderas att ni tittar på mina lösningsförslag för Inlämning 1-3 ovan.

Gamla nyheter

Måndagen den 5:e Mars

Många av er är redan klara med ordinare inlämningsuppgifter.

För er andra har jag nu även konstruerat restuppgifter för Inlämning 3. Ni har två veckor på er om ni vill bli klara med kursen i samband med ordinarie tentamen (För närmare instruktioner, se uppgiftsbladet).

Fredagen den 2:a Mars

Vi är klara med ordinare föreläsningar på kursen. Jag har dock bokat in handledning på Torsdag vecka 10 och Onsdag vecka 11 mellan kl 13 och 15. Det är Simon Ottervald som skall handleda. Dessutom har jag bokat in en extra repetitionslektion på Måndag v11 mellan 13 och 16 med mig själv. Vi har också redovisningar nu på Måndag för de som lämnade in inlämning 3 i tid. Jag har konstruerat restuppgifter för Inlämning 1 och restuppgifter för inlämning 2 för de av er som vet med er att ni missade första omgången. Omgång 3 återkommer jag till i början av nästa vecka. Även ni som klarat tidigare uppgifter kan använda er av restuppgifterna för repetition. Lösningsförslag för ordinarie Omgång 2 finns nedan. Lösningsförslag för omgång 1 återkommer jag till. Titta igenom lösningsförslagen för ordinare omgång av inlämningsuppgifterna så kan det hjälpa när ni skall lösa restuppgifterna eftersom en del uppgifter liknar varandra.

Måndagen den 27:e Februari

Vi är nu väsentligen klara med kursen innehållsmässigt. De återstående två föreläsningarna tänkte jag använda till repetition. Jag delade idag ut förra årets tentamen på kursen . Jag har dessutom skrivit ett lösningsförslag till Omgång 2 av inlämningsuppgifterna . Lösningsförslag till omgång 1 (och omgång 3 självklart) återkommer jag till.

Handledning

Jag har efter förslag från er studenter infört handledning på kursen. Den andra handledningsomgången ska ske nu på Onsdag den 29:e Februari kl 10-12 i Seminarierum 6202. Simon Ottervald som har gått kursen tidigare är den som kommer att handleda.

Onsdagen den 22:a Februari

Grafteorin och matriskapitlet har gått lite snabbare än min ursprungsplanering.Detta innebär att vi andra timmen idag påbörjade rekursion och induktion, och att vi nästa vecka kommer att få tid över till repetition.

Idag lämnade jag ut sista sista inlämningsuppgiften . Ni har en vecka på er.

Onsdagen den 15:e Februari

Idag gick vi igenom kapitel 5.2 (Promenader i grafer, Eulerspår, Eulerkretsar) och kapitel 5.3 i kursboken (Dijkstras algoritm).

Mer om grafteorin Som jag nämnde på föreläsningen i Måndags finns det ett mindre fel i kursboken TOG, Definition 5.9 av grafer. Strängt taget så är det riktad graf som Thorbiörnson definierar. I en graf som inte är riktad så beskrivs inte bågarna (eller kanterna) av ordnade talpar (a,b), utan av mängderna {a,b} där a och b är hörn i grafen. För alternativa varianter av beviset av Teorem 5.24 om Euler-kretsar och Euler-spår se exempelvis en sida från Umeå Universitet , eller följande artikel från nämnaren . Dessa länkar beskriver också bättre algoritmen för hur vi faktiskt kan hitta ett Euler-spår (eller en Euler-krets). Detta gick vi igenom på föreläsningen idag, och det är någonting ni bör kunna.

Fredagen den 10:e Februari

Vi är nu klara med kapitel 3 och 7 i Träd och Grafer. Idag gick vi igenom Boolesk algebra. Nästa vecka börjar vi med grafteori (planeringen ändrad och vi går igenom grafteorin innan rekursion och induktion för att bättre synka med ALDA-kursen). Kom ihåg att göra omgång två av inlämningsuppgifterna tills på Onsdag.

Måndagen den 6:e Februari

Idag har vi jobbat med avsnitt 3.3, 3.4, samt 3.6 i kursboken (TOG). Jag har konstruerat en ny omgång inlämningsuppgifter . Inlämnas senast Onsdag nästa vecka.

Fredagen den 3:e Februari

Vi har påbörjat de muntliga examinationerna av Inlämning 1. Vi fortsätter på Måndag. Idag började vi med relationer och på föreläsningen idag så gick vi igenom sektion 3.1 och 3.2 i Träd och Grafer. Läs igenom de avsnitten och försök er på uppgifterna! Vi fortsätter med relationskapitlet på Måndag.

Torsdagen den 2:e Februari

Igår slutförde vi talteorin. Vi pratade litegrann om komplexitetsteori , framförallt om tidskomplexitet och ordo, omega och theta-notationen. Vi gick också igenom Karatsubas algoritm för att multiplicera heltal. Av intresse är att tidskomplexiteten hos den metoden är O(nlog(3)/log(2) )=O(n1.585 ) för multiplikation av två tal vardera med n siffror. Detta är bättre än "skolboksmultiplikationen" som har tidskomplexsitet O(n2). Vi gick också igenom hur RSA-metoden för kryptering fungerar och om varför den fungerar. Här dyker Euklides algoritm upp igen liksom i många delar av talteoriavsnittet. Euklides algoritm skall ni kunna såväl framlänges som baklänges.

Allmänt om talteoridelen. Vi har under talteoridelen använt oss av både Bergström och Träd och Grafer (Kapitel 2, samt 3.4 - vi återkommer lite till 3.4 när vi betraktar kongruenser som exempel på en ekvivalensrelation). Allt i Bergström utom Sats 2.10 om rationella rötter ingår. Exempel 2.3.4 är det viktigt att ni förstår (Jag gick också igenom det på föreläsningen i måndags). Alla uppgifter i TOG kan göras samt alla i Bergström utom uppgift 18,27,28.

Fredagen den 27:e Januari

Onsdag och Fredag den här veckan har vi jobbat med talteori (TOG, 2.1-2.2 + Kongruensaritmetik). I Bergström så motsvarar det även där avsnitt 2.1-2.2, samt avsnitt 2.3.4. Till skillnad från kursboken så föredrog vi att använda kongruensnotationen från början när det gäller rester (jämför avsnitt 3.4 i TOG). Ni kan läsa igenom de avsnitten i kursboken (när det gäller avsnitt 3.4 i TOG så handlar det även om ekvivalensrelationer. Vi kommer till det senare i kursen!) och lösa tillhörande övningsuppgifter. Sista halvtimmen idag påbörjade vi även avsnitt 2.3 i Träd och Grafer, med ett exempel på Euklides algoritm. Läs gärna igenom det avsnittet i kursboken så blir det lättare när vi fortsätter med det på Måndag. Talteorin beräknas avslutas nästa vecka.

Måndagen den 23:e Januari

Vad har vi gjort hittills: Än så länge så har vi följt den preliminära kursplaneringen. Måndagen och Torsdagen vecka 3 gick vi igenom mängdläran. På Fredagen gick vi igenom kombinatorik. På Måndagen vecka 4 slutförde vi kombinatoriken, och sista halvtimmen påbörjade vi talteorin som smått.

Länkar till kombinatorikdelen. På måndagen vecka 4 gick vi igenom fler kombinatorikexempel, till exempel pokerhänder, se exempelvis Antal händer av de olika slagen eller Poker - kombinationer och sannolikheter . Vi pratade också om antalet lösningar av ekvationer av typen x_1+...+x_n=m där x_k är naturliga tal och m heltal. För mer information om dessa problem och annan kombinatorik se exempelvis En not från Lund (mer omfattande) eller Föreläsningar från Växjö. För en alternativ beskrivning av multiplikationsprincipen se till exempel En not från Uppsala. För fler övningsuppgifter se även Uppgifter från Uppsala.

Inlämningsuppgifter

Första inlämningsuppgiften delades ut. Den skall lämnas in skriftligt senast Onsdagen den 1:a Februari. Notera att även om vi kommer kommer ha en muntlig examination på inlämningsuppgiften (Fredagen den 3:e Februari eller Måndagen den 6:e Februari) gruppvis så skall uppgifterna lösas enskilt. Grupper för examination kommer att meddelas senare.

Undervisningsformer

Undervisningen kommer att bestå av 21 st Föreläsningar/Lektioner på Måndagar, Onsdagar och Fredagar vecka 3-9, kl 13-1445 enligt schema.

Kurslitteratur

Som kurslitteratur så kommer vi att använda: Thorbiörnsons bok [TOG] skall gå att köpa på kårbokhandeln inom kort. Logic, Basics & Beyond har använts som kurslitteratur i tidigare kurs, så den kanske ni redan har. Övrigt material kan komma att delas ut under kursens gång.

Alternativ kurslitteratur, länkar på nätet

Det finns många böcker/lecture notes som kan användas som brevidläsningslitteratur

Kursinnehåll

Kursen behandlar området diskret matematik: teori för strukturer som består av åtskilda objekt. Kursen presenterar begrepp och resultat inom följande områden: Genomgående under kursen tränas förmågan att hantera matematiska beskrivningar och att kommunicera tankegångar med hjälp av matematiska beteckningar.

Preliminär Kursplanering

(Uppdaterad 10:e Februari)

Officiella kursmål - Hämtat från kursplanen

Kursens övergripande mål är att ge nödvändiga baskunskaper och förståelse av matematiska begrepp samt beräkningsmetoder och skrivsätt som kan tillämpas inom IT-området. Efter genomförd kurs förväntas studenten kunna:

Examination

Kursen kommer att examineras på två sätt.

Kursinformation i pdf-format