Deelnemende opleiding
|
Examendoel
|
Bachelor Technische Informatica (BSc TI)
|
Bachelor
|
Vakbeschrijving
Het doel van dit vak is drieledig. Ten eerste zullen elementaire algoritmen en datastrukturen worden behandeld die worden gebruikt voor het oplossen van problemen die veelvuldig voorkomen in informatica-toepassingen. Daarnaast worden de basisprincipes en technieken voor het analyseren van de complexiteit van algoritmen (en operaties op datastrukturen) behandeld. Hierbij gaat het met name om tijdscomplexiteit (worst-case en average-case) en ruimtecomplexiteit. Tenslotte worden complexiteitsklassen (P en NP) geintroduceerd. Het vak behelst belangrijke algoritme-ontwerptechnieken zoals verdeel-en-heers, greedy methoden, depth-first en breadth-first zoeken, en dynamisch programmeren. Inhoud: graafalgoritmen, sorteren, lijsten, bomen, stacks, (priority) queues, hashing. Na het succesvol afronden van dit vak kan de student:
- Elementaire algoritmen en datastructuren, die zijn ontwikkeld voor het oplossen van problemen die veelvuldig voorkomen in informaticatoepassingen, uitleggen en toepassen. Behandeld worden: graafalgoritmen, sorteren, lijsten, bomen, stacks, (priority) queues, hashing, verdeel-en-heers techniek, greedy methoden, depth-first en breadth-first zoeken en dynamisch programmeren.
- Complexiteit van algoritmen en operaties op datastructuren analyseren. Hierbij gaat het voornamelijk om tijdscomplexiteit (worst--case en average-case) en ruimtecomplexiteit.
- Beargumenteren waarom een probleem in de complexiteitsklasse P (Polynomial time) of NP (Non-deterministic Polynomial time) zit.
Voorkenniseisen
De student beheerst de basis van object georiënteerd programmeren. Dit wordt behandeld bij: Programmeren 1 (192135000) en Programmeren 2 (192135050).
De student beheerste de basis van complexiteit en algoritmen, recurrente betrekkingen en inleiding algebra. Dit wordt behandeld bij: Discrete Wiskunde II (191521620).
|