===== Forendiskussionen ===== * [[https://fsi.informatik.uni-erlangen.de/forum/thread/11145-Klausur-SS2013]] ===== Lösungsversuch ===== ==== Aufgabe 1 - Wissensfragen ==== **a)** ganz auf die Deklaration des Ausnahmetyps X verzichten\\ **b)** falsch\\ **c)** true\\ **d)** falsch\\ **e)** falsch\\ **f)** falsch, richtig: FIFO\\ **g)** O(n). Einfügen, nach Prüfen ob doppelt vorhanden: O(n). Um einen Wert zu löschen muss dieser erst gefunden werden: O(n). O(n) + O(n) = O(n).\\ **h)** falsch\\ (unsicher) Wenn wir in eine Hashtabelle einen Wert einfügen wollen, aber die Stelle bereits belegt ist, haben wir eine Primärkollision. Wenn wir dann diese durch Sondierung auflösen und unseren Wert an einen neuen Ort anlegen wollen, dieser aber auch belegt ist, dann bekommen wir eine Sekundärkollision. Der Fall hier ist aber eine Doppelkollision (siehe auch Foliensatz 11 Folie 87) **i)** class GenericContainer >\\ Da in Zeile 6 auf die Methode "compareTo" zwingend zugegriffen werden muss. **j)** O(n log n) \\ **k)** falsch\\ **l)** falsch\\ **m)** O(n log n)\\ ==== Aufgabe 2 (UML und OOP) ==== **a)**\\ ist unverdaulich\\ 42\\ 2\\ 0.815 kg\\ 4711\\ 4711\\ Apfelringe\\ Birnenmus\\ **b)**


public interface Essbar {
    String menge = "0.815 kg";
    java.util.ArrayList digestif = new java.util.ArrayList();
    /* List ist besser als Array, denn so muessen wir nicht unbedingt die Groesse festlegen */
    String verdauen(int portionen);
}

**c)**


 public class MilchShake extends ObstGericht implements Trinkbar{
    static String menge = "1 Becher";
    String bananen = "Hola Chica";
    private boolean laktosefrei = false;
   
    public String verdauen(long portionen){
        return Long.toString(portionen);
    }
   
    public static String schaelen(long aepfel){
        return "Apfelmus";
    }
   
    public String schaelen(String birnen){
        return "Birnenmus";
    }
}

==== Aufgabe 3 (Abstrakte Datentypen) ==== Seien a, b vom Datentyp MathExpr und d vom Datentyp double. **a)**


ops:
diff: MathExpr → MathExpr

axs:
diff(const(d)) = const(0)
diff(v) = const(1)
diff(add(a, b)) = add(diff(a), diff(b))

**b)**


ops:
sub: MathExpr x MathExpr → MathExpr
mul: MathExpr x MathExpr → MathExpr

axs:
diff(sub(a, b)) = sub(diff(a), diff(b))
diff(mul(a, b)) = add(mul(diff(a), b), mul(a, diff(b))

**c)**


axs:
diff(sin(a)) = mul(cos(a), diff(a))
diff(cos(a)) = sub(const(0), mul(sin(a), diff(a))) 
**Besser (wenn a negativ ist):**
diff(cos(a)) = mul(sub(const(0), sin(a)), diff(a))
//Geht nicht auch folgendes:?
diff(cos(a)) = mul(mul(const(-1),sin(a)),diff(a))

==== Aufgabe 4 (Streuspeicherung) ==== **a)**\\ i) ^ Buckets ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ ^ Schlüssel | V2 | V4 | | | V3 | V1 | ^ | V5 | | | | | V6 | ii) h’(VK) := 0 **b)**\\ i) ^ Buckets ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ ^ Schlüssel | V2 | V4 | V6 | V5 | V3 | V1 | ii) Lastfaktor = Eingetragene Schlüssel / Buckets = 6/6 = 1 = 100% ==== Aufgabe 5 (Rekursion) ==== **a)**


