Diskret matematik, 7,5 hp

Innehåll

Kursen behandlar ett urval teman ur området diskret matematik.

Modul 1 (6.5 hp): Teori
Inom området enumerativ kombinatorik fördjupas behandlingen av induktion och rekursion samt räknetekniker för olika kombinatoriska objekt. I gränslandet mellan talteori och mängdlära behandlas den hierarkiska uppbyggnaden av talsystem baserat på den axiomatiska grunden för de naturliga talen. I anslutning till denna uppbyggnad behandlas funktioner och relationer i allmänhet, och ekvivalensrelationer i synnerhet.

Begreppet algoritm presenteras och analyseras med särskilt fokus på korrekthet och effektivitet. Exempel tas här i första hand från sortering och grafteori. Inom grafteoriområdet behandlas också grundläggande teoretiska resultat och klassiska problem med en översikt över tillämpningar.
 
Modulen avslutas med en introduktion till abstrakt algebra, där begreppen grupp, ring och kropp behandlas, och de välbekanta talsystemen samt moduloräkning sätts in i detta sammanhang.

Modul 2 (1 hp): Laborationer
I den laborativa modulen används digitala verktyg för att genomföra beräkningar med grund i kursens teoriinnehåll. Detta omfattar programmering i språket Python.

Förväntade studieresultat

För godkänd kurs ska den studerande kunna:

Kunskap och förståelse

• redogöra för den axiomatiska uppbyggnaden av talsystem
• redogöra för generaliserade former av induktion och rekursion
• redogöra för grundläggande grafteori
• redogöra för grundläggande begrepp i abstrakt algebra

Färdighet och förmåga

• tillämpa mer avancerade kombinatoriska principer för enumeration
• lösa de optimeringsproblem som behandlats i kursen
• lösa enkla rekursionsekvationer
• utföra beräkningar och hantera definitioner i grundläggande abstrakt algebra
• formulera och implementera pseudokod för sorterings- och grafalgoritmer samt skriftligt kommunicera lösningar

Värderingsförmåga och förhållningssätt

• analysera ett urval sorteringsalgoritmer och grafalgoritmer med avseende på korrekthet och komplexitet

Behörighetskrav

För tillträde till kursen krävs en kurs i algebra om minst 7,5 hp i vilket ska ingå talteori och kombinatorik eller motsvarande kunskaper.

Undervisningens upplägg

Undervisningen bedrivs i huvudsak i form av föreläsningar och lektionsundervisning samt handledning av datorlaborationer.

Examination

Examinationen på modul 1 sker genom skriftliga prov. Examinationen på modul 2 sker genom skriftlig laborationsrapport. På modul 1 sätts något av omdömena Underkänd (U), Godkänd (G) eller Väl godkänd (VG). På modul 2 sätts endast omdömet Underkänd (U) eller Godkänd (G). För att bli godkänd på hela kursen krävs att samtliga examinerande delar är godkända och betyget på kurs avgörs av omdömet på modul 1. På hel kurs ges något av betygen Underkänd (U), Godkänd (G) eller Väl godkänd (VG).

Avsteg från kursplanens examinationsform kan göras för en student som har beslut om pedagogiskt stöd på grund av funktionsnedsättning. Individuell anpassning av examinationsformen ska övervägas utifrån studentens behov. Examinationsformen anpassas inom ramen för kursplanens förväntade studieresultat. Efter begäran av studenten ska kursansvarig lärare, i samråd med examinator, skyndsamt besluta om anpassad examinationsform. Beslutet ska sedan meddelas studenten.

Den som godkänts i prov får ej undergå förnyat prov för högre betyg. Ett omprov ska erbjudas senast två 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. 22 §). Begäran om ny examinator ställs till prefekten för institutionen för matematik och matematisk statistik.

Tillgodoräknande
Student har rätt att få prövat om tidigare utbildning eller motsvarande kunskaper och färdigheter förvärvade i yrkesverksamhet kan tillgodoräknas för motsvarande utbildning vid Umeå universitet. Ansökan om tillgodoräknande skickas in till Studentcentrum/Examina. Mer information om tillgodoräknande finns på Umeå universitets studentwebb, www.student.umu.se, och i högskoleförordningen (6 kap). Ett avslag på ansökan om tillgodoräknande kan överklagas (Högskoleförordningen 12 kap) till Överklagandenämnden för högskolan. Detta gäller såväl om hela som delar av ansökan om tillgodoräknande avslås.

Övriga föreskrifter

I en examen får denna kurs ej ingå tillsammans med en annan kurs med likartat innehåll. Vid osäkerhet bör den studerande rådfråga studierektorn i matematik och matematisk statistik.

I de fall kursplanen upphör att gälla eller genomgår större förändringar erbjuds minst tre provtillfällen (inklusive ordinarie provtillfälle) enligt föreskrifterna i den ändrade eller nedlagda kursplanen.