Øvelser 1:
Kombinatorik og sandsynlighedsteori
I skal lave øvelserne inden timerne torsdag. I kan med fordel lave dem i grupper og diskutere dem indbyrdes. Det er vigtigt, at I forstår opgaverne og kan forklare dem til hinanden. På torsdag diskuterer vi opgaverne, og I skal være klar til at præsentere dem for klassen.
Øvelse 1: Repetition af boolesk algebra¶
Betragt den booleske funktion \(F(x, y, z)=x y+y(z+x)\).
a. Angiv sandhedstabellen for denne funktion. Hvis tabellen er konstrueret korrekt, vil den sidste kolonne indeholde \(F\) og have 8 rækker. Ved at læse rækkerne fra bunden og op får du en binær værdi. Konverter denne værdi til decimal og angiv dette som dit resultat. (1)
- 200
b. Reducer udtrykket fra (a) så meget som muligt og opret det tilsvarende logiske kredsløb.
c. Brug boolesk algebra til at forenkle følgende logiske kredsløb og angiv resultatet som et boolesk algebraudtryk.
\(AB+AC\)
Øvelse 2: Kombinatorik og sandsynlighed¶
a. En bestilling af en personlig digital assistent kan specificere enhver af fem hukommelsesstørrelser, enhver af tre typer af skærme, enhver af fire størrelser af en harddisk, og kan enten inkludere eller ikke inkludere en pen-tablet. Hvor mange forskellige systemer kan bestilles? Angiv hvilken regel/sætning fra bogen, som du bruger.
Vi multiplicerer antallet af muligheder for hver af valgene: \(5 \cdot 3 \cdot 4 \cdot 2=120\), hvilket betyder at vi bruger Sætning 5.1 (Multiplikationsreglen)
b. En trådløs garageport har en kode bestemt af op- eller nedstillingen af 12 kontakter.
i. Hvor mange mulige koder er der?
\(2^{12} = 4096\)
ii. Hvad er sandsynligheden for at en indbrudstyv gætter den rigtige kode i første forsøg?
\(\frac{1}{4096} = 0.000244 = 0.0244\%\)
Øvelse 3: Kombinatorik og sandsynlighed¶
En gruppe af 3 børn skal dannes i en klasse af 15 børn.
a. På hvor mange forskellige måder kan du danne gruppen, hvis rækkefølgen af børnene ikke betyder noget?
\(\frac{15!}{(15-3)!\cdot 3!}=455\)
b. På hvor mange forskellige måder kan du danne gruppen, hvis rækkefølgen af børnene betyder noget?
\(\frac{15!}{(15-3)!}=2730\)
c. Hvad er sandsynligheden for at gruppen vil bestå af de tre børn Xavier, Ygritte og Zelda?
\(\frac{1}{455}=\frac{6}{2730}=0.00220 = 0.220\%\)
Øvelse 4: Pokerhænder¶
På hvor mange måder kan du give en pokerhånd af fem kort fra et standard spil af 52 kort? Hvor mange måder er der også at vælge 47 kort fra et standard spil af 52 kort?
\(\frac{52!}{(52-5)!\cdot 5!}=2,598,960\)
Øvelse 5: Garageporte og indbrudstyve genbesøgt¶
Husk garageportene fra øvelse 2b. Hvad er sandsynligheden for at en indbrudstyv gætter den rigtige kode på 3 forsøg, forudsat at gættene sker med tilbagelægning, dvs. at sandsynligheden for hvert forsøg er den samme?
\(P(\) mindst én korrekt \() = 1-\left(\frac{4095}{4096}\right)^3 \approx 0.00073\)
Øvelse 6: Webstedsadgangskoder¶
En webside kræver at brugeren opretter en adgangskode, der indeholder præcis 4 tegn. Lad \(A\) betegne mængden af adgangskoder, der kun indeholder bogstaver (der er 26 små bogstaver, a-z, og 26 store bogstaver, A-Z), lad \(B\) betegne mængden af adgangskoder, der kun indeholder tal (0-9), og lad \(C\) betegne mængden af adgangskoder, der kan indeholde både bogstaver og tal. En hacker forsøger at gætte adgangskoden for en bestemt bruger. Hvad er sandsynligheden for at han gætter den korrekte adgangskode i første forsøg i hver af tilfældene nedenfor?
a. Websiden tillader kun adgangskoder fra mængde \(A\)
\(\frac{1}{7,311,616}\)
b. Websiden tillader kun adgangskoder fra mængde \(B\).
\(\frac{1}{10,000}\)
c. Websiden tillader kun adgangskoder fra mængde \(A \cup B\).
\(\frac{1}{7,321,616}\)
d. Hvad er sandsynligheden for at hackeren gætter den korrekte adgangskode i første forsøg, hvis websiden tillader adgangskoder fra mængde \(C\)?
\(\frac{1}{14,776,336}\)
Øvelse 7: Sandsynlighed¶
De mulige fem udfald af et tilfældigt eksperiment er lige sandsynlige. Udfaldsrummet er \({a,b,c,d,e}\). Lad \(A\) betegne hændelsen \({a,b}\), og \(B\) betegne hændelsen \({c,d,e}\).
a. Tegn et Venn-diagram der viser udfaldsrummet og hver af hændelserne A og B.
b. Bestem hver af følgende sandsynligheder:
\(P(A)\)
\(P(B)\)
\(P(\overline{A})\)
\(P(A \cup B)\)
\(P(A \cap B)\)
\(P(A) = \frac{2}{5}\)
\(P(B) = \frac{3}{5}\)
\(P(\overline{A}) = \frac{3}{5}\)
\(P(A \cup B) = 1\)
\(P(A \cap B) = 0\)
Øvelse 8: Udfordringsøvelse¶
En computeradgangskode består af 4 tegn, hver en af 26 små bogstaver eller 26 store bogstaver eller et heltal mellem 0 og 9. Hvis adgangskoden skal indeholde mindst ét bogstav og mindst ét heltal, hvor mange forskellige adgangskoder er mulige?
Den nemmeste måde at beregne dette på er først at beregne antallet af 4-tegns adgangskoder og derefter trække dem fra, der ikke opfylder reglen, dvs. adgangskoderne der enten kun indeholder bogstaver eller kun tal: \(62^4-52^4-10^4=7,454,720\)