Stochastische algoritmen

Abstract

Ik heb tijdens mijn thesis stochastische algoritmen bestudeerd. Ik heb mij vooral gebaseerd op het werk van Rajeev Motwani en Prabhakar Raghavan en hun boek Randomized Algoritmes. Ik ben begonnen met het bestuderen van stochastische algoritmen in het algemeen, tesamen met enkele technieken voor het bestuderen van deze algoritmes. Daarna heb ik enkele specifieke toepasingen nader bekeken. De eerste toepssing is het gebruik van stochastische algoritmen bij datastructuren. Dit vooral omdat ik mij moeilijk kon voorstellen hoe men dit goed kon toepassen. Mijn verbazin was ook groot toen bleek dat dit niet alleen vrij makkelijk was, maar ook nog eens mooie resultaten behaalde. De tweede toepassing die ik bestudeerd heb gaat over online algoritmes. Dit vooral omdat ik nog niet veel gezien had over online algoritmes en dit mij wel interessant leek. Aan het begin van de thesis staat wat kanstheorie en een beetje wiskunde. Deze wordt gebruikt in de rest van de thesis. Voor deze statestiek heb ik gebruik gemaakt van de cursussen van kanstheorie van Prof. dr. Callaert en Prof. dr. Veraverbeke. De bewijzen in de hoofdstukken over stochastische algoritmen zijn in de meeste gevallen ge¨ınspireerd door het boek zelf, maar ze zijn verder uitgewerkt, dikwijls versimpeld en soms ook helemaal zelf gemaakt. Ook de oefeningen zijn allemaal zelf gemaakt.