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:loesungws16 [07.02.2018 10:37] – l Horscchtpruefungen:bachelor:aud:loesungws16 [02.08.2019 07:32] (aktuell) – Aufgabe 4 angepasst dom
Zeile 1: Zeile 1:
-<note warning>~ Hier entsteht in nächster Zeit eine Beispiellösung ~ 
- 
-</note> 
- 
 ===== Forendiskussionen ===== ===== Forendiskussionen =====
  
Zeile 27: Zeile 23:
 ** a) ** ** a) **
  
-TODO+Bucket 1: 27 - 75 
 + 
 +Bucket 3: 44 - 4 - 0 
 + 
 +Bucket 5: 13 - 65 - 33 
 + 
 +Bucket 7: 46 - 26 
  
 ** b) ** Es werden nur die ungeraden Buckets befüllt, da 2 und 8 nicht teilerfremd sind. ** b) ** Es werden nur die ungeraden Buckets befüllt, da 2 und 8 nicht teilerfremd sind.
  
-** c) ** TODO+** c) ** 
  
-==== Aufgabe 4 RadixSort ==== +Bucket 0: 12 S 
-** a) ***+ 
 +Bucket 1: 33 D 
 + 
 +Bucket 2: 66 S 
 + 
 +Bucket 3: 28 P 
 + 
 +Bucket 4: 14 D 
 + 
 +Bucket 5: 6 S 
 + 
 +Bucket 6: 18 D 
 + 
 +Bucket 7: 5 D 
 + 
 +Bucket 8: 15 P 
 + 
 +Bucket 9: 9 D 
 + 
 +==== Aufgabe 3 RadixSort ==== 
 +** a) **
 <code java> <code java>
 void radixSort (LinkedList<Integer> list) { void radixSort (LinkedList<Integer> list) {
- LinkedList<Integer>[] bs = new LinkedList[];+        //prepare sufficient buckets bs with empty lists: 
 + LinkedList<Integer>[] bs = new LinkedList[10];
  for (int i = 0; i < bs.length; i++) {  for (int i = 0; i < bs.length; i++) {
- bs[i] = new LinkedList();+ bs[i] = new LinkedList<>();
  }  }
 +        //for each segment of the Integer radix...
  for (int i = 0; i < 10; i++) {  for (int i = 0; i < 10; i++) {
 +                //...distribute values into buckets:
  for (Integer x: list) {  for (Integer x: list) {
- int b = (x/Math.pow(10,i)) % 10;+ int b = (int) (x/Math.pow(10,i)) % 10;
  bs[b].addLast(x);  bs[b].addLast(x);
  }  }
 +                //...recollect values from buckets:
  list.clear();  list.clear();
- for (int i = 0; i < bs.length; i++) { + for (int j = 0; j < bs.length; j++) { 
- list.addAll(bs[i]); + list.addAll(bs[j]); 
- bs[i].clear();+ bs[j].clear();
  }  }
  }  }
Zeile 57: Zeile 84:
 <code java> <code java>
 ... ...
-int b = ((x/Math.pow(10,i)) % 10) + 9;+int b = ((int) (x/Math.pow(10,i)) % 10) + 9;
 ... ...
 </code> </code>
-==== Aufgabe 5 Sortieren====+ 
 +oder einfacher: 
 +<code java> 
 +... 
 +bs[b + 9].addLast(x); 
 +</code> 
 +==== Aufgabe 4 Dynamische Programmierung ====
 **a)** **a)**
- +<code java> 
-^L * ^A1 ^B1 ^F ^A2 ^B2| +long countNaive(int n) { 
-|A1|L*|B1|F |A2|B2|  + if (n == 0 || n == 1) { 
-|A1|B1|L*|F |A2|B2| + return 1; 
-|A1|B1|F |L*|A2|B2| + } 
-|A1|A2|B1|F |L*|B2| + long sum = 0;  
-|A1|A2|B1|B2|F |L*|+ for (int i = 0; i < n; i++) { 
 + sum += countNaive(i) * countNaive(n-1-i); 
 + } 
 + return sum; 
 +} 
 +</code>
  
 **b)** **b)**
  
