Seminarium geavanceerde algoritmen

Het Seminarium geavanceerde algoritmen wordt verzorgd door Jeannette de Graaf en Walter Kosters, en sluit aan op het college Analyse van algoritmen. Het Seminarium van het najaar van 1996 stond overigens onder leiding van Han La Poutré. In het studiejaar 1997/1998 is het seminarium niet gegeven. in het studiejaar 1998/1999 wordt het onder leiding van Elena Marchiori gegeven als Seminarium heuristische zoektechnieken. In het studiejaar 1999/2000 en het studiejaar 2000/2001 wordt het vak niet gegeven. In 2001/2002 wordt een Seminarium Advanced BioComputing verzorgd.

In het voorjaar van 1996 is een klein Seminarium verzorgd, waar het boek Axioms and hulls van D.E. Knuth (Springer Lecture Notes in Computer Science 606, 1992) besproken werd. Er komt hopelijk nog een schriftelijke verslaglegging. (Deze hoop lijkt in 2000 wel vervlogen.)
In het boek worden onder meer zogenaamde CC-systemen geïntroduceerd. Een CC-systeem is een relatie op geordende drietallen verschillende punten die voldoet aan vijf eenvoudige axioma's, waaraan ook voldaan wordt door de "counterclockwise" relatie op punten in het platte vlak. Beslissingsprocedures gebaseerd op de CC-axioma's blijken NP-volledig te zijn. Er zijn onder meer verbanden met sorteernetwerken, en algoritmen voor het vinden van convexe omhulsels en Delaunay-triangulaties.
Het programma was als volgt:

  1. vrijdag 1 maart: R.R.A. Beugelsdijk bespreekt Hoofdstuk 1: Axioma's
  2. vrijdag 15 maart: G.A. Labrujere bespreekt Hoofdstuk 2: Onafhankelijkheid en Hoofdstuk 3: Interior triple systems
  3. vrijdag 29 maart: R.R.A. Beugelsdijk bespreekt Hoofdstuk 4: Draaikolk-vrije (vortex-free) toernooien
  4. vrijdag 12 april: G.A. Labrujere bespreekt Hoofdstuk 5: Pre-CC-systemen en CC-systemen
  5. vrijdag 26 april: R.R.A. Beugelsdijk bespreekt Hoofdstuk 6: Een NP-volledig probleem
  6. vrijdag 24 mei: G.A. Labrujere bespreekt Hoofdstuk 7: Toernooien aan elkaar plakken
  7. vrijdag 7 juni: R.R.A. Beugelsdijk bespreekt Hoofdstuk 8: Spiegelingsnetwerken
  8. vrijdag 14 juni: G.A. Labrujere bespreekt Hoofdstuk 11: Convexe omhulsels

Vorm en inhoud van het vak

De deelnemers worden in teams van twee personen verdeeld. Ieder van de deelnemers moet enkele malen een voordracht houden van drie kwartier. Er kan hierbij uit een aantal onderwerpen gekozen worden. Elk team kiest twee onderwerpen; per onderwerp wordt twee maal drie kwartier gesproken. Degene die bij het ene onderwerp voor de pauze spreekt, is bij het andere onderwerp als tweede aan de beurt.
Voor de presentatie worden twee A4's gemaakt waarin kort de inhoud van de voordracht omschreven wordt. Na de presentatie wordt in omstreeks 15 A4's de voordracht gedetailleerd uitgewerkt. Alle schriftelijke rapportages worden in LaTeX gemaakt en na afloop gebundeld. Actieve deelname (bijvoorbeeld het stellen van vragen) van de andere deelnemers wordt tijdens de voordrachten verwacht.

Het tweede gedeelte van het Seminarium bestaat doorgaans uit het in andere tweetallen opzoeken en verwerken van "alle" artikelen die te vinden zijn op het gebied van een gegeven probleem: in 1994 heaps, in 1995 dames op het schaakbord. Hiertoe moeten de bibliotheek en WWW intensief gebruikt worden. Elke week vinden besprekingen plaats, waarbij de activiteiten van de komende week gecoördineerd worden. Enkele belangrijke bronnen: Lecture Notes in Computer Science (de grijze boeken van Springer) en tijdschriften als Information Processing Letters, Computer Journal, Journal of Algorithms. Per gevonden referentie wordt naast gegevens als auteur, titel en vindplaats, ook een korte samenvatting van de inhoud, zeg een tiental regels, gegeven; we gebruiken hiervoor BIBTeX. Ook hiervan zal weer een mondelinge presentatie verwacht worden, van elk van de deelnemers: er wordt per deelnemer een van de gevonden artikelen besproken.
Voor de eindbeoordeling tellen schriftelijke en mondelinge presentatie beide mee.

Welke onderwerpen aan de orde komen wordt in overleg bepaald.
Als voorbeeld: in het voorjaar van 1993 zijn achtereenvolgens besproken:

In 1994 zijn behandeld: Verder is dat jaar een uitgebreid onderzoek naar literatuur over heaps gedaan, wat zo'n 190 referenties opleverde; in het bijzonder werden besproken pairing heaps, interval heaps, parallel heaps en weak heaps.

In 1995 kwamen aan de orde:

Bij het tweede gedeelte werden, zoals eerder vermeld, "dames op schaakbord" behandeld. Uiteindelijk werden 66 referenties gevonden.

Materiaal

Gebruik wordt gemaakt van het boek Introduction to algorithms van T.H. Cormen, C.E. Leiserson en R.L. Rivest, MIT Press, 1990.
Het belangrijkste materiaal staat in dit boek en in diverse artikelen.

De schriftelijke rapportages komen te staan in kloeke boekwerkjes: die van het voorjaar 1993 (gezipt PostScript, 476 kB, helaas niet met alle plaatjes) en het voorjaar 1994 (gezipt PostScript, 202 kB) zijn beschikbaar. Deze files kunnen (na met gunzip uitgepakt te zijn) eenvoudig geprint worden. Ze zijn "ingebonden" in te zien bij de docenten.

Vragen en/of opmerkingen kunnen worden gestuurd naar: kosters@liacs.nl.

7 september 2000 - http://www.liacs.nl/home/kosters/sga.html