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 [22.03.2018 14:38] – LasagneAlFornopruefungen:bachelor:aud:loesungws15 [23.03.2020 10:40] (aktuell) – kat04
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 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();