DISKRET MATEMATIK 2005-2006


Kursledare: Lars-Christer Böiers tel. 046-2228562.

Förkunskaper: Endimensionell analys 1-2 och Linjär algebra räcker.

Tid: Se schema för F1, Pi1, E2, D2, C3.

Omfattning: Kursen ges under lp 4 med två dubbeltimmar föreläsning och två dubbeltimmar övning i veckan samt några seminarieövningar.

Poäng: 4.

Litteratur:
Böiers: Diskret matematik, Studentlitteratur 2003
Böiers: Diskret matematik, övningsbok, Studentlitteratur 2003

Anmälan: Via KA-systemet.


Funktioner och relationer.
Funktionsbegreppet diskuteras noggrant och generaliseras till begreppet relation. Så kallade ekvivalensrelationer och ordningsrelationer är viktiga inom såväl matematik som tillämpade ämnen.
Kombinatorik.
I många sammanhang ställs frågor av typen ``hur många?''. (Hur många kodord finns i en given kod? Hur många jämförelser kräver en viss sorteringsalgoritm?) I kursen diskuteras olika metoder att lösa problem av detta slag, bl.a. den så kallade principen om inklusion/exklusion och metoden med genererande funktion.
Talteori.
Vi diskuterar delbarhetsrelationen för hela tal, primtal, diofantiska ekvationer, och framför allt det viktiga begreppet räkning modulo n. Talteori är av ovärderlig betydelse bland annat inom kodningsteori och kryptologi, men används även inom så vitt skilda områden som våglära (akustik, radar), kvantmekanik, optimering, musik, ...
Grafteori.
En graf kan lite slarvigt uppfattas som en geometrisk figur bestående av ett antal punkter (noder) av vilka en del är parvis förbundna med kurvor (bågar). Sådana förekommer mer eller mindre uttalat i de flesta vetenskaper: fysik, kemi, datalogi, elektroteknik, kommunikationsteknik, diverse samhällsvetenskaper. Vi studerar några klassiska men ändå aktuella problem. Kan man i en given graf finna en sluten väg som passerar varje nod exakt en gång, alternativt som passerar varje båge exakt en gång? Det senare hänger samman med det så kallade handelsresandeproblemet. Är det möjligt att rita en given graf i ett plan utan att några bågar korsas? Hur många färger fordras om man vill färga noderna i en graf så att grannar alltid får olika färg?


Lars Vretare