Search
Nederlands
  Prospectuses 2007-2008
Radboud universityProspectusesFaculty of Science > Bachelor Informatica en Informatiekunde

Analyse van algoritmen/complexiteit 

(Course ID)
Vakcode
I00010
(Credits)
Studiepunten
6
(Scheduled)
Periode
H
Inleiding (Introduction)
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 (Objectives)
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 (Subjects)


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.

Studielastverdeling (Study investment)
  • 32 uur hoorcollege
  • 32 uur werkcollege
  • 104 uur zelfstudie
Toetsvorm (Examination)


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

Er wordt nagedacht over een verandering van onderwijsvorm en/of tentaminering; als dit doorgaat word je tijdig geïnformeerd.

Vereiste voorkennis (Pre-requisites)

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.

Literatuur (Literature)

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

Website
http://www.cs.ru.nl/~bolke/T2/T2dl1.html
Bijzonderheden (Extra information)

*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...)


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.

 


 

 

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

Er wordt nagedacht over een verandering van onderwijsvorm en/of tentaminering; als dit doorgaat word je tijdig geïnformeerd.