Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen   (Ü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:aud:loesungss12 [18.02.2013 20:04] – Dawodopruefungen:bachelor:aud:loesungss12 [28.03.2016 01:38] (aktuell) – tomabrafix
Zeile 1: Zeile 1:
 ===== Forendiskussionen ===== ===== Forendiskussionen =====
  
-FIXME - Bitte um Forenthreads erweitern!+  * [[https://fsi.informatik.uni-erlangen.de/forum/thread/9989-Klausur-02-08-12-Algo-von-Floyd]]
  
 ===== Lösungsversuch ===== ===== Lösungsversuch =====
Zeile 14: Zeile 14:
  
 **d)** **d)**
-  * Passt+  * Passt nicht, die Vererbungsbeziehung fehlt
   * Passt   * Passt
   * Passt nicht, die Vererbungsbeziehung geht in die andere Richtung   * Passt nicht, die Vererbungsbeziehung geht in die andere Richtung
Zeile 24: Zeile 24:
 **f)** (unsicher) **f)** (unsicher)
   * 2. Antwort: O(n log(n))   * 2. Antwort: O(n log(n))
-  * 3. Antwort: O(log(n * m))+  * 3. Antwort: O(m-n)
   * 3. Antwort: O(2^abs(n))   * 3. Antwort: O(2^abs(n))
  
Zeile 31: Zeile 31:
  
 {{:pruefungen:bachelor:aud:08-12-graph1.png|:pruefungen:bachelor:aud:08-12-graph1.png}} {{:pruefungen:bachelor:aud:08-12-graph1.png|:pruefungen:bachelor:aud:08-12-graph1.png}}
 +
 +Lösungsweg:
 +Alle Spalten mit einem unendlichen Kantengewicht legen die Knoten fest mit dem Spaltenindex als Knotennamen. In diesem Fall gibt es also die Knoten 0-4 (einschl.). Die Zahlen in der ersten Zeile geben dabei einen Indexbereich im zweiten Teil des Arrays an. Im Folgenden "IK-Zahlen" genannt.
 +
 +Der zweite Teil des Arrays ohne unendliche Kantengewichte wird nun also in mehrere Bereiche für jeden Knoten aufgeteilt. Dabei geben die jeweiligen IK-Zahlen die erste Spalte zu einem Bereich an. Für Knoten 0 fängt der Bereich 0 also mit Spalte 5 an. Bereich 1 für Knoten 1 fängt aber auch bei Knoten 5 an, weshalb für Knoten 0 keine Spalte übrig bleibt. Bereich 2 fängt ab Spalte 6 an und damit umfasst Bereich 1 nur Spalte 5. Am Ende sieht unser geteiltes Array also so aus:
 +
 +<code>Knoten _1__|_______2_______|___________3___________|_______4____
 +        0   |    3     4    |     0     1     4     |   0    1
 +γ       12  |    6     7    |     10    8     5     |   11   9
 +</code>
 +
 +Jetzt kann man die Kanten ganz einfach ablesen. Die Kanten gehen dabei immer vom jeweiligen Knoten des Bereiches zu dem Knoten in der ersten Zeile der Tabelle. Somit enstehen aus obiger Tabelle folgende Kanten:
 +
 +1->0, 2->3, 2->4, 3->0, 3->1, 3->4, 4->0, 4->1
 +
 +Die zweite Zeile repräsentiert die Kantengewichte.
  
 **b)** **b)**
Zeile 69: Zeile 85:
  
 Graph: \\ Graph: \\
-FIXME \\+{{:pruefungen:bachelor:aud:12-08-02-a3b-graph.png?300|}}\\
 (Allgemeine Bemerkung: Der Algorithmus von Floyd erzeugt jede Kante, die es vorher noch nicht gab, bzw. "verbessert" die Gewichte von bestehenden Kanten.\\ (Allgemeine Bemerkung: Der Algorithmus von Floyd erzeugt jede Kante, die es vorher noch nicht gab, bzw. "verbessert" die Gewichte von bestehenden Kanten.\\
-Sollte der Graph in dieser Aufgabe vollständig gezeichnet werden oder sollen wirklich nur die Kanten enthalten sein, die durch die obige Tabelle ermittelt wurden?+FIXME: Sollte der Graph in dieser Aufgabe vollständig gezeichnet werden oder sollen wirklich nur die Kanten enthalten sein, die durch die obige Tabelle ermittelt wurden?
  
 ==== Aufgabe 4 - Doppelte binäre Suche ==== ==== Aufgabe 4 - Doppelte binäre Suche ====
Zeile 242: Zeile 258:
 **a)** **a)**
  
 +**Frage 1:** \\
 Ein kürzerer String soll vor einem längeren einsortiert werden, das heißt, bei einem Vergleich muss ein kürzerer String wie ein längerer, jedoch //lexikographisch kleinerer// String behandelt werden. Ein kürzerer String soll vor einem längeren einsortiert werden, das heißt, bei einem Vergleich muss ein kürzerer String wie ein längerer, jedoch //lexikographisch kleinerer// String behandelt werden.
  
