Kursen behandlar 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. Vidare behandlas 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 behandlar 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
För godkänd kurs ska den studerande kunna
Kunskap och förståelse • redogöra för den grundläggande talteorin
Färdighet och förmåga • lösa problem för delbarhet och primtal. • 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. • 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.
Värderingsförmåga och förhållningssätt • kritiskt granska, egna eller andras, matematiska resonemang
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
Examinationen sker genom skriftliga prov. På skriftliga prov ges något av betygen Underkänd (U), Godkänd (G) eller Väl godkänd (VG). För att bli godkänd på kursen krävs att samtliga examinerande delar är godkända. Betyget utgår från en sammanfattande bedömning av resultaten vid examinationens olika delar och sätts först när alla delar är godkända.
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 ett ytterligare omprov erbjudas inom ett år från ordinarie provtillfälle, så kallat uppsamlingsprov. I de fall då 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. 22 §). 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 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
