Diskret matematik, 7,5 hp

Huvudområde med fördjupning

Programmering 7,5 hp. Engelska 6.

Kursen ges inom programmet Tillämpad artificiell intelligens (AI) 180 hp. Kursen ges även som fristående kurs.

Kursens mål är att studenten utvecklar en förståelse och kunskap relaterad till grundläggande kombinatorik, sannolikhet och grafteori samt frekvent förekommande grafalgoritmer som har betydelse inom datavetenskap. Studenten ska tillägna sig ett vetenskapligt förhållningssätt till sannolikhetsteori och grafteori samt befästa och utveckla sina förkunskaper i ämnet.

Efter avslutad kurs ska studenten kunna:

Kunskap och förståelse

• definiera och redogöra för innebörden av de centrala begreppen inom kombinatorik, sannolikhetsteori och grafteori
• diskutera de teoretiska och praktiska aspekterna av grafalgoritmer

Färdighet och förmåga

• lösa enkla kombinatoriska problem med hjälp av permutationer, kombinationer och variationer
• tillämpa lösningsmetoder för att beräkna sannolikheter
• identifiera grundläggande typer av grafer som Eulergraf, Hamiltongraf, planär, träd etc
• genomlysa verkliga konkreta problem och översätta dessa till matematiska modeller

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

• föreslå och värdera lämpliga matematiska modeller för tillämpade problem inom kursens område
• kritiskt granska modellval och beräkningsresultat

Kombinatorik och sannolikhetsteori:
Grundläggande kombinatorik: permutationer, kombinationer, variationer. Principen om inklusion/exklusion. Sannolikhetslärans aspekter: stokastisk variabel, betingad sannolikhet, oberoende händelser, Bayes sats, väntevärde.

Grafteori och grafalgoritmer:
Definitioner och egenskaper för olika typer av grafer: enkel, oriktade/riktade, träd, planär, Eulergraf och Hamiltongraf, spännträd, Handelsresandeproblemet TSP (Travelling salesman problem) etc. Djup-först-sökning DFS (Depth First Search) och Bredd-först-sökning BFS (Breadth First Search), Dijkstras, Prims och Kruskals algoritmer.

Modellering:
Projekt där studenten implementerar och testar enkla grafalgoritmer i ett valfritt programmeringsspråk t.ex. Python.

Undervisningen organiseras i form av föreläsningar, övningar och individuellt projektarbete. Studenten får även handledning under projektarbetet.

Kursen examineras genom skriftlig individuell tentamen samt såväl skriftlig som muntlig redovisning av projektarbetet.

Om särskilda skäl finns får examinator göra undantag från angiven examinationsform och medge att en student examineras på annat sätt. Särskilda skäl kan till exempel vara beslut om riktat pedagogiskt stöd.

I kursen ingår kursvärdering. Denna är vägledande för utveckling och planering av kursen. Kursvärderingen dokumenteras och redovisas för studenterna.