Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » algoks » Forendiskussionen   (Übersicht)

Dies ist eine alte Version des Dokuments!


Forendiskussionen

Lösungsversuch

Lösungen ohne gewähr, da irgendwann zwischen 11 und 1 Uhr und 6-7 Uhr vor der Klausur schnell gemacht (ja abends, und morgens). Ich klatsche es nur hier hin, fuer die naechste Generation. Viel Spaß bei der Klausur m(

Aufgabe 1 - Komplexität

  • a)

a) O(n)

b) O(n³)

c) O(n^2)

d) O(n log n)

e) 1

f) 2

g) O(h²)

h) O(h^4)

  • b)

nein, nein, ja, ja

Aufgabe 2 - Lösen linearer Gleichungsszsteme

a) Erste iteration:

R_1 = |2 1  3|
      |0 1 -2|
      |0 3 -4|

Lösung:

R = |2 1  3|
    |0 1 -2|
    |0 0  2|

L = |1  0 0|
    |2  1 0|
    |-2 3 1| 

b)

x = |-3|
    |3|
    |2|

c)

x_1 = |8|
      |0|
      |0|
      |8|
      
x_2 = |8|
      |-4|
      |-4|
      |8|

d)

x_1 = | 8|
      |-4|
      | 2|
      | 7|

e) Theoretisch exakt, praktisch wegen Rundungsfehlern oft als iteratives Verfahren angewendet.

Aufgabe 3 - Speicherung dünn besetzter Matrizen

a)

val     2 3 -4 7 3 2 2 -1
row_ind 2 3  4 1 2 3 1  3
col_ptr 0 0 3 6 6 8

b)

Speicherung erfolgt im CRS-Format. Hierzu muss nur row_ind als col_ind bzw. col_ptr als row_ptr interpretiert/kopiert werden.

c)

| 0 4  0 0 |
| 0 0  0 0 |
| 0 0  3 8 |
| 0 2 -1 4 |
| 0 0  0 0 |

Aufgabe 4 - Falten und Filtern

a)

ja (1 2 1)^T (1 2 1)

nein

ja (1 2 3)^T (-1 0 1)

b)

5^2 * (N-4)^2

c)

2*5*(N-4)^2

d)

double getValue (const unsigned int& x, const unsigned int& y) const {
    return data.at(2 * x + y);
}

e)

void setValue (const unsigned int& x, const unsigned int& y, double value) {
    data.at(2 * x + y) = value;
}

f)

filter
{
	double filter[3][3] = 
	{
	{0,1,0},
	{1,-4,1},
	{0,1,0}
	};

	for(int x=1;x<src.getDim()-1; x++)
	{
		for(int y=1;y<src.getDim()-1; y++)
		{
			double newValue=0;
			for(int i=0;i<3;i++)
			{
				for(int j=0;j<3;j++)
				{
				newValue+=src.getValue(x-1+i,y-1+j)*filter[j][i];
				}
			}
			dest.setValue(x-1,y-1,newValue);
		}
	}
}

g)

filter
{
	Image tmp(src.getDim());
	double filterX[3]={3,10,3};
	double filterY[3]={1,0,-1};
	for(int x=0;x<src.getDim();x++)
	{
		for(int y=1;y<src.getDim()-1;y++)
		{
			double newValue=0;
			for(int i=0;i<3;i++)
			{
				newValue+=src.getValue(x,y-1+i)*filterY[i];
			}
			tmp.setValue(x,y-1,newValue);
		}
	}

	for(int x=1;x<src.getDim()-1;x++)
	{
		for(int y=1;y<src.getDim()-1;y++)
		{
			double newValue=0;
			for(int i=0;i<3;i++)
			{
				newValue+=src.getValue(x-1,y-1+i)*filterX[i];
			}
			tmp.setValue(x-1,y-1,newValue);
		}
	}
}

Aufgabe 5 - Interpolation

a)

y-Werte = 1, -1, 1, 2

von-nach: 0–0.5, 0,5–1,5, 1,5–3, 3–4(,5)

b)

 | -2x+1
<  2x-3
 | 1/2x

c)

m_1 = 0

m_2 = 3/2

d)

e)

f_p = 8

f)

rho = 1/4

sigma = 1/2

tau = 1/4

f_p = 6

Aufgabe 6 - Bezier-Kurven

meine Sexistische Bildbeschreibung

! i have no idea what i am doing here, schlimmste Bezier-Aufgaben den ich so begegnet bin !

a)

Schaut wie Busen (von oben) aus. :)

b)

Busen der links und rechts ausbuechst :)

c)

„Brustbein“ ist unterhalb des mitleren zackens

d)

Lösungsansatz: i have no idea what i am doing here Zuerst die Ecken:

c_0 = kp[0];
d_(kp.dim-1) =kp[kp.dim -1

Dann den rest mit dem Code aus der Vorlesung (oder Script)

for(k = 1, ....){
   for(i...){
   }

Vor ende der aeusseren For-Schleife die interesanten Werte uebernehmen:

c_k = kp_k
d_kp.dim -k  = kp_kp.dim-k
}

Ggf. Arbeitskopie von kp machen, off by one Fehler

Aufgabe 7 - Singulaerwertzerlegung

a)

Singulaerwerte: 6, 3, 3

Rang: 3

Bildraum: <1/9(1 4 8)^T,1/9(4 7 -4)^T, 1/9(8 -4 1)^T>

Kern: <1/2 (-1 1 1 1)^T

Konditionszahl: 2

b)

Formel

|   5 |
| -11 |
|   9 |
|   7 |

c)

Formel siehe hier fuer Erklaerung.

A_1 = u_1 * sigma_1 * v1^T

A_1 =
1/3 * | 1 1 1 -1 |
      | 4 4 4 -4 |
      | 8 8 8 -8 |

Aufgabe 8 - Nichtlineare Optimierung

a)

x_1 = (9/8 3) ^T

s_0 = (1 0)

b)

maxIter
||x_i+1 - x_i|| < epsilon
||F(x_i)|| < epsilon (Nullstellensuche)

c)

x^1 = (1 3)

d)

(1 0)^T

e) [5/4,13/4] T

Aufgabe 9 - Median Cut

Median Cut konnte ich aus den Vorlesungsfolien nicht nachvollziehen.