Välkommen till kursen! 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.

Material

• Föreläsningsmanuskript: Introduktion
• Wikipedia-artiklar Bubbelsortering, Triangeltal och Tidskomplexitet

Denna enhet består av två föreläsningar:

Föreläsningen om logik 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 sanningsvärdestabeller, och grundläggande begrepp såsom satisfierbarhet och tautologi. I slutet av föreläsningen ges en (mycket kort) introduktion till predikatlogik.

Föreläsningen om mängder ger 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 standardnotationer inom mängdläran, om begreppet delmängd och om operationer på mängder: union, snitt, differens och komplement.

Material

• Föreläsningsmanuskript: Logik och mängder
• Övningsuppgifter: Logik och mängder, facit
• Wikipedia-artiklar Satslogik och Predikatlogik

Innehåll

Efter denna enhet ska du kunna förklara följande koncept:

• sats och predikat
• logiska operationer och sanningsvärdestabeller
• satisfierbarhet, tautologi, kontradiktion
• mängd
• relationer mellan mängder, operationer på mängder
• venndiagram

Efter denna enhet ska du kunna utföra följande procedurer:

• avgöra om en sats är satisfierbar
• avgöra om en sats är en tautologi eller en kontradiktion
• avgöra om två satser är logiskt ekvivalenta
• beskriva en mängd genom uppräkning och med mängdbyggare
• rita ett venndiagram för en mängd

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 talföljder, summor och olikheter.

• Föreläsningsmanuskript: Rekursion och induktion
• Övningsuppgifter: Rekursion och induktion, facit
• Wikipedia-artiklar Matematisk induktion och Riskornen på schackbrädet

Innehåll

Efter denna enhet ska du kunna förklara följande koncept:

• talföljd, element
• rekursiv formel, sluten formel
• aritmetisk talföljd, aritmetisk summa
• geometrisk talföljd, geometrisk summa

Efter denna enhet ska du kunna utföra följande procedurer:

• översätta mellan en rekursiv och en sluten formel
• räkna med aritmetiska talföljder och aritmetiska summor
• räkna med geometriska talföljder och geometriska summor
• genomföra enkla induktionsbevis

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.

• Föreläsningsmanuskript: Talteori
• Övningsuppgifter: Talteori, facit
• Wikipedia-artikel RSA

Innehåll

Efter denna enhet ska du kunna förklara följande koncept:

• kvot, rest, kongruens
• delbarhet, delbarhetsregler
• primtal, Eratosthenes’ såll
• största gemensamma delare, Euklides’ algoritm

Efter denna enhet ska du kunna utföra följande procedurer:

• simulera Eratosthenes’ såll
• simulera Euklides’ algoritm

Föreläsningen om sannolikhetsteori repeterar grundläggande begrepp från gymnasiet. Som nya begrepp introduceras betingad sannolikhet och Bayes’ lag. 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äsningsmanuskript: Kombinatorik och sannolikhet
• Övningsuppgifter: Kombinatorik och sannolikhet, facit
• Wikipedia-artiklar träddiagram och Bayes sats

Innehåll

Efter denna enhet ska du kunna förklara följande koncept:

• utfall, händelse, Kolmogorov-axiomen
• slumpförsök i flera steg, träddiagram
• betingad sannolikhet, Bayes’ lag
• permutation, kombination, binomialkoefficient

Efter denna enhet ska du kunna lösa textuppgifter genom att

• använda räkneregler för träddiagram och Bayes’ regel
• använda formler för att beräkna antalet möjligheter inom ramen för urnmodellen

En graf är en struktur som består av noder (”punkter”) 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.

• Föreläsningsmanuskript: Grafteori
• Övningsuppgifter: Grafteori, facit
• Wikipedia-artiklar Königsbergs sju broar och Handelsresandeproblemet

Innehåll

Efter denna enhet ska du kunna förklara följande koncept:

• graf, grad
• väg, cykel, sammanhang
• Eulergraf, Hamiltongraf
• träd, uppspännande träd

Efter denna enhet ska du kunna utföra följande procedurer:

• avgöra om en graf är en Eulergraf
• hitta en väg i en viktad graf med hjälp av närmaste grannen-metoden
• hitta ett uppspännande träd i en graf

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. Som exempel på sådana metoder presenteras Newtons metod för att approximera nollställen till en funktion och gradientsökning, tekniken som driver många aktuella maskininlärningsalgoritmer.

Denna föreläsning består 2023 endast av förinspelat material och fysisk föreläsning uteblir.

• Föreläsningsmanuskript: Numeriska metoder
• Motivering till numeriska metoder
• Wikipedia-artiklar Newtons metod, Fast inverse square root, och Gradient descent

Innehåll

Efter denna enhet ska du kunna förklara följande koncept:

• Newtons metod
• gradientsökning

Efter denna enhet ska du kunna utföra följande procedurer:

• tillämpa Newtons metod för att approximera nollställen till en funktion
• tillämpa Newtons metod för att approximera kvadratroten till ett tal