I00010 (I00010)
Analyse van algoritmen/complexiteit*
< 2006/2007 > 04-09-2006 t/m 13-01-2007 (19-02-2007) H
Informatica - Bachelor (2003) Software: Programmeren en algoritmiek (3 ec) (3 ec) Grondslagen (3 ec) (3 ec)
omvang
6 ec (168 uur) : 32 uur plenair college, 0 uur groepsgewijs college, 0 uur computerpracticum, 32 uur 'droog' practicum, 0 uur gesprekken met de docent, 0 uur onderling overleg met medestudenten (werkgroepen, projectwerk e.d.), 104 uur zelfstudie
investering
6 ec * 28 u/ec + #std * (1 + 6ec * 0.35 u/student/ec)
inzet tentatief

examinator
afdeling
tijdbesteding

dr. Dick van Leijenhorst
das
145u.

speciale web-site
/~bolke/T2/T2dl1.html

 

Het college is gewijd aan een inleiding in de zgn. Complexiteitstheorie. Daarin stel je vragen als: hoe snel loopt mijn algorithme? zijn er snellere versies mogelijk? hoeveel geheugen kost het? zijn er klassen van "moeilijke" algorithmen aan te wijzen? - enzovoorts...

Leerdoelen



Na het volgen van het college kan de student: eenvoudige algoritmen modelleren, verder toepassen, en qua complexiteit analyseren. Meer specifiek is hij/zij qua kennis en/of vaardigheid ingevoerd in zekere basismethoden en zekere basisalgoritmen met hun complexiteitsanalyse:

* geschikte modellering van algoritmen; overeenkomsten en verschillen van modellen en hun onderlinge vertaling;
* enige ad hoc berekeningsmodellen zoals de begrippen pseudocode,verdeel-en-heers en parallellisme, het bitoperatiemodel en decomparison tree.
* technieken ter verbetering van de effcientie van berekeningen kunnen aangeven. In dit verband werken met de O-symboliek, meer specifiek de begrippen onder- en bovengrens, polynomiaal, en exponentieel.
* enige belangrijke deelgebieden van de klassieke complexiteitstheorie, zoals complexiteit van arithmetische bewerkingen, toepassingen daarvan bv. in de cryptografie, en sorteren.


Daarnaast is de student bovendien ingevoerd in:

* Enige fundamentele berekeningsmodellen als complexiteitshulpmiddelen, met name de Turingmachine en varianten waaronder de niet-deterministische.
* Bepaalde basistechnieken om algorithmen in te delen naar hun moeilijkheidsgraad.
* Onderling vergelijken van problemen, deze naar elkaar transformeren,en indelen in klassen naar moeilijkheidsgraad.
* Iets over de aanpak van ongrijpbare problemen via approximatieve methoden.
* de uitbouw der complexiteitstheorie naar meer theoretische vraagstellingen

Onderwerpen

aa


In het eerste deel van het college ligt de nadruk op de analyse van algoritmen met basisbegrippen als berekeningsmodellen w.o. pseudocode, resource analyse van recursieve algoritmen. Daarna volgt de indeling van algoritmen in complexiteitsklassen zoals P en NP.
Tenslotte vormt een voornaam bestanddeel een keuze uit klassieke theorie, zoals arithmetische complexiteit, sorteren, cryptografie, graph algorithmen.

Toelichting

* Het college is gewijd aan een inleiding in de zgn. Complexiteitstheorie. Daarin stel je vragen als: hoe snel loopt mijn algorithme? zijn er snellere versies mogelijk? hoeveel geheugen kost het? zijn er klassen van "moeilijke" algorithmen aan te wijzen? - enzovoorts...

Enkele mensen vinden e.e.a. soms nogal trucjesachtig en/of moeilijk toepasbaar.

Welnu: vragen naar de complexiteit van programma's doemen in werkelijkheid overal op, kijk maar eens in de bibliotheek of bij andere vakken. Mooie en slim bedachte theorie heeft daarnaast natuurlijk ook waarde op zich!

"Trucjes" zitten vaak in de voorkennis (rekenen). Methoden zoals geschikt rekenmodel kiezen, recursieve programma's analyseren, vormen van verdeel-en-heers, indelen in complexiteitsklassen, zijn standaardbagage van elke informaticus.

Een doel van ons college is ook kennisvermeerdering, door allerlei algorithmen uit de informatica (waaronder enkele "topstukken" zoals de FFT) te behandelen.

Kortom: een interessant theoretisch vak met vele toepassingen in de praktijk! (al zeg ik het zelf...)

Werkvormen

Wekelijks is er een hoorcollege en een practicumbijeenkomst. Tijdens het practicum werk je (onder begeleiding) aan theoretische opgaven.

Vereiste voorkennis

Allereerst een zekere 'wiskundige rijpheid'. In het bijzonder moet je in staat zijn je redeneringen c.q. bewijzen helder teformuleren. Enige 'breedte' is nodig; meer specifiek is enige kennis van de discrete wiskunde, algebra en analyse vereist.

Het college bouwt verder op de theorie van talen, automaten en berekenbaarheid en gebruikt die van de vakken discrete wiskunde (WD1/2) en Algebra voor Informatici (WA).

Er is een regeling voor HBO-instromers die een verkorte versie van ons college kunnen volgen; zie daartoe de website.

Tentaminering


Het tentamen is schriftelijk; en om te kunnen deelnemen aan de tentamens dien je het practicum te hebben gevolgd.

Combinatiemogelijkheden


Hier leer je vooral analyserende en vergelijkende complexiteitstheorie, en enige specifieke algoritmen. Dit is kennis die bij het grootste deel van de vakken van de studie informatica noodzakelijk is.

Ons college geeft aansluiting naar enkele specifieke specialisatievakken.Wij noemen:

* Voortgezette complexiteitstheorie (CXT) dit is een verdere uitbereiding van de complexiteitstheorie waarbij ook weer de genoemde specifieke bekwaamheden benodigd zullen zijn.
* C&A: codes en algorithmen (cryptografie, datacompressie)
* IR1 en 2
* ISDN, waarbij de complexiteitstheorie en de -berekeningen toegepast zullen worden,
* Computeralgebra (te volgen bij de subfaculteit wiskunde)
* De combinatie van (onderdelen van) T1, T2, T3 en WL vormt een goede inleiding in de berekenbaarheidstheorie.


Literatuur

Er is een nieuw dictaat, te downloaden via de website (z.o.).

Ter inzage en verbreding beveel ik nog onderstaand boek aan, dat een aantal jaren op college is gebruikt. (Wegens aansluitingsproblemen is het vervangen door een dictaat.) Het is:

Herbert S. Wilf, 'Algorithms and Complexity', Prentice Hall International editions, 1986, ISBN 0-13-022054-x 025

Het boek is momenteel uitverkocht maar valt gratis te downloaden vanaf de website van de auteur: http://www.cis.upenn.edu/~wilf/alfComp.html.


Voor verdere info over het college zie: http://www.cs.kun.nl/~bolke/T2/T2dl1.html


Evaluatie: studentenquêtes http://www.cs.ru.nl/~bolke/T2/T2enq2006.html; docentevaluatie
Rendement: 20 begonnen, 18 echt meegedaan, 8 geslaagd met 1e kans, 10 geslaagd totaal
Q: