Kursplan

Kursplan för: Matematik GR (B), Diskret matematik, 7,5 hp

Mathematics BA (B), Discrete Mathematics, 7.5 Credits

Allmänna data om kursen

Kurskod: MA105G
Ämne huvudområde: Matematik
Nivå: Grundnivå
Progression: (B)
Namn (inriktning): Diskret matematik
Högskolepoäng: 7,5
Fördjupning vs. Examen: G1F - Kursen ligger på grundnivå och fordrar mindre än 60 hp kurs(er) på grundnivå som förkunskapskrav.
Utbildningsområde: Naturvetenskap 100%
Ansvarig avdelning: Avdelningen för ämnesdidaktik och matematik
Inrättad: 2007-01-18
Fastställd: 2010-01-18
Senast ändrad: 2013-06-26
Giltig fr.o.m: 2013-07-01

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 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 både färgade och ofärgade 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, färgningar
- Några grafteoretiska algoritmer: uppspännande träd och kortaste vägar.

Behörighet

Matematik GR (A): Algebra och diskret matematik, 7,5 hp eller Introduktion till diskret matematik, 7,5 hp eller Diskret matematik A, 6hp

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

Examination sker vanligen med skriftlig tentamen. Inlämningsuppgifter och/eller muntlig tentamen kan förekomma.

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

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.

Litteratur

Obligatorisk litteratur

Biggs, Discrete Mathematics, Oxford University Press, 2nd ed., ISBN 0-19-850718-6