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 [16.06.2019 13:05] – Aufgabe 1 (Wissensfragen) gemacht gabriel2029 | pruefungen:bachelor:aud:loesungws18 [26.06.2019 14:15] – TOKAMAK | ||
---|---|---|---|
Zeile 23: | Zeile 23: | ||
=== c) === | === c) === | ||
- 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. | - 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. | ||
- | - Das Omega-Kalkül beschreibt alle Funktionen, die mindestens so schnell wachsen wie eine gegebene Funktion. | + | - Richtig, das Omega-Kalkül beschreibt alle Funktionen, die mindestens so schnell wachsen wie eine gegebene Funktion. |
- Falsch, n liegt in O(n^2), n^2 aber nicht in O(n). | - Falsch, n liegt in O(n^2), n^2 aber nicht in O(n). | ||
- 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). | - 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). | ||
Zeile 38: | Zeile 38: | ||
- Falsch, ein Spannbaum für einen Graphen mit n Knoten hat immer genau n - 1 Kanten. | - Falsch, ein Spannbaum für einen Graphen mit n Knoten hat immer genau n - 1 Kanten. | ||
- Richtig, der Algorithmus von Krukal beginnt mit einem " | - Richtig, der Algorithmus von Krukal beginnt mit einem " | ||
- | - Falsch, | + | - Falsch, |
=== f) === | === f) === | ||
Zeile 49: | Zeile 49: | ||
=== 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; |
- | + | ||
- | // | + | |
- | int[][] mem = new int[n][n]; | + | |
- | for(int row = n-1; row >=0; row--) { | + | |
- | mem[row][n-1] = a[row][n-1]; | + | |
- | + | ||
- | } | + | |
- | + | ||
- | | + | // Feld initialisieren und letzte Spalte befüllen |
- | + | int[][] mem = new int[n][n]; | |
- | int b = 0; | + | for(int row = 0; row < n; row++) { |
- | //von der vorletzten Spalte bis zur vordersten | + | |
- | for(int col = n-2; col >= 0; col--) { | + | } |
- | //Suche den Grössten | + | |
- | //darüber, darunter oder gleicher Reihe und speichere dessen Wert in b | + | int b = 0; |
- | for(int row = n-1; row >= 0; row--) { | + | // von der vorletzten Spalte bis zur vordersten |
- | if (row == 0) { | + | for(int col = n-2; col >= 0; col--) { |
- | b = Math.max(mem[row][col+1], | + | // Suche den größten |
- | } else if(row == n-1) { | + | // darüber, darunter oder gleicher Reihe und speichere dessen Wert in b |
- | b = Math.max(mem[row][col+1], | + | for(int row = 0; row < n; row++) { |
- | } else { | + | |
- | for(int r = row-1; r <= row+1; r++) { | + | b = Math.max(mem[row][col+1], |
- | b = Math.max(mem[r][col+1], | + | } else if(row == n-1) { |
- | } | + | b = Math.max(mem[row][col+1], |
- | } | + | } else { |
- | //Der neue Wert in mem ist der alte in a plus b | + | b = 0; |
- | mem[row][col] = a[row][col] + b; | + | |
- | } | + | b = Math.max(mem[r][col+1], |
- | } | + | } |
- | + | | |
- | | + | |
- | for( int i = 0; i < mem.length; i++) { | + | |
- | if(mem[i][0] > best) { | + | mem[row][col] = a[row][col] + b; |
- | best = mem[i][0]; | + | } |
- | } | + | } |
- | } | + | } |
- | + | | |
- | + | //Suche das Maximum in der ersten Spalte | |
- | + | for(int i = 0; i < n; i++) { | |
- | return best; | + | if(mem[i][0] > best) { |
+ | best = mem[i][0]; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | return best; | ||
} | } | ||
</ | </ | ||
Zeile 103: | Zeile 119: | ||
=== a) === | === a) === | ||
^ Fach ^ k // | ^ Fach ^ k // | ||
- | | 0 | E => K | + | | 0 | E => U |
| 1 | | 1 | ||
| 2 |? => | | | 2 |? => | | ||
Zeile 136: | 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.contains(v)) sptree.put(v, | ||
+ | | ||
+ | // Betrachte alle Nachbarn im Graphen | ||
+ | for (T w : graph.get(v)) { | ||
+ | // Überprüfe, | ||
+ | if (!nums.contains(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 '' |