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:19] – 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 8: Zeile 4:
  
 ==== Aufgabe 1 Wissensfragen ==== ==== Aufgabe 1 Wissensfragen ====
-** a) ** 1 und 3+** a) ** 1 und 4
  
-** b) ** 2 und 3+** b) ** 1 und 2
  
-** c) ** 2    +** c) ** 2 und 4   
-  *  "Die Länge des Feldes ist keine 2er-Potenz.": unsicher, ob das hier eine Rolle spielt+  
 +** d) ** 1 und 3
  
-** d) ** 3+** e) ** 2 und 3
  
-** e) ** 1 und 4 +** f) ** 1 und 3
-  * Man spricht nur bei "ungerichteten" Graphen von "Grad", bei gerichteten unterscheidet man Eingangs- und Ausgangsgrad. Wenn ein Knoten ein Grad 0 hat, dann gibt es keine Kante auf ihn. Der Graph ist also bereits ab einem Knoten mit Grad 0 nicht mehr zusammenhängend. Vorausgesetzt der Graph besteht aus mehr als einem Knoten. Da nichts anderes Korrekt scheint, muss dass also so passen. +
-  * Ein stark zusammenhängender Graph hat zyklen, womit der Graph kein DAG mehr sein kann +
-** f) ** 2 und 4 +
-  * "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 und 3
-  * unsicher +
-==== Aufgabe 5 Sortieren==== +
-**a)**+
  
-^L * ^A1 ^B1 ^F ^A2 ^B2| +** h) ** 3 und 4
-|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 2 Streupeicherung ==== 
-<code java> +** a) **
-import static org.junit.Assert.*; +
-import java.util.*;+
  
 +Bucket 1: 27 - 75
  
-public class Insertionsort<E extends Comparable<E>> extends SortAlgos<E> { +Bucket 3: 44 - 4 - 0 
-  + 
-  +Bucket 5: 13 - 65 - 33 
- public static <E extends Comparable<E>> void sort(E[] a) { + 
- E temp; +Bucket 7: 46 - 26 
-  + 
- for (int n = 1; n < a.length; n++) { + 
-  +** b) ** Es werden nur die ungeraden Buckets befüllt, da 2 und 8 nicht teilerfremd sind. 
- temp = a[n]; // entnommenes Element merken + 
- int i = n - 1; +** c) **  
-  + 
- while (i >= 0 && temp.compareTo(a[i]) < 0) { +Bucket 0: 12 S 
- a[i + 1] = a[i]; + 
- i--; +Bucket 1: 33 D 
- } + 
- a[i + 1] = temp; // entnommenes Element +Bucket 2: 66 S 
- // einsetzen + 
- }+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> 
 +void radixSort (LinkedList<Integer> list) { 
 +        //prepare sufficient buckets bs with empty lists: 
 + LinkedList<Integer>[] bs = new LinkedList[10]; 
 + for (int i = 0; i < bs.length; i++) { 
 + bs[i] = new LinkedList<>();
  }  }
-  +        //for each segment of the Integer radix... 
- private static String toString(Element[] x){ + for (int i = 0; i < 10; i++) { 
- String res=""; +                //...distribute values into buckets: 
- for(Element e:x){ + for (Integer x: list) { 
- res=res+e.toString();+ int b = (int) (x/Math.pow(10,i)) % 10; 
 + bs[b].addLast(x); 
 + } 
 +                //...recollect values from buckets: 
 + list.clear(); 
 + for (int j = 0; j < bs.length; j++) { 
 + list.addAll(bs[j]); 
 + bs[j].clear();
  }  }
- return res; 
  }  }
-  +} 
- public static void main(String[] args) { +</code> 
- Element[] nonuniqueElements2 = {  +** b) ** 
- new Element(1, "Ich") ,  +<code java> 
- new Element(2, "wissen"),  +... 
- new Element(4, "ist"), +int b = ((int) (x/Math.pow(10,i)) % 10) + 9; 
- new Element(2, "ob"), +... 
- new Element(1, "wuerde"), +</code> 
- new Element(2, "der"), + 
- new Element(1, "gerne"), +oder einfacher: 
- new Element(2, "Algorithmus"), +<code java> 
- new Element(3, "stabil"), +... 
- new Element(2, "auch"), +bs[b + 9].addLast(x); 
- new Element(2, "wirklich"), +</code> 
- }; +==== Aufgabe 4 Dynamische Programmierung ==== 
-  +**a)** 
- String nonunique2_ElementsExpect="IchwuerdegernewissenobderAlgorithmusauchwirklichstabilist"; +<code java> 
-  +long countNaive(int n) { 
- Element[] test=nonuniqueElements2.clone(); + if (n == 0 || n == 1) { 
- System.out.println("Unsortiert: " +Arrays.toString(test)); + return 1;
- Insertionsort.sort(test); +
- String x=toString(test); +
-  +
- System.out.println("Sortiert: " +Arrays.toString(test)); +
- assertEquals(nonunique2_ElementsExpect,x);+
  }  }
 + long sum = 0; 
 + for (int i = 0; i < n; i++) {
 + sum += countNaive(i) * countNaive(n-1-i);
 + }
 + return sum;
 } }
 +</code>
  
 +**b)**
  
-class Element implements Comparable<Element> { +<code=java> 
- int key; +long countDP (int n) { 
- String value;+ long[] mem = new long[n + 1]; 
 + mem[0] = 1; 
 +        mem[1] = 1; 
 +         
 + return countDPH(mem, n); 
 +}
  
- Element(int key, String value) { +private long countDPH (long[] mem, int n) { 
- this.key = key; +        // Lookup 
- this.value = value; + if (mem[n] != 0) { 
- } + return mem[n]; 
-  + } else { 
- @Override + long sum = 0; 
- public int compareTo(Element o) { + for (int i = 0; i < n; i++) { 
- if (key < o.key) { + sum += countDPH(mem, i) * countDPH(mem, n-1-i);
- return -1; +
- } else if (key > o.key) { +
- return 1;+
  }  }
- return 0; +                // Memoization 
- } + mem[n] = sum; 
-  + return sum;
- @Override +
- public String toString() { +
- if(value instanceof String){ +
- return (String) value; +
- } +
-  +
- return value.toString();+
  }  }
 } }
 </code> </code>
-==== Aufgabe 7 Graphen ====+ 
 +oder schöner: 
 <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>