Diskret matematik, 7,5 hp

Huvudområde med fördjupning

Programmering 7,5 hp. Engelska 6 eller Engelska nivå 2. Undantag ges för kravet på svenska, för dig med utländska betyg.

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 logik, grundläggande talteori, grundläggande kombinatorik, rekurrensrelationer, och grafteori samt frekvent förekommande grafalgoritmer som har betydelse inom datavetenskap. Studenten ska tillägna sig ett vetenskapligt förhållningssätt till logik, talteori 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 logik, grundläggande talteori, kombinatorik, rekurrensrelationer och grafteori
• diskutera de teoretiska och praktiska aspekterna av grafalgoritmer

Färdighet och förmåga

• använda grunderna i logik och talteori
• lösa enkla kombinatoriska problem med hjälp av permutationer, kombinationer och variationer
• lösa rekkurensrelationer
• 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

Logik, bevis och grundläggande talteori:
Logik: negation, konjunktion, disjunktion, implikation, bi-implikation (ekvivalens), de Morgans lag, kvantifikatorer, delbarhet, modulär aritmetik, aritmetikens fundamentalsats, induktionsbevis.

Kombinatorik och rekurrensrelationer:
Grundläggande kombinatorik: permutationer, kombinationer, variationer. Principen om inklusion/exklusion. Aspekter inom rekurrensrelationer: aritmetiska och geometriska talföljder, linjära inhomogena rekurrensrelationer med konstanta koefficienter, simultana rekurrensrelationer.

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:
Enkla grafalgoritmer i ett valfritt programmeringsspråk t.ex. Python (implementatering och testing).

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.