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

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)) = x==y

same(F(x, a), F(y, b)) = x==y && same(a, b)

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

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

Aufgabe 7

a) Alpha

b) Beta

c) Gamma

d) 4711

e) Klassenvariable

f) öffentlich, überladen

g) 16 überlädt 6