Studies

Aufgabe 1: Allgemeine Fragen

  1. Wandeln sie die Zahl 13245 in 5-adischer Zahlendarstellung in Dezimaldarstellung um. Bei dieser Aufgabe muss der Lösungsweg erkenntlich sein. Ein Ergebnis ohne Lösungsweg gibt keine Punkte.

    4·50 + 2·51 + 3·52 + 1·53 = 214


  2. Gegeben sei folgende Syntaxdefinition in Backus-Naur-Form für natürliche Zahlen in Binärdarstellung.

    <Binaerzahl> ::= 0 | <NichtNullDarstellung>
    <NichtNullDarstellung> ::= 1 <Binaerzahl>*


    Welche der folgenden Zeichenreihen sind mit obiger Syntaxdefiniton herleitbar? Begründen Sie Ihre Aussage, indem Sie entweder eine korrekte Herleitung angeben (und dabei keine Schritte überspringen) oder indem Sie begründen warum die Zeichenreihe nicht herleitbar ist.

    • 1010

      <Binaerzahl>
      0| <NichtNullDarstellung>
      1 <Binaerzahl>*
      1 <Binaerzahl><Binaerzahl><Binaerzahl> 1010


    • 200

      Die Ziffer Zwei kommt in der BNF nicht vor.


    • 0111

      Keine führenden nullen ausser bei der Zahl 0


  3. Gegeben seien drei (sechsseitige) Würfel. Aufgabe ist es diese Würfel so auf einen Tisch anzuordnen, dass alle Würfel die selbe Augenzahl zeigen. Dafür werde folgender Algorithmus vorgeschlagen.

    (1) Wirf alle drei Würfel auf einen Tisch
    (2) Falls nicht alle Würfel die selbe Augenzahl zeigen, nimm die Würfel auf     und beginne bei (1)


    Entscheiden Sie, welche der folgenden Eigenschaften der Algorithmus erfüllt. Begründen Sie Ihre Entscheidung kurz.

    • Terminierend

      Die Terminiertheit kann nicht bewiesen oder wiederlegt werden. Der Fall das unendlich oft gewürfelt wird kann auch vorkommen. Daraus folgt, der Algorithmus ist nicht terminierend, auch wenn er es vielleicht in 99% aller Fälle tut.

    • Deterministisch

      Nein, da Wirkung und Reihenfolge der Einzelschritte nicht eindeutig festgelegt ist. Algorithmen heißen deterministisch, wenn zu jedem Zeitpunkt ihrer Ausführung höchstens eine Möglichkeit zur Fortsetzung besteht.

    • Partiell korrekt

      Ja ist partiell korrekt, da es zu keinem Fehler kommen kann. Der Programmcode lässt keine Fehler zu.

    • Korrekt

      Nein, da nicht terminierend.



  4. Gegeben ist folgender Programmcode:

    int i = 1; int j = 5;

    System.out.println( ++i ); // Ausgabe: i = 2

    System.out.println( j-- ); // Ausgabe: j = 5

    System.out.println( i ); // Ausgabe: i = 2

    System.out.println( j ); // Ausgabe: j = 4

    Ergänzen Sie die zu erwartenden Ausgabewerte (Eine Begründung ist nicht nötig).


  5. Gegeben sei folgender Java-Code:

    public static void swap(int[] a,int[] b) {
      int[] tmp = a;
      a = b;
      b = tmp;
      b[0] = 42;
    }


    der Code wird folgendermaßen aufgerufen:

    public static void main(String[] args){
      int[] x = new int[] {0,1};
      int[] y = new int[] {2,3};
      swap(x,y);
      //*)
    }


    Was ist der Inhalt der Variablen x und y nach Ausführung des Codes swap(a,b) an Position //*) der main-Methode? Warum?

    y = {42,1}, x = {2,3} wegen call by value. Bei call by value werden aber Referenzen übergeben, so dass der Inhalt der Arrays sich außerhalb der Methode ändert. 1P call by value, 1P Referenzen übergeben, 1P sonst nix falsch.


  6. Nennen Sie die zwei Möglichkeiten zur Übersetzung von generischen Typen und erklären Sie diese.

    1. Heterogene Übersetzung: Für jede Instantiierung (Stall<Tier>, Stall<Schaf>, Stall<Kuh> etc.) wird individueller Byte-Code erzeugt, also drei unterschiedliche (heterogene) Klassen. (1 Punkt)
    2. Homogene Übersetzung: Für jede parameterisierte Klasse (Stall<T>) wird genau eine Klasse erzeugt, die die generische Typeninformation löscht (type erasure) und die Typ-Parameter durch die Klasse Object ersetzt. Für jeden konkreten Typ werden zusätzliche Typanpassungen in die Anweisung eingebaut. (1 Punkt)


Aufgabe 2: Algorithmen

  1. Implementieren Sie eine statische Methode boolean isQuadratzahl (int zahl) in Java, die den Wahrheitswert true zurückgibt, falls zahl eine Quadratzahl ist. Die Funktion überprüft also das mathematische Prädikat ∃ i ∈ ℕ : i · i = zahl. Sie können annehmen, dass zahl positiv ist.

    public static boolean isQuadratzahl (int zahl){
      for(int i = 1; i <= zahl; i++){
        if(i * i == zahl){
          return true;
        }
      }
      return false;
    }


    Gesamtkorrektheit: 2 Punkte, kleinere Fehler 1 Punkt Abzug.
  2. Implementieren Sie eine statische Methode void invertieren(int[] werte) in Java, die ein Integer-Array als Argument erhält und dieses invertiert. Aus dem Array [0,1,2,3] soll also das Array [3,2,1,0] werden. Beachten Sie, dass die Methode kein Array zurückgeben soll. Sie können davon ausgehen, dass das Array eine Länge von mindestens 1 hat.

    public static void invertieren(int[] werte){
      for(int i = 0; i < (werte.length/2); i++){
        int tmp = werte[i];
        werte[i] = werte[werte.length-i-1];
        werte[werte.length-i-1] = tmp;
      }
    }


    • Kein int[] zurückgegeben: 1 Punkt
    • Es wird nur bis werte.length/2 durchgegangen: 1 Punkt
    • Gesamtkorrektheit: 1 Punkt
  3. Implementieren Sie eine statische Methode int[] interleave(int[] werte1, int[] werte2) in Java die zwei Integer Arrays werte1 und werte2 mit der gleichen Länge so in einem neu erstellten Array einsortiert das abwechselnd je ein Wert aus werte1 und werte2 ins Ergebnisarray einsortiert wird. Fangen Sie den Fall unerlaubter Argumente, also zweier Arrays unterschiedlicher Länge, mit den in der Vorlesung gelernten Techniken ab. Sie können davon ausgehen, dass beide Arrays eine Länge von mindestens 1 haben.

    Beispielsweise werden die Arrays [1,2,3,4] und [5,6,7,8] zu dem Array [1,5,2,6,3,7,4,8] zusammengefügt, das dann als Ergebnisarray zurückgegeben wird.

    public static int[] interleave(int[] werte1, int[] werte2){
      if(werte1.length != werte2.length){
        throw new IllegalArgumentException ("Ungleiche Länge");
      }
      int[] result = new int[werte1.length*2];
      for(int i = 0; i < werte1.length; i++){
        result [2*i] = werte1[i];
        result [2*i+1] = werte2[i];
      }
      return result;
    }


    • 1 Punkt für Längenabfrage + Exception
    • 1 Punkt für Erstellung des Ergebnisarrays mit korrekter Länge
    • 1 Punkt für 2i, 2i+1
    • 1 Punkt Gesamtkorrektheit


Aufgabe 3: Beweis durch vollständige Induktion

Zeigen Sie mit Hilfe der vollständigen Induktion, dass folgende Aussage für alle n ∈ ℕ gilt:

Induktion

Induktionsanfang:
  • Zu zeigen: 12 = ∑1i=1 (2 · i - 1) = 1 ✓
  • 2 Punkte
  • nachdem n ∈ ℕ müssen wir das für 0 nicht zeigen

Induktionsschluss:
Insgesamt 4 Punkte, Punkteabzug je nach schwere der Fehler
Annahme:
Induktion
Zu zeigen: