Modellering en simulatie

Gegeven door Wim Michiels 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

24 januari 8u

• Wat is een Givens-rotatie? Leg uit hoe Givens-rotaties gebruikt kunnen worden om vierkante matrix te transformeren naar equivalente Hessenberg-matrix? Wat is het nut daarvan in de context van QR-algoritme voor berekenen van eigenwaarden?
• Bespreek volledig jpeg algoritme aan de hand van bijgevoegde figuur. Kan je eveneens een beeld comprimeren met behulp van methoden uit het hoofdstuk "Numerieke lineaire algebra"? Welke, hoe? Geef beknopt antwoord.
• Waarom is variantiereductie belangrijk bij Monte-Carlo methodes? Welke technieken voor variandie-reductie ken je? Leg ze uit een geef plus- en minpunten.
• Spreek over "discrete-time finite-state" Markov-kettingen (definities, relevante begrippen, eigenschappen, voorstellingswijzen, ...) en geef aan hoe men de statinaire (?) toestand ("steady-state") van een systeem dat hierdoor beschreven kan wordne, kan bepalen. Illustreet dit laatste met een klein numeriek voorbeeld. Geef praktisch voorbeeld van systeem dat beschreven kan worden door dergelijke Markov-ketting.

17 januari 13u

• Bespreek QR-factorisatie met kolompivotering (geef algoritme). Hoe kan men QR gebruiken om een lage rang benadering te verkrijgen? Ken je nog een andere manier om een (goede) lage rang benadering te krijgen?

• 2D FFT. Vergelijk complexiteit hiervan met die van rechtstreeks gebruik van de formules. (formules voor x_m,n en X_m,n gegeven). Bespreek kort hoe men dit kan gebruiken voor beeldcompressie.

• Geef algemene definitie voor de volgende begrippen: status, entiteit, attribuut, gebeurtenis, bericht, activiteit, vertraging, klok. Beschrijf een wachtrijsysteem met 2 bedieners en duidt alle begrippen duidelijk aan in je beschrijving. Beschrijf de gebeurtenissen a.d.h.v. flow-charts.

• Bespreek discrete birth-death processen. Welke verdelingen zijn van belang en waarvoor dienen ze? Wat weet je nog meer over deze processen (vermeld zeker memoryless, birth rate, death rate, steady state).

25 januari 13u

• Leg QR algoritme zonder split uit voor bepalen van eigenwaarden en eigenvectoren van een vierkante matrix A. Leg de werking uit door analogie uit te leggen met deelruimte iteratie.

Wat is de bedoeling van QR met split ? Leg dit verder uit aan de hand van de matrix A_k=[a b ; epsilon c] (waarbij ook de formule voor A_k+1 = R_k Q_k + Kappa I gegeven is).

• Leg het jpeg algoritme uit aan de hand van de figuur uit de cursus (de figuur met 6 matrices ondereen: coëfficiënten, quantisatiematrix, ...). Zijn er uit het hoodstuk Numerieke Lineaire algebra ook methodes die je kan gebruiken om afbeeldingen te comprimeren (hij doelt hiermee op lage rang benadering).

• Wat zijn stochastic activity networks ? Wat is het ? Hoe wordt het gemodelleerd en gesimuleerd ?

• Geef een algemene definitie voor volgende begripppen: status,entiteit,attribuut,gebeurtenis,bericht, activiteit, klok en vertraging. Stel een model op van een wachtrijsysteem met 2 bedieners en duid hierbij de bovenstaande begrippen aan. Beschrijf de verbanden en interacties tussen entiteiten. Stel ook flow diagramma op voor dit systeem?

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 fourier 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.

11 januari voormiddag

1) QR factorisatie. Givens algoritme + kort een ander naar keuze (Givens met kolompivotering was voldoende blijkbaar). Leg ook uit of de QR factorisatie al dan niet uniek is. (Deze is uniek als A vierkant en van volle rang is, als A niet vierkant en van volle rang is, is enkel de gereduceerde QR-factorisatie uniek. Als A niet van volle rang is, is de QR-factorisatie niet uniek.)

2) Vermenigvuldigen veeltermen en grote getallen met DFT. Complexiteit geven.

3) Waaraan moeten pseudo RNG voldoen? Hoe bouw je continu niet-uniforme verdelingen? Geef enkele voorbeelden waaronder zeker eentje die vaak voorkomt in Markov kettingen. Geef voordelen, nadelen, moeilijkheden, ... Leg ook uit wat de problemen waren bij het genereren van uniforme punten in een cirkel/driehoek, refereer hiervoor naar je ervaring uit de oefenzittingen.

4) Model maken voor systeem met twee bedieningsstations, flow diagramma's maken en enkele begrippen uitleggen (status, activiteit, ...).

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