class MaxFlowMinCut {
      
    void erreichbareVerteiler(Verteiler v, List ev){
        if(!ev.contains(v)){
            ev.add(v);
            for(Rohr r : v.rohre){
                this.erreichbareVerteiler(r.a, ev);
                this.erreichbareVerteiler(r.e, ev);
            }
        }
    }

**b)**


double schnittDurchfluss(List quelleSeite, List senkeSeite){
        double sum = 0;
        for(Verteiler v : quelleSeite){
            for(Rohr r : v.rohre){
                if((v.equals(r.e) && senkeSeite.contains(r.a)) || (v.equals(r.a) && senkeSeite.contains(r.e))){
                    sum += r.df;                    
                }
            }
        }
        return sum;
    }

**c)**


// Achtung, diese Lösung ist ziemlich sicher falsch. Nicht rekursiv gelöst wie gefordert und damit werden auch nicht alle Lösungen gefunden
double durchfluss(List quelleSeite, List senkeSeite, Verteiler senke){
	Verteiler[] ssa = senkeSeite.toArray(new Verteiler[senkeSeite.size()]);
	double df = schnittDurchfluss(quelleSeite, senkeSeite);
	for(Verteiler v : ssa){
		if(!v.equals(senke) && senkeSeite.contains(v)){
			quelleSeite.add(v);
			senkeSeite.remove(v);
			df = Math.min(df, this.schnittDurchfluss(quelleSeite, senkeSeite));
			senkeSeite.add(v);
			quelleSeite.remove(v);
		}
	}
	return df;		
}

==== Aufgabe 6 (Graphen) ==== **a)** ^ Q ^ A ^ B ^ C ^ D ^ E ^ F ^ Queue ^ |[0] | x | x | x | x | x | x | Q | | | [1] | 3 | x | 5 | x | x | A, B, D | | | | 3 | x | 4 | [2] | x | E, B, D | | | | [3] | x | 4 | | 10 | B, D, F | | | | | 7 | [4] | | 10 | D, C, F | | | | | 6 | | | [5] | F, C | | | | | [6] | | | | C | |0 | 1 | 3 | 6 | 4 | 2 | 5 | | **b)**\\ Q --> A --> D --> F (oder)\\ Q --> B --> D --> F **c)**\\ (Q,A) (A,E) (B,D) (D,F) (D,C) (A,D)\\ 9 Meter Kabel ==== Aufgabe 7 (Sortierverfahren) ==== **a)**


class GroessenVergleicher implements Comparator {
      
    @Override
    public int compare(Socke o1, Socke o2) {
        if (o1.g < o2.g) {
            return -1;
        } else if (o1.g == o2.g) {
            return 0;
        } else {
            return 1;
        }
    }
}

**b)**


public int compare(Socke o1, Socke o2) {
        return o1.m.compareTo(o2.m);
    }    
}

**c)**


@Override
public int compare(Socke arg0, Socke arg1) {
   int c = gv.compare(arg0, arg1);
   return c != 0 ? c : mv.compare(arg0, arg1);
}

**d)**


    private void mergeSort(int from, int to) {
        if (to <= from) {
            return;
        }
        int mitte = (from + to) / 2;
        mergeSort(from, mitte);
        mergeSort(mitte + 1, to);
        int links = from;
        int rechts = mitte + 1;
        int counter = from;
        for (int i = from; i <= to; i++) {
            sTmp[i] = s[i];
        }
        while (links <= mitte && rechts <= to) {
            if (v.compare(sTmp[links], sTmp[rechts]) <= 0) {
                s[counter++] = sTmp[links++];
            } else {
                s[counter++] = sTmp[rechts++];
            }
        }
        while (links <= mitte) {
            s[counter++] = sTmp[links++];
        }
        while (rechts <= to) {
            s[counter++] = sTmp[rechts++];
        }
    }