Diskret matematik

Mål

• Modellera och lösa problem genom att använda begrepp och metoder i kombinatorik, rekursion, mängdlära samt relationer och avbildningar.
• Tillämpa talteori och grafteori genom projektarbete
• Kommunicera skriftligt och muntligt lösningar genom att använda relevanta matematiska begrepp och metoder i kursen, samt ha kännedom om tillämpningar.

Innehåll

Kursen består av två delar: Del 1 på 4 hp, och Del 2 på 2 hp

Del 1:

• Kombinatorik: Permutationer och kombinationer. Principen för inklusion och exklusion med tillämpningar i modellering. Duvslagsprincipen. Mängder
• Relationer och avbildningar för effektivt räknande.
• Rekursion: Rekursiva ekvationer och avbildningar. Linjära rekursiva ekvationer och system av linjära rekursiva ekvationer

Del 2:

• Talteori: Delbarhet och linjära diofantiska ekvationer. Modulär aritmetik.
• Grafer: Grundläggande begrepp i grafer: Grafer och nätverk, träd, bipartita grafer, planära grafer, färgningar.

Observera att tillämpningar av talteori och grafer examineras genom projektet, som innehåller verkliga tillämpningar. Exempel på sådana projekt: RSA-kryptering, kryptering för blockkedjor, matchningar och optimering (samhälleliga tillämpningar), fylogenetiska träd, beslutsträd, kromatiska tal och komplexitet av algoritmer, grannmatriser och dataöverföring.