| Website: | website met extra informatie |
| Vakcode: | INFOB3DW |
| Studiepunten: | 7.5 ECTS |
| Periode: | periode 34 (week 6 t/m 27, dwz 7-2-2012 t/m 6-7-2012; herkansing week 34)
|  |
| Timeslot: | |
| Deelnemers: | tot nu toe 19 inschrijvingen |
| Rooster: | Let op: m.i.v. het collegejaar 2008/2009 is het rooster te vinden in Osiris |
| Docenten: | Dit is een oud rooster!
|
| Inhoud: | Er was ten onrechte een limiet gesteld van 15 deelnemers. Die is nu verwijderd. Ook wanneer je je nog niet hebt ingeschreven (kan nu weer) dan ben je dinsdagochtend van harte welkom. Dinsdag 7-2 is er geen werkcollege.
Dit vak wordt door het departement Informatica verzorgd op verzoek van het departement Wiskunde. Het is een niveau 3 keuzevak bij Wiskunde; studenten Informatica kunnen het opvoeren in hun profileringsruimte. De inhoud van het vak is gewijzigd ten opzichte van vorig jaar: een gedeelte van de stof van vorig jaar (Latijnse vierkanten, block designs, coderingstheorie) is vervangen door stof die afgelopen jaar in het vak Combinatorische Optimalisatie (WISB376) zat.
Het is een semester-vak; er is 1 maal hoorcollege en 1 maal werkcollege per week, en dit twee perioden lang. Volgens de voorlopige planning staat het hoorcollege geroosterd op dinsdagochtend 9.00-10.45; het werkcollege staat geroosterd op dinsdagochtend 11.00-12.45.
Om het vak te halen moet je zowel de tussentoets aan het eind van periode 3 als de eindtoets aan het eind van periode 4 maken.
De drie hoofdvragen in de combinatoriek zijn:
-
Hoeveel oplossingen bestaan er (telprobleem)?
-
Bestaat er een oplossing (beslissingsprobleem)?
-
Welke is de beste oplossing (optimaliseringsprobeem)?
Bij deze cursus zullen voornamelijk de eerste en de derde vraag aan bod komen. Hierbij komen ook de benodigde technieken aan bod.
Inhoud in periode 3:
-
Basisregels voor het tellen van het aantal mogelijkheden
-
Genererende functies
-
Opstellen en oplossen van recurrente betrekkingen.
-
Tellen met behulp van de techniek van Inclusion/Exclusion.
-
Pólya theorie.
Inhoud in periode 4:
-
Dynamische programmering;
-
Kortste pad en minimale opspannende boom;
-
Matching en toewijzingsproblemen;
-
Max flow en min cost max flow problemen;
-
Complexiteitstheorie.
Vereiste voorkennis:
Bekendheid met bewijstechnieken als inductie en bewijs uit het ongerijmde. Voldoende wiskundige rijping en gezond verstand. |
| Literatuur: | F.S. Roberts en B. Tesman
CRC Press (2009)
Applied Combinatorics, 2nd edition
ISBN: 9781420099829
Hetzelfde boek is eerder verschenen bij Prentice Hall (ISBN 9780130796035); dit is nog verkrijgbaar bij een aantal boekensites. De inhoud van dit boek is volledig gelijk aan de inhoud van het nieuwe boek, maar het nieuwe boek bevat nog 40 bladzijden met antwoorden (en soms hele korte uitwerkingen) van geselecteerde opgaven. |
| Werkvorm: | Er is zowel in periode 3 als in periode 4 een keer per week een hoorcollege van twee uur. Daarnaast is er een werkcollege, ook van twee uur in de week.
|
| Toetsvorm: | Toetsvormen:
Na afloop van periode 3 en periode 4 zijn er deeltentamens. Deze tellen allebei mee voor 40% van het eindcijfer. Daarnaast zijn er zes sets van inleveropgaven. De uitslagen hiervan worden gemiddeld en tellen voor 20% voor het eindcijfer.
Afhankelijk van het aantal deelnemers is er een schriftelijk dan wel een mondeling hertentamen. Volgens de regels van de faculteit mag je alleen deelnemen wanneer je een 4 hebt gehaald, maar die regel hanteer ik zeer soepel. De uitslag hiervan is ook het eindcijfer, dus inleveropgaven tellen dan niet meer mee.
|
| Inspanningsverplichting voor aanvullende toets: | Om aan de aanvullende toets te mogen meedoen moet de oorspronkelijke uitslag minstens 4 zijn. Hier let ik echter niet op. |
| Beschrijving: | Zie inhoud. |
