Modellering en simulatie

Fout bij het aanmaken van de miniatuurafbeelding: Bestand is zoek

Gegeven door Ann Haegemans en Ronald Cools

Het Examen

Het examen is mondeling, gesloten boek met schriftelijke voorbereiding.

En enkele nota's uit de laatste les van Cools:

• Oppervlakkige kennis was vorig jaar (blijkbaar) voldoende, maar dit jaar niet meer. Enige diepgang vereist in de antwoorden
• Voldoende op papier zetten!

Practica

Yahtzee simulatie. Lage rang benadering. Tellen mee voor 4/20 punten.

Examenvragen

11 januari 13u

• Wat is een Givens rotatie? Hoe wordt deze gebruikt bij het omvormen van een matrix A tot een Hessenberg matrix? Wat is daarvan het voordeel voor het QR-algoritme?

• Bespreek het splitsingsalgoritme van Danielson-Lanczos en leg gedetailleerd de snelle fourrier transformatie uit. Sta hierbij stil bij de hoeveelheid rekenwerk.

• Continuous-time birth-death-proces uitleggen.

• Waarom wordt variatiereductie gebruikt bij Monte Carlo? Welke technieken ken je? Bespreek voor en nadelen.

2008-2009

Practica: lagerangbenadering en spel van de raaf

24 augustus 2009, 8:00

• Legt QR algoritme voor bepalen van eigenwaarden en eigenvectoren van een vierkante matrix A. verklaar de convergentie door analogie uit te leggen met deelruimte iteratie. mogelijke verbeteringen ? als A symmetrisch, welke is de invloed van het methode. (--> hier moet je de convergentie volledig kunnen uitleggen/bewijzen !!)

• De discrete fourier transformatie en de inverse discrete fourier transformatie zijn gegeven door:

$X_k=\sum _{n=0}^{N-1}{x}_n{W}_N^{kn},k=0,\dots ,N-1$

$x_n=\frac{1}{N}\sum _{k=0}^{N-1}{X}_k{W}_N^{-kn},n=0,\dots ,N-1$

$W_N=e^{2\pi i/N}$

Leg in het kort uit hoe de snelle fouriertransformatie werkt. Veralgemeen dit naar twee dimensies en beschrijf een snel algoritme voor de transformatie van een 2-dimensionaal beeld van $M\times N$ pixels. (-->je moet zeker de complexiteit kunnen hebben + hoe je daaran komt)

• legt uit "stochastic activity networks" en leg verbanden met monte carlo.

• wat weet u over inventarissystemen? leg hierbij de volgende concepten uit: status,entiteit,atribuut,gebeurtenis,bericht, activiteit, klock en vertraging. Beschrijf de verbanden en interacties tussen entiteiten. flow diagramma's voor die systeem?

Prof Haegemans was deze keer wel aanwijzig + die stelde veel bijvragen (-_-).

13 januari 2009, 13.30

• QR algoritme + verband met deelruimte iteratie. Wat zijn mogelijke verbeteringen ?
• Cellulaire automaten: wat zijn ze, welke soorten ken je, welke toepassingen ?
• toevalsgeneratoren voor continue verdelingen: waaraan moeten ze voldoen ? hoe maken ? theorie + voorbeelden. Welke problemen ben je tegengekomen in de oefenzittingen bij het maken van een RNG om uniform een punt te kiezen in een cirkel of driehoek.
• beschrijf een wachtrij model met 2 servers, leg allerlei begrippen uit en duid aan.

Prof. Cools was zeer vriendelijk. Prof Haegemans kon er niet zijn, dat deel was schriftelijk.

19 januari 2009, 13.30

• Hoe definieert men een 'continuous-time birth-death' proces? Welke waarschijnlijksverdelingen spelen hierin een rol en wat is die rol? Wat weet u nog over dergelijke processen? (Ik verwacht in uw uitleg ondermeer de begrippen 'memoryless', 'birth rate', 'death rate', 'steady state'). Geef een hoog niveau beschrijving van het algoritme om een dergelijk proces te simuleren. Geef het verband tussen een dergelijk proces en wachtrijen.
• Waarom is variantiereductie belangrijk bij Monte Carlo methodes? Welke technieken voor variantiereductie kent u? Leg ze uit en geef hun plus- en minpunten.
• Wat is een orthogonale projector? Welke deelruimtes zijn hiermee geassocieerd? Hoe kan men gegeven een willekeurige (niet noodzakelijk orthogonale) basis van een deelruimte $S\subset {\mathbb{ℝ}}^m$ een orthogonale projector opstellen? Bepaal een orthogonale projector op de deelruimte van ${\mathbb{ℝ}}^3$, opgespannen door

$[2,0,1{]}^T,[1,-1,1{]}^T$

• De discrete fourier transformatie en de inverse discrete fourier transformatie zijn gegeven door:

$X_k=\sum _{n=0}^{N-1}{x}_n{W}_N^{kn},k=0,\dots ,N-1$

$x_n=\frac{1}{N}\sum _{k=0}^{N-1}{X}_k{W}_N^{-kn},n=0,\dots ,N-1$

$W_N=e^{2\pi i/N}$

Leg in het kort uit hoe de snelle fouriertransformatie werkt. Veralgemeen dit naar twee dimensies en beschrijf een snel algoritme voor de transformatie van een 2-dimensionaal beeld van $M\times N$ pixels.

2006-2007

Maandag 11 juni, groene opgaves

Cools was zeer vriendelijk. Hij probeert je redenering te volgen om te zien waar je in de fout gaat, zonder met veel woorden te zeggen dat je in de fout gaat. Bijvragen op details, geeft je wel wat bedenktijd.

Haegemans wil het onderste uit de kan halen. Het papegaaienwerk doorziet ze meteen. Stel bij alles wat je wil opschrijven de Waarom vraag en je hebt een idee van de bijvragen. Alles wat je niet goed kunt antwoorden legt ze gedetailleerd (maar snel) terug uit. Formules veronderstelt ze dat je kunt toepassen en "afleiden" (ik had bv in Givensrotatie de elementjes in de teller van plaats gewisseld, heeft uitgerekend om aan te tonen dat ik dan het verkeerde element 0 maak. Kuch). Complexiteit niet van buiten leren, ze wil toch weten of je het kunt aantonen.

Je hebt meer dan genoeg tijd om onderstaande vragen op te lossen. Opschrijven alsof het een schriftelijk examen is.

1) Leg het wachtrijsysteem met 2 bedieners uit adv een model. Leg status, entiteit, attribuut, gebeurtenis, bericht, activiteit, vertraging en de systeemklok uit. Duidt aan. Beschrijf de verbanden en interacties tussen entiteiten. Illustreer gebeurtenissen adv flow diagramma's. (Flow diagramma's beslissing opsplitsen voor elke bediener).

2) Leg uit hoe een software generator voor een niet uniforme verdeling gemaakt wordt. Geef theorie en voorbeelden. Beschrijf moeilijkheden, performantie,... Wat verwacht je van een software random generator (voldoen aan statistische eigenschappen, reproduceerbaar door seed, systeemoverdraagbaar, ...)

3) Leg de Givensrotatie uit (welke speciale eigenschappen heeft deze matrix. Waarom kiezen we c²+s²=1). Hoe wordt deze gebruikt voor de QR factorisatie (FORMULES KENNEN!). Hoe wordt Q bekomen, hoe wordt R bekomen. Hoe wordt per givensrotatie elke element in een rij beinvloedt? Geef complexiteit van deze methode. Ken je nog een andere methode voor de QR factorisatie? Bespreek diens complexiteit en de verschillen met deze. Waarvoor worden QR factorisaties gebruikt?

4) Leg het discrete FFT uit adv stroomschema N=8 in boek. Bewijs stelling Danielson. Wat is zijn complexiteit voor N = 2^m (EN leg uit hoe je hieraan komt!). Hoe kunnen we FFT gebruiken voor compressie (JPG, meerdimentionale FFT,..).

Zoals gezegd in de les

Zoals overlopen in de lessen van professor Haegemans (maar ze ging er nogal snel over, weet dus niet of ik alles juist opgeschreven heb ;))

- Uitleggen van orthogonale projectie - Waarvoor dient de Givens rotatie en hoe passen we die toe? Waarvoor dient de bovendriehoeksmatrix. Geef de complexiteit van de methode.

- Leg de Lage rang benadering in detail uit (ref. practicum!)

- Beschrijf in detail de methode van de machten (via 1 vector en via deelruimte)

- Waarvoor dient QR factorisatie. Welke varianten bestaan er. Vergelijk deze onderling (werking, complexiteit).

- Wat zijn Cellulaire automaten? Welke soorten zijn er? Hoe worden ze ingedeeld? Hoe worden ze gebruikt? Geef een practische toepassing (ref encodering).

- Een vraag over Fourier Analyse: formules kunnen opstellen, tekening uitleggen, toepassingen geven

Voorbeeldexamenvragen

- Spreek over de stappen die nodig zijn om een wiskundig model om te zetten in een computerprogramma.

- Wat is een orthogonale projector. Welke deelruimtes zijn er geassocieerd met een orthogonale projector. Hoe kan men, gegeven een willekeurige (niet noodzakelijk orthogonale) basis van een deelruimte $S\subset R^m$ een orthogonale projector op die deelruimte construeren?

- Leg uit hoe men een tweedimensioneel beeld kan comprimeren door middel van Discrete Fourier Transformaties (DFT).

- Bespreek het genereren van toevalsgetallen die continu, niet-uniform verdeeld zijn.

- Beschrijf m.b.v. een flow-diagramma de aankomstgebeurtenissen in een wachtrijsysteem met twee bedieners. Duid in het diagramma aan wanneer en hoe de systeemstatus wordt aangepast. Duid eveneens het plannen van toekomstige gebeurtenissen aan.

- Geef een aantal toepassingen van cellulaire automaten.

2005-2006

- Uitleg geven rond Hessenbergmatrix: wat is het? hoe verkrijgen? nut?

- vraag rond DFT