Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen, bei Fragen bitte:   (Ü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
Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:aud:loesungws18 [15.06.2019 07:26] – added java syntax highlighting dompruefungen:bachelor:aud:loesungws18 [07.07.2019 09:22] – SpeedyGonzalez
Zeile 8: Zeile 8:
 ====   Aufgabe 1 (Wissensfragen)==== ====   Aufgabe 1 (Wissensfragen)====
 === a) === === a) ===
-  - To-Do +  - Richtig, es werden nur die drei Variablen ''xMax'', ''xSuf'' sowie ''i'' zusätzlich angelegt. 
-  - To-Do +  - Falsch, sie liegt in ''x.length''. 
-  - To-Do +  - Falsch, es werden zusätzlich die Arrays ''r'' und ''rn'' angelegt, die in jeder Schleiteniteration //ungefähr// doppelt so groß gewählt ist 
-  - To-Do+  - Richtig. Das sich aber zu überlegen, ist aber nicht ganz so einfach. Der Graycode erstellt eine Sortierung aller Binärwörter der Länge n (also insgesamt 2^n Wörter), sodass die Hamming-Distanz zweier aufeinanderfolgender Wörter genau 1 ist. Der eigentliche Algorithmus beginnt dabei beim Trivialfall n = 1. Alle anderen Fälle n werden aufgebaut, indem der Fall n - 1 verwendet wird. Die Laufzeit ist also //ungefähr// 2^1 + 2^2 + ... 2^n = 2^(n + 1) - 1. Nicht berücksichtigt in dieser Überlegung ist u. a., dass das Feld ''rn'' in jedem Schritt um eine weitere Reihe ''x'' ergänzt wird. Ansonsten kann man auch durch die Betrachtung des Quellcodes auf ähnliche Ergebnisse kommen. 
 + 
 +Anmerkung zum O-Kalkül: Grundsätzlich beschreibt das O-Kalkül immer eine obere Schranke, wenn z. B. eine Funktion f(n) in O(n) liegt, liegt sie auch in O(n^2), aber nicht unbedingt in O(1) (vgl. dazu auch Lösungsvorschlag der Miniklausur dieses Semesters).
  
 === b) === === b) ===
-  - To-Do +  - Falsch, ''CatRoom'' ist Unterklasse von ''CatBase'' 
-  - To-Do +  - Richtig. 
-  - To-Do +  - Falsch, es ist nur ein einfaches Feld. Bei der Notation muss man allgemein wissen, dass Felder immer an der //gegenüberliegenden// Seite der Beziehung notiert werden.   
-  - To-Do+  - Richtig, zu jedem ''CatRoom'' gibt es maximal ein ''CatHouse'', also wird jeder ''CatRoom'' von höchsten einem ''CatHouse'' referenziert (in KonzMod-Logik würde also insbesondere die funktionale Abhängigkeit ''CatRoom'' -> ''CatHouse'' gelten).
  
 === c) === === c) ===
-  - To-Do +  - Richtig. Das ist ein bisschen gemein, da in der Aufgabenstellung einfach die Variabeln n und c vertauscht wurden. Trotzdem ist die Aussage korrekt ist, auch wenn die eigentliche Intention dieser Variablen nicht mehr erfüllt ist. 
-  - To-Do +  - Richtig, das Omega-Kalkül beschreibt alle Funktionen, die mindestens so schnell wachsen wie eine gegebene Funktion. 
-  - To-Do +  - Falsch, n liegt in O(n^2), n^2 aber nicht in O(n). 
-  - To-Do+  - Falsch, liege f(n) = n^2 in O(n), und g(n) = n in O(n^2), dann liegt f(n) - g(n) = n^2 - n nicht in O(n).
  
 === d) === === d) ===
-  - To-Do+  - Richtig, man kann von jedem Knoten aus jeden anderen erreichen.
   - Falsch, der Graph enthält Zyklen, z.B. **v0**>v1>v3>**v0**   - Falsch, der Graph enthält Zyklen, z.B. **v0**>v1>v3>**v0**
-  - To-Do +  - Falsch, die Tiefensuche müsste nach dem Besuchen von Knoten v1 den Knoten v3 besuchen. 
-  - Richtig+  - Richtig, man muss hier halt wissen, wie die Adjazenzfelddarstellung aussieht.
  
  
 === e) === === e) ===
