FSI Informatik/pruefungen/bachelor/aud/loesungws17

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!

Aufgabe1

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,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

Aufgabe2

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

Aufgabe3

   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;
		}
	}

c) 2^n

   long mgl (int n){
		return (long) Math.pow(2, n);
	}

Aufgabenstellung: ohne API!

  long mgl(int n){
                return (long) n==0?1:mgl(n-1)*2;
  }

beide Ansätze sind falsch, ohne Methoden aus der Java-API und ohne weitere Anweisungen, 1 « n

   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;
	}

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

Aufgabe4

  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;
   	if(c.v != 0 && vs[c.v] == true){
       	return false;}
       vs[c.v] = true;
   }
   if(vs[0]&& s >= sum){
       return false;
       }
   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;
  }

  boolean solve (LinkedList<Cell> cs){
    if(cs.size()<=0){ //alternativ sollte hier auch Folgendes gehen: if(cs.isempty()){...}
           return true;
    }
     Cell z = cs.removeFirst();
     for( z.v = 1; z.v <= 9; z.v++){
         boolean ok = true;
         for( Chain c : z.ks){
             if(!c.satisfiable()){
                 ok = false;
             }
         }
         if( ok && solve(cs)){
             return true;
         }
     }
     z.v = 0;
     cs.addFirst(z);         
     return false;
   }

Aufgabe5

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

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;
}

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

c) bitte ergänzen

Feld 1
   while(r != udfs.get(r) {
      r = udfs.get(r);
   }
Feld 2 
   while(pc != r) {
      udfs.put(c, r);
      c = pc;
      pc = udfs.get(c);
   }

Aufgabe6

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)))

ich hätte hier: frac2cf(Frac(n,d)) = F¹⁾)

c) 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))) Das oben macht ja schon teilweise syntaktisch keinen Sinn

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

Aufgabe7

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

¹⁾
n-n%d)/d, frac2cf(Frac(d,n%d