- NB: man kan ikke skrive latex i alternativene - To typer spørsmål: quiz med multiple choice, eller vanlig med multiple choice - Linjeskift: dollar backslash backslash dollar - Leaderboard etter spørsmål: pleier å legge inn etter feks 7 og deretter etter alle 10 - 5 til 10 min med oppsummering og påminninger om notasjon før quiz - NB: ta med kvikk lunsj og appelsin! - handshake til vinneren - "Henrik" har vunnet to ganger, kan bli hat trick - Angående publisering av ekstranotatene - Vi bør snakke med han som Tjerand baserte notatene sine på før vi kommer så langt - Øystein Skartsæterhagen, ansatt på lærerutdanningen ved NTNU - Aslak er også veldig for ting som er gratis for studentene, skeptisk til at dette heftet skal komme som en ekstrakostnad for studentene de neste årene **Quiz 1 290923, Tallteori 1, 15 sek per oppgave** - Hovedquiz: 1. 12 er delbart på 1. 2 2. 3 3. 4 4. alle 5. ingen 2. 12 deler 1. 4 2. 36 3. 57 4. alle 5. ingen 3. gcd av 24 og 40 er 1. 1 2. 2 3. 4 4. 6 5. 8 4. lcm av 6 og 8 er 1. 2 2. 12 3. 24 4. 32 5. 48 5. 57 er relativt primsk til 1. 19 2. 27 3. 38 4. alle 5. ingen 6. Hvilket av disse utsagnene er usant? 1. transitivitet: $a|b\land b|c\rightarrow a|c$ 2. den gange-relasjonen like under: $a|b\land c|d\rightarrow a\cdot c|b\cdot d$ 3. "flere egenskaper" 1: $m|a\cdot b\rightarrow m|a\lor m|b$ 7. Hvilket av disse utsagnene er usant? 1. "flere egenskaper" 2: $m|a\cdot b\land m\perp a\rightarrow m|b$ 2. "flere egenskaper" 4: $m|a \land n|a \rightarrow m\cdot n|a$ <- 3. "flere egenskaper" 3: $m\cdot n|a\rightarrow m|a\land n|a$ 8. En diofantisk likning er på formen 1. $ax+b=y$ 2. $ax^2+bx=c$ 3. $ax+by=c$ <- 4. $ax+by=cz$ 9. $ax + by = c$ har en løsning hviss 1. gcd(a,b) = 1 2. gcd(c,b) | a 3. gcd(a,b,c) = 1 4. gcd(a,b) | c <- 5. gcd(a,b) = c 10. Euklids utvidede algoritme løser 1. bare gcd(a,b) 2. bare lcm(a,b) 3. bare diofantiske likninger 4. både gcd(a,b) og lcm(a,b) 5. både gcd(a,b) og diofantiske likninger - Lengre oppgave: løs en gitt diofantisk likning **Quiz 2, 051023, Kongruensregning/Tallteori 2** - Først gå litt nøye gjennom mod vs (mod) på tavlen - Hovedquiz: 1. (10 sek) 13 er kongruent med 1. 0 (mod 11) 2. **2 (mod 11)** 3. 5 (mod 11) 4. 7 (mod 11) 5. 12 (mod 11) 2. (10 sek) 13 er kongruent med 1. 1 (mod 12) 2. -11 (mod 12) 3. 25 (mod 12) 4. **alle** 5. ingen 3. (15 sek) 30 er kongruent med 1. 16 (mod 7) 2. 3 (mod 27) 3. -20 (mod 10) 4. **alle** 5. ingen 4. (15 sek) Hvis a er kongruent med b modulo m, så: 1. (a - b) | m 2. ~~a | m~~ 3. **m | (a - b)** 4. m | a 5. ~~ingen av de~~ 5. (15 sek) $2x \equiv 10\ (mod\ 8)$ løses av ... 1. x = 1 2. x = 5 3. x = 9 4. **alle** 5. ingen 6. (15 sek) $k \cdot a \equiv k \cdot b\ (mod\ m)$ impliserer: a) $a \equiv b\ (mod\ m)$ b) $a \equiv b\ (mod\ m/(a\cdot b))$ c) $a \equiv b\ (mod\ m/(gcd(a, b))$ d) **$a \equiv b\ (mod\ m/(gcd(k, m))$** e) kan kun forenkles hvis $k \perp m$ 7. Hva er inversen til 2 modulo 3? (altså slik at $2^{-1}\cdot 2 \equiv 1\ (mod\ 3)$) 1. 0 2. 1/2 3. 1 4. **2** 5. 2 har ingen invers modulo 3 7. Hva er inversen til 2 modulo 4, altså slik at $2^{-1}\cdot 2 \equiv 1\ (mod\ 4)$? 2. 1/2 3. 1 4. 2 5. 3 6. **2 har ingen invers modulo 4** 8. Hvilket utsagn er *usant*? a) $a$ har invers modulo $m$ hvis $a \perp m$ b) $a$ har invers modulo $m$ hvis, og bare hvis, $a \perp m$ c) $a$ har invers modulo $m$ hvis $m$ er et primtall d) $a$ har invers modulo $m$ hvis, og bare hvis, $m$ er et primtall e) $a$ har invers modulo $m$ hvis, og bare hvis, $-a$ har invers modulo $m$ 9. Hva er hva? a) % binæroperasjon, $\equiv_m$ ekvivalensklasse, $[a]_m$ ekvivalensrelasjon b) % ekvivalensrelasjon, $\equiv_m$ binæroperasjon, $[a]_m$ ekvivalensklasse c) % ekvivalensklasse, $\equiv_m$ ekvivalensrelasjon, $[a]_m$ binæroperasjon d) % binæroperasjon, $\equiv_m$ ekvivalensrelasjon, $[a]_m$ ekvivalensklasse e) % ekvivalensrelasjon, $\equiv_m$ ekvivalensklasse, $[a]_m$ binæroperasjon f) % ekvivalensklasse, $\equiv_m$ binæroperasjon, $[a]_m$ ekvivalensrelasjon 10. Hvilken påstand er usann? Kvotientmengden $\mathbb{Z}_m$ er: a) lik $\mathbb{Z}/\equiv_m$ b) består av ekvivalensklasser c) har uendelig mange elementer d) lik $\mathbb{Z}/m \cdot \mathbb{Z}$ e) er tellbar - Oppgave 1, alt 1 (5 min): Hva er $2^{100}\ \%\ 5$ ? - Oppgave 1, alt 2 (10 min): Hva er $3^{25}\ \%\ 85$? - Oppgave 2 (10 min): likningssett, kinesisk rest - $x \equiv\ 2\ (mod\ 3)$ - $x \equiv\ 3\ (mod\ 5)$ - $x \equiv\ 8\ (mod\ 7)$ - Løsninger: $x \equiv\ 386\ \equiv\ 281\ \equiv\ 176\ (mod\ 105)$ - Hmm ... hverken potensiering eller er kinesisk rest er med i quizzen så langt. Burde egt. ha begge deler. **Quiz 3; 131023, Kryptografi** - Hovedquiz 1. Fermats lille teorem sier (for primtall $p$): 1. $a^{p-1} \equiv 0\ (mod\ p)$ 2. $a^{p} \equiv 1\ (mod\ p-1)$ 3. $a^{p-1} \equiv 1\ (mod\ p)$ 4. $a^{p} \equiv 1\ (mod\ p)$ 2. Eulers teorem sier (for $a \perp m$): a. $a^{\phi(m)} \equiv 1\ (mod\ m)$ b. $a^{m} \equiv 1\ (mod\ \phi(m))$ c. $a^{\phi(m)} \equiv 0\ (mod\ m)$ d. $a^m \equiv 1\ (mod\ m)$ 3. Hvis $N$ er et produkt av to primtall $N = p\cdot q$, så er $\phi(N)$ 1. $p/q$ 2. $(p-1)(q-1)$ 3. $(p + q)/2$ 4. $(p - 1)(p - 2) \dots (p-q)$ 4. Hva er riktig? a) Kryptologi er å lage koder, kryptografi er å knekke koder, og begge er kryptanalyse. b) Kryptografi er å lage koder, kryptanalyse er å knekke koder, og begge er kryptologi. c) Kryptologi er å lage koder, kryptanalyse er å knekke koder, og begge er kryptografi. 5. I Diffie–Hellman nøkkelutveksling så ender Alice og Bob opp med den delte nøkkelen: a) $A + B = g^a + g^b$ b) $A\cdot B = g^{a+b}$ c) $A^b = B^a = g^{ab}$ d) $A^B = g^{a g^b}$ 6. Finn en feil: Med offentlig nøkkel-kryptografi så ... a) kan Bob dele den offentlige nøkkelen sin med hvem som helst. b) kan Bob lese meldinger som Alice sender ham, så lenge Bob har den offentlige nøkkelen til Alice. c) kan hvem som helst med den offentlige nøkkelen til Bob, sende en hemmelig melding til Bob. d) kan hvem som helst med den offentlige nøkkelen til Bob, utføre nøkkelutveksling med Bob. e) kan Bob digitalt signere dokumenter som hvem som helst kan verifisere. 7. Hvorfor kan ikke Eva knekke RSA-kryptering? a) Fordi hun ikke husker formelen for $\phi(N)$. b) Fordi hun trenger inversen til $e$, og hun kan ikke regne inverser. c) Fordi hun trenger å faktorisere $N$ for å regne ut $\phi(N)$, og hun kan ikke faktorisere. d) Fordi hun trenger $N$ for å regne ut $\phi(N)$, og $N$ er hemmelig. 8. Ca. hvor store tall må man bruke for at RSA skal være sikkert? 1. $N \approx 100$ 2. $N \approx$ en million 3. $N \approx$ en trillion (en milliard milliarder) 4. $N \approx$ en googol (ettall med 100 nuller bak) 5. Enda større 9. Bonus: med en kvantedatamaskin kan man ... a) Gjøre alt som en vanlig datamaskin kan, bare mer effektivt. b) Simulere kvantefysikk effektivt. c) Faktorisere tall effektivt. d) Regne diskrete logaritmer effektivt. e) Alle disse unntatt a). - Lengre oppgave: Gitt RSA parametre og en melding, finn cifferteksten. (Vis at den dekrypterer rett på tavlen.) **Quiz uke 44, 031123:** 1. Hva er definisjonen til $\binom{n}{k}$? 1. $\frac{n!}{k!}$ 2. $\frac{n!}{(n-k)!}$ 3. $\frac{n!}{(n-k)!k!}$ 4. $\frac{n!}{((n-k)k)!}$ 2. Hvilken av formlene er relevant når: du skal finne hvor mange forskjellige måter du kan trekke 10 kort fra en kortstokk på? a) Ordnet utvalg med rep.: $n^k$ b) Ordnet utvalg uten rep.: $\frac{n!}{(n-k)!}$ c) Uordnet utvalg med rep.: $\binom{k+n-1}{k}$ d) Uordnet utvalg uten rep.: $\binom{n}{k}$ 3. Hvilken av formlene er relevant når: du skal finne antall forskjellige veier du kan kjøre gjennom 10 veikryss, og veien splitter i to for hvert kryss? 1. Ordnet utvalg med rep.: $n^k$ 2. Ordnet utvalg uten rep.: $\frac{n!}{(n-k)!}$ 3. Uordnet utvalg med rep.: $\binom{k+n-1}{k}$ 4. Uordnet utvalg uten rep.: $\binom{n}{k}$ 4. Hvilken av formlene er relevant når: du skal finne hvor mange forskjellige måter 100 av 250 studenter kan rekke opp hånden på? 1. Ordnet utvalg med rep.: $n^k$ 2. Ordnet utvalg uten rep.: $\frac{n!}{(n-k)!}$ 3. Uordnet utvalg med rep.: $\binom{k+n-1}{k}$ 4. Uordnet utvalg uten rep.: $\binom{n}{k}$ 5. Hvilken av formlene er relevant når: du skal finne hvor mange forskjellige måter 250 studenter kan gjennomføre en avstemning med fire svaralternativer på? 1. Ordnet utvalg med rep.: $n^k$ 2. Ordnet utvalg uten rep.: $\frac{n!}{(n-k)!}$ 3. Uordnet utvalg med rep.: $\binom{k+n-1}{k}$ 4. Uordnet utvalg uten rep.: $\binom{n}{k}$ 6. Husk at trekanttallene er gitt ved $T_n = 1 + 2 + ... + n = n(n+1)/2$. Antall kanter i den komplette grafen $K_n$ er gitt av trekanttallet 1. $T_{n-1}$ 2. $T_{n}$ 3. $T_{n+1}$ 4. $T_{K_n}$ 7. Summen av grader er alltid lik 1. Antall noder 2. Antall kanter 3. Dobbelte av antall noder 4. Dobbelte av antall kanter 8. Grafen gitt av denne nabotabellen er en ... ![[Quiz-44_nabotabell.jpg]] 6. Multigraf 7. **Pseudograf** 8. Rettet graf 9. Ingen av delene: den er *enkel* 9. Hva er usant? a) Komplementet til en komplett graf er en tom graf. b) Tomme og komplette grafer er selvkomplementære. c) Alle komplette grafer på $n$ elementer er isomorfe. d) Alle tomme grafer på $n$ elementer er isomorfe. 10. Bonus: Hva vet vi om algoritmer for å avgjøre om to grafer er isomorfe? a) Vi har en effektiv algoritme. b) Vi har en effektiv *kvante*algoritme. c) Vi har ikke en effektiv (kvante)algoritme, men det kan hende den bare ikke har blitt oppdaget enda. d) Vi har ikke en effektiv algoritme, og hvis noen oppdaget en så måtte P vært lik NP, og derfor tror vi ikke at den finnes. 11. Lengre oppgave (tavle): 1. a) gitt en graf med partall noder, er den selvkomplementær? (Svar: nei; vis hvorfor. Ser at *ingen* grafer med partall noder kan være selvkomplementære.) 2. b) gitt to grafer, er de isomorfe eller ikke? (Svar: ja, oppgi isomorfi.) Quiz U45, 101123 1. En sekvens av noder kalles en ... 1. sti 2. krets 3. **vandring** 4. sykel 2. En vandring uten gjentakende noder er en ... 1. **sti** 2. krets 3. vandring 4. sykel 3. En lukket vandring uten gjentakende kanter er en ... 1. sti 2. **krets** 3. vandring 4. sykel 4. En lukket vandring uten gjentakende noder er en ... 1. sti 2. krets 3. vandring 4. **sykel** 5. Hvilken graf-egenskap har *ikke* nødvendigvis et **tre**? 6. Asyklisk 7. Sammenhengende 8. Rotfestet 9. Selv-isomorf 6. En Eulergraf har en *hva* som er innom hver kant nøyaktig én gang: 1. sti 2. **krets** 3. vandring 4. sykel 7. Hva vet vi om algoritmer for å avgjøre om en graf har en Eulervei? a) Vi har en effektiv algoritme. b) Vi har en effektiv *kvante*algoritme. c) Vi har ikke en effektiv (kvante)algoritme, men det kan hende den bare ikke har blitt oppdaget enda. d) Vi har ikke en effektiv algoritme, og hvis noen oppdaget en så måtte P vært lik NP, og derfor tror vi ikke at den finnes. 8. En Hamiltongraf har en *hva* som er innom hver node nøyaktig én gang: 1. sti 2. krets 3. vandring 4. **sykel** 9. Hva er usant? a) Eulerkretser kan *ikke* være innom flere *kanter* b) Eulerkretser *kan* være innom flere *noder* c) Hamiltonsykler kan *ikke* være innom flere *noder* d) Hamiltonsykler *kan* være innom flere *kanter* 10. Hva vet vi om algoritmer for å avgjøre om en graf har en Hamiltonsti? a) Vi har en effektiv algoritme. b) Vi har en effektiv *kvante*algoritme. c) Vi har ikke en effektiv (kvante)algoritme, men det kan hende den bare ikke har blitt oppdaget enda. d) Vi har ikke en effektiv algoritme, og hvis noen oppdaget en så måtte P vært lik NP, og derfor tror vi ikke at den finnes. Quiz U46 1. En endelig tilstandsmaskin er definert til å være en *hva* med én startnode, minst én aksepterende node, og én utadgående kant per symbol? 1. graf 2. rettet graf 3. pseudograf 4. rettet pseudograf 2. Alle beregnbare språk lar seg gjenkjenne av en endelig tilstandsmaskin. 1. usant 2. sant, men ikke vice versa 4. sant, og vice versa 3. Regulære språk er induktivt definert via operasjonene 1. $\cup, \cap, \ast$ 2. $\cup, \cap, ||$ 3. $\cap, ||, \ast$ 4. $\cup, ||, \ast$ 4. Alle regulære språk lar seg gjenkjenne av en endelig tilstandsmaskin. 1. usant 2. sant, men ikke vice versa 3. sant, og vice versa 5. Hvilket regulære uttrykk beskriver språket $(\{1\} \cup \{2\})^\ast \cup \{a, b\} \{a, b\}$? a) $1^\ast 2^\ast | (ab)(ab)$ b) $(1|2)^\ast \cup (a|b)(a|b)$ c) $(1|2)^\ast | (a|b)(a|b)$ d) $1^\ast 2^\ast | (a|b)(a|b)$ 6. Språket $0^\ast 1^\ast$ er regulært (lar seg gjenkjenne av en tilstandsmaskin). 1. sant 2. sant, men ikke effektivt 3. usant 7. Språket $0^n 1^n$ er regulært (lar seg gjenkjenne av en tilstandsmaskin). 1. sant 2. sant, men ikke effektivt 3. usant 8. Hvilket språk gjenkjenner denne tilstandsmaskinen? 1. $0^\ast 1^\ast$ 2. $(0|1)^\ast 1$ 3. $1 (0|1)^\ast$ 4. $(0|1)^\ast$ 9. Hvilket språk gjenkjenner denne tilstandsmaskinen? 1. $(a|b)(b|a)$ 2. $a(a|b)^\ast | b(a|b)^\ast$ 3. $(a|b)(a|b)^\ast$ 4. $(a|b)^\ast$ 10. En endelig tilstandsmaskin a) kan *ikke* gjøre alt som en vanlig datamaskin kan b) *kan* gjøre alt som en vanlig datamaskin kan, men ikke *effektivt* c) kan *ikke* gjøre alt som en kvantedatamaskin kan d) *kan* gjøre alt som en kvantedatamaskin kan, men ikke *effektivt* 11. En Turingmaskin (= lese/skrive-hode med et endelig antall tilstander på en uendelig lang teip) 1. kan *ikke* gjøre alt som en vanlig datamaskin kan 2. *kan* gjøre alt som en vanlig datamaskin kan, men ikke *effektivt* 3. kan *ikke* gjøre alt som en kvantedatamaskin kan 4. *kan* gjøre alt som en kvantedatamaskin kan, men ikke *effektivt*