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:loesungws15 [07.04.2017 09:27] Danplanpruefungen:bachelor:aud:loesungws15 [23.03.2020 10:40] (aktuell) kat04
Zeile 9: Zeile 9:
 ** b) ** 2 und 3 ** b) ** 2 und 3
  
-** c) ** 2   +** c) ** 2   || Ziemlich sicher, dass auch 1 richtig ist.
   * zu 1) (2. Meinung: "(stimmt hier nicht auch 1?)") => wenn man bei der linearen Suche ("< oder "=") überprüft, müsste man sicherstellen, dass die zu durchsuchende Zahlenreihe immer aufsteigend sortiert ist. Mit einer allgemeinen Methode zur linearen Suche würden die Suchen mit Sicherheit für alle anderen Fälle daneben gehen.    * zu 1) (2. Meinung: "(stimmt hier nicht auch 1?)") => wenn man bei der linearen Suche ("< oder "=") überprüft, müsste man sicherstellen, dass die zu durchsuchende Zahlenreihe immer aufsteigend sortiert ist. Mit einer allgemeinen Methode zur linearen Suche würden die Suchen mit Sicherheit für alle anderen Fälle daneben gehen. 
   * zu 2) Lineare Suche überprüft im intervall [0:n] ob das i-te-Element == gesuchte Element ist, wenn das gesuchte Element das erste Element ist, dann ist man sofort fertig. Die binäre Suche braucht dazu mindestends noch ein schritt.    * zu 2) Lineare Suche überprüft im intervall [0:n] ob das i-te-Element == gesuchte Element ist, wenn das gesuchte Element das erste Element ist, dann ist man sofort fertig. Die binäre Suche braucht dazu mindestends noch ein schritt. 
Zeile 23: Zeile 23:
   * "löst das Rucksackproblem für n Elemente mit O(n^2) zusätzlichem Speicher.": Unsicher, ob man mit dem Algorithmus das Problem lösen kann oder wie die Lösung aussieht.    * "löst das Rucksackproblem für n Elemente mit O(n^2) zusätzlichem Speicher.": Unsicher, ob man mit dem Algorithmus das Problem lösen kann oder wie die Lösung aussieht. 
  
-** g) ** 2 +** g) ** 2  (achtung, falsch: Folgendes beachten)
   * unsicher   * unsicher
   * Ich denke 4 müsste stimmen   * Ich denke 4 müsste stimmen
   * Bei 2 bin ich mir auch unsicher, da das eigentlich die Definition des Theta-Kalküls ist (auch ein Landau-Symbol), in den Folien aber steht, dass man mit dem O-Kalkül meistens das meint.   * Bei 2 bin ich mir auch unsicher, da das eigentlich die Definition des Theta-Kalküls ist (auch ein Landau-Symbol), in den Folien aber steht, dass man mit dem O-Kalkül meistens das meint.
 +    * Meiner Meinung nach: 3 und 4 sind richtig! Da 1 die definition von gross Omega und 2 von gross Theta ist, wobei die 3 und 4 mit den Rechenregeln des O Kalkuels, bzw 3 bei genauerem Nachdenken ueber den Logarithmus richtig sein muessen. T(n) = T(0.666 * n) = T(c * n) = T(n) + w mit c als Konstante > 1 ist.
  
 ==== Aufgabe 2 Streuspeicherung ==== ==== Aufgabe 2 Streuspeicherung ====
Zeile 44: Zeile 45:
   * C 3 (P)-> 4   * C 3 (P)-> 4
   * D 3 (P)-> 4 (S)-> 0   * D 3 (P)-> 4 (S)-> 0
-  * E 0 (P)-> 1 (S)-> 4 (S)-> 2+  * E 0 (S)-> 1 (P)-> 4 (S)-> 2
  
 ==== Aufgabe 3 Binäre Suche ==== ==== Aufgabe 3 Binäre Suche ====
Zeile 108: Zeile 109:
 <code java> <code java>
  
