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:loesungws16 [07.02.2018 10:19] – Horscchtpruefungen:bachelor:aud:loesungws16 [22.05.2019 12:32] – SpeedyGonzalez
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
-  +
-  +
- public static <E extends Comparable<E>> void sort(E[] a) { +
- E temp; +
-  +
- for (int n = 1; n < a.length; n++) { +
-  +
- temp = a[n]; // entnommenes Element merken +
- int i = n - 1; +
-  +
- while (i >= 0 && temp.compareTo(a[i]) < 0) { +
- a[i + 1] = a[i]; +
- i--; +
- } +
- a[i + 1] = temp; // entnommenes Element +
- // einsetzen +
- } +
- } +
-  +
- private static String toString(Element[] x){ +
- String res=""; +
- for(Element e:x){ +
- res=res+e.toString(); +
- } +
- return res; +
- } +
-  +
- public static void main(String[] args) { +
- Element[] nonuniqueElements2 = {  +
- new Element(1, "Ich") ,  +
- new Element(2, "wissen"),  +
- new Element(4, "ist"), +
- new Element(2, "ob"), +
- new Element(1, "wuerde"), +
- new Element(2, "der"), +
- new Element(1, "gerne"), +
- new Element(2, "Algorithmus"), +
- new Element(3, "stabil"), +
- new Element(2, "auch"), +
- new Element(2, "wirklich"), +
- }; +
-  +
- String nonunique2_ElementsExpect="IchwuerdegernewissenobderAlgorithmusauchwirklichstabilist"; +
-  +
- Element[] test=nonuniqueElements2.clone(); +
- System.out.println("Unsortiert: " +Arrays.toString(test)); +
- Insertionsort.sort(test); +
- String x=toString(test); +
-  +
- System.out.println("Sortiert: " +Arrays.toString(test)); +
- assertEquals(nonunique2_ElementsExpect,x); +
- } +
-}+
  
 +Bucket 5: 13 - 65 - 33
  
-class Element implements Comparable<Element> { +Bucket 7: 46 - 26
- int key; +
- String value;+
  
- Element(int key, String value) { + 
- this.key = key; +** b) ** Es werden nur die ungeraden Buckets befüllt, da 2 und 8 nicht teilerfremd sind. 
- this.value = value;+ 
 +** 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 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... 
- @Override + for (int i = 0; i < 10; i++) { 
- public int compareTo(Element o) { +                //...distribute values into buckets: 
- if (key < o.key) { + for (Integer x: list) { 
- return -1; + int b = (int) (x/Math.pow(10,i)) % 10; 
- } else if (key > o.key) { + bs[b].addLast(x);
- return 1;+
  }  }
- return 0; +                //...recollect values from buckets: 
- } + list.clear(); 
-  + for (int j = 0; j < bs.length; j++) { 
- @Override + list.addAll(bs[j]); 
- public String toString() { + bs[j].clear();
- if(value instanceof String){ +
- return (String) value;+
  }  }
-  
- return value.toString(); 
  }  }
 } }
 </code> </code>
-==== Aufgabe 7 Graphen ====+** b) **
 <code java> <code java>
-public class GraphWS15 {+... 
 +int b = ((int) (x/Math.pow(10,i)) % 10) + 9; 
 +... 
 +</code>
  
- void sammle(boolean[][] am, int k, Set<Integer> verb, Set<Integer> bes) { +oder einfacher: 
- if (!bes.contains(k)) { +<code java> 
- verb.add(k); +... 
- bes.add(k); +bs[b + 9].addLast(x); 
- for (int i = 0; i < am[k].length; i++) { +</code> 
- if (am[k][i]){ +==== Aufgabe 4 Dynamische Programmierung ==== 
- sammle(am, i, verb, bes); +**a)** 
- } +<code java> 
- }+long countNaive(int n) { 
 + if (n == 0 || n == 1) { 
 + return 1; 
 + } 
 + int sum = 0; //sum muesste eigentlich ein long sein 
 + for (int i = 0; i < n; i++){ 
 + sum = sum + countNaive(i) * countNaive(n-1-i); 
 + } 
 + return sum; 
 +}
  
- for (int i = 0; i < am.length; i++) { +long countDP (int n) { 
- if (am[i][k]){ + long[] mem = new long[n+1]; 
- sammle(am, i, verb, bes); + mem[0] = mem[1] = 1; 
- } + return countDPH(mem, n); 
- }+} 
 + 
 +private long countDPH (long[] mem, int n) { 
 + if (mem[n] != 0) { 
 + return mem[n]; 
 + } else { 
 + int sum = 0; 
 + for (int i = 0; i < n; i++){ 
 + sum = sum + countDPH(mem, i) * countDPH(mem, n-1-i);
  }  }
 + mem[n] = sum;
 + return sum;
  }  }
 +}
  
- List<Set<Integer>> mszt(boolean[][] am) { +long countIter (int n) { 
- // Ergebnisliste: + ... 
- List<Set<Integer>> ergebnis = new LinkedList<>(); + for (int k = 2; k < n+1; k++){ 
- // Menge besuchter Knoten: + for (int i = 0; i < n; i++){ //Meiner Meinung nach mus hier unbedingt!!! i < k stehen, sonst rechnet man mit unbefuellten werten (buttom up beachten!) 
- Set<Integer> bk = new HashSet<>(); + mem[k] = mem[k] + mem[i] * mem[n-1-i]; //hier auch mem[k-1-i]!
- // 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); +
- } +
- +
  }  }
 + }
 + ...
 +}
 +</code>
  
- return ergebnis;+oder schöner: 
 + 
 +<code java> 
 +private long countDPH (long[] mem, int n) { 
 + if (mem[n] != 0) { 
 + return mem[n];
  }  }
 + for (int i = 0; i < n; i++){
 +            mem[n] += countDPH(mem, i) * countDPH(mem, n-1-i);
 + }
 + return mem[n];
 +}
 +</code>
  
- void itg(boolean[][] am, Set<Integer> vs) { +==== Aufgabe 5 Graphen ==== 
- for (int i=0;i<am.length;i++){ +** a) ** 
- for (int j=0;j<am[i].length;j++){ +Ergebnis: A 14, E 18, H4 6, H7 3, M 2, W 0 
- if (am[i][j]){ + 
- if (vs.contains(i) && vs.contains(j)){ +** b) ** siehe Tafeluebungsfolien 
- // ok + 
- } +** c) ** M - H7, M - W, M - H4, A - E, A - H4 oder A - W 
- else { + 
- am[i][j] = false; +** d) **  
- } +nein: bei 4 Knoten ungerader Grad 
- } +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;  
- 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>