Discrete Wiskunde en Programmeren, najaar 2004
Discrete Wiskunde en Programmeren, najaar 2004
Dit is een verplicht vak in het tweede jaar van de wiskundeopleiding;
zie ook de beschrijving van het vak in de studiegids wiskunde.
Voor kwartaal 5 ziet het rooster er zo uit:
Aanvang: | donderdag 9 september 2004 |
College: |
| Plaats: | A2041 | |
| Dag en Tijd: | donderdag, 8:45 - 10:30 |
Eerste college: donderdag 9 september
Behandeld: Hoofdstuk 1 uit het boek (in vogelvlucht)
Het eerste huiswerk (inleveren uiterlijk 17 september)
bestaat uit het lezen van Hoofdstuk 1 van het
boek (van Johnsonbaugh) en het maken van de volgende opgaven (let op: dit zijn
opgaven uit de lijst van Exercises na elke sectie van het boek, niet van de
`Section Review Exercises' die daaraan vooraf gaan).
De nummers verwijzen nu naar de nieuwe, zesde `internationale' editie,
tussen haakjes de oude (vijfde) editie.
- section 1.1: Exercises 23 and 53 (ongewijzigd)
- section 1.2: Exercise 45 [niet alleen Ja of Nee, ook een reden geven] (ongewijzigd)
- section 1.4 Exercises 51 and 62 (section 1.3: Exercises 59 and 70)
- section 1.5: Exercise 44 (section 1.4: Exercise 24)
- section 1.6: Exercise 5 (section 1.6: Exercise 5)
Tweede college: donderdag 16 september
Behandeld: Delen van Hoofdstukken 2,3,5 (Hoofdstuk 2 uit het oude boek) in vogelvlucht
De tweede collectie huiswerkopgaven moet uiterlijk 24 september ingeleverd
worden en bestaat uit de volgende opgaven (tussen haakjes nummering in oude editie):
- section 2.1: Exercise 78 (ongewijzigd)
- section 5.2: Exercise 63 (section 2.3: Exercise 49)
- section 3.1: Exercise 36 (section 2.4: Exercise 35)
- section 3.2: Exercise 47 (section 2.5: Exercise 41)
- section 2.2: Exercise 69 (section 2.8: Exercise 77)
- Verzin een formule voor de uitkomst als functie van het natuurlijke getal
n van de som over 1/P(S), waar de som loopt over alle niet-lege
deelverzamelingen van {1,2,3,..,n} en waar P(S) het product
van de elementen van S aangeeft.
Derde college: donderdag 23 september.
Eerste Magma sessie
De eerste aanzet voor een Nederlandse inleiding in het gebruik van Magma
staat
hier
(en in Postscript
hier).
Let wel op dat er af en toe nuttige informatie wordt toegevoegd ...
Huiswerk: de eerste Inleiding file doorwerken.
Vierde college: donderdag 30 september.
Behandeld: Hoofdstuk 4 (Hoofdstuk 3 uit oude editie) van het boek
Geen verdere huiswerkopgaven
Vijfde college: donderdag 7 oktober
Tweede Magma sessie (Daan)
Aan de orde komen vooral `controle structuren'. Zie hiervoor
de
tweede versie van de Nederlandse Magma inleiding, die
hier
staat (en in Postscript
hier)
en vooral het
document van Daan,
waarvan de opgaven moeten worden gemaakt en ingeleverd.
Zesde college: donderdag 14 oktober
Derde Magma sessie (Daan)
an de orde komen vooral `functies' (en procedures); zie de Inleiding file
en vooral het
tweede document van Daan,
waarvan de opgaven moeten worden gemaakt en ingeleverd.
Zevende college: donderdag 21 oktober
Behandeld: Hoofdstuk 6 (was Hoofdstuk 4)
Huiswerkopgaven, uit dit hoofdstuk (tussen haakjes oude nummering):
- section 6.1 (section 4.1): Exercises 55, 56, 58
- section 6.2 (section 4.2): Exercises 68, 69
- section 6.3 (section 4.3): Implementeer in Magma een functie om de `volgende' permutatie te genereren
- section 6.7 (section 4.7): Exercise 32
- section 6.8 (section 4.8): Exercise 29
Achtste college donderdag 4 november, en
negende college donderdag 11 november
Behandeld: Hoofdstuk 7 (was 5)
Huiswerk opgaven:
- section 7.1 (was 5.1): Exercises 26, 27, 28
- section 7.2 (was 5.2): Exercises 40, 42
Vierde Magma sessie (Daan):
donderdag 18 november:
Implementeeropdrachten:
- schrijf in Magma een functie met als
- input:
twee even lange rijtjes rationale getallen c, b, en een natuurlijk getal k
-
output:
a_k, waar a gegeven is door de recurrente betrekking
a_(n+1) = c_1*a_1 + ... + c_n*a_n
met begincondities a_1 = b_1, ..., a_n = b_n.
- gebruik dit om fibonacci(100), fibonacci(200) ... fibonacci(500) uit te
rekenen (beginvoorwaarden uit het boek)
- verbeter de functie zodanig dat je om a_n uit te rekenen gebruik maakt van
een eerder uitgerekende a_m -- dus zo dat je om fibonacci(500) uit te rekenen
er iets aan hebt dat je fibonacci(400) al hebt uitgerekend. Hint: misschien
ligt een procedure meer voor de hand?
- schrijf een functie met als
input:
twee rijtjes c, b ter lengte twee (van coefficienten en
beginvoorwaarden voor een tweede orde recurrente betrekking A)
-
output:
een functie, die voor input n, de waarde A_n oplevert gebruik makend van
de gesloten formule A_n = u*p^n + v*q^n (als in sectie 7.2)
- Implementeer de 3 sorteeralgoritmen (voor rijtjes gehele getallen) uit
sectie (7.3), namelijk selection -, merge - en insertion sort.
- Schrijf een functie die op input een positief geheel getal N en een positief
geheel getal B een rij van N willekeurige natuurlijke getallen tot B genereert
en aantoont dat je 3 sorteeralgoritmen hetzelfde antwoord opleveren met deze
rij als input
- Pas elk van de 3 functies zo aan dat ook de complexiteit wordt bijgehouden,
dat wil zeggen, voor elke input rij wordt ook het aantal vergelijkingen
opgehoest benodigd door de sorteeralgoritmen.
- Vergelijk de performance van de algoritmen op het sorteren van een rij van
10000 natuurlijke getallen onder de 25000.
Tiende college: donderdag 25 november
Behandeld: Hoofdstuk 8 (was 6), paragraaf 1, 2, 3
Huiswerkopgaven, uit dit hoofdstuk (tussen haakjes oude nummering):
- section 8.1 (section 6.1): Exercises 45, 48
- section 8.2 (section 6.2): Beantwoord de volgende vragen (in de stijl van Exercises 10--18).
Teken een graph met de volgende eigenschappen, of laat zien dat deze niet bestaat:
- Een enkelvoudige (=simpele) graph met 5 punten, waarvan de graden 2,2,4,4,4 zijn;
- Een enkelvoudige (=simpele) graph met 5 punten, waarvan de graden 2,3,4,4,4 zijn;
- Een enkelvoudige (=simpele) graph met 5 punten, waarvan de graden 2,3,3,4,4 zijn;
- Een samenhangende (=verbonden) graph met 5 punten, waarvan de graden 2,2,4,4,4 zijn;
- Een samenhangende (=verbonden) graph met 5 punten, waarvan de graden 2,3,4,4,4 zijn;
- Een samenhangende (=verbonden) graph met 5 punten, waarvan de graden 2,3,3,4,4 zijn.
- section 8.2: Exercises 58, 59, 60
- section 8.3: Exercise 11
college: donderdag 2 december AFGELAST
Elfde college: donderdag 9 december
Behandeld: Hoofdstuk 8 (was 6), paragraaf 3, 4, 5
Verdere opgaven uit dit hoofdstuk:
- section 8.3: Exercise 35
- section 8.4: Exercise 5
- section 8.5: Exercises 12, 14, 21, 25
Vijfde Magma sessie: donderdag 16 december, en
Zesde Magma sessie: donderdag 23 december
De opdrachten voor 16 december en 23 december zijn als volgt:
- Vind en lees de inleiding van het graphentheorie deel in magmahelp.
- Maak met het graph-datatype van Magma een aantal van de
volgende graphen uit het boek. Deze kunnen dan gebruikt worden om de algoritmen
op te testen:
- de graph Figure 8.1.7
- de graphen uit Exercise 8.1.5, 6, 9, 10, 17, 18, 49
- de graphen uit Exercise 8.2.23, 32, 33
- de graph Figure 8.4.1
- de graphen uit Exercise 8.4.7, 8
- de n-kubus graph (als functie van n)
- Implementeer tenminste 3 van de volgende algoritmen in Magma:
- een algoritme om te testen of een graph samenhangend is of niet
- een algoritme dat beslist of een graph bipartite is of niet
- een algoritme dat beslist of in een graph een Euler pad bestaat, en zo ja,
dat pad ook oplevert
- een algoritme dat beslist of in een graph een Hamiltoncykel bestaat, en
zo ja er 1 oplevert, of de kortste wanneer de kanten niet-negatieve gewichten
hebben.
- Dijkstra's kortste-pad algoritme 8.4.1
- een algoritme om planariteit te testen (dit kan ook als onderwerp in het tweede semester gebruikt worden)
Zie het als uitdaging om de algoritmen efficient en/of elegant te maken ...
Last update: 16 december 2004