Sök Stäng

Diskret matematik

7,5 hp

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. Aspecter 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:
Projekt där studenten implementerar och testar enkla grafalgoritmer i ett valfritt programmeringsspråk t.ex. Python.

Utbildningstillfällen