SluitenHelpPrint
Switch to English
Cursus: 192140200
192140200
Algoritmen, Datastructuren en Complexiteit
Cursus informatieRooster
Cursus192140200
Studiepunten (ECTS)5
CursustypeCursus
VoertaalNederlands
Contactpersoondr.ir. R. Langerak
E-mailr.langerak@utwente.nl
Docenten
Docent
dr.ir. R. Langerak
Contactpersoon van de cursus
dr.ir. R. Langerak
Collegejaar2011
Aanvangsblok
1B
AanmeldingsprocedureZelf aanmelden via OSIRIS Student
Inschrijven via OSIRISJa
Cursusdoelen

Inhoud

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

Verplicht materiaal
-
Aanbevolen materiaal
Boek
Cornmann, Leiserson, Ryvest, Stein: Introduction to Algorithms, Third Edition (Student Edition), MIT Press, 2009.
Werkvormen
Hoorcollege

Werkcollege

Toetsen
Tentamen

SluitenHelpPrint
Switch to English