De module Analyse van Algoritmen is onderdeel van de minor
Software Engineering binnen de opleiding Informatica aan de
Hogeschool Leiden. Deze pagina bevat enige practische informatie
over de module.
Docent
Naam: Rudy van Vliet
telefoon: 071-527 7050
email: rvvliet@liacs.nl
Boek
Bij deze module maken we gebruik van het boek
Algorithmics, the Spirit of Computing, third edition,
van David Harel en Yishai Feldman. Het ISBnummer is
0-321-11784-0. Te verkrijgen bij de betere boekhandel.
Lesrooster + behandelde stof
In het collegejaar 2006-2007 is er gedurende zeven weken twee
keer per week anderhalf uur les gegeven. Dit was een combinatie van
(hoofdzakelijk) hoorcollege en (aanvullend) opgaven maken.
Hieronder staat het lesrooster, zoals dat is gevolgd.
Bij alle lessen is ook de behandelde stof vermeld.
Woensdag 22 november 2006, 13:00-14:30, Z313
Behandelde stof: Herhaling recursieve functies (Hanoi), grafen, bomen,
treesort (veelal uit Hst 2 van boek).
Verder: voorwaarts zoeken (DFS), zijwaarts zoeken (BFS), markeren bezochte
knopen in grafen (begin Hst 4), bloksorteren als extra voorbeeld BFS
(n.a.v. programmeeropgave Booksort).
Opgave 4.2a, gewezen op opgaven 4.2c.
Donderdag 23 november 2006, 13:00-14:30, B122
Behandelde stof: uitputtend zoeken, binair zoeken, interpolatie zoeken,
maximale afstand in convexe veelhoek, verdeel en heers, gretig algoritme
en een nog gretiger algoritme voor minimale opspannende boom, dynamisch
programmeren, Beiers bierfestijn als voorbeeld dynamisch programmeren
(n.a.v. programmeeropgave The Bavarian Beer Party),
on-line algoritmes (vervolg Hst 4). De heap was al bekend.
Woensdag 29 november 2006, 13:00-14:30, Z313
Behandelde stof:
extra opgave kortste pad met dynamisch programmeren,
(n.a.v. Hst 4). Fouten in programma's: voorbeelden
uit de praktijk, syntax-fouten en logische fouten,
zoeken woord `money', testen geeft geen
zekerheid, oneindige lussen, partiële en totale correctheid,
beweringen/invarianten, convergenten, omkeren van een string (begin Hst 5).
Donderdag 30 november 2006, 13:00-14:30, F178
Behandelde stof:
extra opgave correctheid sorteren,
bewijzen met inductie,
bewijzen correctheid recursieve functies (Hanoi) met inductie,
precondities en postcondities,
ook docent gebruikt invarianten en pre- en postcondities,
beperkingen computer bij bewijs correctheid,
vier-kleurenprobleem als illustratie belang correct programma
(vervolg Hst 5).
Gewezen op opgaven 5.8-5.14 (met name opgave 5.12) en opgave 5.15.ii.
Woensdag 6 december 2006, 13:00-14:30, Z309
Behandelde stof: constante factor tijdswinst bij slimme implementatie
algoritmes, orde verschil bij verschillende algoritmes, grote-O-notatie,
complexiteit geneste lussen (met voorbeeld sorteeralgoritme van
30 november), complexiteit recursieve algoritmes (begin Hst 6).
Opgaven 6.2, 6.4, 6.9.
Donderdag 7 december 2006, 13:15-14:45, Z315
Behandelde stof: analyse treesort, mergesort, slechtste-geval vs
gemiddelde-geval, binair zoeken is optimaal, complexiteit algoritmes
voor convex omhulsel (eind Hst 6).
Opgaven 6.9, 6.19.
Dinsdag 12 december 2006, 11:30-13:00, B122
Behandelde stof: algoritmische kloof, recursieve oplossing Hanoi is
optimaal, polynomiale vs exponentiële groei,
beslissingsproblemen, handelsreizigersprobleem
(TSP), Hamilton pad probleem, landkaart-3-kleurings probleem,
graaf-k-kleurings probleem, polynomiaal certificaat, P, NP, NPC
(NP-volledige problemen)
(begin Hst 7).
En passant behandelde opgaven: 7.1, 7.9.
Woensdag 13 december 2006, 13:00-14:30, B122
Behandelde stof: herhaling P, niet-deterministische algoritmes,
NP, NPC (NP-volledige problemen), reductie Hamilton pad probleem naar
handelsreizigersprobleem, als één NP-volledig probleem polynomiaal
is dan is P=NP, beslissingsprobleem vs optimaliseringsprobleem.
Opgaven 7.10, 7.11.
Donderdag 21 december 2006, 13:00-14:30, B115
Behandelde stof: complexiteit uitdrukken in grootte van de invoer,
b.v. bij sorteren getallen, kortste pad met dynamisch programmeren,
niet-priem en Hanoi; beslisbare en onbeslisbare tegelproblemen (begin
Hst 8). Opgave 8.1b.
Dinsdag 9 januari 2007, 11:00-12:30, B122
Behandelde stof: correspondentieprobleem is onbeslisbaar,
(on-)begrensdheid en (on-)beslisbaarheid, reductie om
(on-)beslisbaarheid te bewijzen, enkele voorbeelden van stopprobleem
(vervolg Hst 8).
Opgaven 8.4, 8.6, 8.7, 8.8, 8.11.
Donderdag 11 januari 2007, 11:00-12:30, F104
Behandelde stof: stopprobleem is niet beslisbaar (Hst 8),
wanneer is foutkans acceptabel? deterministische en probabilistische
algoritmen voor priemtest met grote en kleine foutkans (uit Hst 11)
Donderdag 18 januari 2007, 11:00-12:30, B115
Behandelde stof: probabilistisch patroon herkennen (met vingerafdruk),
Monte Carlo en Las Vegas algoritmen (vervolg Hst 11),
public-key cryptografie (signatures niet behandeld!)
en in het bijzonder RSA cryptografie (begin Hst 12).
Extra opgave over RSA cryptografie.
Tentamenstof
De tentamenstof was de stof die tijdens de lessen is behandeld (zie hierboven).
Ze bestond dus uit stof uit het boek en door de docent
toegevoegd materiaal. De stof uit het boek besloeg de volgende bladzijden:
uit hoofdstuk 8: 191-197 onderaan, 199 onderaan-205 onderaan
uit hoofdstuk 11: 297-298 bovenaan, 301-306 bovenaan, 307 bovenaan-309
uit hoofdstuk 12: 317-halverwege 319, 321 onderaan-323.
Zoek zelf even op in het boek welke opgaven bij deze bladzijden horen.
En vergeet natuurlijk niet de door de docent toegevoegde stof.
Tentamens
De module is afgesloten met een schriftelijk tentamen en een
schriftelijk hertentamen. Beide tentamens zijn nagekeken en je
vindt ze hieronder, samen met de uitslagen: