Discrete modellen in de toegepaste wiskunde (WISB136), collegejaar 2011-2012
Docent
Rob Bisseling
(R.H.Bisseling "AT" uu.nl, kamer 517 wiskundegebouw, 030-2531481)
Tijdstip en plaats
Hoorcollege. Maandagmiddag 13.15-15.00 uur, periode 3. Start op 6-2-2012.
(Eenmalig is er GEEN hoorcollege, nl op maandag 13 februari, maar wel werkcollege.)
Data hoorcollege: 6, 20, 27 februari, 5, 19, 26 maart, 2 april. Plaats: BBL 165
Werkcollege. Maandagmiddag 15.15-17.00 uur.
Data werkcollege: 6, 13, 20, 27 februari, 5, 19, 26 maart, 2 april. Plaats BBL 205
ECTS
Dit vak levert 3,75 ECTS op.
Inhoud
- Definities van grafen, gewogen en ongewogen, gericht en ongericht. Graad van een knoop.
- Representaties van grafen: verbindingsmatrix, incidentiematrix, burenlijst
- Isomorfisme en automorfisme
- Kortste-pad algoritme van Dijkstra, A* algoritme, met industriele routeringstoepassingen
- Het vierkleurenprobleem: planaire grafen, vijfkleurenstelling
- Kleuringsalgoritmen. Chromatisch getal, greedy methoden.
- Zoekmethoden: breadth-first search, depth-first search
- Opspannende bomen
- Graafmatching, augmenterend pad, Berge's stelling. Toepassingen
- Sociale netwerken als graaf
Vereiste voorkennis
Bekendheid met bewijstechnieken als inductie en bewijs uit het ongerijmde.
Bekendheid met begrippen uit de lineaire algebra als (standaard)basis,
matrices, eigenwaarde en eigenvector.
Kennis en inzicht
Na afronding van de cursus kent de student:
- Het verschil tussen gerichte en ongerichte grafen, gewogen en ongewogen grafen
- Algoritmen voor het bepalen van het kortste pad in een graaf, het zoeken in de breedte en de diepte.
- Greedy algoritmen voor gewogen graafmatching.
- Basisdefinities als graad van een knoop, samenhangendheid, perfecte matching, planaire graaf, chromatisch getal
- Het begrip Euler-pad
- Het bewijs van de stelling van Berge
Vaardigheden
Na afronding van de cursus kan de student:
- Algoritmen beschrijven en uitvoeren op een eenvoudig voorbeeld voor: kortste pad bepalen, greedy graafmatching, greedy graafkleuring
- Eigenschappen bewijzen van eenvoudige voorbeeldgrafen in de betreffende gevallen
- Knopen vinden met bijzondere eigenschappen via zoekalgoritmen voor kleine grafen
- Het grafenspel Sprouts spelen
- Bepalen of een grafenmatching maximaal is, en in bijzonder gevallen maximum
Tijdsschema hoorcollege
De stof refereert aan het boek van Bondy en Murty uit 2008. H6.1 = Hoofdstuk 6, sectie 1.
Op dit moment is het schema voorlopig.
Precieze informatie op sectieniveau (welke secties wel/niet) volgt tijdens de cursus.
- 6 februari 2012: Introductie grafen, motivatie kortste-pad.
Sectie 1.1, 1.2 (t/m "Testing for isomorphism"), 6.3 (t/m Dijkstra's algorithm)
- 13 februari: geen hoorcollege, wel werkcollege
- 20 februari: planaire grafen, dualiteit.
Sectie 10.1, 10.2 (t/m directed graphs Fig 10.13).
- 27 februari: Euler's formule, 4-kleurenprobleem, grafen kleuren:
Sectie 10.3, 11.1, 11.2 (maar met makkelijker bewijs voor 5-kleurenstelling),
14.3 (tot midden pg. 364, boven Brooke's stelling).
- 5 maart: wandelingen, Eulertour. Sectie 3.1, 3.2, 3.3.
- 19 maart: zoekalgoritmen, BFS en DFS, Sectie 6.1.
- 26 maart: matching, stellingen van Berge, Hall. Sectie 16.1, 16.2 (t/m Corollary 16.5).
- 2 april: matching algoritme: Egervary. Sectie 16.5 t/m ST. 16.21. Toepassingen in netwerkclustering.
Werkcollegeleiders
- Philip Klop (philip.klop "AT" gmail.com)
- Sytske van der Sluis (s.e.van.der.sluis "AT" umail.leidenuniv.nl)
Toetsing
Elke week levert elke student individueel een opgave in die door de
werkcollegeleiding wordt nagekeken. Hierbij gelden strikte deadlines.
Aan het eind van het blok is er een tentamen. De weging is:
inleveropgaves 10 %, tentamen 90 %, of 100% tentamen als dit cijfer hoger is.
Studenten die aan hun inspanningsverplichting hebben voldaan maar voor de cursus
zakken kunnen eenmaal een hertentamen doen dat dan voor 100 % telt.
Literatuur
"Graph Theory" by Adrian Bondy and U.S.R. Murty, Series: Graduate Texts in Mathematics,
Vol. 244 3rd Corrected Printing, 2008. ISBN 978-184628-969-9.
Het boek is verkrijgbaar bij de A-Eskwadraat boekverkoop en ook in de boekhandel.
Tevens is een PDF-versie gratis te downloaden voor UU-studenten via Springer-Link online.
De stof van dit college komt globaal overeen met (delen van) hoofdstukken 1, 6, 11, 14, 15, 16.
Inleveropgaven
Elke week (behalve de laatste) zal er een inleveropgave zijn die meetelt voor de bonus.
In totaal dus 7 inleveropgaven, waarvan de beste 5 meetellen.
Beoordeling met een geheel cijfer 0-10. Het gemiddelde wordt vertaald en afgerond naar een
werkcollegecijfer (geheel cijfer 0-10).
Elke week wordt de serie huiswerkopgaven aangekondigd op deze webpagina.
Er kan mee geoefend worden bij het werkcollege van die week.
De inleveropgave uit de serie moet vervolgens uiterlijk aan het begin
van het werkcollege van de daaropvolgende week zijn ingeleverd bij de werkcollegeleider.
De inleveropgave moet individueel gemaakt worden, zelf opgeschreven en (uiteraard!) begrepen.
Zonodig kan opheldering gevraagd worden door de werkcollegeleider. Je mag natuurlijk wel samenwerken
bij het oplossen van de opgave.
Huiswerkopgaven
De vetgedrukte opgave is inleveropgave.
- 6 februari: Sectie 1.1: opg 1, 2, 5, 6, 7, 9, 12, 14.
Sectie 1.2: opg 1, 2.
- 13 februari: Opgavenblad werkcollege 2
- 20 februari: Sectie 10.1: opg 1b,3,4,6,8, 9.
Sectie 10.2: opg 8, 10.
- 27 februari: Sectie 10.3: opg 2, 4, 8, 9a.
Sectie 11.1: opg 7.
Sectie 14.1: opg 1.
- 5 maart: Sectie 3.1: opg 2, 6, 7, 8.
Sectie 3.2: opg 3, 4.
Sectie 3.3: opg. 1, 2.
- 19 maart: Opgavenblad werkcollege 6
- 26 maart: Sectie 16.1: Opg. 1, 2, 6, 9, 10.
Sectie 16.2: Opg. 3.
- 2 april: Sectie 16.5 Opg. 1, 2. Geen inleveropgave. Tevens vragenuurtje+oefenen
Tentamens
Interessante links
Frequente vragen
Pagina laatst bijgewerkt: 31 mei 2013
Terug naar thuispagina Rob Bisseling