- void sort(String[] a) { +void sortierenDurchEinfuegen(String[] a) { 
- String temp+ String tmp
-  +  
- for (int n = 1; n < a.length; n++) {+ for (int n = 1; n < a.length; n++) {
   
- temp = a[n]; // entnommenes Element merken+ tmp = a[n]; // entnommenes Element merken
   
-                        int i = n - 1;+ int i = n - 1;
   
- while (i >= 0 && temp.compareTo(a[i]) < 0) { + while (i >= 0 && tmp.compareTo(a[i]) < 0) { 
- a[i + 1] = a[i]; + a[i + 1] = a[i]; 
- i--; + i--;
-+
- +
- a[i + 1] = temp; // entnommenes Element +
- // einsetzen+
  }  }
 +
 + a[i + 1] = tmp; // entnommenes Element
 + // einsetzen
  }  }
 +}
  
  
Zeile 157: Zeile 158:
 <code java> <code java>
 long aDP(int n){ long aDP(int n){
- if(mem == null || n >= mem.length){+ if(mem == null || n >= mem.length){  
 +                                 // Bemerkung: n > mem.length reicht, da mem mit n+1 initialisiert wird
  long[] oldMem=mem;  long[] oldMem=mem;
  mem=new long[n+1];  mem=new long[n+1];
Zeile 184: Zeile 186:
 </code> </code>
 ==== Aufgabe 7 Graphen ==== ==== Aufgabe 7 Graphen ====
 +
 +**a)**
 <code java> <code java>
-public class GraphWS15 {+void sammle(boolean[][] am, int k, Set<Integer> verb, Set<Integer> bes) { 
 +  if (!bes.contains(k)) { 
 +    verb.add(k); 
 +    bes.add(k); 
 +    for (int i = 0; i < am[k].length; i++) { 
 +        if (am[k][i]) { 
 +            sammle(am, i, verb, bes); 
 +        } 
 +    }
  
- void sammle(boolean[][] am, int k, Set<Integer> verb, Set<Integer> bes) { +    for (int i = 0; i < am.length; i++) { 
- if (!bes.contains(k)) { +        if (am[i][k]) { 
- verb.add(k); +            sammle(am, i, verb, bes); 
- bes.add(k); +        
- for (int i = 0; i < am[k].length; i++) { +    } 
- if (am[k][i]){ +  } 
- sammle(am, i, verb, bes); +
- +</code>
- }+
  
- for (int i = 0; i < am.length; i+++**b)**
- if (am[i][k]){ +
- sammle(am, i, verb, bes); +
-+
-+
-+
- }+
  
- List<Set<Integer>> mszt(boolean[][] am) {+<code=java> 
 +List<Set<Integer>> mszt(boolean[][] am) {
  // Ergebnisliste:  // Ergebnisliste:
  List<Set<Integer>> ergebnis = new LinkedList<>();  List<Set<Integer>> ergebnis = new LinkedList<>();
 +
  // Menge besuchter Knoten:  // Menge besuchter Knoten:
  Set<Integer> bk = new HashSet<>();  Set<Integer> bk = new HashSet<>();
 +
  // Ermittle alle Teilgraphen mittels Hilfsmethode sammle:  // Ermittle alle Teilgraphen mittels Hilfsmethode sammle:
  for (int k = 0; k < am.length; k++) {  for (int k = 0; k < am.length; k++) {
- if (!bk.contains(k)){+ if (!bk.contains(k)) { 
  // falls k noch nicht besucht => sammle mit k verbundene Knoten  // falls k noch nicht besucht => sammle mit k verbundene Knoten
  Set<Integer> verb = new HashSet();  Set<Integer> verb = new HashSet();
- sammle(am,k,verb, bk);+ sammle(am, k, verb, bk);
  ergebnis.add(verb);  ergebnis.add(verb);
 +
 +                                //einfacher waere hier statt den letzten drei zeilen folgendes:
 +                                //sammle(am, k, ergebnis.get(k), bk); 
  }  }
   
  }  }
- 
  return ergebnis;  return ergebnis;
  }  }
 +</code>
  
- void itg(boolean[][] am, Set<Integer> vs) { +**c)** 
- for (int i=0;i<am.length;i++){ + 
- for (int j=0;j<am[i].length;j++){ +<code=java> 
- if (am[i][j]){ +void itg(boolean[][] am, Set<Integer> vs) { 
- if (vs.contains(i) && vs.contains(j)){ +    for (int i = 0; i < am.length; i++) { 
- // ok +        for (int j = 0; j < am.length; j++) { 
- +            if (am[i][j]) { 
- else +                if (!vs.contains(i) || !vs.contains(j)) {  // es muss sowohl x als auch y in vs enthalten sein 
- am[i][j] = false;+                    am[i][j] = false; // der Graph ist gerichtet, daher reicht die Betrachtung an einer Stelle 
 + } 
 +     } 
 + }  
 +    } 
 +
 + 
 +// alte Loesung: 
 +void itg(boolean[][] am, Set<Integer> vs) { 
 + for (int i = 0; i < am.length; i++) { 
 + for (int j = 0; j < am.length; j++) { 
 + if (am[i][j]) { 
 + if (!(vs.contains(i) && vs.contains(j))) 
 +                                 am[i][j] = false; 
 +                                                am[j][i] = false;
  }  }
  }  }
- } + }
- +
  }  }
- +
-  +</code> 
- public static void main(String[] args){+ 
 +Code zum selber testen: 
 +<code=java>  
 +public static void main(String[] args){
                 //Beispielaufruf mit aus 3 Subgraphen bestehendem Graph                 //Beispielaufruf mit aus 3 Subgraphen bestehendem Graph
  GraphWS15 g = new GraphWS15();  GraphWS15 g = new GraphWS15();
Zeile 269: Zeile 297:
    * path(Node(g, n), x, y) = path(g, x, y)    * path(Node(g, n), x, y) = path(g, x, y)
    * path(Edge(g, a, b), x, y) =  true      falls (path(g, x, a) ^ path(g, b, y)) v (path(g, y, a) ^ path(g, b, x))   ;  path(g, x, y) sonst    * path(Edge(g, a, b), x, y) =  true      falls (path(g, x, a) ^ path(g, b, y)) v (path(g, y, a) ^ path(g, b, x))   ;  path(g, x, y) sonst
 +
 +** c) **  
 +    * isRoot(Edge(g, a, b), x) = isRoot(g,x)    falls x!=b
 +       false sonst