Zoek
English
  Studiegidsen 2008-2009
Radboud UniversiteitStudiegidsenFaculteit der Natuurwetenschappen, Wiskunde en Informatica > Bachelor Informatica en Informatiekunde

Complexiteit 

Vakcode
IBC004
Studiepunten
3
Periode
tweede semester
Inleiding

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

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!

Het college draagt bij aan de voorbereiding op mastervakken als computeralgebra (afd. wiskunde), cryptografie, complexiteitstheorie, en meer.

Methoden zoals geschikt rekenmodel kiezen, recursieve programma's analyseren, vormen van verdeel-en-heers, indelen in complexiteitsklassen, zijn standaardbagage van elke informaticus.

Kortom: een interessant theoretisch vak met vele toepassingen in de praktijk!


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 fundamentele en praktische berekeningsmodellen zoals als complexiteitshulpmiddelen, met name de Turingmachine en varianten waaronder de niet-deterministische; pseudocode, en parallellisme.
* technieken ter verbetering van de efficientie van berekeningen kunnen aangeven. In dit verband werken met de O-symboliek, meer specifiek de begrippen onder- en bovengrens, polynomiaal, en exponentieel.
* Bepaalde basistechnieken om algorithmen in te delen naar hun moeilijkheidsgraad.
* Onderling vergelijken van problemen, deze naar elkaar transformeren,en indelen in klassen naar moeilijkheidsgraad.
* de uitbouw der complexiteitstheorie naar meer theoretische vraagstellingen


Onderwerpen

In het college ligt de nadruk op de analyse van algoritmen met basisbegrippen als berekeningsmodellen w.o. pseudocode, resource analyse van recursieve algoritmen; dit ter illustratie toegepast op graph algorithmen. Daarna volgt de indeling van algoritmen in complexiteitsklassen zoals P en NP.


N.b. Overige bestanddelen van de klassieke theorie, zoals arithmetische complexiteit, sorteren, cryptografie, zijn m.i.v. 2008/9 verschoven naar het mastercollege Complexiteitstheorie.


Studielastverdeling
  • 16 uur hoorcollege
  • 16 uur werkcollege
  • 52 uur zelfstudie
Toelichting werkvormen

Dit is een "klassiek" theoretisch college. Er is een wekelijkse cyclus:

- je bereidt een stukje theorie alvast voor en maakt huiswerkopgaven die je inlevert (dag en tijd worden nog afgesproken).
- hoorcollege: de voorbereide theorie wordt behandeld en je mag vragen stellen
- werkcollege: uitleg vorige huiswerkopgaven en nieuwe maken onder assistentie. Huiswerk lever je in

Er is geen aanwezigheidsplicht. Wel houden we je huiswerkresultaten bij; als die onverhoopt sterk achterblijven overleggen we met je.

Toetsvorm
Schriftelijk tentamen, gesloten boek.
Vereiste voorkennis
Allereerst een zekere 'wiskundige rijpheid'. In het bijzonder moet je in staat zijn je redeneringen c.q. bewijzen helder te formuleren.

Het college bouwt voort op de theorie van talen, automaten en berekenbaarheid en gebruikt enige discrete wiskunde.

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.math.upenn.edu/%7Ewilf/AlgComp3.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