Kursen innehåller tekniker för enumeration av urval med och utan upprepning, samt med och utan hänsyn till ordning. Exempel på detta ges i form av permutationer, kombinationer, binomialsatsen och så kallade staketproblem. Kursen innehåller vidare Stirlingtal, sållningsprincipen och brevlådeprincipen. Sambanden med surjektioner och partitioner ges. Metoder för att lösa enklare rekursioner av första ordningen och av andra ordningens linjära rekursioner med konstanta koefficienter. Kursen innehåller också en genomgång av grundläggande satslogik och kvantifikatorer. Grundläggande talteori gås igenom i form av den största gemensamma delaren, Diofantiska ekvationer och aritmetikens fundamentalsats. Kursen innehåller också tillämpningar inom grafteorin, detta i form av isomorfi, sortering och träd, Dijkstras algoritm, Kruskal och Prims algoritm, flöden i nätverk med max-minsatsen och Ford-Fulkersons algoritm.
Förväntade studieresultat
Efter avslutad kurs ska studenten kunna
- använda binomialtal, stirlingtal, rekursionsekvationer och sållningsprincipen för att lösa enumerationsproblem med och utan upprepning samt med och utan hänsyn till ordning.
- avgöra om två uttryck är ekvivalenta i satslogiken och använda kvantifikatorer.
- redogöra för den grundläggande talteorin och lösa problem för delbarhet och primtal.
- tillämpa kombinatoriska grafer, riktade grafer och multigrafer för att modellera och lösa följande optimeringsproblem: att hitta den kortaste vägen i en riktad graf, att hitta ett minimalt uppspännande träd, att bestämma ett maximalt flöde i ett nätverk.
- tillämpa teorin för träd för att beskriva och analysera sorteringsalgoritmer, och för att omvandla till och från polsk notation.
Behörighetskrav
För tillträde till kursen krävs Ma D (områdesbehörighet 8 med ett eller flera undantag)
Undervisningens upplägg
Undervisningen bedrivs i huvudsak i form av föreläsningar och lektionsundervisning.
Examination
Kunskapsredovisningen sker i form av skriftliga prov. På de skriftliga proven ges något av betygen Underkänd (U), Godkänd (G) eller Väl godkänd (VG). På hela kursen ges något av betygen Underkänd (U), Godkänd (G) eller Väl godkänd (VG). Betyget utgör en sammanfattande bedömning av resultaten vid examinationens olika delar och sätts först när alla obligatoriska moment är godkända. Den som godkänts i prov får ej undergå förnyat prov för högre betyg.
Ett omprov ska erbjudas senast tre månader efter ordinarie provtillfälle, dock ska omprov erbjudas tidigast tio arbetsdagar efter det att resultatet av det ordinarie provet har meddelats och kopia av studentens tentamen är tillgänglig. Dessutom skall minst ytterligare ett omprov erbjudas inom ett år från ordinarie provtillfälle, s.k. uppsamlingsprov.
I de fall prov eller obligatoriska undervisningsmoment inte kan upprepas enligt gällande regler för omprov och ompraktik kan det istället ersättas med annan uppgift. Omfattningen av och innehållet i sådan uppgift skall stå i rimlig proportion till det missade obligatoriska momentet.
En student som utan godkänt resultat har genomgått två prov för en kurs eller en del av en kurs, har rätt att få en annan examinator utsedd, om inte särskilda skäl talar emot det (HF 6 kap. 11b §). Begäran om ny examinator ställs till prefekten för institutionen för matematik och matematisk statistik.
Examination baserad på denna kursplan garanteras under minst två år efter studentens förstagångsregistrering på kursen.
Tillgodoräknande av del av kurs beslutas av betygsättande lärare. Tillgodoräknande av hel kurs beslutas av kanslichefen för Umeå School of Education (USE). Blankett för tillgodoräknande www.umu.se/blankett/SA
Tillgodoräknande prövas alltid individuellt (se universitetets regelsamling och tillgodoräknandeordning).
Diskret matematik och diskreta modeller. n D. 1 Eriksson Kimmo, Gavel Hillevi Lund : Studentlitteratur : 2002 : ix, [1], 355 s. : ISBN: 91-44-02465-7 Obligatorisk Se Umeå UB:s söktjänst
Ross Sheldon M. Topics in finite and discrete mathematics Cambridge : Cambridge University Press : 2000 : 265 s. : ISBN: 0-521-77259-1 (hb) ; CIP entry Obligatorisk Se Umeå UB:s söktjänst
Grimaldi Ralph P. Discrete and combinatorial mathematics : an applied introduction 5. ed. : Boston, Mass. : Addison-Wesley : 2004 : 833, 32, 91, 24 s. : ISBN: 0-321-21103-0 (international ed.) Se Umeå UB:s söktjänst
