Lösungsversuch Klausur 12. Februar 2013

Bachelor Algorithmik kontinuierlicher Systeme
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Lösungsversuch Klausur 12. Februar 2013
Hier mal meine Versuche zur letzten Klausur:

O(n²), O(n³), O(n³), O(n²), O(n), O(n²), O(n²)?, O(n²)?

a) Nicht wirklich ne Ahnung, soll das irgendwie allgemein funktionieren?

EDIT:
P1(0,0,1)
P2(1/2,0,1/2)
P3(1/3,1/3,1/3)
P4(1,1,-1)

b) LINKS: der Bereich gegenüber von R ohne die Dreiecke links und rechts
RECHTS: der Dreiecksbereich unter R

c) Ich weiß nicht ob ich da auf dem richtigen Weg bin. Interpoliere zuerst in x-Richtung, einmal oben, einmal unten.
f(R1) = 13-5/4x
f(R2) = 11+1/2x
Jetzt müsste ich doch nochmal in y-Richtung gehen oder? Kommt bei mir aber ein ganz schöner Mist raus. Kann man den Punkt dann einfach einsetzen und damit weiterrechnen? Wäre mein Ergebnis 9.

EDIT: Richtiges Ergebnis wohl 12.

d) keine Ahnung wie ich das angehen soll

EDIT: 11

Filter haben wir damals kaum gemacht, wäre nett wenn mir da jemand bisschen auf die Sprünge helfen könnte.
a) Nicht separierbar, separierbar (-1,-2,-1)^T (-1,0,1), nicht separierbar, separierbar (1,1,1,1)^T (1,1,1,1)
Vorfaktoren sind soweit ich weiß egal, es geht ja nur um lineare Abhängigkeit.
b)?
c)?
d) (0, 1, 0)
(1, -4, 1)
(0, 1, 0)
e)Sobel: Kantendetektion, TP: Glättung

a) x=(0.5, 2, -1, 2)^T
b) det(A) = det(R) = 54
c)
Q= |0.6 -0.8 |
|0.8 0.6 |
R= |5 0.2 |
|0 -1.4 |

a) Hab ich als Ergebnis von Casteljau: (6 4)^t
b) Wie genau funktioniert dass denn formal? Ich weiß wie die Kurve ca aussehen muss, aber wenn da ein t angegeben ist, soll das wohl recht exakt sein? Muss man da irgendwie die Strecken zwischen den Punkten nutzen?
c) kA

EDIT:

a) SW: 6/4, 3/4, 2/4
Rang: 3
Bild: die drei Spaltenvektoren von U inkl Vorfaktor
Kern: (1 -1 -1 1)^T
Kond: 3

b) Als Covarianzmatrix:
C=
| 18 0 |
1/4*| 0 8 |

EDIT: Da Diagonalmatrix sind die EW einfach die Werte auf der Diagonalen und die EV die Spaltenvektoren, also zB (1,0)^T und (0,1)^T

a)
-1 für -1<= x < 0
2 für 0 <= x < 1,5
4 für 1,5 <= x < 2

b) [-1;1]: 3/2x + 1/2
[1;2]: 2x

c)
L0: (x-1)/-2 * (x-2)/-3
L1: (x+1)/2 * (x-2)/-1
L2: (x+1)/3 * (x-1)

L(x)=y0L0+z1L1+y2*L2

d)
N0: 1
N1: (x+1)
N2: (x+1) * (x-1)

c0=-1, c1=3/2, c2= 1/6

Bitte bei Fehlern berichtigen, ich ändere das dann hier und trags dann noch ins Wiki ein.

Grüße

3

Kann es sein, dass in der Aufgabenstellung der 3.b) hier “die inneren (N-4)x(N-4) Pixel” gemeint sind? Statt (N-2)x(N-2)…

4
  1. … damit kenn ich mich nicht aus :wink:
    2a) keine Ahnung, weiß hier irgendjemand, was die richtige Lösung ist?

b) passt
c) 12
d) 11 (ich habe mir beta, gamma, delta berechnet über die Formel für baryzentrische Koordinaten und dann mit beta * f_b + gamma * f_c + delta * f_d das Ergebnis berechnet, geht das irgendwie schneller?)

