Områden¶

Kursen delas i sju områden. De väger inte lika tungt på tentamen, och de är inte oberoende — modulär aritmetik ligger till grund för både RSA och linjära koder, och gruppteorin förklarar i tysthet varför båda fungerar.

Läsordning¶

Sidorna är skrivna för att läsas i den här ordningen, och senare sidor förutsätter de tidigare:

Logik, mängder och relationer — vokabulären som allt annat uttrycks i. Ekvivalensrelationer återkommer som sidoklasser i gruppteorin; uppräknelighet är ett återkommande problem i del C.
Talteori och kryptografi — Euklides algoritm och dess följder: diofantiska ekvationer, modulära inverser, Fermats lilla sats, RSA.
Kombinatorik och sannolikhet — att räkna noggrant, och den handfull standardmodeller som finns (permutationer, stjärnor och streck, Stirlingtal).
Grafteori — grader, sammanhang, Euler och Hamilton, träd, planaritet.
Gruppteori — axiomen, Lagranges sats, cykliska grupper, permutationer.
Induktion — en bevismetod snarare än ett ämne, men examineras i egen rätt.
Kodningsteori — linjära koder, som samtidigt är delgrupper till \((\mathbb{Z}_2)^n\) och en tillämpning av allt ovan.

Hur områdena hänger ihop¶

\(\mathbb{Z}_n\) är både en grupp under addition och, inskränkt till sina enheter \(\mathbb{Z}_n^{\times}\), en grupp under multiplikation. RSA är Fermats lilla sats tillämpad på den andra.
Ekvivalensrelationer partitionerar en mängd i klasser. Kongruens modulo \(n\) är en ekvivalensrelation, och dess klasser är precis elementen i \(\mathbb{Z}_n\). Lagranges sats är samma idé: sidoklasser partitionerar en grupp.
En linjär kod är en delgrupp till \((\mathbb{Z}_2)^n\), vilket är varför \(\lvert C \rvert\) alltid är en tvåpotens — det är Lagranges sats igen.
Räkning dyker upp inuti grafteorin (gradsummor), gruppteorin (delgruppers ordning) och kodningsteorin (hur många ord som ligger inom avstånd \(t\)).

Om ett bevis känns som att det behöver ett verktyg du inte fått, kontrollera om någon av dessa kopplingar är den avsedda vägen.