Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Aufgabe 1   (Übersicht)

Dies ist eine alte Version des Dokuments!


Aufgabe 1

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!

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

e) 1,2

Aufgabe 2

a)

b) 31,23,29,19,7,17,13,5,11, 3, 2

c) 41,29,37,23,19,31,13,2,3,5,7,11,17

Aufgabe 3

a)

   int anzahlGutUndDoppelt (int n){
		boolean [] b = new boolean[n];
		int z = 0;
 
		for(int i=0;i<b.length-1;i++){
			b[i] = true;
			for (int x = i+1; x<b.length;x++){
				b[x]=true;                             //alternativ zu i+1 geht auch if (i == x) x++; oder?
				if(istGut(b)){
					z++;
				}
				b[x]=false;
			}
			b[i]=false;
		}
		return z;
	}

b) ist leider nur wenig elegant

   void naechste(boolean[]b){
		boolean carryNew = false, carryOld=true;
 
		for(int i=0; i<b.length;i++){
			if(b[i]&&carryOld){
				b[i]= !b[i];
				carryNew = true;
				carryOld=false;
			}
			else if(!b[i]&&carryOld){
				b[i]= !b[i];
				carryNew = false;
				carryOld=false;
			}
			else if(b[i]&&carryNew){
				b[i]= !b[i];
				carryNew = true;
			}
			else if(b[i]&&carryNew){
				b[i]= !b[i];
				carryNew = false;
			}
		}
	}

Evtl besser :)

  void naechste(boolean[]b){
	  boolean carryNew = false, carryOld=true;
	  for(int i=0; i<b.length;i++){
	  carryOld=carryNew;
		  if(carryOld){
			  if(b[i]==true){
				  carryNew=false;
			  }else{
				  b[i]=true;
				  carryNew=false;
			  }
		  }
	  }
  }
 

Evtl noch besser:

public static void naechste(boolean[] b) {
		boolean carryNew = false;
		boolean carryOld = true;
		for(int i = 0; i < b.length; i++) {
			carryNew = b[i] && carryOld;
			b[i] = b[i] ^ carryOld;
			carryOld = carryNew;
		}
	}

Evtl noch besserer:

for (int i = 0; i < b.length; i++) {
	b[i] = b[i]? false : true;
	if(b[i]) break;
}

c) 2^n

long mgl (int n){
	return 1 << n; // n Bits nach links shiften
}

d)

   int anzahlGute(int n){
		int z = 0;
		boolean[]b = new boolean[n];
		long mglk = mgl(n);
		for(int i=0;i<mglk;i++){
			if(istGut(b)){
				z=z+1;
			}
                        naechste(b);
		}
		return z;
	}

e) ueber(n - 1, k - 1) und ueber(n - 1, k)

Aufgabe 4

a)

class Cell {
  List<Chain> ks;
  int v;
}
 
class Chain {
  List<Cell> zs;
  int sum;
 
boolean satisfiable() {
  int s = 0;
  boolean[] vs = new boolean[10];
 
  for(Cell c : zs) {
    s = s + c.v;
    vs[c.v] = true;  //hier wird die Zahl auf "true" gesetzt
    if (c.v != 0 && vs[c.v] == true) {   // ii)  //und hier wird deswegen dann immer false zurueckgegeben
      return false;
    }       
    //Loesung vs[c.v] erst nach Abfrage auf "true" setzen
    //vs[c.v] = true;
  }
  if (s > sum && vs[0] == true) { // i)
    return false;
  } else if (s != sum && vs[0] == false) { // i)
    return false;
  }
 
  return true;
}

b)

boolean solve (LinkedList<Cell> cs) {
    if (cs.size() <= 0) { 
        return true;
    }
    Cell z = cs.removeFirst();
 
    // try to assign 1 to 9 to its v and check all chains that z belongs to
    for (z.v = 1; z.v <= 9; z.v++) {
        boolean ok = true;
        for (Chain c : z.ks) {
            if (!c.satisfiable()) {
                ok = false;
            }
        }
        // if all chains are ok => recurse
        if (ok && solve(cs)) {
            return true;
        }
    }
 
    // backtrack
    z.v = 0;
    cs.addFirst(z);
 
    return false;
}

Aufgabe 5

class UndirEdge<T> {
    public final T v, 
    public final T w;
 
    UndirEdge(T v, T w) { 
    this.v = v;
    this.w = w; 
    }
} 
 

a)

Map<T, T> initUnionFind(List<UndirEdge<T>> es) { 
   Map<T, T> ufds = new HashMap<T, T>();
 
  for (UndirEdge<T> e: es) {
     ufds.put(e.v,e.v);
     ufds.put(e.w,e.w);
  }
  return ufds;
}
 

b)

   void union(Map<T, T> ufds, T v, T w) {
      ufds.put(v,w);
   }
 

c)

T find(Map<T, T> ufds, T n) {
 
   // find root of n in ufds:
   while (r != udfs.get(r) {
      r = udfs.get(r);
   }
 
   // r is now pointing to the root of the partial set tree.
   // perform path compression:
   T c = n;
   pc = ufds.get(c);
 
   while (pc != r) {
   // so lange wir noch nicht bei der Wurzel sind, machen wir die Knoten auf dem Pfad dorthin zu Kindern der Wurzel
      union(ufds, c, r);
      c = pc;
      pc = udfs.get(c);
   }
   return r;
}

Aufgabe 6

a) F(4,F(1,F(2,L(3))))

b) frac2cf(Frac(n, 1)) = L(n)

frac2cf(Frac(n, d)) = F(n/d, frac2cf(Frac(d, n%d)))

c)

cf2frac(L(n)) = Frac(n, 1)

cf2frac(F(b, cf)) = Frac(b * num(cf2frac(cf)) + den(cf2frac(cf)), num(cf2frac(cf)))

d)

same(L(x), L(y)) = if(x==y) then true else false

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),L(y)) = false

same(L(x),F(y,b)) = false

Aufgabe 7

bei a) - d) bin ich mir sicher, beim Rest könnt ihr mich gerne verbessern! Nein, bist du nicht.

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.

c) Gamma

d) 4711

e) Laut API hat out nen static modifier, also Klassenvariable f) öffentlich, statisch überladen Anmerkung: Laut API nicht statisch soweit ich das sehe g) 16 überlädt 6