Institut for Matematik og Datalogi 22. februar 1999 Odense Universitet LF

DM11 — F99 — Ugeseddel 4

Forelæsningen d. 23/2

Vi gennemgår afsnit 3.2 og 3.3 samt afsnittet “Structural Induction” i noterne undtagen eksemplet s. 1 n. til s. 2 m. Derefter gennemgår vi afsnit 2.3.

Forelæsningen d. 2/3

Vi gennemgår afsnit 2.4–2.5 undtagen afsnittene “Representations of integers” og “Algorithms for integer operations”.

Opgaver til uge 9

Giv en rekursiv definition af binære træer med højde h, hvor højden af træet er defineret som antallet af knuder på den længste sti fra roden til et blad. Brug strukturel induktion til at vise, at et binært træ af højde h har højst 2^{h} − 1 knuder.

3. udgave: Afsnit 3.3: 18, 24^{(∗)}, 27, 28, 30, 32^{(∗∗)}, 36, 38 Afsnit 2.3: 5, 6, 13, 21, 22, 23

4. udgave: Afsnit 3.3: 18, 24^{(∗)}, 27, 28, 30, 32^{(∗∗)}, 36, 38 Afsnit 2.3: 5, 6, 13, 21, 22, 23

(∗): Begrebet “well-formed formula” defineres i eks. 8.

(∗∗): Du behøver ikke at give et formelt bevis for, at din løsning er rigtig.