Na deze cursus is de student in staat om zelfstandig algoritmes te ontwerpen, analyseren en implementeren. De leerdoelen van deze cursus zijn:
1. Het ontwerpen van efficiente algoritmen voor computationele problemen middels fundamentele ontwerptechnieken.
2. Het analyseren van de looptijd en correctheid van algoritmes en datastructuren middels geavanceerde bewijs- en analysemethoden.
3. Het implementeren van bestaande en nieuw-ontworpen algoritmes op efficiente wijze.
4. Het toepassen van algoritmische ontwerp- en analysetechnieken op nieuwe problemen en contexten.
5. Het begrijpen en toepassen van concepten uit computationele complexiteitstheorie en graaftheorie.
Toetsing:
- twee tentamens
- vier practica
- 4 mini-toetsen
Ieder van de twee tentamens telt voor 40 procent van je eindcijfer. Voor ieder correct practicum (zoals beoordeeld door DomJudge), verdien je 0.25 punten voor je eindcijfer, dus in totaal 10 procent. De mini-toetsen tellen voor totaal 10 procent van je eindcijfer. Om voor het vak een eindcijfer te krijgen, moet je wel tenminste twee correcte practica hebben en een cijfer voor beide tentamens.
Als je niet voldoet aan de vereisten om een cijfer te krijgen of je onafgeronde eindcijfer is tenminste een 4 en minder dan 5.50, dan kun je aan de aanvullende toetsing meedoen als: je een cijfer voor beide tentamens hebt met gemiddeld tenminste een 4 en tenminste een correct practicum; of als je een cijfer hebt voor precies een van beide tentamens, dat tenminste een 4 is, en je hebt tenminste twee correcte practica.
De aanvullende toets bestaat uit een van vier opties, die je zelf mag kiezen: een extra practicum doen; twee extra practica doen; het hertentamen doen; het hertentamen en een extra practicum doen.
Het hertentamen gaat over de inhoud van de hele cursus. Het cijfer voor het hertentamen vervangt het laagste of missende cijfer van de deeltentamens.
|
 |
|
De snelheid van software is belangrijk in veel applicaties. Daar heb je niet alleen snelle computers en slimme compilers voor nodig, maar ook efficiente algoritmes. In Algoritmiek leer je technieken om zulke efficiente algoritmes te ontwerpen, analyseren en implementeren. Ook zie je verschillende problemen waar deze technieken hun toepassing vinden.
De cursus omvat zowel meer theoretische aspecten van het vak (analyse van looptijd en correctheid) als meer praktische aspecten (implementatie). De hoorcolleges geven je hiervoor een stevige basis. Je bestudeert en gebruikt de geleerde technieken voor bewijzen en analyse in de werkcolleges en werkt aan hun implementatie tijdens de practica.
De onderwerpen van deze cursus zijn:
- technieken om algoritmen te ontwerpen: divide-and-conquer, dynamisch programmeren (en het optimaliteitsprincipe), en greedy algoritmen (en de greedy choice property)
- analyse van verschillende soorten algoritmen: recursieve en gerandomiseerde algoritmen
- verschillende soorten van looptijdanalyse van algoritmen: worst-case, geamortizeerde en gemiddelde looptijd
- algoritmen voor problemen op netwerken en grafen: kortste paden, opspannende bomen, koppelingen, stromingen, snedes
- de representatie in een computer van netwerken en grafen
- algoritmen voor zoeken in teksten
- dynamische zoekbomen
- computationele complexiteit en NP-volledigheid
Voorkennis en ingangseisen:
Deze cursus vereist goede kennis van de programmeertaal C#, zoals onderwezen in Imperatief Programmeren (INFOIMP) of Gameprogrammeren (INFOB1GP), voor de practica. We vereisen ook basiskennis van datastructuren en looptijdanalyse van algoritmen, zoals onderwezen in Datastructuren (INFODS) of Datastructuren en Algoritmen voor KI (INFOB2DAKI). Studenten die deze vakken niet gevolgd hebben, maar een zeer sterke wiskundige achtergrond en wat programmeerervaring hebben, kunnen het vak mogelijk ook succesvol voltooien met wat extra zelfstudie. Als je niet zeker weet of jouw voorkennis voldoende is voor het volgen van dit vak, vraag het dan na bij de cursuscoordinator.
Materiaal (aanbevolen):
Boek: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, derde editie, MIT Press / McGraw Hill, 2009. De tweede en vierde editie van het boek zijn redelijk equivalent aan de derde en mogen ook gebruikt worden.
Voertaal:
De hoorcolleges zijn in het Nederlands of het Engels, naar gelang de docent. De opgaven van de tentamens, practica, mini-toetsen en werkcolleges zijn in het Engels.
|
|
|