-**b)** +**Frage 2:** \\
 Das Wort muss vorne mit den Füllsymbolen aufgefüllt werden, da die Sortierung von hinten nach vorne erfolgt. Würde man es hinten mit den Füllsymbolen auffüllen, so erreicht man eine lexikographische Sortierung, das heißt: \\ Das Wort muss vorne mit den Füllsymbolen aufgefüllt werden, da die Sortierung von hinten nach vorne erfolgt. Würde man es hinten mit den Füllsymbolen auffüllen, so erreicht man eine lexikographische Sortierung, das heißt: \\
 aal \\ aal \\
Zeile 257: Zeile 273:
 aligator \\ aligator \\
 computer computer
 +
 +**Frage 3:** \\
 +Ein Vergleichen der Zeichen von hinten nach vorne ist notwendig, damit eine lexikographische Sortierung erfolgt und beispielsweise "aa" vor "ab" einsortiert wird. Äußerst wichtig ist hierbei, dass das Verfahren stabil sein muss!
 +
 +**b)**
 +
 +^ Stelle ^ Reihung ^^^^
 +^ - | /AIA | IPV2 | R2D2 | / /AI |
 +^ 3 | IPV2 | R2D2 | /AIA | / /AI |
 +^ 2 | / /AI | R2D2 | /AIA | IPV2 |
 +^ 1 | / /AI | R2D2 | /AIA | IPV2 |
 +^ 0 | / /AI | /AIA | IPV2 | R2D2 |
  
 **c)** **c)**
  
-Ein Vergleichen der Zeichen von hinten nach vorne ist notwendig, damit eine lexikographische Sortierung erfolgt und beispielsweise "aa" vor "ab" einsortiert wird. Äußerst wichtig ist hierbei, dass das Verfahren stabil sein muss!+Reales Char-Indizes: 
 +^ 0 ^ 1 ^ 2 ^ 3 ^ 
 +| t | e | s | t | 
 +| a | u | d | |  
 +| a | n | d | |  
 +| s | p | | |  
 +| x | | | | 
 + 
 +Virtuelle Char-Indizes (= pos): 
 +^ 0 ^ 1 ^ 2 ^ 3 ^ 
 +| t | e | s | t | 
 +| | a | u | d | 
 +| | a | n | d |  
 +| | | s | p | 
 +| | | | x | 
 + 
 +<code> 
 +public static int getBucket(int pos, String name) { 
 + int realPos = pos - (4 - name.length()); 
 +  
 + if(realPos < 0) 
 + return mapChar('/'); 
 +  
 + return mapChar(name.charAt(realPos)); 
 +} 
 +</code> 
 + 
 +**d)** 
 + 
 +<code> 
 +static void radixSort(ArrayList<String> names) { 
 + List<String>[] b = new ArrayList[37]; 
 + for(int bi = 0; bi < b.length; bi++) { 
 + b[bi] = new ArrayList<>(); 
 + } 
 +  
 + for(int i = 3; i >= 0; i--) { 
 + for(String s : names) {  
 + int bucket = getBucket(i, s);  
 + b[bucket].add(s); 
 + } 
 +  
 + names.clear(); 
 + for(int bi = 0; bi < b.length; bi++) { 
 + names.addAll(b[bi]); 
 + b[bi].clear(); 
 + } 
 + } 
 +} 
 +</code> 
 + 
 +Programm zum selber Testen: {{:pruefungen:bachelor:aud:08-12-radixsort.java.txt|:pruefungen:bachelor:aud:08-12-radixsort.java.txt}} 
 + 
 +==== Aufgabe 8 - AVL-Bäume ==== 
 + 
 +**a)** 
 + 
 +{{:pruefungen:bachelor:aud:08-12-avl1.png|:pruefungen:bachelor:aud:08-12-avl1.png}} 
 + 
 +Balancefaktor des neuen Knotens: 0 
 + 
 +{{:pruefungen:bachelor:aud:08-12-avl2.png|:pruefungen:bachelor:aud:08-12-avl2.png}} 
 + 
 +Balancefaktor des neuen Knotens: 0 
 + 
 + 
 +**b)**
  
 +{{:pruefungen:bachelor:aud:08-12-avl3.png|:pruefungen:bachelor:aud:08-12-avl3.png}}
  
 +{{:pruefungen:bachelor:aud:08-12-avl4.png|:pruefungen:bachelor:aud:08-12-avl4.png}}