Göm menyn

TDP015 Grunder i matematik och logik

Föreläsningar


Kursintroduktion

Föreläsningens första timme presenterar kursens mål, upplägg och organisation. Den andra timmen ger en introduktion till matematikens roll i datalogin. Det konkreta exemplet som vi tittar på är hur man räknar ut antalet jämförelseoperationer i bubbelsorteringsalgoritmen. Detta leder till triangeltalen och motiverar varför man behöver matematiska bevis.

Enhet 1: Logik

Denna enhet är en introduktion till logik. Den introducerar satslogikens klassiska logiska konnektiv såsom konjunktion och implikation, en procedur för hur man bevisar ekvivalenser mellan logiska uttryck med hjälp av sanningstabeller och boolesk algebra, och grundläggande begrepp såsom satisfierbarhet och tautologi. I slutet av enheten nämns predikatlogik.

Enhet 2: Mängdlära

Denna enhet är en introduktion till de mest grundläggande koncepten inom mängdlära. Den handlar om mängdbegreppet, om hur man kan specificera mängder, om begreppet delmängd och om operationer på mängder: union, snitt, differens och komplement. I slutet på enheten introduceras begreppet ”funktion” samt några viktiga egenskaper hos funktioner: injektivitet, surjektivitet och bijektivitet.

  • Föreläsningsmanuskript
  • Material om funktioner ur Jonasson och Lemurell (skickas ut via epost)
  • Wikipedia-artikel Russells paradox
  • Övningsuppgifter finns i föreläsningsmanuskriptet och i materialet ur Jonasson och Lemurell

Enhet 3: Rekursion och induktion

Denna enhet introducerar induktionsbevis och förklarar hur de hänger ihop med rekursiva definitioner. Precis på samma sätt som man i en rekursiv funktion litar på att de rekursiva anropen gör jobbet antar man i ett induktionsbevis att man redan bevisat ett påstående för mindre värden. Vi går igenom induktionsbevis om rekursiva talföljder, aritmetiska summor och olikheter.

Enhet 4: Talteori

I denna enhet går vi igenom grundläggande talteoretiska begrepp: delbarhet, primtal, Euklides algoritm för att beräkna den största gemensamma delaren för två tal och heltalsdivision. Talteori har tillämpningar bl.a. inom kryptoanalys.

Enhet 5: Numeriska metoder

Det finns många matematiska problem för vilka man inte kan hitta en exakt lösning, eller där att hitta en sådan lösning vore alltför kostsamt. I samband med sådana problem är man intresserad i tekniker för att approximera lösningar. Dessa tekniker kallas numeriska metoder. I denna föreläsning lär vi känna Newtons metod för att approximera nollställen till en funktion.

Enhet 6: Grafteori

En graf är en struktur som består av noder (”prickar”) och bågar (”sträck”). Grafteori har tillämpningar vid optimeringsproblem. Till exempel kan varje nod eller båge i en graf innebära en viss kostnad. Med hjälp av grafalgoritmer kan man då bestämma den minsta totalkostnaden. I det här kursavsnittet introduceras några vanliga begrepp, problem och enklare tillämpningar inom grafteorin.

Enhet 7: Kombinatorik och sannolikhetsteori

Inom kombinatoriken härleder vi formler för hur man räknar i olika sammanhang: med eller utan återläggning, med eller utan hänsyn tagen till ordning. Centrala begrepp är permutation, kombination och binomialkoefficient. Föreläsningen om sannolikhetsteori repeterar grundläggande begrepp från gymnasiet men introducerar även två nya räkneregler: lagen om total sannolikhet och Bayes lag.


Sidansvarig: Marco Kuhlmann
Senast uppdaterad: 2017-05-15