Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Aufgabe 1   (Ü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:loesungws17 [24.07.2019 09:19] – Kleine Korrektur bei Aufgabe 5c) dompruefungen:bachelor:aud:loesungws17 [05.08.2019 15:57] (aktuell) – TOKAMAK
Zeile 1: Zeile 1:
-**__Aufgabe1__** +====   Aufgabe 1 ====
 a) 1,3,4     //4 ist falsch, nicht die Argumentfolge, sondern die Werte der Terminierungsfunktion müssen streng monoton fallend sein// a) 1,3,4     //4 ist falsch, nicht die Argumentfolge, sondern die Werte der Terminierungsfunktion müssen streng monoton fallend sein//
  
 b) 2,3      //4 ist wahr, mit dem Konzept des Ergebnisse durchreichen lässt sich eine iterative Methode mit Laufzeit O(n) und vier lokalen Variablen (also konstantem Speicherbedarf) schreiben //Anmerkung: Meines Erachtens sollte hier nur 4 richtig sein, da bei 2 zwar der Laufzeitaufwand von O(n) stimmt, aber der Speicheraufwand sollte in O(1) machbar sein, bleibt also die Frage, ob das "benoetigt" hier bedeutet, dass man min. einen Speicheraufwand von O(n) hat. Ausserdem sollte 3 falsch sein, da DP einen Laufzeitaufwand von O(n) hat! b) 2,3      //4 ist wahr, mit dem Konzept des Ergebnisse durchreichen lässt sich eine iterative Methode mit Laufzeit O(n) und vier lokalen Variablen (also konstantem Speicherbedarf) schreiben //Anmerkung: Meines Erachtens sollte hier nur 4 richtig sein, da bei 2 zwar der Laufzeitaufwand von O(n) stimmt, aber der Speicheraufwand sollte in O(1) machbar sein, bleibt also die Frage, ob das "benoetigt" hier bedeutet, dass man min. einen Speicheraufwand von O(n) hat. Ausserdem sollte 3 falsch sein, da DP einen Laufzeitaufwand von O(n) hat!
  
-c) 2,4 Ist 2 nicht die Definition von groß-O? //Ja, 2 ist falsch, 3 ist wahr (das ist literally die Definition von Theta)//+c) 2,3,4 Ist 2 nicht die Definition von groß-O? //Ja, 2 ist falsch, 3 ist wahr (das ist literally die Definition von Theta)//
  
 d) 1,4 d) 1,4
Zeile 11: Zeile 10:
 e) 1,2 e) 1,2
  
-**__Aufgabe2__**+====   Aufgabe 2 ====
  
 a)  a) 
Zeile 24: Zeile 23:
  
  
-**__Aufgabe3__**+====   Aufgabe 3 ====
  
 a) a)
Zeile 103: Zeile 102:
  }  }
 </code> </code>
-c) 2^n+ 
 +Evtl noch besserer: 
 <code java> <code java>
-   long mgl (int n){ +for (int i = 0; i < b.length; i++) { 
- return (long) Math.pow(2, n); + b[i] = b[i]? false : true; 
- }+ if(b[i]) break; 
 +}
 </code> </code>
-Aufgabenstellung: ohne API!+ 
 +c) 2^n 
 <code java> <code java>
-  long mgl(int n){ +long mgl (int n){ 
-                return (long) n==0?1:mgl(n-1)*2; + return 1 << n; // n Bits nach links shiften 
-  }+}
 </code>                   </code>                  
-beide Ansätze sind falsch, ohne Methoden aus der Java-API und ohne weitere Anweisungen, 1 << n+
  
 d)  d) 
Zeile 133: Zeile 137:
 </code> </code>
 e) e)
 +ueber(n - 1, k - 1) und ueber(n - 1, k)
  
-ueber(n-1,k-1) und ueber(n-1,k) +====   Aufgabe 4 ====
- +
-**__Aufgabe4__**+
  
 a) a)
 <code java> <code java>
-  class Cell {+class Cell {
   List<Chain> ks;   List<Chain> ks;
   int v;   int v;
-  }+}
  
-  class Chain {+class Chain {
   List<Cell> zs;   List<Cell> zs;
   int sum;   int sum;
  
-  boolean satisfiable(){ +boolean satisfiable() { 
- int s = 0; +  int s = 0; 
- boolean[] vs = new boolean[10]; +  boolean[] vs = new boolean[10]; 
- for(Cell c : zs) { + 
-   s = s + c.v; +  for(Cell c : zs) { 
-   if(c.v != 0 && vs[c.v] == true){ +    s = s + c.v; 
-       return false;} +    vs[c.v] = true;  //hier wird die Zahl auf "true" gesetzt 
-       vs[c.v] = true; +    if (c.v != 0 && vs[c.v] == true) {   // ii)  //und hier wird deswegen dann immer false zurueckgegeben 
-   } +      return false; 
-   if(vs[0]&& s >= sum){ +    }        
-       return false; +    //Loesung vs[c.v] erst nach Abfrage auf "true" setzen 
-       } +    //vs[c.v] = true;
-   else if(sum != s){        //Hier muss man noch mit !vs[0] verunden, muss ja nur gleich sein, wenn alle Zahlen bekannt sind// +
-       return false; +
-   } +
-   return true;+
   }   }
 +  if (s > sum && vs[0] == true) { // i)
 +    return false;
 +  } else if (s != sum && vs[0] == false) { // i)
 +    return false;
 +  }
 +   
 +  return true;
 +}
 </code> </code>
 b) b)
 <code java> <code java>
-  boolean solve (LinkedList<Cell> cs){ +boolean solve (LinkedList<Cell> cs) { 
-    if(cs.size()<=0){ //alternativ sollte hier auch Folgendes gehen: if(cs.isempty()){...} +    if (cs.size() <= 0) {  
-           return true;+        return true;
     }     }
-     Cell z = cs.removeFirst(); +    Cell z = cs.removeFirst(); 
-     for( z.v = 1; z.v <= 9; z.v++){ + 
-         boolean ok = true; +    // try to assign 1 to 9 to its v and check all chains that z belongs to 
-         for( Chain c : z.ks){ +    for (z.v = 1; z.v <= 9; z.v++) { 
-             if(!c.satisfiable()){ +        boolean ok = true; 
-                 ok = false; +        for (Chain c : z.ks) { 
-             } +            if (!c.satisfiable()) { 
-         } +                ok = false; 
-         if( ok && solve(cs)){ +            } 
-             return true; +        } 
-         } +        // if all chains are ok => recurse 
-     } +        if (ok && solve(cs)) { 
-     z.v = 0; +            return true; 
-     cs.addFirst(z);          +        } 
-     return false; +    } 
-   }+ 
 +    // backtrack 
 +    z.v = 0; 
 +    cs.addFirst(z); 
 + 
 +    return false; 
 +}
 </code>    </code>   
  
-**__Aufgabe5__**+====   Aufgabe 5 ====
 <code java> <code java>
 class UndirEdge<T> { class UndirEdge<T> {
Zeile 249: Zeile 262:
  
  
-**__Aufgabe6__** +====   Aufgabe 6 ====
 a)  a) 
 +
 F(4,F(1,F(2,L(3)))) F(4,F(1,F(2,L(3))))
  
 b)  b) 
 +
 frac2cf(Frac(n, 1)) = L(n) frac2cf(Frac(n, 1)) = L(n)
  
-frac2cf(Frac(n, d)) = F(n/d,frac2cf(Frac(d,n%d))) +frac2cf(Frac(n, d)) = F(n/d, frac2cf(Frac(d, n%d)))
- +
-ich hätte hier: +
-frac2cf(Frac(n,d)) = F((n-n%d)/d, frac2cf(Frac(d,n%d)))+
  
 c) c)
 +
 cf2frac(L(n)) = Frac(n, 1)  cf2frac(L(n)) = Frac(n, 1) 
  
-cf2frac(F(b, cf)) = Frac( num(Frac(b x den(Frac(cf))+den(cf2frac(cf)),den(cf2frac(cf))), 
- 
-den(Frac(b x den(Frac(cf))+den(cf2frac(cf)),den(cf2frac(cf))) 
-) 
- 
-Ich hätte hier: 
 cf2frac(F(b, cf)) = Frac(b * num(cf2frac(cf)) + den(cf2frac(cf)), num(cf2frac(cf))) cf2frac(F(b, cf)) = Frac(b * num(cf2frac(cf)) + den(cf2frac(cf)), num(cf2frac(cf)))
-Das oben macht ja schon teilweise syntaktisch keinen Sinn 
  
 d) d)
  
-same(L(x), L(y)) = if(x==y) then true else false +same(L(x), L(y)) = x==y 
- +
-//sollte man hier nicht immer "true zurückgeben? Es ist ja gefragt, ob sie die gleiche Darstellung haben. Und sie haben die gleiche Darstellung, egal ob x = y oder nicht.// +
- +
-same(F(x, a), F(y, b)) = if(x==y) && same(a==b) then true else false +
- +
-//hier auch einfach true, oder?//+
  
 +same(F(x, a), F(y, b)) = x==y && same(a, b) 
  
 same(F(x, a),L(y)) = false same(F(x, a),L(y)) = false
Zeile 289: Zeile 289:
 same(L(x),F(y,b)) = false same(L(x),F(y,b)) = false
  
-**__Aufgabe7__** +====   Aufgabe 7 ====
- +
-bei a) - d) bin ich mir sicher, beim Rest könnt ihr mich gerne verbessern! Nein, bist du nicht.+
  
 a) Alpha  a) Alpha 
  
-b) Beta, Wenn man den Code abtippt, sieht man, dass Beta ausgeben wird. Ich vermute, dass das Interface Alpha aufgerufen wird, da dies der statische Typ beim Objekt ag ist. Da der Parameter c der Methode omega int ist, wird hier implizit von char zu int gecastet. Dadurch wird omega(int i) (Klasse Beta) statt omega(char c) (Klasse Gamma) aufgerufen, da **int** hier eben besser passt.+b) Beta
  
 c) Gamma  c) Gamma 
Zeile 301: Zeile 299:
 d) 4711 d) 4711
  
-e) Laut API hat out nen static modifier, also Klassenvariable// +e) Klassenvariable
- +
-f) öffentlich, statisch überladen      Anmerkung: Laut API nicht statisch soweit ich das sehe+
  
 +f) öffentlich, überladen
  
 g) 16 überlädt 6 g) 16 überlädt 6