Matematik GR (A), Diskret Matematik A, 6 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 enkla 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 visa någon förtrogenhet med bevis, i synnerhet induktionsbevis och elementära motsägelsebevis.

Innehåll

- Satslogik, logiska resonemang
- Ekvivalensrelationer, partitioner
- Elementär talteori, delbarhet, Euklides algoritm, rekursion, moduloräkning
- Kombinatorik
- Introduktion till komplexitet av algoritmer
- Inledande grafteori: träd och tillämpningar
- Några grafteoretiska algoritmer: uppspännande träd och kortaste vägar

Behörighet

Matematik GR (A), Algebra, 3 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

T101: Skriftlig tentamen, 6 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 (T101). 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.

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

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

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.