Diskret matematikk: gratis øving, teori og oppgaver

1. Logikk og mengder

Hva handler det om?

Datamaskiner er bygget på logikk: sant og usant, og og eller. Mengder er måten matematikken samler ting på. Begge deler dukker opp overalt i programmering, databaser og digitale kretser.

Begreper og formler

• Utsagnslogikk: $\neg p$ (ikke), $p \wedge q$ (og), $p \vee q$ (eller), $p \rightarrow q$ (hvis … så).
• $p \rightarrow q$ er bare usann når $p$ er sann og $q$ er usann.
• De Morgans lover:

• Kontraposisjon: $p \rightarrow q$ er ekvivalent med $\neg q \rightarrow \neg p$.
• En sannhetsverditabell med $n$ variabler har $2^n$ rader.
• Mengder: union $A \cup B$ (i A eller B), snitt $A \cap B$ (i begge), komplement.
• Inklusjon–eksklusjon:

• En mengde med $n$ elementer har $2^n$ delmengder (potensmengden).

Slik løser du oppgavene

1. Logikk: lag en sannhetsverditabell, eller bruk De Morgan og kontraposisjon.
2. Telling med overlapp: legg sammen og trekk fra det som er telt to ganger.
3. «Ingen av delene»: totalt minus unionen.

Eksempel

40 studenter: 25 tar matte, 18 tar fysikk og 10 tar begge. Hvor mange tar ingen av dem?

1. $|M \cup F| = 25 + 18 - 10 = 33$.
2. Ingen av dem: $40 - 33 = 7$.

Vanlige feil

• Å tro at $p \rightarrow q$ er usann når $p$ er usann. Et løfte er ikke brutt hvis betingelsen ikke inntreffer.
• Å glemme å trekke fra snittet og dermed telle noen to ganger.
• Å forveksle den omvendte ($q \rightarrow p$) med kontraposisjonen.

Begreper i denne delen

Øv på logikk og mengder i appen →

2. Kombinatorikk

Hva handler det om?

Hvor mange passord finnes? Hvor mange måter kan et lag velges på? Kombinatorikk er systematisk telling. Det brukes i sannsynlighet, sikkerhet (hvor lang tid tar det å gjette et passord?) og algoritmer (hvor mange tilfeller må sjekkes?).

Begreper og formler

• Multiplikasjonsprinsippet: $a$ valg etterfulgt av $b$ valg gir $a\cdot b$ muligheter.
• Ordnede utvalg med tilbakelegging: $n^k$ (for eksempel en PIN-kode).
• Permutasjoner: $n$ ting i rekkefølge: $n! = n\cdot(n-1)\cdots 1$.
• Ordnet utvalg uten tilbakelegging (rekkefølgen betyr noe):

• Kombinasjoner (rekkefølgen betyr ikke noe):

• Håndhilsninger mellom $n$ personer: $\binom{n}{2} = \dfrac{n(n-1)}{2}$.

Slik løser du oppgavene

1. Spør: betyr rekkefølgen noe? Kan samme ting velges flere ganger?
2. Rekkefølge og gjentak: $n^k$. Rekkefølge uten gjentak: $P(n,k)$. Uten rekkefølge: $\binom nk$.

Eksempel

8 løpere kjemper om gull, sølv og bronse. Hvor mange mulige pallplasseringer finnes?

1. Rekkefølgen betyr noe, og ingen kan få to medaljer.
2. $P(8,3) = 8\cdot 7\cdot 6 = 336$.

Vanlige feil

• Å bruke kombinasjoner når rekkefølgen betyr noe (eller omvendt).
• Å glemme at $0! = 1$.
• Å legge sammen når valgene skal ganges.

Begreper i denne delen

Øv på kombinatorikk i appen →

3. Grafer og modulregning

Hva handler det om?

En graf er noder (punkter) koblet med kanter (linjer). Veinett, datanettverk, venner i sosiale medier og avhengigheter mellom programmoduler er alle grafer. Modulregning er «klokkeregning» med rester, og brukes i hashing, kryptering og kontrollsifre.

Begreper og formler

• Grad til en node: antall kanter som går ut fra den. Håndhilselemmaet:

• Komplett graf $K_n$ (alle koblet til alle) har $\dfrac{n(n-1)}{2}$ kanter.
• Et tre er en sammenhengende graf uten sykler. Et tre med $n$ noder har nøyaktig $n - 1$ kanter.
• Eulerkrets (bruk hver kant nøyaktig én gang og kom tilbake): finnes når grafen er sammenhengende og alle noder har partall grad.
• Korteste vei i en vektet graf: Dijkstras algoritme. Utvid alltid fra den nærmeste noden du ikke har ferdigbehandlet.
• Modulregning: $a \bmod m$ er resten når $a$ deles på $m$. For eksempel $17 \bmod 5 = 2$.

Slik løser du oppgavene

1. Tell kanter via gradene: summer og del på 2.
2. For trær og komplette grafer: bruk formlene.
3. Korteste vei: prøv alle rimelige ruter i små grafer, eller følg Dijkstra.

Eksempel

Kanter: A–B (4), A–C (1), C–B (2), B–D (5), C–D (8). Korteste vei fra A til D?

1. A–C–B koster $1 + 2 = 3$, som er billigere enn A–B direkte (4).
2. Videre B–D: $3 + 5 = 8$. Alternativet A–C–D koster $1 + 8 = 9$.
3. Korteste vei er A–C–B–D med lengde 8.

Vanlige feil

• Å glemme å dele gradsummen på 2.
• Å tro at den direkte kanten alltid er kortest.
• Å bruke negative rester: i matematikken er $a \bmod m$ alltid mellom 0 og $m - 1$.

Begreper i denne delen

Øv på grafer og modulregning i appen →