Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen, bei Fragen bitte:
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:aud:loesungws18 [15.06.2019 07:26] – added java syntax highlighting dom | pruefungen:bachelor:aud:loesungws18 [26.06.2019 16:01] – TOKAMAK | ||
---|---|---|---|
Zeile 8: | Zeile 8: | ||
==== | ==== | ||
=== a) === | === a) === | ||
- | - To-Do | + | - Richtig, es werden nur die drei Variablen '' |
- | - To-Do | + | |
- | - To-Do | + | - Falsch, es werden zusätzlich die Arrays '' |
- | - 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 // |
+ | |||
+ | 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, '' |
- | - To-Do | + | - Richtig. |
- | - To-Do | + | - Falsch, es ist nur ein einfaches Feld. Bei der Notation muss man allgemein wissen, dass Felder immer an der // |
- | - To-Do | + | - Richtig, zu jedem '' |
=== 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**> | - Falsch, der Graph enthält Zyklen, z.B. **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 " |
- | - To-Do | + | - Falsch, die Laufzeit liegt in O(|V| log|V|). |
=== f) === | === f) === | ||
- | - To-Do | + | - Falsch, der '' |
- | - To-Do | + | - Richtig. |
- | - To-Do | + | - Richtig. Wenn '' |
- | - To-Do | + | - Falsch. wp(" |
==== | ==== | ||
=== a) === | === a) === | ||
+ | < | ||
+ | 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, | ||
+ | } | ||
+ | } | ||
+ | |||
+ | // Der Wert des aktuellen Feldes muss noch dazu addiert werden | ||
+ | best += a[row][col]; | ||
+ | return best; | ||
+ | } | ||
+ | </ | ||
=== b) === | === b) === | ||
< | < | ||
- | public | + | 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 | + | |
- | 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 | |
- | 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--) { | + | |
- | //Suche den Grössten | + | b = Math.max(mem[row][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], |
- | if (row == 0) { | + | } else { |
- | b = Math.max(mem[row][col+1], | + | b = 0; |
- | } else if(row == n-1) { | + | |
- | b = Math.max(mem[row][col+1], | + | b = Math.max(mem[r][col+1], |
- | } else { | + | } |
- | for(int r = row-1; r <= row+1; r++) { | + | |
- | b = Math.max(mem[r][col+1], | + | |
- | } | + | |
- | } | + | 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 | |
- | | + | 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; | + | |
} | } | ||
</ | </ | ||
Zeile 101: | Zeile 119: | ||
=== a) === | === a) === | ||
^ Fach ^ k // | ^ Fach ^ k // | ||
- | | 0 | E => K | + | | 0 | E => U |
| 1 | | 1 | ||
| 2 |? => | | | 2 |? => | | ||
Zeile 134: | Zeile 152: | ||
==== | ==== | ||
+ | === a) === | ||
+ | < | ||
+ | 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, | ||
+ | | ||
+ | // Betrachte alle Nachbarn im Graphen | ||
+ | for (T w : graph.get(v)) { | ||
+ | // Überprüfe, | ||
+ | if (!nums.containsKey(w) { | ||
+ | sptree.get(v).add(w); | ||
+ | num = helperNums(v, | ||
+ | } | ||
+ | } | ||
+ | | ||
+ | return num; | ||
+ | } | ||
+ | </ | ||
+ | |||
+ | === b) === | ||
+ | < | ||
+ | private long helperLows(T v) { | ||
+ | long low = nums.get(v); | ||
+ | | ||
+ | for (T w : sptree.get(v)) { | ||
+ | long wLow = helperLows(w); | ||
+ | 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, | ||
+ | } | ||
+ | | ||
+ | for (T w : graph.get(v)) { | ||
+ | low = Math.min(low, | ||
+ | } | ||
+ | | ||
+ | return low; | ||
+ | } | ||
+ | </ | ||
+ | |||
==== | ==== | ||
=== a) === | === a) === | ||
- | //push4(ts, x, y) = Push(Push(Push(Push(ts, | + | //push4(ts, x, y) = Push(Push(Push(Push(ts, |
=== b) === | === b) === | ||
- | // | + | // |
+ | |||
+ | //... = c, falls n < = 0// | ||
+ | |||
+ | //... = paintHLine(Paint(c, | ||
| | ||
=== c) === | === c) === | ||
- | // | + | // |
- | getCol(Paint(c, | + | |
+ | //getCol(Paint(c, | ||
+ | |||
+ | //... = col, falls x = a und y = b// | ||
+ | |||
+ | //... = getCol(c, x, y), sonst// | ||
=== d) === | === d) === | ||
- | // | + | // |
- | floodH(c, | + | |
+ | //floodH(c, Push(ts, x, y), oc, nc) = ...// | ||
+ | |||
+ | //... = floodH(Paint(c, | ||
+ | |||
+ | //... = floodH(c, ts, oc, nc), sonst // | ||
____________________________________________________________________ | ____________________________________________________________________ | ||
- | ==== | + | ==== |
+ | < | ||
+ | public void sort(List< | ||
+ | sort(in, 0, new BucketPool(45)); | ||
+ | } | ||
+ | |||
+ | private void sort(List< | ||
+ | List< | ||
+ | if (charPos < 5) { | ||
+ | bs = bp.getBuckets(9); | ||
+ | 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 != ' | ||
+ | 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< | ||
+ | sort(bucket, | ||
+ | |||
+ | /* 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 | ||
+ | | ||
+ | */ | ||
+ | |||
+ | in.addAll(bucket); | ||
+ | } | ||
+ | |||
+ | // Hier muss man die Buckets wieder aus dem Pool entfernen | ||
+ | bp.dropBuckets(bs); | ||
+ | } | ||
+ | } | ||
+ | </ | ||
+ | Anmerkung zu der Stelle '' | ||
+ | * Arbeit mit '' | ||
+ | * Man iteriert mit einem Index '' |