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

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
pruefungen:bachelor:algoks:loesungws15 [20.07.2016 21:30] – tomabrafixpruefungen:bachelor:algoks:loesungws15 [05.08.2020 08:52] (aktuell) – nename0
Zeile 55: Zeile 55:
 **a)**\\ **a)**\\
   val = [5, 1, 3, -6, -2, -1]   val = [5, 1, 3, -6, -2, -1]
-  col_idx = [2, 4, 2, 4, 1, 3]+  col_ind = [2, 4, 2, 4, 1, 3]
   row_ptr = [1, 1, 3, 3, 5, 7]   row_ptr = [1, 1, 3, 3, 5, 7]
  
 **b)**\\ **b)**\\
 +Im CRS-Format sind gegeben: val, col_ind, row_ptr
 Von Null verschiedene Von Null verschiedene
-  * Zeilen: Anzahl versch. Elemente in col_ptr - 1 +  * Zeilen: Anzahl versch. Elemente in row_ptr - 1. Alternativ: for i in range(0, len(row_ptr)-1): if (row_ptr[i] != row_ptr[i+1]) row_count++; 
-  * Spalten: Anzahl versch. Elemente in col_idx +  * Spalten: Anzahl versch. Elemente in col_ind 
-  * Elemente: letztes Element row_ptr - 1+  * Elemente: letztes Element row_ptr - 1. Alternativ: len(val) = len(col_ind)
  
 **c)**\\ **c)**\\
Zeile 74: Zeile 75:
 ==== Aufgabe 5 (Polynominterpolation) ==== ==== Aufgabe 5 (Polynominterpolation) ====
 **a)**\\ **a)**\\
-          | -1   fuer x in [-1, 0] +          | -1   fuer x in [-1, 0) 
-   l(x) = {  2   fuer x in [0, 1.5]+   l(x) = {  2   fuer x in [0, 1.5)
           |  4   fuer x in [1.5, 2]           |  4   fuer x in [1.5, 2]
                      
 **b)**\\ **b)**\\
-          | 3/2x + 1/2   fuer x in [-1, 0] +          | 3x/2 + 1/2   fuer x in [-1, 1) 
-   l(x) = { 2x           fuer x in [0, 1.5]+   l(x) = { 2x           fuer x in [1, 2]
  
 **c)**\\ **c)**\\
Zeile 86: Zeile 87:
 l_1 = [(x+1)(x-2)/(1+1)(1-2)] = -1/2 * (x^2 -x -2)\\ l_1 = [(x+1)(x-2)/(1+1)(1-2)] = -1/2 * (x^2 -x -2)\\
 l_2 = [(x+1)(x-1)/(2+1)(2-1)] = 1/3 * (x^2 - 1) l_2 = [(x+1)(x-1)/(2+1)(2-1)] = 1/3 * (x^2 - 1)
 +
 +Ich glaube nicht, dass das Ausmultiplizieren gefordert war. Dies wird in neueren Klausuren auch explizit angemerkt.
  
 **d)**\\ **d)**\\
-p(x) = -l_0 + 2*l_1 + 4*l_2 = -1/6 * (x^2 -3x +2) -(x^2 -x -2) + 4/3 * (x^2 - 1)+-1, 2 und 4 (das sind genau die y_i)
  
 **e)**\\ **e)**\\
Zeile 119: Zeile 122:
      
  **b)**\\  **b)**\\
-b_0 = (18, 8)^T +Affine Transformation \Phi(x, y) = (y, x)^T + (-2, 0)^T. 
-b_1 = (10, 0)^T + 
-b_2 = (2, 8)^T +b_0 = (14, 8)^T 
-b_3 = (58, 32)^T+b_1 = (6, 0)^T 
 +b_2 = (-2, 8)^T 
 +b_3 = (54, 32)^T
  
 **c)**\\ **c)**\\
 +
 +Sehr ungenau, aber man sieht das Konzept: https://i.imgur.com/IPK64lC.png
  
 **d)**\\ **d)**\\
Zeile 133: Zeile 140:
 **e)**\\ **e)**\\
  
 +Man skizziere sich drei Punkte und führe den De-Casteljau-Algorithmus aus.
 +Zuerst interpoliert man d_0 und d_1: 1/2 (d_0 + d_1)\\
 +Dann d_1 und d_2: 1/2 (d_1 + d_2)\\
 +Nun interpoliert man diese beiden Punkte und gelangt zu:\\
 +1/2 (1/2 (d_0 + d_1)) + 1/2 (1/2 (d_1 + d_2)) = 1/4 d_0 + 1/2 d_1 + 1/4 d_2
  
 ==== Aufgabe 7 (Programmierung: Bilineare Interpolation) ==== ==== Aufgabe 7 (Programmierung: Bilineare Interpolation) ====
 +<code> 
 +def getInterpolatedPixel(img, u, v): # img ist np array 
 +  xf = v * (img.shape[1] - 1) 
 +  yf = u * 8img.shape[0] - 1) 
 +  p00 = (floor(xf), floor(yf)) 
 +  p01 = (ceil(xf), floor(yf)) 
 +  p10 = (floor(xf), ceil(yf)) 
 +  p11 = (ceil(xf), ceil(yf)) 
 +  w0 = xf - p00[0] 
 +  w1 = yf - p11[1] 
 +  return w1 * ((1-w0) * img[p00] + w0 * img[p01]) + (1-w1) * ((1-w0) * img[p10] + w0 * img[p11])) 
 +</code>
 ==== Aufgabe 8 (Baryzentrische Koordinaten) ==== ==== Aufgabe 8 (Baryzentrische Koordinaten) ====
 **a)**\\ **a)**\\
