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:loesungws15 [07.04.2017 09:27] – Danplanpruefungen:bachelor:aud:loesungws15 [24.07.2019 16:12] – dom
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 184: Zeile 185:
 </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 296:
    * 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