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
Letzte ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws07 [15.02.2013 10:17] – Dawodopruefungen:bachelor:aud:loesungws07 [27.05.2014 23:10] – yef
Zeile 1: Zeile 1:
-==forum==+===== Forendiskussionen =====
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7567-Frage-Klausur-21-Februar-2008]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7567-Frage-Klausur-21-Februar-2008]]
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7104-WP-kalkuel-21-02-2008]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/7104-WP-kalkuel-21-02-2008]]
Zeile 10: Zeile 10:
   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8877-Klausur-21-2-2008-A10-d-e]]   * [[https://fsi.informatik.uni-erlangen.de/forum/thread/8877-Klausur-21-2-2008-A10-d-e]]
  
-====Lösungsversuch====+===== Lösungsversuch =====
  
-===Aufgabe 1 - Binärsuche===+==== Aufgabe 1 - Binärsuche ====
 **a)** O(n) **a)** O(n)
  
Zeile 57: Zeile 57:
 **c)** O(log n) **c)** O(log n)
  
-===Aufgabe 2 - Graphen===+==== Aufgabe 2 - Graphen ====
 **a)** **a)**
   * **Ja**   * **Ja**
Zeile 97: Zeile 97:
 BD, BC, DG, BA, FI, GE, GI, FH BD, BC, DG, BA, FI, GE, GI, FH
  
-===Aufgabe 3 - Java===+==== Aufgabe 3 - Java ====
 **a)** **a)**
 Java Datei zum Ausprobieren: {{:pruefungen:bachelor:aud:test.java-ws07.txt|:pruefungen:bachelor:aud:test.java-ws07.txt}} Java Datei zum Ausprobieren: {{:pruefungen:bachelor:aud:test.java-ws07.txt|:pruefungen:bachelor:aud:test.java-ws07.txt}}
Zeile 126: Zeile 126:
  
  
-=== Aufgabe 4 - Arithmetische Ausdrücke - Grammatik ===+==== Aufgabe 4 - Arithmetische Ausdrücke - Grammatik ====
 (nicht mehr Stoff aktueller Semester) (nicht mehr Stoff aktueller Semester)
  
-===Aufgabe 5 - ADT===+==== Aufgabe 5 - ADT ====
 **a)** **a)**
   * number   * number
Zeile 173: Zeile 173:
 </code> </code>
  
-=== Aufgabe 6 - Rucksackproblem ===+==== Aufgabe 6 - Rucksackproblem ====
 **a)** **a)**
 ^    ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^ ^    ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^ 10 ^ 11 ^ 12 ^
Zeile 191: Zeile 191:
   P(2, 1) -> k_2 = 3 gehört nicht rein -> P(1, 1)   P(2, 1) -> k_2 = 3 gehört nicht rein -> P(1, 1)
   P(1, 1) -> k_1 = 1 gehört rein -> Rucksack vollständig gefüllt   P(1, 1) -> k_1 = 1 gehört rein -> Rucksack vollständig gefüllt
- 
  
 **c)** **c)**
 <code java> <code java>
-for(int i = 1; i < n; i++) {            // Zeilen +for(int i = 1; i < n; i++) { // Zeilen 
-    for(int j = 0; j < m + 1; j++) {    // Spalten + for(int j = 0; j <= m; j++) { // Spalten 
-        if((tab[i][j] == OHNE || tab[i][j] == MIT) && i < n-1) { // Wenn in einer Zeile MIT oder OHNE steht +  
-            tab[i+1][j] = OHNE;         // so muss die Zelle daraunter den Wert OHNE haben. + // Fall P(n - 1, K): Gibt es in der Zelle direkt darüber eine Lösung, 
-            if(j + k[i+1] <= m) + // dann ist P(n, K) = P(n - 1, K) 
-                tab[i+1][j+k[i+1]] = MIT; + // Das aktuelle Elemente gehört somit nicht zur Lösung -> OHNE 
-        } + if(tab[i - 1][j] != UNMOEGLICH) { 
-    }+ tab[i][j] = OHNE; 
 + 
 + // Fall P(n - 1, K - k_n): Gibt es in der Zeile darüber, nach links versetzt 
 + // eine Lösung (Achtung: ArrayIndexOutOfBoundsException), dann ist 
 + // P(n, K) = P(n - 1, K) + k_n 
 + // Das aktuelle element gehört somit zur Lösung -> MIT 
 + } else if(elements[i] <= j && tab[i - 1][j - elements[i]] != UNMOEGLICH) { 
 + tab[i][j] = MIT; 
 + } 
 + }
 } }
 </code> </code>
 +
 +Vollständiges Programm: \\
 +{{:pruefungen:bachelor:aud:rucksack.java.txt|:pruefungen:bachelor:aud:rucksack.java.txt}}
  
 **d)** **d)**
-// unsicher! +  * **Ja** 
-  * nein +  * **Ja** 
-  * ja +  * **Ja**, durch sukzessives Ausprobieren für Kapazitäten < m 
-  * nein +  * **Nein**, das Verfahren verwendet eine Integer-DP-Tabelle bzw. greift auf Indizes basierend auf der Elementgröße zu
-  * ja+
  
-=== Aufgabe 7 - Binäre Bäume ===+==== Aufgabe 7 - Binäre Bäume ====
 **a)**  **a)** 
 Der Binärbaum muss eine totale Ordnung aufweisen:\\ Der Binärbaum muss eine totale Ordnung aufweisen:\\
Zeile 285: Zeile 295:
   * **Nein**, man muss eines Tiefensuche vewenden   * **Nein**, man muss eines Tiefensuche vewenden
  
-=== Aufgabe 8 - Sortieren ===+==== Aufgabe 8 - Sortieren ====
  
 **a)** **a)**
Zeile 425: Zeile 435:
  
  
-=== Aufgabe 9 - Aufwände, O-Kalkül ===+==== Aufgabe 9 - Aufwände, O-Kalkül ====
 **a)** **a)**
   * **O(log n)**   * **O(log n)**
-  * **O(k)**+  * **O(n)**, da k * n/2
   * **O(n²)**   * **O(n²)**
   * **O(n)**   * **O(n)**
Zeile 490: Zeile 500:
   (m = m) =    (m = m) = 
   (true)   (true)
-