Zeile 152: Zeile 175:
  
 **d)**\\ **d)**\\
-  * rho < 0, sigma > 0, tau > 0 +  * rho < 0, sigma > 0, tau > 0, rho + sigma + tau = 1 
-  * rho > 1, sigma < 0, tau < 0+  * rho > 1, sigma < 0, tau < 0, rho + sigma + tau = 1. (rho > 1 ist redundant, da dies aus rho = 1 - sigma - tau > 1 folgt.)
  
 ==== Aufgabe 9 (Faltung) ==== ==== Aufgabe 9 (Faltung) ====
Zeile 164: Zeile 187:
  
 **c)**\\ **c)**\\
-Wegen d_a(x) = d(x-a) gilt Integral( f(x) * d_a(x-a) dx) = f(a)+(f * d_a)(x) = \int f(y) d_a(x-y) dy = f(x-a), denn x - y = a <=> y = x - a, und an dieser Stelle wird f 'evaluiert'. Steht auch so in den Folien.
  
 **d)**\\ **d)**\\
-Der erste Uebergang leicht nach unten gebogen, dann linear:+Der erste Uebergang leicht nach unten gebogen (quadratisch), dann linear:
 (-1/2, 0) -> (3/2, 1) -> (3/2 + x, 1 + x) (-1/2, 0) -> (3/2, 1) -> (3/2 + x, 1 + x)
 +
 +Quadratisch kommt daher, dass man in das erste Dreieck hineinläuft. Die 'Slices' des Dreiecks, die man immer hinzufügt, werden größer und größer, sozusagen 1 + 2 + 3 + 4, was bekanntermaßen O(n^2) ist.\\
 +Es tritt dann bei x=0,5 vollkommene Überlappung auf. Nun haben wir ein Trapez, das mit größer werdendem x immer weiter nach rechts geschoben wird und oben durch f begrenzt wird. Formel für den Flächeninhalt eines Trapezes ist h * (a + c)/2. Die Höhe, oder hier die Breite des Trapezes, ändern wir nicht, sie bleibt konstant 1. Lediglich a und c ändern wir, diese sind aber gerade die Bilder unter f. Da diese immer 'gleichzeitig' nach rechts geschoben werden, ändert sich a + c auch nur linear. Der Flächeninhalt ist also linear in x. Nun braucht man nur zwei Punkte sich im Kopf kurz zu errechnen und zeichnet sich seine Gerade durch.
 +
 +**e)**\\
 +Unterscheide nach x < -2, -2 <= x <= 2, 2 < x < \infty.\\
 +(f*g_2)(x) =\\
 +0 falls x < -2,
 +1/8 (x+2)^2 falls 2 <= x <= 2,\\
 +x falls 2 < x < \infty (also sonst)
 +
 +==== Aufgabe 10 (Hauptkomponentenanalyse) ====
 +
 +**a)**\\
 +
 +Schwerpunkt S = (1, 1)^T\\
 +A := (p_0 - S | p_1 - S | ... | p_4 - S)
 +
 +Dann ist C = 1/(5 - 1) * AA^T = 1/2 {{9, 0}, {0, 4}}.
 +
 +**b)**\\
 +<code>
 +det(B-\lambda Id) = (1-\lambda)(7-\lambda) // bitte a^2-b^2 = (a-b)(a+b) nutzen :)
 +
 +Eig(1) = span{(1, 1)^T}\\
 +Eig(7) = span{(-1, 1)^T}</code>
 +
 +==== Aufgabe 11 (Numerische Integration) ====
 +
 +**a)**\\
 +2 + 18 = 20
 +
 +**b)**\\
 +1/8 * ( 0+1 + 1+8 + 8+27 + 27+64) = 136/8 = 17
 +
 +**c)**\\
 +<code>
 +T_f(1/2) = 20    \
 +                  v
 +T_f(1/4) = 17  ---> T_f^1 (1/4) = (4T_f(1/4) - T_f(1/2))/3 = 16 (was übrigens der exakte Wert des Integrals ist)
 +</code>
 +
 +**d)**\\
 +<code>(1 - 0) * (1/6 * f(0) + 4/6 * f((0 + 1)/2) + 1/6 * f(1)) = 16</code>
 +
 +Hier muss der exakte Wert rauskommen, denn die Simpson-Regel angwandt auf ein kubisches Polynom ist immer exakt (folgt aus der einen Fehlerabschätzung, welche max{|f^(4)(x)|} erwähnt, was ja 0 bei kubischen Polynomen ist!).
 +
 +**e)**\\
 +O(h^2)
 +
 +**f)**\\
 +O(h^4)