3a) zum 2. Filter: (-1, -2, -1)^T (1, 0, -1)
zum 4. Filter: 1/2(1,1,1,1)^T * 1/6(1,1,1,1) (Vorfaktoren nicht vergessen - ich weiß aber nicht, ob man die einfach beliebig wählen kann??)
b) c) ?
d) (0, 1, 0)
(1, -4, 1)
(0, 1, 0)

4a) ich habe x = (1, 2, -1, 2)^T (kann auch ein Rechenfehler sein)
b) passt
c) da gibts ja glaub ich mehrere Lösungen…

6a) (6 5/3)^T (kann auch ein Rechenfehler sein)
b) du musst die Strecken zwischen den Punkten im Verhältnis 1/3 zu 2/3 teilen und jeweils diese neuen Punkte miteinander verbinden → wieder teilen usw.
c) ?

a) ist die Konditionszahl nicht der 6/4 durch 3 → 1/2 ? (ich habe das aus Blatt 8 Aufgabe2d)
b) habe die gleiche Covarianzmatrix, EW/EV keine Ahnung

b) es ist doch nearest neighbor gefragt → oder verwechsle ich da gerade etwas?
-1 für -1<= x < 0
2 für 0 <= x < 1,5
4 für 1,5 <= x < 2

8c) und d) hab ich genauso

5

Also ich hab mir jetzt hierzu (und auch für das Rechteck) eine kleine Zeichnung gemalt und die Flächenverhältnisse berechnet. Damit gehts eigentlich ganz gut, zumindest wenn man einen karierten Block hat. :smiley: Weiß jemand, ob dieser Weg in Ordnung ist (also zeichnen und über die Flächeninhalte berechnen)?

6

die 6a hab ich auch so und bei der c) muss man einfach die Formel, die angegeben ist, benutzen. Dabei ist halt das B_i^n das Bernsteinpolynom und bei der Summe muss man einfach einmal i = 0 und einmal i = n setzen, da 0 und n ja die Endpunkte sind. Dann noch f(0) und f(1) ausrechnen und dann kommt genau das was zu zeigen ist raus.

die Konditionszahl bei der SVD ist ja sigma_max / sigma_min, also 6/4 / 2/4 = 3

bei der b) musst du stückweise linear interpolieren, da hab ich auch

7

2a) P1(0,0,1)
P2(1/2,0,1/2)
P3(1/3,1/3,1/3)
P4(1,1,-1)

2b) hab ich auch so

2c) hab ich auch 12

2d) hab ich auch 11

5b) alpha = 1, x1= (1,0)^T, g1=(1,0)^T, beta=1, s1=(-1,-1)^T, x2=(0,-1)^T

5c) s0=(-4,-2)^T, t0= 7/11, x1=1/11*(35, 25)^T

6a) 1/3*(13, 5)^T

7a) hab ich auch so
|18 0|
7b) hab ich auch die Covariansmatix mit 1/4* | 0 8| , dann für lambda1= 7,67 und lambda2 -1,17, kann mir aber vorstellen, dass das nicht so stimmt

  1. hab ich auch so
8

aaaachja stimmt, danke!

9

Das ist eine Diagonalmatrix und da sind die Diagonaleinträge einfach die EW und die Einheitsvektoren die EV, also v1=(1, 0)T und v2=(0,1)T. :wink:

10

oh mann…klar! danke!!!

11

Hab mal einiges oben editiert.

Zur 2c,d)
Könntet ihr da bitte kurz euer Vorgehen beschreiben? Meins hat so ja offensichtlich nicht ganz gestimmt.

[quote=ANE:1374849846]
5b) alpha = 1, x1= (1,0)^T, g1=(1,0)^T, beta=1, s1=(-1,-1)^T, x2=(0,-1)^T

5c) s0=(-4,-2)^T, t0= 7/11, x1=1/11*(35, 25)^T[/quote]

Kannst du das bitte mal erklären? Ich scheitere schon an der a) weil mir der Ansatz nicht klar ist…

12

zur 2c) und d)
Stichwort: gewichtete Flächen

