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 Matematik D eller Matematik 4 (områdesbehörighet 9/A9 med ett eller flera undantag) eller motsvarande.
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 (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5). På hela kursen ges något av betygen Underkänd (U), Godkänd (3), Icke utan beröm godkänd (4) eller Med beröm godkänd (5). 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.
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 styrelsen 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
Tillgodoräknande prövas alltid individuellt (se universitetets regelsamling och tillgodoräknandeordning).
Litteratur
Giltig från:
2013 vecka 3
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.) Obligatorisk Se Umeå UB:s söktjänst
