Discrete Wiskunde 1 (WB010B)
Voorjaarssemester 2010
| Periode |
01-02-2010 t/m 16-04-2010
hoorcollege in weken 5-6, 8-13
|
| Collegetijden |
| Hoorcollege: |
Donderdag, 13:30 - 15:30 |
Lin 3 |
| Werkcollege: |
Maandag, 15:30 - 17:30 |
HG03.082, studentassistent Jorik Mandemaker
HG03.084, studentassistent Sep Thijssen
|
| Tentamen: |
Vrijdag 16 april 2010,
14.00 - 17.00, HG00.068 |
| Hertentamen: |
Donderdag 15 juli 2010,
9.00 - 12.00, HG00.062 |
Nieuw:
Het college op 1 april 2010 vindt in de terminalkamer HG00.023 plaats (geen
grapje).
Onderwerpen van Discrete Wiskunde 1
- inclusie/exclusie
- dubbel tellen
- recurrentie, voortbrengende functies
- deelverzamelingen, partities, permutaties
- Polya theorie
- grafen
Literatuur
Het college volgt het boek A Course in Combinatorics (second edition)
van J.H. van Lint en R.M. Wilson, Cambridge University Press,
ISBN 978-0-521-00601-9 (2001).
- Behandelde stof week 1: hoofdstuk 10
- binomiaalcoefficienten
- principe van inclusie/exclusie
- Behandelde stof week 2: hoofdstuk 13
- tellen van permutaties en partities
- Stirling getallen, Bell getallen
- Behandelde stof week 3: hoofdstuk 14
- recursie
- voortbrengende functies, exponentiele voortbrengende functies
- Behandelde stof week 4: hoofdstuk 37
- lemma van Burnside
- cykel index polynoom
- stelling van Polya
- Behandelde stof week 5: hoofdstuk 37 (vervolg)
- banen op kleuringen onder groepsactie op objecten en kleuren
- de Bruijn's veralgemening van de stelling van Polya
- Behandelde stof week 6: hoofdstukken 1, 2
- grafen
- Eulerse grafen, Hamiltonse grafen
- bomen
- stelling van Cayley, Prüfer code
- Behandelde stof week 7: hoofdstuk 2
- gewogen grafen
- minimale opspannende bomen, algoritme van Kruskal
- kortste paden, algoritme van Dijkstra
- Stof voor volgende week:
travelling salesman (praktische opdracht)
Werkcollege
Bij elke les hoort een aantal huiswerkopgaven en soms een programmeeropdracht.
Huiswerkopgaven
week 1
(in te leveren tot 10 februari 2010).
Huiswerkopgaven
week 2
(in te leveren tot 25 februari 2010).
Uitwerkingen voor een gecorrigeerde versie van
Opgave 4
Huiswerkopgaven
week 3
(in te leveren tot 4 maart 2010).
Huiswerkopgaven
week 4
(in te leveren tot 11 maart 2010).
Huiswerkopgaven
week 5
(in te leveren tot 18 maart 2010).
Voorbeelden
om in Magma met cykel index polynomen te werken
Huiswerkopgaven
week 6
(in te leveren tot 25 maart 2010).
Huiswerkopgaven
week 7
(in te leveren tot 1 april 2010).
Praktische opdracht
week 8
(in te leveren tot 16 april 2010).
Magma input
voor travelling salesman (nxn matrices met de afstanden/kosten):
- D1: afstanden tussen 25 Nederlandse steden
- D2: kosten tussen 50 knopen (voldoen niet aan driehoeksongelijkheid)
- D3: afstanden tussen 100 random punten in het vlak
Magma functies
voor gewogen grafen:
- algoritme van Prim (minimale opspannende boom)
- algoritme van Dijkstra (kortste paden van a naar alle andere knopen)
- gretig algoritme voor travelling salesman
Het is heel erg aanbevolen, aandacht aan de sommetjes te besteden,
want dit is de beste manier om de stof te herhalen
en vertrouwd met de methodes te worden.
Hier is een zeer nuttige
inleiding
in het gebruik van Magma (door W. Bosma).
De ultimatieve bron van informatie is het
handbook
van Magma functies.
Tentaminering
Het eindcijfer C is samengesteld uit het tentamencijfer T en het
huiswerkcijfer H volgens de formule
C = max(T, 0.75 T + 0.25 H).
Het is mogelijk dat het tentamen een van de huiswerkopgaven bevat.
Als voorbeeld en ter oefening vind je hier het
tentamen
van vorig jaar.
Deze pagina met informatie over de cursus:
http://www.math.ru.nl/~souvi/dw1_10/dw1.html