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

Syfte

Den studerande skall under kursen tillägna sig grundläggande kunskaper och färdigheter i diskret matematik, i synnerhet de grenar som är av särskilt intresse i datavetenskapliga tillämpningar.

Lärandemål

Efter avslutad kurs skall studenten
- kunna visa någon förtrogenhet med mängder och elementära kombinatoriska metoder till att räkna mängders kardinalitet, i synnerhet inklusions-exklusions principen och lådprincipen
- kunna visa insikter om heltalen och heltalen modulo n och i synnerhet kunna visa någon förtrogenhet med Euklides algoritm och problem där denna kan användas
- visa förtrogenhet med grafteoretisk terminologi för grafer samt digrafer
- kunna beskriva några grafteoretiska samband samt använda någon grafteoretisk algoritm såsom t.ex. Kruskals eller Dijkstras algoritm
- i enkla fall kunna avgöra om en relation är en ekvivalensrelation eller inte
- kunna utföra enkla logiska resonemang och enkel matematisk argumentation både skriftligt och muntligt
- visa någon förtrogenhet med bevis, i synnerhet induktionsbevis och elementära motsägelsebevis

Innehåll

- Satslogik, logiska resonemang och matematisk argumentation
- Ekvivalensrelationer, partitioner
- Elementär talteori, delbarhet, Euklides algoritm, rekursion, moduloräkning
- Kombinatorik
- Introduktion till komplexitet av algoritmer
- Inledande grafteori, t ex enkla grafer och elementära grafteoretiska samband, träd och tillämpningar samt digrafer.
- Några grafteoretiska algoritmer t ex uppspännande träd och kortaste vägar.

Behörighet

Matematik GR (A), Algebra med funktionslära, 7,5 hp eller Algebra och geometri, 7,5 hp.

Urvalsregler

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

Undervisning

Självstudier och lärarledda sammankomster, eventuellt kombinerade med andra undervisningsformer.

Examination

R200: Muntlig och skriftlig redovisning, 1,5 hp
Betygsskala: Underkänd (U) eller Godkänd (G)

T200: Skriftlig tentamen, 6,0 hp
Betygsskala: På kursen ges något av betygen A, B, C, D, E, Fx och F. A - E är Godkänt, Fx och F är underkänt.
Frivilliga aktiviteter i form av test (quiz), inlämningsuppgifter och dugga ingår. Dessa schemalagda aktiviteter kan generera bonuspoäng som läggs till poängen på tentamen (T200). Bonuspoängen gäller max ett år från kursstart på det kurstillfälle där de frivilliga aktiviteterna är schemalagda. Hur bonussystemet fungerar beskrivs utförligare i kursmiljön.

De examinerande momenten beskrivs tydligare i kursmiljön.

Slutbetyget baseras på en sammanvägd bedömning av hur väl de olika momenten klarats av.

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

Betygskriterier för ämnet finns på www.miun.se/betygskriterier.

Begränsning av examination

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

Betygsskala

På kursen ges något av betygen A, B, C, D, E, Fx och F. A - E är Godkänt, Fx och F är underkänt.