Toeval als methode: Random Algorithms

Najaarssemester 2003

Periode: 01/09/2003 - 19/12/2003
(Herfstvakantie: 20/10/2003 - 24/10/2003)

College/Werkcollege: Dinsdag, 15:30 - 17:30, t/m 14 oktober: N0001
Vrijdag, 15:30 - 17:30, A2043

vanaf 27 oktober:

Maandag, 10:30 - 12:30, A2043 (uitzonderingen: 3 november in CK N7 (N4011), 1 december in CK N6 (N4009))
Woensdag, 8:30 - 10:30, N0001a

Omschrijving

Er zijn verschillende motivaties om random methodes in algoritmes te gebruiken. De meest belangrijke heeft te maken met efficiëntie, want een rigoureuze algoritme kan door het gebruik van toevallige keuzes een grote versnelling ervaren zonder dat de resultaten veranderen (ten minst met hoge kans).
Vaak is het ook makkelijk een resultaat te verifieren dat met behulp van een geheimzinnig methode verkregen is.
Dus maakt een aanpak met een random methode berekeningen mogelijk die met deterministische methodes meer tijd en/of geheugen dan beschikbaar zouden gebruiken.
Een voorbeeld zijn algoritmes om getallen op priemaliteit te testen. Met klassieke methodes zoals het zeef van Eratosthenes kunnen we zeker niet verder dan getallen met 20 cijfers terwijl het met moderne methodes die toevallige keuzes gebruiken ook voor getallen met enkele honderd cijfers nog lukt.

Een andere bron van interesse voor randomness zijn toepassingen waarbij het gewenst is dat uitkomsten onvoorspelbaar zijn. Voorbeelden hiervoor zijn cryptografie (bijvoorbeeld het genereren van publieke sleutels) of software certificatie (bijvoorbeeld tests van compilers).

In dit college zullen we verschillende onderwerpen behandelen waarbij randomness een rol speelt. We beginnen met het genereren van rijen random getallen en zullen verder kijken naar problemen zoals het ontbinden van getallen in priemfactoren of het efficiënte rekenen in (grote) permutatiegroepen tot Monte Carlo en Las Vegas simulaties.

Geplande onderwerpen

Dictaat

Er zullen samenvattigen van de colleges beschikbaar gesteld worden: in pdf of ps formaat.

Huiswerk

Opgaven 1 9 september 2003
Opgaven 2 16 september 2003
Opgaven 3 30 september 2003
Opgaven 4 19 november 2003

Eindopdrachten 8 december 2003

Tentaminering

Inleveren en presentatie van de eindopdrachten.