Algoritmen en datastructuren

Samenvatting

Dit handboek is een leidraad bij de studie van algoritmen en datastructuren. Basiskennis van een object-georiënteerde programmeertaal wordt verondersteld. In de uitgewerkte programmavoorbeelden wordt Java gebruikt, terwijl de meeste algoritmen beschreven worden in een programmeertaal-onafhankelijke pseudocode. De inleidende hoofdstukken geven een overzicht van enkele wiskundige technieken voor het analyseren van algoritmen en datastructuren, zoals asymptotische analyse, het oplossen van recurrente betrekkingen en eigenschappen van bomen. De standaard abstracte datatypes (zoals stapels, wachtlijnen, prioriteitswachtlijnen, lijsten, collecties, gesorteerde collecties en mappen) worden al in een vroeg stadium geïntroduceerd en gebruikt in toepassingen. Hierbij is bewust ... vermeden om de implementatie van de abstracte datatypes al te behandelen. In plaats daarvan beschrijven we uitgebreid wat de Java API levert aan algoritmen en abstracte datatypes en geven we verscheidene voorbeelden van praktische toepassingen waarin deze gebruikt kunnen worden. De nadruk ligt op ontwerptechnieken voor algoritmen, met inbegrip van recursie, brute-kracht-algoritmen, de verdeel-en-heers-strategie, backtracking, gretige algoritmen en dynamisch programmeren. Ter illustratie passen we deze ontwerptechnieken telkens toe op standaardproblemen uit de informatica, wiskunde en/of geomatica. In de afsluitende hoofdstukken worden courante implementaties besproken van standaardsorteeralgoritmen en van standaarddatastructuren, zoals geschakelde lijsten, hashtabellen, binaire zoekbomen en binaire hopen. Over de auteur: VEERLE FACK is professor aan de Faculteit Wetenschappen van de Universiteit Gent. Zij doceert er cursussen in algoritmen en datastructuren en in grafentheorie in de opleidingen informatica, wiskunde, geomatica en bio-informatica, zowel op bachelor- als op masterniveau. Haar onderzoeksinteresses situeren zich in de gebieden van combinatorische algoritmen en toepassingen van grafentheorie in de geomatica en in de bio-informatica.