also zum gegeben f_a multiplizierst du die gegenüberliegende Fläche,
das machst du mit den anderen genauso und addierst sie dann alle zusammen (nicht vergessen durch die Gesamtfläche zu teilen)

Attachment:
IMAG0385.jpg: https://fsi.cs.fau.de/unb-attachments/post_123519/IMAG0385.jpg

13

[quote=xlemmingx]
Hab mal einiges oben editiert.

Zur 2c,d)
Könntet ihr da bitte kurz euer Vorgehen beschreiben? Meins hat so ja offensichtlich nicht ganz gestimmt.

schau mal, ich hoffe das stimmt alles so!?

14

so diesmal mit anhang :wink:

2c ist hier noch falsch!!!

Attachment:
2cd.docx: https://fsi.cs.fau.de/unb-attachments/post_123521/2cd.docx

15

Danke, das sieht schlüssig aus, jetzt weiß ich auch was mit gewichteten Flächen gemeint ist. Aber eigentlich braucht man doch bei dem Ansatz von ANE bei der c) nur die letzten beiden Zeilen? Wozu berechnest du alpha und Fp1/Fp2? Bzw in welchem Fall würde man das brauchen?

Bei der d) erschließt sich mir nicht ganz wie du auf das Gleichungssystem mit der Matrix kommst? Der Rest ist dann klar, aber woher nimmst du die Matrix und den Ergebnisvektor?

16

oh mann…hab ich falsch hingeschrieben…eigentlich musst du für fA und fD, die fP1, fP2 und ihre werte hinschreiben und es kommt zufällig das gleiche raus! sorry!!!

Attachment:
2c.docx: https://fsi.cs.fau.de/unb-attachments/post_123527/2c.docx

17

Hier mal noch die CCS-Programmieraufgabe, sollte Pi mal Daumen stimmen. Ansonsten gibts ja fuer CRS auch schon Musterloesungen.

// a)
CCSMatrix::CCSMatrix(uint height, uint width){
	_height = height;
	_width = width;
	_nonZeroElements = 0;
	_values = null;
	_rowIndices = null;
	_colPtr = width + 1;
}

// b)

float CCSMatrix::getEntry(uint i, uint j){
	temp = _colPtr[j] - _colPtr[j-1];
	if(temp != 0){
		for(int k=0; k<sizeof(_rowIndices); k++){
			if(_rowIndices[k] == i){
				return _values[k];
			}
		}
	}
	else
		return 0.0f;
}

// c)

CCSMatrix::CCSMatrix(Matrix &other){
	_height = other.getHeight();
	_width = other.getWidth();
	_nonZeroElements = other.getNumNonZeroEntries();
	_values = new uint[_nonZeroElements];
	_rowIndices = new uint[_nonZeroElements];
	_colPtr = new uint[_width + 1];

	uint numVal = 0;
	_colPtr[0] = 0;

	for(int j=0;j<_width;j++){
		for(int i=0;i<_height;i++){
			if(other.getEntry(i,j) != 0){
				_values[numVal] = other.getEntry(i,j);
				_rowIndices[numVal] = i;
				numVal++;	
			}
		}
		_colPtr[j+1] = numVal;
	}
}

// d)

Matrix Matrix::operator*(CCSMatrix &other){
	Matrix result(_height, other._width);

	int temp = 0;
	int col = 0;

	for(int i=0;i<other.getNumNonZeroElements(); i++){
		while(_colPtr[temp] == _colPtr[temp+1] || i == _colPtr[temp+1]){
			col++;
			temp++;
		}
		for(j=0;j<other.getHeight();j++){
			result.setEntry(j,col,result.getEntry(j,col) + other._values[i] * this.getEntry(j,rowIndices[i]))
		}
	}
	return result;
}
18

Was ist denn so die Vorgabe, wie eine leere Matrix initialisiert werden soll? hier also in der CCSMatrix(height, width)!
Warum genau setzt du da die nonZeroElements auf MxN ?

19

Oehm, weil ich wohl noch geschlafen habe. Muss natuerlich 0 sein.

20

ich komme da auf ganz komische Ergebnisse wie (6,23/9)