-  - To-Do +  - Richtig, genau das tut der Algorithmus von Floyd. 
-  - To-Do +  - Falsch, ein Spannbaum für einen Graphen mit n Knoten hat immer genau n - 1 Kanten. 
-  - To-Do +  - Richtig, der Algorithmus von Krukal beginnt mit einem "leeren" Spannbaum und fügt in jedem Schritt eine Kante hinzu. 
-  - To-Do+  - Falsch, die Laufzeit liegt in O(|V| log|V|).
  
 === f) === === f) ===
-  - To-Do +  - Falsch, der ''finally''-Block wird __immer__ ausgeführt. 
-  - To-Do +  - Richtig. 
-  - To-Do +  - Richtig. Wenn ''a'' und ''b'' erfüllt ist, wird der Code ''X'' ausgeführt, ist ''a'' wahr und ''b'' falsch, wird der Code ''Y'' ausgeführt, ansonsten, also wenn ''a'' nicht erfüllt ist, muss die Bedingung ''Q'' ohne Änderung erfüllt sein. 
-  - To-Do+  - Falsch. wp("A", Q) bezeichnet die schwächste Vor-Bedingung, die gelten muss, damit nach der Ausführung von "A" Q erfüllt ist. Eine Bedingung P müsste mindestens so stark wie wp("A", Q) sein, d. h. man müsste P => wp("A", Q) zeigen.
  
 ====   Aufgabe 2 (Dynamische Programmierung)==== ====   Aufgabe 2 (Dynamische Programmierung)====
  
 === a) === === a) ===
 +<code=java> 
 +private int recurse(int[][] a, int row, int col) { 
 +    int n = a.length; 
 +    int best = 0; 
 +    assert row >= 0 && row < n && col >= 0 && col < n; 
 +    for (int r = row - 1; r <= row + 1; r++) { 
 +        // Betrachte, ob das angeforderte Feld überhaupt im Quadrat liegt 
 +        if (col < n - 1 && r >= 0 && r < n) { 
 +            // Die erreichte Summe wird genau dann maximal, wenn man 
 +            // den Weg wählt, bei dem man von diesem Nachbarfeld die 
 +            // maximale Summe erhält -> Eigentliche Rekursion 
 +            best = Math.max(best, recurse(a, r, col + 1)); 
 +        } 
 +    } 
 +     
 +    // Der Wert des aktuellen Feldes muss noch dazu addiert werden 
 +    best += a[row][col]; 
 +    return best; 
 +} 
 +</code>
  
 === b) === === b) ===
  
 <code=java> <code=java>
-public static int maxPathDP(int[][] a) { +public int maxPathDP(int[][] a) { 
-        int n = a.length; +    int n = a.length; 
- int best = 0;+    int best = 0;
   
-       //Feld initialisieren und letzte Spalte befüllen +    // Feld initialisieren und letzte Spalte befüllen 
- int[][] mem = new int[n][n]; +    int[][] mem = new int[n][n]; 
-              for(int row = n-1; row >=0; row--) { +    for(int row = 0; row < n; row++) { 
- mem[row][n-1] = a[row][n-1]; +        mem[row][n-1] = a[row][n-1];  
-  +    } 
- } +   
-  +    int b = 0; 
-  +    // von der vorletzten Spalte bis zur vordersten 
-       +    for(int col = n-2; col >= 0; col--) { 
-         +        // Suche den größten Nachbarn in der rechten Spalte in einer Reihe 
- int b = 0; +        // darüber, darunter oder gleicher Reihe und speichere dessen Wert in b 
-        //von der vorletzten Spalte bis zur vordersten + for(int row = 0; row < n; row++) { 
- for(int col = n-2; col >= 0; col--) { +     if (row == 0) { 
-                //Suche den Grössten Nachbarn in der rechten Spalte in einer Reihe +                b = Math.max(mem[row][col+1], mem[row+1][col+1]); 
-                //darüber, darunter oder gleicher Reihe und speichere dessen Wert in b +            } else if(row == n-1) { 
- for(int row = n-1; row >= 0; row--) { +                b = Math.max(mem[row][col+1], mem[row-1][col+1]); 
- if (row == 0) { +            } else { 
- b = Math.max(mem[row][col+1], mem[row+1][col+1]); +                b = 0;  
- } else if(row == n-1) { +                for(int r = row-1; r <= row+1; r++) { 
- b = Math.max(mem[row][col+1], mem[row-1][col+1]); +                    b = Math.max(mem[r][col+1], b); 
- } else { +                } 
- for(int r = row-1; r <= row+1; r++) { +     } 
- b = Math.max(mem[r][col+1], b); +             
- } +            // Der neue Wert in mem ist der alte in a plus b 
- } +            mem[row][col] = a[row][col] + b; 
-                //Der neue Wert in mem ist der alte in a plus b +            } 
- mem[row][col] = a[row][col] + b; +        } 
- } +    } 
- } +     
-  +    //Suche das Maximum in der ersten Spalte 
-       //Suche das Maximum in der ersten Spalte +    for(int i = 0; i < n; i++) { 
- for( int i = 0; i < mem.length; i++) { +        if(mem[i][0] > best) { 
- if(mem[i][0] > best) { +            best = mem[i][0]; 
- best = mem[i][0]; +        } 
- } +    } 
- } +     
-  +    return best;
-  +
-  +
- return best;+
 } }
 </code> </code>
Zeile 101: Zeile 119:
 === a) === === a) ===
 ^ Fach      ^ k //(verkettete Liste, zuletzt eingetragener Schlüssel rechts) //      ^  ^ Fach      ^ k //(verkettete Liste, zuletzt eingetragener Schlüssel rechts) //      ^ 
-| 0    | E => K    | +| 0    | E => U    | 
 | 1   |   |  | 1   |   | 
 | 2    |? =>    |  | 2    |? =>    | 
Zeile 134: Zeile 152:
  
 ====   Aufgabe 4 (Artikulationspunkte)==== ====   Aufgabe 4 (Artikulationspunkte)====
 +=== a) ===
 +<code=java>
 +private long helperNums(T v, long num) { 
 +    // Füge Preorder-Knoten hinzu
 +    nums.put(v, num);
 +    
 +    // Nächster Knoten bekommt eine um eins höhere Nummerierung
 +    num++;
 +  
 +    // Schaue, ob in sptree schon eine Adjazenzliste angelegt wurde
 +    // (eigentlich ist das ein Set, das ist aber nicht relevent)
 +    if (!sptree.containsKey(v)){
 +     sptree.put(v, new HashSet<>());
 +    }
 +    // Betrachte alle Nachbarn im Graphen
 +    for (T w : graph.get(v)) {
 +        // Überprüfe, ob Nachbar schon besucht wurde
 +        if (!nums.containsKey(w) {
 +            sptree.get(v).add(w); // Füge Knoten zum Spannbaum hinzu
 +            num = helperNums(v, num); // Führe rekursiv die dfs-Nummerierung aus
 +        }
 +    }
 +    
 +    return num;
 +}
 +</code>
 +
 +=== b) ===
 +<code=java>
 +private long helperLows(T v) {
 +    long low = nums.get(v); // num-Wert des Knoten selbst
 +    
 +    for (T w : sptree.get(v)) {
 +        long wLow = helperLows(w); // low-Wert der Nachbarknoten
 +        if (wLow >= nums.get(v)) {
 +            // Fall, in dem Knoten zu der Menge der Artikulationspunkte hinzugefügt werden muss
 +            aps.add(v);
 +        }
 +        low = Math.min(low, wLow);        
 +    }
 +    
 +    for (T w : graph.get(v)) {
 +        low = Math.min(low, nums.get(w)); // num-Werte der Nachbarknoten
 +    }
 +    
 +    return low;
 +}
 +</code>
 +
 ====   Aufgabe 5 (Abstrakte Datentypen)==== ====   Aufgabe 5 (Abstrakte Datentypen)====
  
 === a) === === a) ===
-//push4(ts, x, y) = Push(Push(Push(Push(ts, x+1, y ), x, y+1), x-1, y ), x, y-1 )//+//push4(ts, x, y) = Push(Push(Push(Push(ts, x+1, y), x, y+1), x-1, y), x, y-1)//
  
 === b) === === b) ===
-//paintHLine(c, x, y, n, nc) = To-Do//+//paintHLine(c, x, y, n, nc) = ...// 
 + 
 +//... = c, falls n < = 0// 
 + 
 +//... = paintHLine(Paint(c, x, y, nc), x + 1, y, n - 1, nc), sonst//
          
 === c) === === c) ===
-//getCol(New,x,y) = White +//getCol(New, x, y) = White// 
-getCol(Paint(c, a, b, col), x, y) = To-Do//+ 
 +//getCol(Paint(c, a, b, col), x, y) = ...// 
 + 
 +//... = col, falls x = a und y = b// 
 + 
 +//... = getCol(c, x, y), sonst//
  
 === d) === === d) ===
-//floodH(c,Empty,oc,nc) = c // oc =􏰁 FoldC, nc =􏰁 FnewC, FoldC ̸= FnewC +//floodH(c,Empty,oc,nc) = c //
-floodH(c,Push(ts,x,y),oc,nc) =To-Do+
  
 +//floodH(c, Push(ts, x, y), oc, nc) = ...//
 +
 +//... = floodH(Paint(c, x, y, nc), push4(ts, x, y), oc, nc), falls getCol(c, x, y) = oc//
 +
 +//... = floodH(c, ts, oc, nc), sonst //
  
 ____________________________________________________________________ ____________________________________________________________________
-====   Aufgabe 6 (Radix-Exchange Sortierung)====+====   Aufgabe 6 (Radix-Exchange-Sortierung)==== 
 +<code=java> 
 +public void sort(List<String> in) { 
 +    sort(in, 0, new BucketPool(45)); 
 +} 
 + 
 +private void sort(List<String> in, int charPos, BucketPool bp) { 
 +    List<List<String>> bs; 
 +    if (charPos < 5) { 
 +        bs = bp.getBuckets(9); 
 +        Iterator<String> it = in.iterator(); 
 +        while (it.hasNext()) { 
 +            String nextString = it.next(); 
 +            char c = nextString.charAt(charPos); 
 +             
 +            // Nur Elemente, die an dieser Stelle einen Char != 0 haben, 
 +            // in andere Liste schieben 
 +            if (c != '0') { 
 +                bs.get(Character.getNumericValue(c)).add(nextString); 
 +                it.remove(); 
 +            }          
 +        } 
 +         
 +        // In in sind im Moment nur noch Strings, 
 +        // die an dieser Stelle 0 sind => Lässt sich wie der Rest sortieren 
 +        sort(in, charPos + 1, bp); 
 +         
 +        // Für alle anderen Strings wurden die eigenen Buckets angelegt 
 +        for (List<String> bucket : bs) { 
 +            sort(bucket, charPos + 1, bp); 
 +             
 +            /* Zum Verständnis: 
 +             * Dadurch, dass die Strings in erster Priorität nach dem Char 
 +             * an Position c sortiert sind, wird die Liste korrekt sortiert: 
 +             * -> Durch sort wird eine Teilliste korrekt sortiert 
 +             * -> Die sortierten Teillisten werden nach dem ersten Character 
 +             *    zusammen gebaut -> korrekte Sortierung 
 +             */ 
 +             
 +            in.addAll(bucket); 
 +        } 
 +         
 +        // Hier muss man die Buckets wieder aus dem Pool entfernen 
 +        bp.dropBuckets(bs); 
 +    } 
 +} 
 +</code> 
 +Anmerkung zu der Stelle ''move strings with '1' - '9' from in to bs'': Hier scheint es prinzipiell zwei andere Möglichkeiten zu geben: 
 +  * Arbeit mit ''for (String nextString : in)'': Nicht wirklich zu empfehlen, da man beim Iterieren durch die Liste Elemente aus dieser entfernen muss. Das kann zu Fehlern beim Iterieren führen. Außerdem ist nicht zwingend vorgeschrieben, dass die Liste keine Duplikate enthält. Bei ''in.remove(nextString)'' würde man diese entfernen. 
 +  * Man iteriert mit einem Index ''i'' über die Liste. Hier muss man beim Entfernen eines Elementes aus der Liste entsprechend ''i'' um eins dekrementieren (um eins verkleinern), damit keine Elemente ausgelassen werden. Diese Lösung funktioniert, ist aber etwas schwieriger zu implementieren. Auch möglich ist es, mit ''i = in.size() - 1'' zu beginnen und abwärts zu zählen. Falls ein Element entfernt wird, wird ''i'' in einem Schritt zusätzlich um 1 verkleinert. Wenn ''i < 0'' ist, wird abgebrochen.