Algoritmen en datastructuren

Dit handboek is een leidraad bij de studie van algoritmen en datastructuren. Daarbij is basiskennis van een object-georiënteerde programmeertaal verondersteld. In de uitgewerkte programmavoorbeelden wordt Java gebruikt; de meeste algoritmen worden beschreven in een programmeertaal-onafhankelijke pseudocode.

De inleidende hoofdstukken geven een overzicht van enkele wiskundige technieken om algoritmen en datastructuren te analyseren, zoals asymptotische analyse en het oplossen van recurrente betrekkingen. De standaard abstracte datatypes, zoals stapels, wachtlijnen, prioriteitswachtlijnen, lijsten, collecties, gesorteerde collecties en mappen, worden al vroeg geïntroduceerd en gebruikt in de toepassingen. Hierbij is bewust vermeden om de implementatie van de abstracte datatypes al te behandelen. In plaats daarvan gaat het boek uitgebreid in op wat de Java API levert aan algoritmen en abstracte datatypes, aangevuld met voorbeelden van praktische toepassingen waarin ze gebruikt kunnen worden.

De nadruk ligt op ontwerptechnieken voor algoritmen, met inbegrip van recursie, brute-kracht-algoritmen, de verdeel-en-heers-strategie, modelleren met grafen en bomen, gretige algoritmen, backtracking en branch-and-bound. Deze ontwerptechnieken worden ter illustratie toegepast op standaardproblemen uit de informatica, wiskunde, bio-informatica en/of geomatica.

De afsluitende hoofdstukken bespreken courante implementaties van standaarddatastructuren, zoals stapels en wachtlijnen, binaire hopen, hashtabellen, geschakelde lijsten en binaire zoekbomen.

VEERLE FACK is professor aan de faculteit Wetenschappen van de UGent. Zij doceert algoritmen en datastructuren in de opleidingen informatica, wiskunde, geomatica en bio-informatica, zowel op bachelor- als op masterniveau. Haar onderzoeksinteresse gaat uit naar discrete algoritmen en hun toepassingen in de geomatica en in de bio-informatica.