Kursplan - Grafteori, nätverk och tillämpningar
Omfattning
7.5 hp
Kurskod
MAA600
Giltig från
Hösttermin 2024
Utbildningsnivå
Avancerad nivå
Successiv fördjupning
A1N (Avancerad nivå, har endast kurs/er på grundnivå som förkunskapskrav).
Huvudområde(n)
Matematik/Tillämpad matematik
Akademi
Akademin för utbildning, kultur och kommunikation
Fastställd
2014-03-05
Reviderad
2023-12-12
Litteraturlistor
Kurslitteraturen är preliminär till 8 veckor innan kursstart. Kurslitteratur kan vara giltig över flera terminer.
Syfte
Syftet med kursen är presentera de centrala begreppen och analysmetoderna inom grafteori, samt att i ett sammanhang av detta utveckla förmågan att hantera logik, algoritmer, modellering och beräkningar på ett givande sätt.
Lärandemål
Efter avklarad kurs ska studenten kunna
- korrekt redogöra för de grundläggande exemplen, idéerna och begreppen inom grafteori
- tillämpa grundläggande grafteoretiska satser
- algoritmer för att lösa vissa standardproblem inom grafteorin
- formulera allmänna matematiska problem i grafteoretiskt språk
- använda standardomformuleringar av grafteoretiska problem för att göra dem algoritmiskt lättare att lösa
- inom datavetenskap och informationsteknik tillämpa grafteoretiska begrepp och metoder
Innehåll
- Enkla grafer, multigrafer, pseudografer och digrafer
- Stigar, cykler, sammanhängande och avstånd
- Algoritmer för att beräkna kortaste avstånd i grafer
- Träd, bipartita grafer och andra elementära grafklasser
- Matchning
- Algoritm för att hitta matchningar i bipartita grafer
- Hörn- och kantfärgning
- Nätverk och flöden
- Representationer av grafer och algoritmiska aspekter
Undervisning
Föreläsningar och lektioner med arbete enskilt och i grupp.
Särskild behörighet
120 hp inom teknik, naturvetenskap eller ekonomi varav minst 60 hp inom teknik och naturvetenskap inklusive 30 hp matematik/tillämpad matematik vari ingår Vektoralgebra, grundkurs, 7,5 hp, samt Diskret matematik, 7,5 hp, eller motsvarande.
Dessutom krävs Svenska 3/Svenska B samt Engelska 6/Engelska A. I de fall kursen ges på engelska görs undantag från kravet på Svenska 3/Svenska B.
Examination
Tentamen (TEN2), 4 högskolepoäng, betyg 3, 4 eller 5
Projekt (PRO1), 3,5 högskolepoäng, betyg 3, 4 eller 5
En student som har ett intyg från MDU avseende sin funktionsnedsättning har möjlighet att anmäla önskemål om anpassning vid salstentamina eller annan examinationsform i enlighet med Regler och anvisningar för examination på grundnivå och avancerad nivå vid Mälardalens högskola (2020/1655). Det är examinator som, utifrån det intyg som utfärdats, beslutar om eventuell anpassning och i så fall vilken anpassning som ska gälla.
Misstankar om vilseledande vid examination (fusk) anmäls, enligt högskoleförordningen, till universitetets rektor och prövas av universitetets disciplinnämnd. Om disciplinnämnden anser att en student gjort sig skyldig till en disciplinförseelse fattar nämnden beslut om en disciplinär åtgärd, vilket är varning eller avstängning.
Betyg
Med beröm godkänd, icke utan beröm godkänd, godkänd, underkänd