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:42] – 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) **  
 + 
 +Bucket 0: 12 S 
 + 
 +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 4 RadixSort ====+==== Aufgabe 3 RadixSort ====
 ** a) ** ** 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>
 +
 +oder einfacher:
 +<code java>
 +...
 +bs[b + 9].addLast(x);
 </code> </code>
 ==== Aufgabe 4 Dynamische Programmierung ==== ==== Aufgabe 4 Dynamische Programmierung ====
Zeile 67: Zeile 100:
  return 1;  return 1;
  }  }
- int sum = 0; + long sum = 0;  
- for (int i = 0; i < n; i++){ + for (int i = 0; i < n; i++) { 
- sum = sum + countNaive(i) * countNaive(n-1-i);+ sum += countNaive(i) * countNaive(n-1-i);
  }  }
  return sum;  return sum;
 } }
 +</code>
 +
 +**b)**
  
 +<code=java>
 long countDP (int n) { long countDP (int n) {
- long[] mem = new long[];+ long[] mem = new long[n + 1];
  mem[0] = 1;  mem[0] = 1;
- mem[1] = 1;+        mem[1] = 1; 
 +        
  return countDPH(mem, n);  return countDPH(mem, n);
- ...+} 
 + 
 +private long countDPH (long[] mem, int n) { 
 +        // Lookup 
 + 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> </code>
-==== Aufgabe 5 Sortieren==== 
-**a)** 
  
-^L * ^A1 ^B1 ^F ^A2 ^B2| +oder schöner:
-|A1|L*|B1|F |A2|B2|  +
-|A1|B1|L*|F |A2|B2| +
-|A1|B1|F |L*|A2|B2| +
-|A1|A2|B1|F |L*|B2| +
-|A1|A2|B1|B2|F |L*|+
  
-**b)** 
- 
-==== Aufgabe 7 Graphen ==== 
 <code java> <code java>
-public class GraphWS15 {+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 sammle(boolean[][] am, int k, Set<Integer> verb, Set<Integer> bes) { +**c)**
- 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); +
- } +
- }+
  
- for (int i = 0; i < am.length; i++) { +<code=java> 
- if (am[i][k]){ +long countIter (int n) { 
- sammle(am, i, verb, bes); + ... 
- } + for (int k = 2; k < n+1; k++) { // for-Schleife fuer bottom-up 
- }+ for (int i = 0; i < k; i++) { 
 + mem[k] = mem[k] + mem[i] * mem[k-1-i];
  }  }
  }  }
 + ...
 +}
 +</code>
  
- List<Set<Integer>> mszt(boolean[][] am) { 
- // 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; +==== Aufgabe 5 Graphen ==== 
- }+** a) ** 
 +Ergebnis: A 14, E 18, H4 6, H7 3, M 2, W 0
  
- void itg(boolean[][] am, Set<Integer> vs) { +** b) ** siehe Tafeluebungsfolien 
- for (int i=0;i<am.length;i++){ + 
- for (int j=0;j<am[i].length;j++){ +** c) ** M - H7, M - W, M - H4, A - E, A - H4 oder A - W 
- if (am[i][j]){ + 
- if (vs.contains(i) && vs.contains(j)){ +** d) **  
- // ok +nein: bei 4 Knoten ungerader Grad 
- } +nein: nicht mal ein Eulerweg 
- else { + 
- am[i][j] = false; +==== 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;  
- public static void main(String[] args){ +     } 
-                //Beispielaufruf mit aus 3 Subgraphen bestehendem Graph +     
- GraphWS15 g = new GraphWS15(); +
- boolean[][] am = {{false, true, false, true, false, false}, +
-                                              {false, false, false, true, false, false}, +
-                                              {false, false, false, false, true, false}, +
-                                              {false, true, false, false, false, false}, +
-                                              {false, false, false, false, false, false}, +
-                                              {false, false, false, false, false, false}}; +
- //Set<Integer> verb = new HashSet(); +
- List<Set<Integer>> n = g.mszt(am); +
- System.out.println(n.size());  +
- System.out.println(n.get(0).size());  +
- System.out.println(n.get(1).size());  +
- System.out.println(n.get(2).size());  +
- }+
 } }
 </code> </code>