Diskret matematik¶
En kurswiki för SF1610 Diskret matematik (KTH), organiserad kring de sju områden som tentamen hämtar sina uppgifter från.
Var du börjar¶
Om du repeterar inför tentamen är den snabbaste vägen områdessidorna — var och en anger de definitioner och satser du förväntas kunna återge, ger den gängse algoritmen eller receptet, och löser ett exempel hämtat från en riktig tentamen.
Vill du veta hur tentamen faktiskt ser ut — uppdelningen i tre delar, betygsgränserna, och varför presentationen ger poäng — läs Tentamen först.
De sju områdena¶
| Område | Typiska tentauppgifter |
|---|---|
| Logik, mängder och relationer | Uppräknelighetsbevis, ekvivalensklasser, sanningstabeller, DNF/KNF |
| Talteori och kryptografi | Diofantiska ekvationer, modulära inverser, RSA-nyckelgenerering |
| Kombinatorik och sannolikhet | Räkning med komplement, stjärnor och streck, Stirlingtal |
| Grafteori | Euler/Hamilton, planaritet och Eulers formel, isomorfi |
| Gruppteori | Lagranges sats, cykelnotation, delgrupper till \(S_n\) |
| Induktion | Delbarhet, summationsformler, olikheter |
| Kodningsteori | Linjäritet, minsta avstånd, feldetektering och felrättning |
En anmärkning om hur kursen bedöms¶
Varje tentamen upprepar samma varning, så den är värd att ta på allvar:
För full poäng på en uppgift krävs att lösningen är väl presenterad och lätt att följa. Det innebär speciellt att införda beteckningar definieras, att den logiska strukturen tydligt beskrivs i ord eller symboler och att resonemangen är väl motiverade och tydligt förklarade.
Ett korrekt slutsvar utan synligt resonemang ger som högst två poäng av fyra. Det mesta dessa sidor visar dig är hur argumentet skrivs ner, inte bara vad svaret är.
Beteckningar som används genomgående¶
Matematik renderas med KaTeX, både i löpande text som \(\gcd(15, 17) = 1\) och som block:
| Symbol | Betydelse |
|---|---|
| \(\mathbb{Z}_n\) | Heltalen modulo \(n\) |
| \(\mathbb{Z}_n^{\times}\) | Enheterna (inverterbara element) modulo \(n\) |
| \(\mathcal{P}(A)\) | Potensmängden av \(A\) |
| \(\lvert A \rvert\) | Kardinaliteten av \(A\); även ordningen av en grupp |
| \(\langle g \rangle\) | Delgruppen genererad av \(g\) |
| \(S_n\) | Symmetriska gruppen på \(\{1, \dots, n\}\) |
| \(\delta(C)\) | Minsta avståndet för en kod \(C\) |