Matematik GR (B), Diskret matematik, 7,5 hp

Syfte

Den studerande skall under kursen förvärva fördjupade kunskaper och färdigheter inom den diskreta matematiken, med speciell tonvikt på kombinatorik, permutationer och grafteori.

Lärandemål

Efter avslutad kurs skall studenten kunna:
- redogöra för definitioner av begrepp och använda dessa för att analysera och tolka frågeställningar inom kursens samtliga huvudområden,
- lösa problem med hjälp av relevant teori, metodik och algoritmer inom kursens samtliga huvudområden,
- redogöra för bevis av ett urval av satser, och
- kommunicera med ett exakt matematiskt språk och presentera tydliga, välorganiserade lösningar med korrekta logiska argument.

Innehåll

Huvudområde 1: Tal och mängder

Repetition av grundläggande mängdlära, logik, mängden av naturliga tal och funktionsbegreppet. Mängden av heltal, delbarhet, primtal. Introduktion till algoritmer, komplexitet och ordo-begreppet (Big O).

Huvudområde 2: Relationer och modulär aritmetik

Introduktion till relationer, ekvivalensrelationer, ekvivalensklasser och partitioner av mängder. Kongruenser och modulär aritmetik.

Huvudområde 3: Kombinatorik och permutationer

Räkning av element, storleken av en mängd och kardinalitetsbegreppet. Kombinatorisk räkning, Eulerfunktionen och klassificering av permutationer. Binomialtal, sållprincipen och partitioner av heltal.

Huvudområde 4: Grafteori med algoritmer

Definitioner och grundläggande satser om grafer, vägar och cykler. Färgning av grafer. Introduktion till träd och algoritmer för sortering och sökning. Uppspännande träd, viktade grafer och algoritmer för minimalt uppspännande träd. Bipartita grafer, matchningar och transversalitet. Riktade grafer, flöde och snitt samt satsen om max-flöde, minsta-snitt.

Behörighet

Matematik 22,5 hp inklusive minst 3 hp linjär algebra.

Urvalsregler

Urval sker i enlighet med Högskoleförordningen och den lokala antagningsordningen.

Undervisning

Föreläsningar och övningar

Examination

I101: Inlämningsuppgifter, 1,5 hp
Betygsskala: Tvågradig skala

T101: Skriftlig tentamen, 6 hp
Betygsskala: Sju-gradig skala, A-F o Fx
Frivilliga aktiviteter kan ingå under kursens gång och kan generera bonuspoäng som läggs till poängen på tentamen (T101). Aktiviteter och bonussystem beskrivs i så fall utförligt i kursmiljön. Eventuella bonuspoäng gäller max ett år från kursstart på det kurstillfälle där de frivilliga aktiviteterna ingår.

Länk till betygskriterier: https://www.miun.se/betygskriterier.

Om en student har ett besked från samordnaren vid Mittuniversitetet om pedagogiskt stöd vid funktionsnedsättning, har examinator rätt att ge anpassad examination för studenten.

Begränsning av examination

Studenter registrerade på denna version av kursplan har rätt att examineras 3 gånger inom loppet av 1 år enligt angivna examinationsformer. Därefter gäller examinationsform enligt senast gällande version av kursplan.

Betygsskala

Sju-gradig skala, A-F o Fx

Övrig information

Kan ej ingå i samma examen som MA095G eller MA098G.