Skriftlig Eksamen DM11

Institut for Matematik og Datalogi Odense Universitet

Torsdag den 9. januar 1997, kl. 9–13

Alle sædvanlige hjælpemidler (lærebøger, notater, etc.) samt brug af lommeregner er tilladt.

Eksamenssættet består af 5 opgaver på 7 nummererede sider (1–7). Fuld besvarelse er besvarelse af alle 5 opgaver. Der er ialt 13 spørsmål, som tillægges samme vægt ved bedømmelsen.

Der må refereres til algoritmer og resultater fra lærebogen inklusive øvelsesopgaverne og de udleverede noter. Specielt må man gerne begrunde en påstand med at henvise til, at det umiddelbart følger fra et resultat i lærebogen (hvis dette altså er sandt!). Henvisninger til andre bøger accepteres ikke som besvarelse af et spørgsmål.

Bemærk, at hvis der er et spørgsmål i en opgave, man ikke kan besvare, kan man godt besvare de efterfølgende spørgsmål og blot antage at man har en løsning til de foregående spørgsmål.

Opgave 1

Denne opgave handler om rekursive definitioner, tælleargumenter og sandsynlighedsregning.

Definer funktionen f : {0, 1}^{∗} → {0, 1}^{∗} som følger (som sædvanlig betegner A^{∗} mængden af strenge over A):

• f(λ) = λ

• f(x0) = f(x)01 for x ∈ {0, 1}^{∗}

• f(x1) = f(x)10 for x ∈ {0, 1}^{∗}

spørgsmål a

Bevis formelt at for alle strenge x ∈ {0, 1}^{∗} gælder der, at f(x) har det samme antal 0’er som 1’er.

spørgsmål b

Angiv en rekursiv definition af mængden S, sådan at S er billedet af (the image of) {0, 1}^{∗} under f.

spørgsmål c

Lad J_{n}, hvor n er et ikke-negativt lige heltal, betegne antallet af strenge over alfabetet {0, 1} der har længde n og har det samme antal 0’er som 1’er. Find J_{n}.

spørgsmål d

Hvad er sandsynligheden for p_{n} at en streng, der er valgt tilfældigt blandt strengene over {0, 1} af længde n (igen et ikke-negativt lige heltal), har det samme antal 0’er som 1’er?

spørgsmål e

Hvad er det forventede antal gange, man skal vælge tilfældige strenge over {0, 1} af længde n (igen et ikke-negativt lige heltal), inden man får én med det samme antal 0’er som 1’er?

Opgave 2

Denne opgave handler om rekursionsligninger (recurrence relations).

Algoritmen A bruger operation O til at løse problemet P. Hvis størrelsen af instansen er 1, så bruger A kun operation O én gang. Hvis størrelsen af instansen er n > 1, så løser algoritmen A 3 instanser af størrelse n−1 rekursivt, og bagefter bruges operationen 2^{n} gange til at kombinere resultaterne.

spørgsmål a

Angiv en rekursionsligning der udtrykker hvor mange gange algoritmen A bruger operationen O, når størrelsen af instansen er n. Hvad er begyndelsesbetingelserne (the initial conditions)?

spørgsmål b

Løs rekursionsligningen fra spørgsmål a. Man kan for eksempel bruge en frembringerfunktion (generating function).

Opgave 3

Denne opgave handler om talteori. Betragt følgende eksempel:

• 323 = 17 · 19,

• 11^{2} (mod 17) ≡ 2 ≡ 138 (mod 17), og

• 10^{2} (mod 19) ≡ 5 ≡ 138 (mod 19).

spørgsmål a

Gør rede for, at en løsning x til x^{2} ≡ 138 (mod 323) kan fås ved at kræve x ≡ 11 (mod 17) og x ≡ 10 (mod 19).

spørgsmål b

Find et x, sådan at 0 ≤ x < 323 og x^{2} ≡ 138 (mod 323).

Opgave 4

Denne opgave handler om r-kombinationer. (Notation: C(m, n) = ( \begin{matrix}m \\ n \end{matrix} ).)

spørgsmål a

Bevis formelt, at

∑_{i=0}^{k} C(r + i, r) = C(r + k + 1, r + 1)

når r ≥ 1.

spørgsmål b

Brug resultatet fra spørgsmål (a), og giv et simplere udtryk for

v_{n} = ∑_{k=3}^{n} k(k − 1)(k − 2).

Der ønskes et udtryk af formen v_{n} = a · C(b, c), hvor a og c er konstanter, mens b afhænger af n.

Opgave 5

Denne opgave handler om gruppeteori.

spørgsmål a

Bevis, at hvis en gruppe G er cyklisk, så er den også abelsk (kommutativ).

spørgsmål b

Bevis at S_{2} (the symmetric group on 2 letters) er cyklisk, og bevis at S_{3} (the symmetric group on 3 letters) ikke er cyklisk.