-==== Aufgabe 7 Graphen ==== +<code=java> 
-<code java> +long countDP (int n) { 
-public class GraphWS15 { + long[] mem = new long[n + 1]; 
- + mem[0] = 1; 
-void sammle(boolean[][] am, int k, Set<Integer> verb, Set<Integer> bes) { +        mem[1] = 1; 
- if (!bes.contains(k)) { +         
- verb.add(k); + return countDPH(mem, n); 
- bes.add(k); +}
- for (int i = 0; i < am[k].length; i++) { +
- if (am[k][i]){ +
- sammle(am, i, verb, bes); +
- } +
- }+
  
- for (int i = 0; i < am.length; i++) { +private long countDPH (long[] mem, int n) { 
- if (am[i][k]){ +        // Lookup 
- sammle(am, i, verb, bes); + if (mem[n] != 0) { 
- } + return mem[n]; 
- }+ } else { 
 + long sum = 0; 
 + for (int i = 0; i < n; i++) { 
 + sum += countDPH(mem, i) * countDPH(mem, n-1-i);
  }  }
 +                // Memoization
 + mem[n] = sum;
 + return sum;
  }  }
 +}
 +</code>
  
- List<Set<Integer>> mszt(boolean[][] am) { +oder schöner:
- // Ergebnisliste: +
- List<Set<Integer>> ergebnis = new LinkedList<>(); +
- // Menge besuchter Knoten: +
- Set<Integer> bk = new HashSet<>(); +
- // Ermittle alle Teilgraphen mittels Hilfsmethode sammle: +
- for (int k = 0; k < am.length; k++) { +
- if (!bk.contains(k)){ +
- // falls k noch nicht besucht => sammle mit k verbundene Knoten +
- Set<Integer> verb = new HashSet(); +
- sammle(am,k,verb, bk); +
- ergebnis.add(verb); +
- } +
-  +
- }+
  
- return ergebnis;+<code java> 
 +private long countDPH (long[] mem, int n) { 
 + // Lookup 
 +        if (mem[n] != 0) { 
 + return mem[n];
  }  }
 + for (int i = 0; i < n; i++) {
 +            // Berechnung + Memoization
 +            mem[n] += countDPH(mem, i) * countDPH(mem, n-1-i);
 + }
 + return mem[n];
 +}
 +</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]){ +long countIter (int n) { 
- if (vs.contains(i) && vs.contains(j)){ + ... 
- // ok + for (int k = 2; k < n+1; k++) { // for-Schleife fuer bottom-up 
- } + for (int i = 0; i < k; i++) { 
- else { + mem[k] = mem[k] + mem[i] * mem[k-1-i];
- am[i][j] = false; +
- } +
- } +
- } +
- +
  }  }
  }  }
-  + ... 
- public static void main(String[] args){ +} 
-                //Beispielaufruf mit aus 3 Subgraphen bestehendem Graph +</code> 
- GraphWS15 g = new GraphWS15(); + 
- boolean[][] am = {{false, true, false, true, false, false}, + 
-                                              {false, false, false, true, false, false}, +==== Aufgabe 5 Graphen ==== 
-                                              {false, false, false, false, true, false}, +** a) ** 
-                                              {false, true, false, false, false, false}, +Ergebnis: A 14, E 18, H4 6, H7 3, M 2, W 0 
-                                              {false, false, false, false, false, false}, + 
-                                              {false, false, false, false, false, false}}; +** b) ** siehe Tafeluebungsfolien 
- //Set<Integer> verb = new HashSet(); + 
- List<Set<Integer>> n = g.mszt(am); +** c) ** M - H7, M - W, M - H4, A - E, A - H4 oder A - W 
- System.out.println(n.size());  + 
- System.out.println(n.get(0).size());    +** d) **  
- System.out.println(n.get(1).size());  +nein: bei 4 Knoten ungerader Grad 
- System.out.println(n.get(2).size()); +nein: nicht mal ein Eulerweg 
 + 
 +==== Aufgabe 6 Rekursion ==== 
 +<code java> 
 +class MaxFlowMinCut { 
 +    void erreichbareVerteiler(Verteiler v, List<Verteiler> ev){ 
 +        if(!ev.contains(v)){ 
 +            ev.add(v); 
 +            for(Rohr r : v.rohre){ 
 +                this.erreichbareVerteiler(r.a, ev); 
 +                this.erreichbareVerteiler(r.e, ev); 
 +            } 
 +        } 
 +    }  
 +     
 +    double schnittDurchfluss(List<Verteiler> quelleSeite, List<Verteiler> senkeSeite){ 
 +        double sum = 0; 
 +        for(Verteiler v : quelleSeite){ 
 +            for(Rohr r : v.rohre){ 
 +                if(senkeSeite.contains(r.a) || senkeSeite.contains(r.e)){ 
 +                    sum += r.df;                     
 +                } 
 +            } 
 +        } 
 +        return sum; 
 +    }  
 +     
 +     
 +    double durchfluss(List<Verteiler> quelleSeite, List<Verteiler> senkeSeite, Verteiler senke){ 
 + Verteiler[] ssa = senkeSeite.toArray(new Verteiler[senkeSeite.size()]); 
 + double df = schnittDurchfluss(quelleSeite, senkeSeite); 
 + for(Verteiler v : ssa){ 
 + if(!v.equals(senke)){  // v.equals ist gleich zu == (Weil es von Object erbt, aber .equals nicht überschreibt) 
 + // Hier kann man noch checken, ob zu v auch eine Kante aus quelleSeite existiert, aber nicht notwendig, da der Cut nur länger weden würde -> nur geringere Laufzeit 
 + quelleSeite.add(v); 
 + senkeSeite.remove(v); 
 + df = Math.min(df, durchfluss(quelleSeite, senkeSeite, senke)); 
 +                        //"Backtracking" 
 + senkeSeite.add(v); 
 + quelleSeite.remove(v); 
 + }
  }  }
 + return df;
 +     }
 +     
 } }
 </code> </code>