Info1-Aufgabensammlung

Inhaltsverzeichnis

Noch mehr Aufgaben…???

Dies ist eine Sammlung von Aufgaben, Anregungen usw. die zur Selbstüberprüfung, Unterhaltung, … dienen soll. Einige Aufgaben sind in der einen oder anderen Form von den Übungblättern bekannt, und es sind auch manche alten Klausuraufgaben enthalten. Die thematische Sortierung entspricht dem Skript, es ist aber nicht alles gleichermaßen abgedeckt. Es wird immer wieder mal Ergänzungen geben.

  • Anordnung/Gruppierung/Titel/genauer Text einer Aufgabe (und auch der Link darauf) kann sich ändern, die "I1-ID" und der wesentliche Inhalt wird aber gleich bleiben.
  • Kennzeichnung TODO bedeutet: noch nicht ganz ausformuliert

Vieles ist selbst ausgedacht, vieles ist inspiriert von

und weiteren

Einführung

Was ist Informatik?

Ja, genau: Was ist Informatik? (I1-ID: zlc7wut0m2i0)

Hier der Versuch einer Definition https://gi.de/themen/beitrag/was-ist-informatik/

Haben Informatiker moralische Verpflichtungen? (I1-ID: gkyki3u0m2i0)

Hilfe! (I1-ID: s1z84w711eh0)

Wie informiert man sich am zuverlässigsten über das Shell-Kommando sort auf einem Linux-PC?

  • [ ] F1-Taste drücken
  • [ ] am Konsolenfenster auf "Help" klicken
  • [ ] Wikipedia-Suche nach "Shell sort"
  • [ ] nach "+Shell +sort" googeln
  • [ ] man sort aufrufen

Sortieren nach Punkten (I1-ID: nipe84411eh0)

Informieren Sie sich darüber, was CSV-Dateien sind. Informieren Sie sich auch über das Shell-Kommando sort, insbesondere über keys, field separators, numerische Sortierung und Sortierungsrichtung.

Hier der Anfang der Datei punkte.csv, die Komma-getrennte Angaben zu erreichten Übungspunkten enthält:

21600001,Herr,Bollman,Fritze-Peter,15
21600002,Frau,Bollwoman,Franzi,19
21600003,Herr,Lindemann,Erwin,17
21600004,Frau,Lindefrau,Edelgard Martha,12
21600005,Herr,Machtnix,Mike,2
.....

Welches Shell-Kommando ist geeignet, die Zeilen nach fallender Punktzahl sortiert auszugeben (erst große, dann kleinere Punktzahlen)?

  • [ ] sort --reverse --k 5 --numeric-sort punkte.csv
  • [ ] sort --r --field-separator=, -k 5 --n punkte.csv
  • [ ] sort -r -t="," -k 5 --n punkte.csv
  • [ ] sort --reverse -t "," -k 5 -n punkte.csv
  • [ ] sort -r --field-separator "," -k 4 -numeric punkte.csv
  • [ ] sort -r --field-separator "," -k 4 punkte.csv

csv zum selber machen (I1-ID: tgcdlj40bii0)

Informieren Sie sich über das Kommando wget.

Führen Sie das folgende an einem der Linux-Rechner im Institut aus:

  1. Legen Sie das Verzeichnis ~/tmp/ an und wechseln dorthin.
  2. Kopieren Sie mittels wget die Dateien https://www.stud.informatik.uni-goettingen.de/info1/data/Dienstlich und https://www.stud.informatik.uni-goettingen.de/info1/data/Privat in dieses Verzeichnis.
  3. Legen Sie durch ein (mittels Pipe kombiniertes Kommando) eine Datei alle.csv an, die zeilenweise all diese Telefondaten Komma-getrennt enthält, und zwar jeden Eintrag nur einmal.
  4. Rufen Sie dann libreoffice alle.csv auf, nehmen die nötigen Einstellungen vor und freuen sich über das Ergebnis.
  5. Überlegen Sie, wie Sie solche Techniken auch bei anderen Gelegenheiten zeitsparend einsetzen können.

Mehr Spaß mit der Kommandozeile (I1-ID: whl0hf50bii0)

Problem, Algorithmus, Programm, Prozess

Gute Spezifikationen, schlechte Spezifikationen (I1-ID: aqo3pz60tmg0)

Es sollen vier Karten sortiert werden. Es dürfen Vergleiche und Vertauschungen benutzt werden. Der Algorithmus soll optimal sein.

  1. Welche Mängel hat diese Spezifikation?
  2. Geben Sie eine bessere an.

Test yourself! (I1-ID: pqokgde0u2i0)

Der euklidische Algorithmus ist so ein Klassiker - es kann wirklich nicht schaden, die wesentlichen Codezeilen (besser noch, den vollständigen Quelltext) jederzeit aus dem Gedächtnis kramen zu können. Können Sie das?

Euklid wird verfolgt (I1-ID: 935dgrq0m2i0)

Wie verarbeitet der euklidische Algorthmus die Startwerte, wenn die Reihenfolge vertauscht ist (also z.B. \(a=12, b=30\)) oder einer/beide Werte negativ sind? Stellen Sie das Ablauf-Protokoll auf.

Volle Konzentration (I1-ID: rpti3ik0mng0)

Betrachten Sie dieses Codefragment …

 1: int n = 7, k = -2; 
 2: int i = 0;
 3: while ( n!=1 && i<3 ) {
 4:     i++;
 5:     if ( n%2 == 0 )
 6:         n /= 2;
 7:     else n = (2*k+1)*n+1;
 8:     k--;
 9: }
10: System.out.println(i);

… und ergänzen Sie die Trace-Tabelle:

Zeile n k i
1 7 -2 -
2 7 -2 0
4 7 -2 1
  -20 -2 1
8   -3 1
  -20 -3 2
    -3 2
8   -4 2
4 -10 -4 3
6   -4 3
8 -5   3

Die Gaußsche Osterformel (I1-ID: plj0j5v0xhi0)

Das Osterdatum ist der erste Sonntag nach dem ersten Vollmond im Frühling. Ganz schön knifflig, aber Old Gauß hat die Frage geklärt. Hier die prosaische Beschreibung in lesbarer Form.

    I. Man dividire die Zahl des Jahres, für welches
man Ostern berechnen will, mit 19, mit 4 und mit
7, und nenne die Reste aus diesen Divisionen, re-
spective a, b und c. Geht die Division auf, so setzt
man den zugehörigen Rest = 0; auf die Quotienten
wird gar keine Rücksicht genommen. Eben das gilt
von den folgenden Divisionen.
    II. Man dividire ferner 19 a + 23 mit 30, und
nenne den Rest d.
    III. Endlich dividire man 2 b + 4c + 6d + 3,
oder 2 b + 4c + 6d + 4, je nachdem das vorgege-
bene Jahr zwischen 1700 und 1799, oder zwischen
1800 und 1899 inclus. liegt, mit 7, und nenne den
Rest e.
    Alsdann fällt Ostern auf den 22 + d + e-ten
März, oder wenn d + e größer als 9 ist, auf den
d + e - 9 April.

Aufgabe: Man formuliere die Osterformel

  1. als Flussdiagramm und
  2. als rudimentären Java-Code

Ringelpietz (I1-ID: svc2vpe0u2i0)

Bekanntlich sorgt nachfolgender Code dafür, dass die in a und b gespeicherten Werte getauscht werden (d.h., was vorher in a gespeichert war, steht jetzt in b und umgekehrt):

tmp = a; 
a = b;   
b = tmp;

Geben Sie ein paar Zeilen an, mit denen man VIER Werte zyklisch tauschen kann (d.h. von a nach b, b nach c, c nach d und d nach a).

It's magic! (I1-ID: jzg81nm0u2i0)

1:    int x = a, y = b;
2:    x = x + y;
3:    y = x - y;
4:    x = x - y;

Zeigen Sie mittels Trace-Tabelle, dass x und y nach Ausführung des Codes ihre Werte getauscht haben - ohne Hilfsvariable zum Zwischenspeichern!!

HelloHipster (I1-ID: lr7irwe0u2i0)

  1. Verändern Sie HelloWorld.java so, dass der Text mit Sprechblase erscheint, z.B. so

     ______________
    /              \
    | Hello, world! \
    \________________\
    
  2. Verändern Sie HelloUser.java ebenso, z.B. java HelloUser Zacharias und java HelloUser Bob erzeugen diese Ausgaben:

     _________________          ___________
    /                 \        /           \
    | Hello Zacharias! \       | Hello Bob! \
    \___________________\      \_____________\
    

    Sie brauchen also:

    • die Länge des Aufrufarguments: args[0].length() und
    • eine Möglichkeit, je nach Situation soundsoviele Zeichen auszugeben: dafür ist die for-Schleife geeignet (ziemlich am Ende von Skript-Kapitel 1 erklärt)
    • Kenntnis des Unterschieds zwischen System.out.print(...) und System.out.println(...).

TODO Ein einfacher Editor (I1-ID: z0yb4hj0dzg0)

Dies ist mit ILIAS zu lösen. Aufgabe wird noch vorbereitet.

Schreiben Sie aus dem Gedächtnis den Euklidischen Algorithmus als Java-Programm mit dem ILIAS-Quelltexteditor (Aha, darum also die Aufgabe pqokgde0u2i0!).

Den Compiler verstehen lernen (I1-ID: 6vkgy3p0m2i0)

Beschreiben Sie, was beim Compilieren und ggf. Ausführen passiert, wenn Sie einzelne der folgenden Wörter in HelloWorld.java auslassen oder falsch schreiben:

  • public
  • static
  • void
  • args

Laden und Starten eines Programms (I1-ID: 7xy39up0m2i0)

Beschreiben Sie, was passiert, wenn Sie versuchen HelloUser mit diesen Befehlszeilen auszuführen:

  • java HelloUser java
  • java HelloUser @!&^%
  • java HelloUser
  • java HelloUser.java Erwin
  • java HelloUser Erwin Lindemann
  • wie eben, aber Erwin Lindemann in doppelten/in einfachen Anführungszeichen.

Tuning (I1-ID: jrhjaye0tmg0)

Der fiktive Assemblercode aus dem Skript (ungefähr Seite 16) ist nicht optimal, denn Befehl 3 wird bei jeder Iteration ausgeführt. Spielen Sie "optimierender Compiler" indem Sie den Code in dieser Hinsicht verbessern.

Programmier-Alltag (I1-ID: gadc3kl0mng0)

Ordnen Sie die folgenden Begriffe zeitlich:

  • Zielcode
  • Quelltext
  • Spezifikation
  • Algorithmus
  • Compiler
  • Editor
  • Testen
  • Lösungsidee

Prozesse und Prozessoren MC (I1-ID: dc46f8c0tmg0)

Kreuzen Sie Zutreffendes an:

  • [ ] Korrekte Algorithmen terminieren.
  • [ ] Der Prozessor speichert den Quellcode im Befehlssatz.
  • [ ] Binärprogramme erhöhen den Befehlszähler in Einerschritten.
  • [ ] Die von-Neumann-Architektur beinhaltet ein Bus-System.
  • [ ] Moderner Assemblercode ist portabel.
  • [ ] Editieren und Testen gehören zu jedem Programmentwicklungszyklus.
  • [ ] Mittels Tracing kann man analysieren wie ein Programm abläuft.
  • [ ] Iterative Algorithmen haben diesen Aufbau: Iteriere - Initialisiere - Terminiere.

Wie kommen die Daten ins Programm? (I1-ID: 8243gry0nng0)

Im aktuellen Shell-Verzeichnis befinden sich die im Skript erwähnte Datei StdIn.class, sowie die Datei Daten.java mit diesem Quelltext:

 public class Daten {
     public static void main(String[] args) {
         int x; 
         if (Integer.parseInt(args[0]) > 0) {
             x = StdIn.readInt();
             System.out.println(x+1);
         } else
             System.out.println("Error");
     }
 }

Was passiert in dieser Situation, wenn in der Shell folgende Kommandos hintereinander ausgeführt werden?:

javac Daten.java
echo 2 | java Daten 1      
  • [ ] Shell meldet … command not found
  • [ ] Shell meldet … file not found
  • [ ] Compilezeitfehler
  • [ ] Laufzeitfehler
  • [ ] logischer Fehler
  • [ ] Textausgabe: 2
  • [ ] Textausgabe: 3
  • [ ] Textausgabe: Error

Code-Steinbruch benutzen (I1-ID: okihjen0u2i0)

  • beschaffen Sie sich den Quelltext Temperatur.java
  • compilieren Sie
  • Wenn dies nicht gelingt, so lesen Sie nochmals die entsprechende Passage im Skript durch und beheben den Fehler
  • Testen Sie die Applikation an einigen Beispielen
  • Benutzen Sie den Quelltext als Code-Steinbruch und programmieren und testen eine Applikation zur Währungsumrechnung (z.B. Dollar in Euro).

Oche (I1-ID: orr68kq0m2i0)

Modifizieren Sie Echo.java so, dass die Argumente in umgekehrter Reihenfolge ausgegeben werden: java Oche 1 2 3 sollte also die Textausgabe 3 2 1 erzeugen.

Java-Kurzeinführung

Spaß mit Kommentaren 1 (I1-ID: cgpjm1s0m2i0)

Siehe https://introcs.cs.princeton.edu/java/11style/

Welchen Wert hat a nach Ausführung des folgenden Codefragments? Erklären Sie, was passiert. Was passiert, wenn das erste Zeichen / entfernt wird?

//*/
a = 17;
/*/
a = -17;
//*/

Spaß mit Kommentaren 2 (I1-ID: sr9g62s0m2i0)

Siehe https://introcs.cs.princeton.edu/java/11style/

Was wird ausgegeben und warum?

public static void main(String[] args) { 
   boolean nesting = true;
   /* /* */ nesting = false; // */ 
   System.out.println(nesting);
}

Spaß mit Ausdrücken (I1-ID: 9rfji1a1n2i0)

+= ist der zusammengesetzte Additionsoperator, eine Verallgemeinerung von ++:

a += b; // der aktuelle Wert von b wird zu a addiert
  1. Ist dieses Code-Fragment erlaubt?

    int x = 1;
    x += ++x+x++;
    System.out.println(x);
    

    Antwort: Der Compiler übersetzt so etwas klaglos, aber wir erlauben solchen Code (und andere demonstrativ verworrene Codezeilen) nicht als Teil einer korrekten Lösung.

    Prüfen Sie das Ergebnis durch Ausprobieren und erklären Sie das Ergebnis.

  2. Erlaubt der Compiler auch dieses Code-Fragment? Begründen Sie die Antwort.

    int x = 1;
    x += (++x+x)++;
    System.out.println(x);
    

for-schachtelt (I1-ID: dskia2l0lji0)

for (int i = 1; i<3; i++) 
    for (int j = 0; j<i ; j++) 
        System.out.print(i+j);
System.out.println();

Welche Ausgabe wird erzeugt?

  • [ ] 122
  • [ ] 123
  • [ ] 135
  • [ ] 233

tie- for-gelegt (I1-ID: 595098l0lji0)

for (int i = 3; i>1; i--) 
    for (int j = i; j>0 ; j--) 
        System.out.print(i+j);
System.out.println();

Welche Ausgabe wird erzeugt?

  • [ ] 65543
  • [ ] 65432
  • [ ] 65443
  • [ ] 54321

FizzBuzz (I1-ID: jcr9ju61d4i0)

Schreiben Sie ein Programm, das die Zahlen von 1 bis 100 zeilenweise wie folgt als Text ausgibt: Ist die Zahl durch 3 teilbar, so wird stattdessen "Fizz" ausgegeben, ist sie durch 5 teilbar, so wird "Buzz" ausgegeben, ist sie jedoch durch 3 und durch 5 teilbar, so wird "FizzBuzz" ausgegeben.

siehe: http://www.codinghorror.com/blog/2007/02/why-cant-programmers-program.html

Hinweis: Hierzu braucht man keine logischen Operatoren (die werden ja erst in Abschnitt 2.1.3 besprochen).

Debugging (I1-ID: irkj24p03og0)

Die Summe der Zahlen 1 bis 9 soll berechnet werden. Der folgende Fragment dazu ist so umständlich entworfen, dass die fehlerhafte Zeile darin übersehen wurde:

 1: boolean zehn = false;
 2: int i = 0, s = 0;
 3: while ( i <= 10 && !zehn) {
 4:     if ( zehn = false) 
 5:         s = s + i;
 6:     i++; 
 7:     if ( i == 10)
 8:         zehn = true;
 9: }
10: System.out.println("Summe: " + s);
  • Welche Zeile ist fehlerhaft?
  • Um welche Art Fehler handelt es sich: Compilezeit-, Laufzeit- oder logischer Fehler?
  • Wenn dieser Fehler korrigiert wird, welche Ausgabe liefert dann die letzte Zeile?

Grundlegende Datentypen und Algorithmen

Information, Daten und Datentypen

Bytesalat (I1-ID: 6bq875g0u2i0)

  • Legen Sie mit einem Editor eine Datei an, in der Sie lediglich auf einer einzelnen Zeile 10 beliebige ASCII-Zeichen speichern. Das Kommando ls -l meldet 11 Bytes in der Datei. Warum?
  • Schreiben Sie nun einige Umlaute in die Datei und speichern erneut. Entspricht das ls -l-Ergebnis Ihren Erwartungen?

Internet-Adressen (TI-ID: jsk8osn0u2i0)

Erkundigen Sie sich grob über IPv4 und IPv6 und vergleichen Sie die Größe der Adressräume (ohne reservierte Adressen) mit der Anzahl der Menschen auf der Erde, Quadratmeter der Erdoberfläche, geschätzte Anzahl der Smartphones und anderer Endgeräte, …

verHEXt (I1-ID: 9xh9c881vmg0)

  1. In HTML-Code sind sogenannte "Hex-Tripletts" zur Angabe von Farben erlaubt: #xxxxxx, wobei jedes x für eine beliebige Hexadezimalziffer steht. Damit lassen sich \(2^n\) verschiedene Farben angeben. Wie groß ist \(n\)?
  2. Die CSS-Spezifikation erlaubt die Angabe von Farben in der abgekürzten Notation #xxx, wobei jedes x für eine beliebige Hexadezimalziffer steht. Wieviele Farben lassen sich damit angeben?
  3. Wieviele Hexziffen wären nötig, um 2 Milliarden verschiedene Farben angeben zu können?

HelloWorld mal anders (I1-ID: fyp7mdk0u2i0)

Die Klasse HelloWorld soll jetzt

Hallo Leute, wie geht's?

(exakt in dieser Form) zur Ausgabe bringen. Wie lautet der entsprechende System.out.println-Aufruf?

Tipp: erkundigen Sie sich, was "Escape-Sequenzen" sind.

Schöner Ausgeben (I1-ID: 2nicmqr0c4i0)

Schreiben Sie

  • unter ausschließlicher Verwendung von ASCII-Zeichen und
  • nur einem einzigen System.out.println-Aufruf

eine Java-Applikation, die folgende zweizeilige Textausgabe erzeugt:

Benjamin Blümchen:    "Töröööh!"
Karla Kolumna:        "Sie haben aber große Füße!"

Ihr Quellcode soll

  • keine Zeilen mit mehr als 80 Zeichen und enthalten und
  • gut lesbar sein (saubere Einrückungsstruktur!).

Tipp zur Einstimmung: Ersetzen Sie mal in HelloWorld.java das String-Literal durch ''Hello'' + ''World!''.

Steuerungsverlust (I1-ID: d6yk1od1z4i0)

Welche Ausgabe erzeugt

System.out.println("Li\rRecht\b\b\bnks");  

und warum?

Countdown (I1-ID: 9ghh22i02ki0)

Probieren Sie das mal aus und erklären was passiert:

for (int i = 100000; i > 0; i--) {
    System.out.printf("\b\b\b\b\b\b\b\b\b\b%10d",i);
}
System.out.println();

(Zu printf siehe Paragraph 3.1-11 im Skript).

Zeichen deuten (I1-ID: ruh2rtd1tng0)

Kreuzen Sie alles Zutreffende an:

  • [ ] Das Leerzeichen ist ein druckbares Zeichen.
  • [ ] Der Befehlszähler wird durch Steuerzeichen gesetzt.
  • [ ] Unicode umfasst insgesamt \(2^{16}\) Zeichen.
  • [ ] iso8859-1 ist keine Teilmenge von ASCII
  • [ ] 'C'++ liefert das gleiche Ergebnis wie 'C'+1.
  • [ ] ''C'' + 1 ist kein erlaubter Java-Ausdruck .
  • [ ] Microsoft-Office enthält auch den Editor Word.
  • [ ] Der Java-Compiler verarbeitet auch Nicht-ASCII-Zeichen.

Prinzip der Informationsverarbeitung (I1-ID: rn6hg3e1tng0)

Das Wort Decodierung kann einen Vorgang oder das Ergebnis eines Vorgangs bezeichnen. Beispiele:

  • Das erfordert eine Decodierung (Vorgang)
  • Die Decodierung überraschte alle Anwesenden (Ergebnis).

Welche der folgenden Wörter/Wortgruppen, sind im Zusammenhang mit Informationsverarbeitung synonym zu Decodierung (Vorgang bzw. Ergebnis) oder decodieren:

Abstraktion, Inhalt, beschreiben, Sinn, nennen, Repräsentation, markieren, Durchführung, Ausgabe, verstehen, Syntax, Bedeutung, verarbeiten, Interpretation, operieren, Anwendung, Eingabe, Semantik, beleuchten, auswerten, liefern, Nachricht

Polynomauswertung mit Horner-Schema (I1-ID: 442a09r0c4i0)

Ein Polynom ist ein Ausdruck \(p(x)\) der Form \(a_{N-1}\cdot x^{N-1}+...+a_1\cdot x+a_0\), wobei die \(a_i\) Zahlen sind (die Koeffizienten, \(a_{N-1}\) ist der Leitkoeffizient) und \(x\) eine unbestimmte Größe. Auswertung des Polynoms an einer Stelle \(x_0\) bedeutet, die Zahl \(x_0\) anstelle von \(x\) einzusetzen und den Wert \(p(x_0)\) des Ausdrucks zu bestimmen.

Modifizieren Sie das Horner-Schema aus der Vorlesung zu einem Algorithmus für die Polynomauswertung. Formulieren Sie den Algorithmus in strukturierter Prosa (initialisiere … iteriere … terminiere …).

Das kommt mir römisch vor! (I1-ID: i7948gk0u2i0)

Lesen Sie den Wikipedia-Artikel zur Römischen Zahlschrift und insbesondere den Abschnitt zur Umrechnung

Formulieren Sie diese Umrechnungsvorschrift möglichst präzise durch Pseudocode (siehe Abschnitt 1.2 im Skript). Wenn Sie wollen, machen Sie das Gleiche für die Subtraktionsregel.

EOL (I1-ID: fhlane81v2i0)

Erzeugen Sie auf einem Windows-PC mittels notepad.exe eine Datei, die 10 mal den Satz

Ich will immer daran denken, dass das Zeilenende irgendwie gespeichert werden muss.

enthält (also 10 Zeilen). Eine gute Gelegenheit, Tastaturkürzel für Kopieren und Einfügen zu üben …

Dann transferieren Sie die Datei geeignet auf einen Linux-Rechner und öffnen die Datei mittels gedit. Wie sehen die Zeilenenden aus?

Dann das Ganze nochmal umgekehrt, dabei nicht die gleiche Datei verwenden, sondern alles neu anlegen. Wie sehen diesmal die Zeilenenden aus? Erklären Sie!

Zum Nachschlagen (I1-ID: nin33tb1v2i0)

Da muss man dabei gewesen sein! (I1-ID: nqx18v71v2i0)

Joel Spolsky: The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets (No Excuses!) (zuletzt abgerufen: [2018-08-30 Do])

Joel Spolsky ist der Mitbegründer von Stack Overflow - und der muss es schließlich wissen.

NaNu (I1-ID: 8e0b7ja0rhi0)

Dass man nicht durch 0 dividieren sollte ist klar. Aber wie geht java damit um? Lassen Sie 1/0, 1/0.0 und 0./0. berechnen und erklären Sie, was passiert.

Probieren Sie weitere Kombinationen aus und achten Sie darauf in welchen Fällen Laufzeitfehler passieren und in welchen lediglich Informationsverlusst auftreten kann.

Programmieren mit integrierten Datentypen

Vergleiche einsparen (I1-ID: 1uy278z0m2i0)

In Ordne.java werden 12 Vergleiche benutzt, um drei Zahlen zu ordnen. Es geht jedoch auch mit weniger:

Ordnung2.png

Programmieren Sie dies nach, d.h. Ihr Quellcode sollte nur noch 5 Vergleichsausdrücke enthalten.

Intervalltraining (I1-ID: uje57770tmg0)

Das Intervall \([x,y]\) besteht aus allen Zahlen \(z\) für die \(x\le z\le y\) gilt. \(x < y\) bedeutet auf dem Zahlenstrahl: Punkt \(x\) liegt links von Punkt \(y\). Ein leeres Intervall ist in jedem anderen Intervall enthalten.

Hier eine Reihe von Ausdrücken, die Informationen zu Intervallen \([a,b], [c,d]\) beschreiben:

  • [ ] !(a < b || c > d) && !( d < c)
  • [ ] (!(a < b) || c > d) && (a != b)
  • [ ] !(!(a >= b || c >= d) && (b < c))
  • [ ] ((a >= b || c >= d) || (b >= c))
  • [ ] !( a > b || c > d) && (b <= c)
  • [ ] (a >= c && b <= d) || !(b >= a)
  • [ ] (a <= b && c <= d) && !(c > b && a > d)
  • [ ] (a <= d && c <= b) && !(c > b && a > d)

Unten ein Programm, das interaktiv Grenzen von Intervallen einliest und dann Informationen dazu ausgibt.

Aufgabe: Im Mittelteil die richtigen Ausdrücke aus den obenstehenden auswählen, so dass die Beziehungen richtig widergespiegelt werden:

public class Intervalltraining {
    public static void main(String[] args) {
        double a, b, c, d;
        System.out.println("Bitte die Intervallgrenzen eingeben!");
        System.out.print("a = "); a = StdIn.readDouble();
        System.out.print("b = "); b = StdIn.readDouble();
        System.out.print("c = "); c = StdIn.readDouble();
        System.out.print("d = "); d = StdIn.readDouble();
        
        // waehlen Sie die passenden Ausdruecke aus:
        boolean bedingung1 =                            ; 
        boolean bedingung2 =                            ;
        boolean bedingung3 =                            ;
        boolean bedingung4 =                            ;

        if (bedingung1)
            System.out.println("Eines der Intervalle ist leer."); 
        if (bedingung2)
            System.out.println("[a,b] ist in [c,d] enthalten.");
        if (bedingung3)
            System.out.println("[a,b] und [c,d] haben gemeinsame Punkte.");
        if (bedingung4)
            System.out.println("[a,b] liegt links von [c,d] (beide nichtleer)");
    }
}

Eigenbau-Zeichentabelle (I1-ID: 3yacsp61m2i0)

java/Zeichentabelle.java

in Vorlesung erst ohne Kdozeilenparameter, dann mit vorführen:

  • 0 127 => ASCII
  • 0 - 255 => isolatin1
  • 0 - 65634 => Unicode
  • 0 - 65634 => Unicode aber mit Endlosschleife!

Quelltext-Kommentar enthält entsprechende Übungsanregung, unten ausformuliert als Aufgabe

Ziel: eine nummerierte Liste aller ASCII-Zeichenwerte und zugehörigen Zeichen (jedoch bei Steuerzeichen nur ein Hinweis)

Ausbaustufe: Bei Aufrufparametern \(a\), \(b\) nur die Zeichenwerte \(\in[a,b]\) behandeln — bei Bedarf auch Zeichen jenseits des ASCII-Bereichs.

  • Eine (noch fehlerhafte) Lösung
    public class Zeichentabelle {
      public static void main  (String[] args) {
        char start = (char) 0, stop = (char) 127;
        if ( args.length == 2) {
            start = (char) Integer.parseInt(args[0]);
            stop = (char) Integer.parseInt(args[1]);
        }
        for (char c = start; c <= stop; c++){// ...
          System.out.print((int) c + " : "); // Zeichenwert (Ordnungszahl)
          if (Character.isISOControl( c)) 
            System.out.println("Steuerzeichen");
          else 
            System.out.println( c);          // das zugehoerige Zeichen
        }
      }
    }
    /* dieser Quelltext enthaelt einen (absichtlichen) logischen Fehler: 
       Bei Aufruf 'java Zeichentabelle 0 65635' entsteht eine Endlosschleife.  
       - Warum?
       - Korrigieren Sie den Fehler! */    
    /* Um die Zeichen auf der Konsole richtig darzustellen, muss
       mindestens deren Zeichencodierung auf UTF-8 gesetzt werden
       (einstellbar ueber das Fenstermenue). */
    

char-Merkwürdigkeiten (I1-ID: 8w1aucc1tng0)

In folgendem Quelltext gibt es mindestens eine Zeile, die der Compiler nicht akzeptiert. Streichen Sie alle betroffenen Zeilen. Welche Textausgaben erzeugen dann die verbleibenden Zeilen?

1: char c = 'a';  System.out.println(c); 
2: c = c+1; System.out.println(c);             
3: System.out.println('c'+1);                  
4: System.out.println((char)('c'+1));

Umlaute (I1-ID: dgv4c791n2i0)

Schreiben Sie nur unter Verwendung von ASCII-Zeichen ein Java-Programm, dass die Textausgabe ÄÖÜß erzeugt.

Nur Sterne sehen (I1-ID: cgu8rno0kyg0)

Das folgende Programm(fragment) erzeugt Ausgabezeilen mit Sternen (*):

public class Sterne { 
    public static void main(String[] args) { 
        String stern1 =          "*";          System.out.println(stern1);
        String stern2 = stern1 + "*" + stern1; System.out.println(stern2);
        String stern3 = stern2 + "*" + stern2; System.out.println(stern3);
        String stern4 = stern3 + "*" + stern3; System.out.println(stern4);
        String stern5 = stern4 + "*" + stern4; System.out.println(stern5);
        // usw.
    }
}

Wieviele Sterne enthält die \(n\)-te Ausgabezeile?

  • [ ] \(n\)
  • [ ] \(2^n-1\)
  • [ ] \(2^n\)
  • [ ] \(2\cdot n+1\)

int-Merkwürdigkeiten (I1-ID: v9uftru00og0)

Welche Textausgaben liefert folgendes Fragment?

int x = Integer.MAX_VALUE;  //  2147483647
int y = Integer.MIN_VALUE;  // -2147483648

System.out.println( x + y); 
System.out.println(-x + y); 
System.out.println( x + 1); 
System.out.println( 4 * y);

0-Falle (I1-ID: 3pyjg14136i0)

Was erzeugt folgende Programmfragment?

while (true)
    System.out.println(0815);
  • [ ] eine Ausgabe
  • [ ] einen Compilezeitfehler
  • [ ] eine Endlosschleife
  • [ ] einen Programmabbruch

Begründen Sie Ihre Antwort.

Zeichen, Wörter und Zeilen zählen (I1-ID: wtda5ss0m2i0)

Das Shell-Kommando wc (word count) gibt zu einer im Argument angegebenen Datei aus, wieviele Zeichen, Wörter und Zeilen enthalten sind. Programmieren Sie das mit Java für die Standardeingabe nach, d.h.

java Wc < datei

soll die gleiche Ausgabe liefern wie

wc datei

Hinweise:

  • Ein Wort ist eine beliebige Folge von Nicht-Whitespace-Zeichen, die durch Datei-Anfang bzw. Whitespace-Zeichen begrenzt wird.
  • Eine Zeile ist eine beliebige Folge von Nicht-Newline-Zeichen, die durch Datei-Anfang bzw. Newline-Zeichen begrenzt wird.
  • Benutzen Sie drei Zähler chars, word, lines: der erste wird bei jedem Lesen eines Zeichens (mittels StdIn.readChar()) aktualisiet, der zweite wenn ein Whitespace angetroffen wird, der dritte nur bei Newlines.

Wir setzen voraus, dass das letzte zeichen in der Datei ein Newline-Zeichen ist.

Zitierwut (q6wevb11x4i0)

Lesen Sie nach, was der H-Index ist und schreiben Sie ein Program, das ihn aus fallend geordneten Zitierhäufigkeiten berechnet, die als Kommandozeilenargumente übergeben werden.

extern-intern-Umwandlung (I1-ID: puo7o391fzg0)

Überprüfen Sie durch ein kleines, selbt ausgedachtes Beispielprogramm, ob boolean Boolean.parseBoolean(String) Groß-/Kleinschreibung des Arguments berücksichtigt. Wird anstelle ``true'' auch so etwas wie ``yes'' akzeptiert? Was passiert bei Eingaben wie ``776&ä#1''?

Es kommt, wie es kommen muss … (I1-ID: e2t5dsk0u2i0)

Programmieren Sie Ihre Umrechnungsvorschrift(en) aus Aufgabe i7948gk0u2i0 in Java. Hilfreich ist dabei die Routine StdIn.readChar() zum Einlesen einzelner Zeichen, hier ein Verwendungsbeispiel.

Alles in Ordnung? (I1-ID: j2829291fzg0)

Schreiben Sie eine Applikation, die beliebig viele \texttt{int}-Werte \(z_1, z_2, ..., z_n\) einliest und feststellt, ob diese aufsteigend geordnet sind, d.h. ob \(z_1\le z_2\le ... \le z_n\)

Dreieckszahlen (I1-ID: 49fe8ax0m2i0)

Wikipedia: Eine Dreieckszahl ist eine Zahl, die der Summe aller Zahlen von 1 bis zu einer Obergrenze \(n\) entspricht.

Lösen Sie mit Java folgendes Problem:

Eingabe
natürliche Zahl \(n\)
Ausgabe
Komma-getrennt die aufsteigend geordnete Liste aller natürlichen Zahlen \(\le n\), die Dreieckszahlen sind.
Beispiele
  • Eingabe: 17, Ausgabe: 0, 1, 3, 6, 10, 15
  • Eingabe: -2, keine Ausgabe

Nonsquares (I1-ID: 94j6max0m2i0)

Lösen Sie mit Java folgendes Problem:

Eingabe
natürliche Zahl \(n\)
Ausgabe
Komma-getrennt die aufsteigend geordnete Liste aller positiven natürlichen Zahlen \(\le n\), die keine Quadratzahlen sind.
Beispiele
  • Eingabe: 17, Ausgabe: 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17
  • Eingabe: -2, keine Ausgabe

Nonpowersoftwo (I1-ID: 9dz969x0m2i0)

Lösen Sie mit Java folgendes Problem:

Eingabe
natürliche Zahl \(n\)
Ausgabe
Komma-getrennt die aufsteigend geordnete Liste aller positiven natürlichen Zahlen \(\le n\), die keine Zweierpotenzen sind.
Beispiele
  • Eingabe: 17, Ausgabe: 3, 5, 6, 7, 9, 10, 11, 12, 13,
  • Eingabe: -2, keine Ausgabe

Faustformeln (I1-ID: z4fjo8x0m2i0)

Siehe https://www.johndcook.com/blog/2009/07/01/three-rules-of-thumb/

Berechnen Sie jeweils die relative Genauigkeit:

  • Duff's Regel

    \(pi\) Sekunden sind ein Nanojahrhundert.

    Abgewandelte Form: Ein Jahr besteht aus ungefähr 30 Megasekunden.

  • Hopper's Regel

    In einer Nanosekunde legt Licht einen Fuß zurück.
    (Vakuumlichtgeschwindigkeit: 299 792 458 m/s, 1 Fuß = 30.48 cm)

  • 72er Regel

    Ein mit \(n\%\) p.a. verzinstes Guthaben verdoppelt sich in ungefähr \(72/n\) Jahren.

    Wie groß ist der Fehler z.B. bei 6% Verzinsung?

Das 163er Phänomen (I1-ID: ls20b9112xh0)

Alexander Aitken (1895-1967) hat entdeckt, dass

\(e^{\pi\sqrt{163}} = 262537412640768743.9999999999992...\)

double-Genauigkeit ist leider nur ausreichend, um etwas Einfacheres (aber ebenso Verblüffendes) nachzuweisen. Nämlich:

Der Wert \(e^{\pi\sqrt{163}/3}\) ist auch "fast ganzzahlig".

  • Lösung
     1:    double x = Math.PI*Math.sqrt(163)/3;
     2:    System.out.println( Math.exp(x)); // naive Rechnung
     3:    // zu Fuss:
     4:    // double sum = 1.0, term = 1.0;
     5:    // for (int i = 1; term != 0.0; i++) {
     6:    //     term *= x/i;
     7:    //     sum += term;
     8:    // }
     9:    // System.out.println( sum);
    10: 
    11:    // // bestimme nur fraktionalen Anteil
    12:    double frac = 0.0, term = 1.0;
    13:    for (int i = 1; frac != frac + term; i++) {
    14:        term *= (x/i) % 1;
    15:        term %= 1;
    16:        frac += term;
    17:        frac %= 1;
    18:    }
    19:    System.out.println( frac);
    
    cd java/ls20b9112xh0
    javac Programm.java; java Programm
    

Ein Fünftel (I1-ID: maucghl0u2i0)

Die dezimale Gleitkommazahl 0.2 ist gleich dem unendlichen periodischen Dualbruch \((0.\overline{0011})_{2}.\)

Das ist auch leicht zu überprüfen durch Nachrechnen von Hand (machen Sie das mal, siehe Paragraph 2.2-23 im Skript).

Überprüfen mit Hilfe von DualFraction führt jedoch nur zu endlich vielen Dualziffern. Warum?

Pi hexadezimal (T1-ID: 0q7lsex0m2i0)

Überprüfen Sie die ersten paar hexadezimalen Nachkommastellen von \[\pi = (3,243F6A8885A308D313198A2E03707344A4093822299F31D00...)_{16}.\]

Hinweis: Sie benötigen dafür NICHT die berühmte BBP-Formel, sondern nur DualFraction.java als Codesteinbruch für ein neues Programm HexadecimalFraction.java in dem die Schleife anzupassen ist, damit es die Hexadezimal- anstelle der Dual-Bruchentwicklung berechnet.

Was hat Newton denn damit zu tun? (I1-ID: kg1h3nb0b4i0)

Das Newton-Verfahren ist ein Verfahren, das immer bessere Approximationen \(x_{0}, x_{1}, ..., x_{n}\) einer Nullstelle \(x_{\ast}\) der reellwertigen Funktion \(f\) liefert: Ist \(x_{n}\ne x_{\ast}\approx x_{\ast}\), so wird zunächst die Tangente an den Funktionsgraphen an der Stelle \(x_{n}\) betrachtet. Ist \(x_{n}\) genügend "dicht" an \(x_{\ast}\), so wird \(x_{n+1}\) als Schnittpunkt der Tangente an die Funktionskurve im Punkt \(x_{n}\) bestimmt und dieser Punkt ist "noch dichter" dran. Diese Tangente ist die Gerade durch den Punkt \((x_{n},f(x_{n}))\) mit Anstieg \(f'(x_n)\) (\(f'\) ist die Ableitung von \(f\) - damit das klappt muss \(f\) also differenzierbar sein.)

Hier eine Animation dazu (siehe https://de.wikipedia.org/wiki/Newton-Verfahren).

Aufgabe: Überlegen Sie, dass bei dem Verfahren aus der Vorlesung ("immer quadratischere Rechtecke") genau das Gleiche passiert. Aber für welche Funktion?

Kubikwurzel mit Newton (I1-ID: zfhe6v31v2i0)

Die Kubikwurzel von x soll berechnet werden. Leider haben wir gerade vergessen, dass die Funktion Math.cbrt(x) genau das leistet. Aber wir können ja die Idee zur Berechnung von Quadratwurzeln auf diese Situation verallgemeinern. Schreiben Sie also ein kleines Java-Programm dazu und testen es ausgiebig.

Winkelfunktionen zu Fuß programmieren (I1-ID: yea9wrf0tmg0)

Nutzen Sie folgende Reihendarstellungen, um analog zum Beispiel der Exponentialfunktion (siehe Skript Abschnitt 2.2) die Berechnung von Sinus und Kosinus in Java zu berechnen, ohne die Bibliothek Math zu benutzen:

\(\sin x = x - x^3/3! + x^5/5! - ...\)

\(\cos x = 1 - x^2/2! + x^4/4! - ...\).

Bedächtig kommt dahergeschritten … (I1-ID: dxc8pe31v2i0)

… vier Drittel Pi mal r zur Dritten.

Gegeben das Volumen einer Kugel, wie ist der Radius? Wir haben gerade keine Lust auf Newton-Verfahren. Schlagen Sie also die Formel nach und schreiben Sie als Java-Ausdruck, wobei Sie alles aus java.lang.Math benutzen dürfen außer Math.cbrt().

Entropie 1 (I1-ID: 9eaiwo41s4i0)

Für \(0< p <1\) ist die binäre Entropiefunktion definiert als

\(H(p)= - p\cdot \log_{2}p - (1-p)\log_{2}(1-p)\).

Schreiben Sie diese Formel als Java-Ausdruck.

Interessant sind übrigens die Grenzfälle \(p=0.0\) und \(p=1.0\), da bei diesen der Logarithmus von 0 zu bestimmen wäre, der bekanntlich nicht definiert ist. Jedoch wird festgelegt \(H(0)=H(1)=0\) — damit wird \(H\) stetig auf dem ganzen Intervall \([0,1]\).

Die Entropie ist eine zentrale Größe in der Informationstheorie. Sie hat Bedeutung in der Nachrichtentechnik aber z.B. auch in der Biologie.

Pi-raten (I1-ID: 2wyc59t0n3i0)

In Paragraph 2.2-31 wird beschrieben, wie \(\pi\) näherungsweise berechnet werden kann. Modifizieren Sie den Quelltext so, dass kein cast auf double notwendig ist.

Hierfür gibt es wenigstens zwei Lösungen. Finden und testen Sie beide mit großem r.

Vermischtes zu elementaren Daten (I1-ID: e638zfi0qtg0)

Kreuzen Sie Zutreffendes an:

  • [ ] int x = Integer.MAX_VALUE; x++; verursacht eine OverflowException.
  • [ ] Steuerzeichen werden vom Steuerwerk interpretiert.
  • [ ] if (b > 0 && a/b < 2) ... ist besser als if (a/b < 2 && b > 0) ...
  • [ ] Umlaute im Quelltext verursachen Compilezeitfehler.
  • [ ] "höchstens 6 Zeichen" ist ein Literal.
  • [ ] Integer.MAX_VALUE++; verursacht einen Ganzzahlüberlauf.
  • [ ] UTF-8 ordnet jedem Zeichen eine Folge von 8 Bytes zu.
  • [ ] double x = 1/0; verursacht keinen Laufzeitfehler.

long, long ago (I1-ID: 5nufzi61yii0)

Der Java-Compiler akzeptiert drei der folgenden Codezeilen nicht. Welche sind das und was ist an Ihnen falsch?

  • [ ] int n1 = 3000000000;
  • [ ] long n2 = 3000000000;
  • [ ] long n3 = 300000000L;
  • [ ] long n4 = 300000000F;

Casting-Show (I1-ID: b9ej9071yii0)

Der Java-Compiler akzeptiert eine der folgenden Codezeilen nicht. Welche ist das, was ist falsch daran und warum sind die anderen drei richtig?

  • [ ] int n1 = (int) 3000000000.;
  • [ ] int n2 = (int) 3000000.0f;
  • [ ] long n3 = (long) 3000000000;
  • [ ] double n4 = (int) 30000000e0;

Felder

Keine Frage des Geschmacks (I1-ID: vgmdz3z07ji0)

Hier zwei fast identische Codevarianten. Welche ist besser (und warum)?

for (int i = 0; i < f.length && f[i] != q; i++)
    System.out.println(i);
for (int i = 0; f[i] != q && i < f.length; i++)
    System.out.println(i);

Feld umgraben (I1-ID: xu71ubs0lyg0)

Die Reihenfolge der Elemente im Feld a der Länge N soll umgekehrt werden. Wählen Sie Code aus, der diese Aufgabe löst, und bei dem die wenigsten Operationen stattfinden.

  1. [ ]
    for (int i = 0; i < N; i++) {
        int tmp = a[i]; 
        a[i] = a[N-i-1];
        a[N-i-1] = tmp;
    }
    
  2. [ ]
    int[] b = new int[N]; 
    for (int i = 0; i < N; i++) 
        b[i] = a[N-i-1];
    a = b;
    
  3. [ ]
    for (int i = 0; i < N/2; i++) {
        int tmp = a[i]; 
        a[i] = a[N-i];
        a[N-i] = tmp;
    }
    
  4. [ ]
    for (int i = 0; i < N/2; i++) {
        int tmp = a[i]; 
        a[i] = a[N-i-1];
        a[N-i-1] = tmp;
    }
    

Noch mehr Feldarbeit (I1-ID: p0kaixs0lyg0)

Welche Ausgabe erzeugt folgender Code:

 public class Feldarbeit {
     public static void main(String[] args) {
         int[] a = { 0, 1, 2, 3, 4, 5, 6, 7}; 
         int N = a.length;
         for (int i = 0; i < N; i++) {
             a[i] = a[(i+1) % N];
         }
         for (int i = 0; i < N; i++) 
             System.out.print(a[i] + " "); 
         System.out.println();
     }
 }
  • [ ] 1 2 3 4 5 6 7 1
  • [ ] 1 2 3 4 5 6 7 0
  • [ ] 1 1 1 1 1 1 1 1
  • [ ] 7 0 1 2 3 4 5 6

Horner: Es gibt immer was zu tun! (I1-ID: 5rajza41s4i0)

Programmieren Sie den Algorithmus aus Aufgabe 442a09r0c4i0 (Koeffizienten per Kommandozeilenargumenten übergeben, \(x_{0}\) von der Standardeingabe lesen).

Im Mittel - arithmetisch oder geometrisch? (I1-ID: eck0y931s4i0)

Sei \(\mathbf{x}=(x_{0}, x_{1}, ..., x_{n-1})\) eine Folge nichtnegativer Zahlen. Ihr arithmetisches Mittel ist der gewöhnliche Mittelwert

\(A(\mathbf{x}):=\frac{1}{n}\sum_{i=1}^{n}x_{i}\)

während ihr geometrisches Mittel definiert ist durch

\(G(\mathbf{x}):=\sqrt[n]\prod_{i=1}^{n} a_{i}\),

Die Ungleichung vom arithmetischen und geometrischen Mittel besagt, dass stets \(G(\mathbf{x})\le A(\mathbf{x})\) gilt. Überprüfen Sie das durch ein Java-Program, das \(x_{0}, x_{1}, ..., x_{n-1}\) von der Standardeingabe liest und die Ungleichung überprüft (\(n\) wird per Kommandozeilenargument übergeben).

Entropie 2 (I1-ID: zzsa6351s4i0)

Für positive Zahlen \(p_{0}, ..., p_{n-1}\) kleiner als 1 für die gilt \(p_{0}+...+p_{n-1}=1\) ist die Entropie definiert als

\(H(p_0,...,p_{n-1}) = -\sum_{i=0}^{n-1}p_i\log_{2}{p_i}\).

Realisieren Sie in Verallgemeinerung der Aufgabe 9eaiwo41s4i0 diese Formel durch ein Java-Programm. Dabei soll \(n\) als Kommandozeilenparameter angegeben werden und anstelle der \(p_{i}\) sollen \(n\) positive ganze Zahlen \(a_{i}\) von der Standardeingabe gelesen werden, die die \(p_{i}\) definieren durch die Formel

\(p_{i}=\frac{a_{i}}{\sum_{i=0}^{n}a_{i}}\).

Der ewige Zweite (I1-ID: kn92zf1085i0)

Paragraph 2.3-3 im Skript zeigt, wie man das Maximum einer Zahlenfolge bestimmt. Modifizieren (und testen) Sie den Code so, dass stattdessen die zweitgrößte Zahl gefunden wird.

Permutationen (I1-ID: fa1gok71s4i0)

Eine Folge \(\mathbf{p}=(p_{0},p_{1}, ...,p_{n-1})\) natürlicher Zahlen heißt Permutation, falls in ihr jeder der Werte \(0, 1, ...,n-1\) genau einmal vorkommt. Schreiben Sie ein Java-Programm, das \(n\) ganze Zahlen von der Standardeingabe liest und testet, ob die Bedingung erfüllt ist (\(n\) wird per Kommandozeilenparameter übergeben).

Hinweis: "Zähltrick" aus dem Skript verwenden.

(Un-)Auffällige Häufung (I1-ID: xm90cao0s4i0)

Schreiben Sie eine Java-Applikation, die zu einer Folge \(\mathbf{a} = (a_{0}, a_{1}, ..., a_{n-1})\) ganzer Zahlen den häufigsten Wert der Folge berechnet (siehe Wikipedia). Die \(a_{i}\) sollen als Kommandozeilenargumente übergeben werden.

Hinweis:

  • Machen Sie sich zunächst klar, dass im Falle \(a_{i}\ge 0\) der "Zähltrick" aus dem Skript anwendbar ist. Dann liegen nämlich die Werte zwischen 0 und einem zu bestimmenden Maximalwert und können als Indizes für ein Zählfeld genutzt werden. Programmieren Sie zunächst diese Variante.
  • Überlegen Sie dann, wie der Trick angepasst werden kann, wenn die Bedingung fallen gelassen wird, also die Werte zwischen beliebigen Minimal- und Maximalwerten liegen und passen Ihr Programm an.

Unimo… was?? (I1-ID: 1sgfsgj0t4i0)

Eine Zahlenfolge \(\mathbf{a} = (a_{0}, a_{1}, ..., a_{n-1})\) heißt unimodal, wenn es ein \(i_{0}

Lösen Sie die Aufgabe OHNE ein Feld zu definieren. Das geht nämlich einfacher und eleganter.

Clever streamen (I1-ID: f5if7j0115i0)

Manche Probleme auf Zahlenfolgen kann man lösen, ohne die Zahlen in einem Feld zu speichern. Stellen Sie sich vor, dass die Zahlen von der Standardeingabe gelesen werden, aber die Anzahl nicht bekannt ist. Damit ist nicht klar, welche Feldlänge zum Speichern erforderlich wäre — dennoch kann man Probleme wie diese einfach lösen

  • Kommt eine bestimmte Zahl in der Folge vor?
  • Ist die Folge aufsteigend sortiert?
  • Was ist das Maximum der Zahlen?

Es gibt weitere Beispiele in dieser Sammlung (z.B. Aufgabe 1sgfsgj0t4i0). Auch der Hase-und-Igel-Algorithmus gehört dazu.

Algorithmen denen nur konstant viel Speicher zur Verfügung steht, die aber dennoch beliebig viele Daten behandeln, heißen Streaming-Algorithmen (Beispiel: Überwachungskamera, kommt eine bestimmte Person ins Bild?).

Hier noch ein Beispiel: Wahlzettel werden durchgesehen. Gibt es eine absolute Mehrheit, d.h. konnte jemand mehr als die Hälfte aller Stimmen auf sich vereinen (und wenn ja, welche)? Stehen nur zwei Personen zur Wahl, ist dies offenbar durch einen Streaming-Algorithmus zu lösen (für jede Person einen Zähler einrichten, am Ende vergleichen); ebenso bei drei, vier … maximal \(k\) zur Wahl stehenden Personen, falls \(k\) vorher bekannt ist. Aber es geht auch bei beliebig großer Anzahl! — mit der Einschränkung, dass die Antwort falsch sein kann, wenn es keine absolute Mehrheit gibt.

Kommen Sie drauf? Falls nicht, können Sie die (überraschend einfache) Antwort bei Wikipedia lesen. Um sich davon zu überzeugen, dass das funktioniert, programmieren Sie es nach.

TODO Ternäre Suche (I1-ID: xza1ptj0t4i0)

siehe Wikipedia

TODO Nullnummern (I1-ID: 7ow27np088i0)

Die mit int[][] tabelle deklarierte Tabelle werde bei der Abarbeitung eines Programms mit Werten gefüllt, dabei sei tabelle[i][j] der Wert in Zeile i Spalte j.

Wählen Sie aus den nachfolgenden Codeschnipseln denjenigen aus, der den Zeilenindex mit der maximalen Anzahl von Nullen bestimmt.

Zeilen sind anders, Spalten auch (I1-ID: lhu27691fzg0)

Folgendes Codefragment soll die Multiplikation eines Zeilenvektors mit einer Matrix sowie einer Matrix mit einem Spaltenvektor realisieren. Wählen Sie die fehlenden Zeilen unten entsprechend aus:

 1:     int[][] m = {{ 0, 1, 2, 3},   // Matrix
 2:                  { 4, 5, 6, 7}, 
 3:                  {8, 9, 10, 11}}; 
 4:     int[] z = { 12, 13, 14};      // Zeile
 5:     int[] s = {15, 16, 17, 18};   // Spalte
 6: 
 7:     /* CODEZEILE AUSWÄHLEN */     // Zeilenanzahl der Matrix
 8:     /* CODEZEILE AUSWÄHLEN */     // Spaltenanzahl der Matrix
 9: 
10:     /* 1: Zeile mal Matrix */
11:     int[] zm = new int[n_sp];
12:     for (int j = 0; j < n_sp; j++) {
13:         zm[j] = 0;
14:         /* CODEZEILE AUSWÄHLEN */
15:             zm[j] = zm[j] + z[i]*m[i][j];
16:     }
17:     /* 2: Matrix mal Spalte */
18:     int[] ms = new int[n_ze];
19:     for (int i = 0; i < n_ze; i++) {
20:         ms[i] = 0;
21:         for (int j = 0; j < n_sp; j++)
22:             /* CODEZEILE AUSWÄHLEN */
23:     }
Zeile 7
  • [ ] int n_ze = m.length;
  • [ ] int n_ze = m[0].length;
  • [ ] int n_ze = m.length();
  • [ ] int n_ze = m[0].length();
Zeile 8
  • [ ] int n_sp = m.length();
  • [ ] int n_sp = m[0].length();
  • [ ] int n_sp = m.length;
  • [ ] int n_sp = m[0].length;
Zeile 14
  • [ ] for (int i = 1; i <= n_ze; i++)
  • [ ] for (int i = 0; i < n_ze; i++)
  • [ ] for (int i = 1; i <= n_sp; i++)
  • [ ] for (int i = 0; i < n_sp; i++)
Zeile 22
  • [ ] ms[i] = ms[i] + m[j][i]*s[i];
  • [ ] ms[i] = ms[i] + m[i][j]*s[i];
  • [ ] ms[i] = ms[i] + m[j][i]*s[j];
  • [ ] ms[i] = ms[i] + m[i][j]*s[j];

Magische Quadrate (I1-ID: mhf864k0t4i0)

Definition (nach Wikipedia): Ein magisches Quadrat der Kantenlänge \(n\) ist eine quadratische Anordnung der natürlichen Zahlen \(1, 2, ..., n^{2}\), so dass alle Zeilen-, Spalten- und Diagonalsummen gleich sind.

Schreiben Sie eine Java-Applikation MagicSquareTest, die eine natürliche Zahl \(n>0\) als Kommandozeilenparameter übernimmt, dann \(n^{2}\) natürliche Zahlen einliest und testet, ob diese zeilenweise quadratisch angeordnet ein magisches Quadrat ergeben.

Primzahlsatz (I1-ID: aaghnl21t4i0)

  1. Modifizieren Sie PrimeSieve ein klein wenig zu einer Applikation \(Primes.java\), die anstelle der Primzahlen \(\le n\) nur deren Anzahl \(\pi(n)\) ausgibt. Überzeugen Sie sich, dass diese Anzahl blitzschnell ermittelt wird, selbst für sehr große \(n\).
  2. Die Funktion \(n\mapsto \pi(n)\) ist eine wichtige zahlentheoretische Funktion. Kenntnis ihres Wachstumsverhaltens ist von immenser Wichtigkeit für moderne Verschlüsselungsverfahren. Der berühmte Primzahlsatz besagt, dass sich \(\pi(n)\) asymptotisch wie \(\frac{n}{\ln n}\) verhält: \(\lim_{n\rightarrow\infty} \frac{\pi(n)}{n/\ln n}=1\).

    Überprüfen Sie dies testweise für zufällige Werte wachsender Größenordnung (z.B. von ca. 20 bis ca. 2Mrd, Wachstum jeweils um Faktor 10).

TODO Schleifen binden (I1-ID: oyla1zv0e5i0)

Gegeben ein mit einer Zahlenfolge initialisiertes Feld

int[] f = {1,2,...}; // geeignete Werte eintragen

und weiterhin:

Links
eine Reihe von Codefragmenten mit Schleifenanweisungen (while, do, for) mit unterschiedlichen Start-/Abbruchbedingungen und if-gesteuerter Ausgabe der Form System.out.print(f[i] + " ") im Schleifenkörpern
Rechts
eine Reihe von theoretisch möglichen Ausgaben

Aufgabe Ordnen Sie die Schleifen den Ausgaben zu.

Gleiches mit Gleichem vergelten (I1-ID: 4rth3g51u5i0)

  1. Was produziert das folgende Codefragment?

    int[] a = {1, 2, 3};
    int[] b = {1, 2, 3};
    System.out.println(a == b);
    
    • [ ] Ausgabe true
    • [ ] Ausgabe false
    • [ ] Compilezeitfehler
    • [ ] eine Exception
  2. Was produziert das folgende Codefragment?

    int[] a = {1, 2, 3};
    int[] b = {1, 2, 3};
    System.out.println(a=b);
    
    • [ ] eine Ausgabe
    • [ ] Compilezeitfehler
    • [ ] eine Exception
  3. Was produziert das folgende Codefragment?

    int[] a = {1, 2, 3};
    int[] b = {1, 2, 3};
    System.out.println(a.equals(b));
    
    • [ ] Ausgabe true
    • [ ] Ausgabe false
    • [ ] Compilezeitfehler
    • [ ] eine Exception

Funktionen und Module

Programmbibliotheken

Pi-cture (I1-ID: egwiyls0n3i0)

Erzeugen Sie mittels StdDraw Bilder wie in Paragraph 2.2-31 des Skripts. r soll als Kommandozeilenparameter angegeben werden.

Archimedische S-Pi-rale (I1-ID: cnl56us0n3i0)

Erzeugen Sie mittels StdDraw Archimedische Spiralen. Der Parameter \(a\) soll als Kommandozeilenparameter angegeben werden.

Programmiersprachen-Nomenklatur

Workflow bei Bytecode-Sprachen (I1-ID: w3vge2715og0)

Im Rahmen von Info I ist eine Applikation TuWas zu entwickeln und zu testen. Eingabe erfolgt interaktiv (z.B. mittels StdIn). Ordnen Sie die folgenden Dinge/Vorgänge nach dem Zeitpunkt, ab dem sie spätestens vorliegen müssen, so dass alles reibungslos ablaufen kann.

  • Start der JVM
  • TuWas.class
  • Compiler
  • TuWas.java
  • Eingaben
  • StdIn
  • Host
  • Header-Informationen

Bemerkung: Für reibungslosen Ablauf sind mehrere Reihenfolgen möglich, aber nicht unter der Bedingung spätestens (da es um eine Info I-Applikation geht, reden wir nicht über dynamisch nachladbare Klassen etc.).

Java-Bytecode disassemblieren (I1-ID: fwsets601ng0)

  • lesen Sie bei Wikipedia nach, was es bedeutet, Binärcode zu disassemblieren und erklären Sie das in der Rechnerübung
  • man kann auch Java-Bytecode disassemblieren, finden Sie mittels man javap heraus, wie das geht und erklären Sie das in der Rechnerübung
  • betten Sie das Java-Fragment aus Paragraph 1.2-19 in die main-Methode einer Applikation ein und compilieren Sie diese
  • benutzen Sie dann javap zum disassemblieren des entstandenen Bytecodes
  • überprüfen Sie, ob der benutzte Java-Compiler den Bytecode im Sinne von Aufgabe jrhjaye0tmg0 optimiert hat

TODO Spaghetti (I1-ID: vv2ezj401ng0)

Speichern Sie den BASIC-Code aus Paragraph 3.1-11 (PRÜFEN!!) in einer Datei. Editieren Sie dann so, dass anstelle der Quadratzahlen \(1^2, 2^2, 3^2, ...\) die Potenzen \(1^1, 2^2, 3^3, ...\) erzeugt werden. Beobachten Sie, wie mühevoll die Wartung von solchem Spaghetti-Code ist.

Misch Masch (I1-ID: uo93wey0oog0)

Kreuzen Sie alles an, was im weitesten Sinne wahr ist (wahre Aussagen, korrekte Formulierungen, Ausdrücke mit Wert true):

  • [ ] Das rekursive Grundschema lautet: Rekurriere - Terminiere (falls trivial)
  • [ ] Die Java-Laufzeitumgebung beinhaltet Compiler, Klassenbibliotheken und die (JVM) Java Virtual Machine.
  • [ ] Die JVM interpretiert Java-Bytecode.
  • [ ] An Ausdrücke dürfen keine Zuweisungen erfolgen. (falsch, denn x[0]=1; ist erlaubt)
  • [ ] Formalparameter sind lokale Variablen.
  • [ ] Methoden mit Signatur int (int) werden mit call-by-reference aufgerufen.
  • [ ] (false ? true : false) == (true ? false : true)
  • [ ] (false ? false : true) == (false ? true : false)

Nachträge zur strukturierten Programmierung

TODO EBNF (I1-ID: xrp6tdd01ng0)

Entwerfen Sie anhand des Beispiels aus Paragraph 3.2-15 (PRÜFEN) eine EBNF-Regel für die switch-Anweisung. Beachten Sie, dass es beliebig viele case-Klauseln geben kann, dass jede optional mit einem break abschließt und dass default auch optional ist.

Spaß mit Strings (I1-ID: 4rtbss10x5i0)

Welche Ausgabe erzeugt System.out.println(s);, wenn String s wie folgt entsteht?:

  • Variante 1

    s = "price: " + 4. + 20;
    
  • Variante 2

    s = "price: " + (4. + 20);
    
  • Variante 3:

    s = "price: " + (double) 4 + 2;
    

Erklärung: String-Umwandlung (Paragraph 2.2-9) und Operator-Priorität (Tabelle in Paragraph 3.3-10)

Eile mit while (I1-ID: zqteygp088i0)

Wandeln Sie die folgende for-Anweisung in eine äquivalente while-Anweisung um:

for (int i = 533; i > -12; i -= 7) {
    System.out.println(i);
}

Gut Ding will while haben (I1-ID: qln7rxh0k5i0)

  1. Formen Sie

    do <Anweisung> while (<Bedingung>);
    

    äquivalent um, so dass stattdessen eine while-Anweisung benutzt wird.

  2. Machen Sie das Gleiche mit

    if (<Bedingung>) <Anweisung>;
    

Sprunghaft (I1-ID: q7titdp088i0)

Welchen Wert hat k nach Abarbeitung des folgenden Codes?

int k = 2;
for (int i = 2; i < 7; i += k) {
    k *= i;
}

Prozedurale Programmierung

Ent- oder weder (I1-ID: 86bdabn088i0)

public static boolean f(boolean x, boolean y) {
    if(x) {
        return y;
    } else if(not y) {
        return x;
    } else {
        return not x;
    }
}
  1. Füllen Sie die Tabelle mit den jeweiligen Ergebniswerten der Methode:

    x y Ergebnis (f(x,y))
    false false t
    false true f
    true false f
    true true t
  2. Der Code im Methodenrumpf kann gleichwertig durch die Anweisung

    return <Ausdruck>;
    

    ersetzt werden. Welcher Ausdruck ist dabei eizusetzen?

    • [ ] !(!x || y)
    • [ ] !y && !x
    • [ ] !x || !y
    • [ ] !(!x && !y)
    • [ ] !(x || y)
    • [ ] !(x ^ y)
    • [ ] (!x ^ !y)
    • [ ] !(x && y)

Notenspiegel (I1-ID: vysdp3p088i0)

Das folgende Punktesystem zur Notenvergabe

Punkte Note
26-30 1
21-25 2
16-20 3
11-15 4
0-10 5

soll durch eine Java-Methode public static int note(int punkte) realisiert werden. Programmieren Sie diese Methode. Bei ungültigen Punktzahlen soll der Wert -1 geliefert werden.

Mehrheitsvotum (I1-ID: rvn1njb1u5i0)

Schreiben und testen Sie eine Methode majority, mit drei boolean-Parametern, die genau dann den Wert true liefert, wenn mindestens zwei der Parameter true sind. Verwenden Sie dabei keine if-Anweisung.

Funktionsaufrufe automatisch verfolgen (I1-ID: nvdj0hq0l5i0)

Modifizieren Sie \texttt{Newton.java} so, dass ein Protokoll wie das des Aufrufs java Newton 1 2 aus dem Skript erzeugt wird:

  • Tipp
    • beim Aufruf: Ausgabe von <Funktionsname> (<Aufrufparameter>)
    • beim Rücksprung: Ausgabe von return <Rückgabewert>
    • Einrücktiefe mit jedem Aufruf erhöhen und jedem return verringern
    • zusätzliche Ausgabe nach jeder erfolgten Zuweisung: | <Variable>: <Wert>

ggT allgemein (I1-ID: j7pkjj50hji0)

Programmieren Sie GGT.java um, so dass die Kommandozeilenparameter als ganze Zahlen interpretiert werden und deren ggT berechnet wird - also auch wenn drei oder mehr Parameter mitgegeben werden.

Das geht ja gar nicht! (I1-ID: oej4tn30x5i0)

Folgende API HexTools soll erstellt werden

Signatur Erklärung
boolean isHexString(String s) prüft, ob s Hexstring ist, d.h. nur Hexadezimalziffern enthält
int hex2int(String h) berechnet und liefert die durch Hexstring h hexadezimal dargestellte Zahl

Ein Entwickler nutzt DecimalDecode.java als Codesteinbruch und schlägt folgenden Methodenrumpf für hex2int vor. Der Vorschlag wird abgelehnt, schon weil er nicht der Spezifikation genügt. Korrigieren Sie an 4 Zeilen (ändern oder streichen), um korrekten Code zu erhalten.

Tipp: Sie dürfen (und sollten) dabei auch auf Bibliotheksfunktionen aus https://docs.oracle.com/javase/7/docs/api/java/lang/Character.html zurückgreifen.

 1: {
 2:     if (!isHexString(h)) return;
 3:     int n = h.length();
 4:     int z = 0; 
 5:     char c; 
 6:     for (int i = 0; i < n; i++) {
 7:         z = 16*z;
 8:         c = h.charAt(i); // das i-te Zeichen von h
 9:         if ('0' <= c && c <= '9') 
10:             z = z + (c - '0');
11:         if ('a' <= c && c <= 'e') 
12:             z = z + (c - 'a');
13:     } 
14:     System.out.println(z);
15: }
  • Lösung
    • Zeile 2: streichen (laut Spezifikation ist h bereits ein Hexstring, also nicht testen)
    • Zeile 8: c = Character.toUpperCase(h.charAt(i));
    • Zeile 11: obere Grenze f
    • Zeile 14: return z;

Faktorisierung genauer betrachtet (I1-ID: nsmdopt0t2i0)

Welche Aussagen treffen zu für den Quelltext Factor.java?

  • [ ] Zeile 5 kann ersetzt werden durch t+=2.
  • [ ] der Basisfall der Rekursion ist "n = 2",
  • [ ] der Basisfall der Rekursion ist "n ist Primzahl",
  • [ ] bei Eingabe 120 ist die Rekursionstiefe 5.
  • Loesung
    • [ ] Nein, zum Beispiel bei n==9 würden nur die Teiler 2 und 4 geprüft werden,
    • [ ] Nein, dieser Fall wird z.B. bei n==3 nicht erreicht.
    • [X]
    • [ ] Nein, die Rekursionstiefe eines Aufrufs ist die Anzahl der Folgeaufrufe. Bei einem Produkt aus \(k\) Primzahlen werden \(k-1\) Folgeaufrufe ausgelöst, in diesem Fall also 4.
    public class Factor {
        static void factor (int n) {
            int t = 2;
            while (n%t != 0 && t*t < n)
                t++;
            if (t*t > n) {             
                System.out.print(n);   
                return;
            }
            System.out.print(t+" "); 
            factor(n/t);             
        }
        public static void main(String[] args) {
            int z = Integer.parseInt(args[0]); // zu faktorisierende Zahl
            System.out.print(z + ": ");
            if ( z > 1) 
                factor(z);
            System.out.println();
        }
    }
    

Faktorisierung iterativ (I1-ID: oo921lu0t2i0)

Programmieren Sie die Funktion factor in Factor.java um, so dass sie ohne Rekursion auskommt.

Wozu die Dualdarstellung auch gut ist (I1-ID: ksufk930u2i0)

Programmieren Sie ModExp.java iterativ.

Hinweis: Nutzen Sie den Zusammenhang zur Dualdarstellung aus: Ist \(e=b_{n}\cdot 2^{n}+ ... + b_{1}\cdot 2^{1} + b_{0}\cdot 2^{0}\), so gilt \[a^{e}\pmod{m} = a^{b_{n}\cdot 2^{n}}\cdots a^{b_{1}\cdot 2}\cdot a^{b_{0}}\pmod{m}.\]

Mephistosequenz (I1-ID: v8h1b4z0m2i0)

Sei \(s_{0}=0\). Für \(n>0\) sei \(s_n=\overline{s_{n-1}}s_{n-1}\), wobei der Überstrich für das bitweise Komplement steht. Also

\(s_{1}=10, s_{2}=0110, s_{2}=10010110, s_{3}=0110100110010110, ...\)

Programmieren Sie eine Funktion public String mephisto(int n), die diese Strings liefert.

Bemerkung: Bekannt ist die (unendliche Version dieser) Sequenz unter dem Namen Thue-Morse-Sequenz. Sie hat viele interessante Eigenschaften.

Fibo-naiv (I1-ID: am4awa40u2i0)

Bei der naiven rekursiven Implementierung der Fibonacci-Folge

public static int f(int n) {
    if ( n <= 1) return n;
    return f(n-1) + f(n-2);
}

hat der Aufruf f(5) diesen Rekursionsbaum

Fibonacci.png

Überlegen Sie, in welcher Reihenfolge die einzelnen Aufrufe erfolgen.

Überzeugen Sie sich, dass dies gerade der Postorder-Traversierung dieses Baumes entspricht (siehe Skript Paragraph 3.4-34).

Überprüfen Sie Ihr Protokoll mit Hilfe der naiven Implementierung, die Sie um Ausgabeanweisungen ergänzen, um den gerade gestarteten Aufruf anzuzeigen.

4-Sterne-Hotel (I1-ID: np3j0tl056i0)

Untenstehendes Programm hat eine ähnliche Struktur wie TuermeVonHanoi.java:

 1: public class Stars {
 2:     public static void stars(int n) { 
 3:         if (n == 0) return;
 4:         for (int i = 0; i < n; i++)
 5:             System.out.print("*");
 6:         System.out.print("|");
 7:         stars(n-1);
 8:         stars(n-1);
 9:     }
10:     public static void main(String[] args) {
11:         int n = Integer.parseInt(args[0]);
12:         stars(n);  
13:         System.out.println();
14:     }
15: }

Wesentlich anders als dort ist jedoch die Reihenfolge: Jeder Aufruf (außer Basisfall) bewirkt erst eine Ausgabe, dann zwei rekursive Aufrufe. Entsprechend wird der Rekursionsbaum in Preorder-Reihenfolge traversiert: Wurzel – Links – Rechts.

Stars.png

Welche Ausgabe produziert demzufolge der Aufruf java Stars 4?

  • [ ] **********||*||***||*||******||*||***||*|
  • [ ] ****|***|**|*|*|**|*|*|***|**|*|*|**|*|*|
  • [ ] **********|*||***|*|||******|*||***|*||||

5-Sterne-Hotel (I1-ID: e8b3b9n056i0)

Betrachten Sie folgendes unvollständige Programm:

 1: public class Stars {
 2:     public static void stars(int n) { 
 3:         if (n == 0) return;
 4:         for (int i = 0; i < n; i++)
 5:             System.out.print("*");
 6:             //  Luecke
 7:     }
 8:     public static void main(String[] args) {
 9:         int n = Integer.parseInt(args[0]);
10:         stars(n);  
11:         System.out.println();
12:     }
13: }

Die Lücke in Zeile 6 muss noch gefüllt werden. Ordnen Sie die Codezeilen

  • System.out.print("|"); stars(n-1); stars(n-1);
  • stars(n-1); System.out.print("|"); stars(n-1);
  • stars(n-1); stars(n-1); System.out.print("|");

den erzeugten Ausgaben zu:

  • ***************|*||***|*|||******|*||***|*||||**********|*||***|*|||******|*||***|*|||||
  • *****|****|***|**|*|*|**|*|*|***|**|*|*|**|*|*|****|***|**|*|*|**|*|*|***|**|*|*|**|*|*|
  • ***************||*||***||*||******||*||***||*||**********||*||***||*||******||*||***||*|

Einfach runterprogrammieren (und runterzeichnen) (I1-ID: fur23qs088i0)

Die Funktion \(f\) ist definiert durch

\(f(n) = 1\) für \(n\le 4\) und \(f(n) = 2\cdot f(n-1) + 3\cdot f(n-2)\) für \(n>4.\)

  1. Implementieren Sie eine Java-Methode int f(int n), die den Funktionswert zu gegebenem \(n\) liefert. Die Deklaration lokaler Variablen im Methodenrumpf und Verwendung von Schleifen ist nicht erlaubt.
  2. Zeichnen Sie den Aufrufbaum ihrer Methode bei Aufruf mit Parameter \(n=7\).

Fibo-clever (I1-ID: xatic0e1v5i0)

Die rekursive Berechnung von Fibonacci-Zahlen ist offenbar ineffizient. Es geht aber auch iterativ, d.h. mittels einer Schleife. Programmieren Sie eine solche Variante, die aber - anders als die memoisierte Lösung (Paragraph 3.4-36) - kein Feld als Zwischenspeicher anlegt.

Binäre Suche rekursiv (I1-ID: y37jizd136i0)

Um in einem aufsteigend sortierten int-Feld nach einem int-Schlüssel zu suchen wird die Methode

public static int search(int key, int[] a) {
    return search(key, a, 0, a.length); 
}

aufgerufen. Programmieren Sie die Methode int search(int key, int[] a, int lo, int hi) rekursiv. Sie sucht innerhalb der Komponenten a[lo], a[lo+1], ..., a[hi-1]

  • Lösung
    public class Search {
        public static int search(int key, int[] a) {
            return search(key, a, 0, a.length);
        }    
        public static int search(int key, int[] a, int lo, int hi) {
            // sucht in a[lo,hi) nach key
            if (hi <= lo) { return -1; }
            int mid = (lo+hi)/2;
            if (key < a[mid])
                return search(key,a,lo,mid);
            else if (a[mid] < key)
                return search(key,a,mid+1,hi);
            else return mid;
        }
        public static void main(String[] args) {
            int[] a = new int[args.length];
            for (int i = 0; i< args.length; i++) {
                a[i] = Integer.parseInt(args[i]);
            }
            int key = StdIn.readInt();
            System.out.println(search(key,a));
        }
    }
    

Sum Sum Sum, Bienchen sum herum (I1-ID: 5rg27x81v2i0)

Programmieren und testen Sie drei Funktionen mit Argument vom Typ int[], die die Summe der gespeicherten Zahlen berechnet:

  1. mit einer for-Schleife
  2. mit einer while-Schleife
  3. rekursiv, indem die erste zur Summe der anderen Zahlen berechnet wird.

Tipp für die rekursive Lösung: Die eigentliche Rekursion erfolgt (ähnlich wie bei der Lösung zur rekursiven binären Suche) durch eine weitere Funktion, die zusätzlich zu dem Feld noch Argumente lo und hi übernimmt und die Summe der Feldkomponenten mit Indizes lo, lo+1, ..., hi-1 berechnet.

Max i mal (I1-ID: 5pr5lpd1p6i0)

Programmieren und testen Sie drei Funktionen mit Argument vom Typ int[], die das Maximum der gespeicherten Zahlen berechnet:

  1. mit einer for-Schleife
  2. mit einer while-Schleife
  3. rekursiv, indem das Maximum aus der ersten und dem Maximum aller anderen Zahlen berechnet wird.

Tipp für die rekursive Lösung: Siehe Hinweis zu anderer Aufgabe.

Max doch mal anders! (I1-ID: im7jqc00q6i0)

Programmieren Sie die rekursive Berechnung des Maximums der Einträge in einem Feld, indem das Maximum gebildet wird aus dem Maximum der "vorderen" und der "hinteren Hälfte" der Zahlen gebildet wird (ähnlich wie bei binärer Suche).

Dies ist ein ein genereller Ansatz, der "Teile und Herrsche" (Divide and Conquer) genannt wird. Auch das Türme-von-Hanoi Problem haben wir bereits damit gelöst. Natürlich kann man auch die Summe der im Feld gespeicherten Zahlen so berechnen. Allen diesen Lösungen ist gemein, dass die rekursive Funktion sich selbst mehrmals aufruft (zwei- oder mehrfache Rekursion).

Tipp: Siehe auch Hinweis zu anderer Aufgabe.

Bemerkung: Selbstverständlich würde man "im Leben" das Maximum/die Summe wohl eher iterativ berechnen - das ist klarer und effizienter Code. Hier geht es aber darum, den Divide&Conquer-Ansatz schon mal an Spielzeug-Beispielen zu studieren.

Eins weiterrücken (I1-ID: xz146ma1v2i0)

Programmieren und testen Sie eine Funktion public void shift(int[] a), die bei Aufruf den Inhalt des Feldarguments zyklisch nach rechts verschiebt, z.B. würde aus [12,18,29,1,3] dies hier werden: [3,12,18,29,1].

Ringelpietz allgemein (I1-ID: tltg5q91v2i0)

(siehe Aufgabe svc2vpe0u2i0)

Programmieren und testen Sie eine void-Funktion, die ein Feldargument a und einen int-Wert d entgegennimmt und bei Aufruf den Inhalt von a um d Plätze zyklisch nach rechts verschiebt.

Beispiel: aus [0,1,2,3,4,5,6] wird beim Verschieben um 4 Plätze diese Anordnung [4,5,6,7,0,1,2,3]

Tipp: Das ist auf direkte Art ein bisschen fummelig. Einfach und klar wird es mit diesem, beispielhaft dargestellten Trick (überzeugen Sie sich, dass das immer funktioniert):

  • Ausgangssituation

    [0,1,2,3,4,5,6] = [[0,1,2,3],[4,5,6]] = [A,B]
    
  • einzeln spiegeln

    [A',B'] = [[3,2,1,0],[6,5,4]] = [3,2,1,0,6,5,4]
    
  • alles spiegeln

    [A',B']' = [4,5,6,0,1,2,3] = Ergebnis
    

Sie sollten übrigens auch überlegen, wie sinnvollerweise mit sehr großen oder auch negativen Werten d zu verfahren ist.

SudokuChecker (I1-ID: tcidje41t4i0)

Vervollständigen Sie SudokuChecker.java so, wie am Ende vom Parapraph 3.4-19 beschrieben.

Beziehungskiste 1 (I1-ID: 8m82qyt068i0)

Für die Methode public static int mystery(int a[]) { ... } stehen anstelle der Pünktchen ... eine Reihe Codeschnipsel zur Auswahl. Ihre Aufgabe ist es, diesen Schnipseln Eigenschaften zuzuordnen. Dabei sind beliebige Kombinationen möglich, z.B. Code, der alle oder der keine der Eigenschaften hat oder auch Eigenschaften, die von keinem Code/von allen Codes erfüllt werden usw. — nichts wird ausgeschlossen.

Der Parameterwert null ist ausgeschlossen.

Code A
int n = a.length;
if (n == 0) {
    return 0;
}
int[] b = new int[n-1];
for (int i = 0; i < n-1; i++) {
    b[i] = a[i];
}
return mystery(b) + 1;
Code B
int n = a.length;
if (n == 0) {
    return 0;
}
int[] b = new int[n-1];
for (int i = 1; i < n; i++) {
    b[i-1] = a[i];
}
return mystery(b) + a[0];
Code C
int n = a.length;
int e = 1;
for (int i = 0; i < n; i++) {
    e += a[i];
}
return e-1;
Code D
int n = a.length;
int e = 0;
for (int i = 1; i < n; i++) {
    e += a[i-1];
}
return e + a[n-1];
Eigenschaft 1
enthält einen Syntaxfehler
Eigenschaft 2
kann abhängig vom Parameterwert Laufzeitfehler verursachen
Eigenschaft 3
berechnet die Summe der im Feld gespeicherten Werte
Eigenschaft 4
liefert den Wert a.length

Für jede richtige Zuordnung gibt es Teilpunkte, für falsche Zuordnungen Abzüge. Negative Punktsumme wird auf 0 aufgerundet.

  • Lösung
    // Code A (liefert den Wert a.length)
    int n = a.length;
    if (n == 0) 
        return 0;
    int[] b = new int[n-1];
    for (int i = 0; i < n-1; i++) 
        b[i] = a[i];
    return mystery(b) + 1;
    
    // Code B (berechnet die Summe der im Feld gespeicherten Werte)
    int n = a.length;
    if (n == 0)
        return 0;
    int[] b = new int[n-1];
    for (int i = 1; i < n; i++) 
        b[i-1] = a[i];
    return mystery(b) + a[0];
    
    // Code C (berechnet die Summe der im Feld gespeicherten Werte)
    int n = a.length;
    int e = 1;
    for (int i = 0; i < n; i++) 
        e += a[i];
    return e-1;
    
    // Code D (berechnet die Summe der im Feld gespeicherten Werte, 
    //         kann abhaengig vom Parameterwert Laufzeitfehler verursachen
    //         (naemlich bei Feldlaenge 0))
    int n = a.length;
    int e = 0;
    for (int i = 1; i < n; i++) 
        e += a[i-1];
    return e + a[n-1];
    

Beziehungskiste 2 (I1-ID: r6o074w068i0)

Für die Methode public static double mystery(int a[]) { ... } stehen anstelle der Pünktchen ... eine Reihe Codeschnipsel zur Auswahl. Ihre Aufgabe ist es, diesen Schnipseln Eigenschaften zuzuordnen. Dabei sind beliebige Kombinationen möglich, z.B. Code, der alle oder der keine der Eigenschaften hat oder auch Eigenschaften, die von keinem Code/von allen Codes erfüllt werden usw. — nichts wird ausgeschlossen.

Der Parameterwert null ist ausgeschlossen.

Code A
int n = a.length;
if (n == 0)
    return 0;
int[] b = new int[n-1];
for (int i = 0; i < n-1; i++) 
    b[i] = a[i];
return ((n-1)*mystery(b) + a[n-1])/n;
Code B
int n = a.length;
java.util.Arrays.sort(a);
double m = 0.;
if (n > 0) 
    m += 1;
for (int i = 0; i < n-1; i++) 
    if (a[i] < a[i+1])
        m += 1;
return m;
Code C
int n = a.length;
if (n <= 1)
    return 0;
double M = Double.NEGATIVE_INFINITY, m = Double.POSITIVE_INFINITY;
for (int i = 0; i < n; i++) { 
    m = Math.min(m,a[i]);
    M = Math.max(M,a[i]);
}
return M-m;
Code D
int n = a.length;
java.util.Arrays.sort(a);
return a[n-1]-a[0];
Eigenschaft 1
hat lineares Laufzeitverhalten
Eigenschaft 2
kann abhängig vom Parameterwert Laufzeitfehler verursachen
Eigenschaft 3
liefert das Maximum der a[i]-a[j], wobei i, j verschiedene Feldindizes sind
Eigenschaft 4
liefert den Mittelwert der Feldeinträge
Eigenschaft 5
liefert die Anzahl verschiedener Feldeinträge

Für jede richtige Zuordnung gibt es Teilpunkte, für falsche Zuordnungen Abzüge. Negative Punktsumme wird auf 0 aufgerundet.

  • Lösung
    Eigenschaften 1 2 3 4 5
    Code A X - - X -
    Code B - - - - X
    Code C X - X - -
    Code D - X X - -

    Erklärung

    Code A
    • es handelt sich um eine lineare Rekursion (jeder Nicht-Basisfall generiert einen neuen Aufruf) mit konstantem Zusatzaufwand für die Ergebnisberechnung => lineares Laufzeitverhalten
    • im Fall n==1 wird der einzige und damit Mittelwert, der im Feld gespeicherten Werte geliefert; für größere n ist es auch der Mittelwert (kann man formal mit vollständiger Induktion nachweisen)
    Code B
    • nach dem Sortieren stehen gleiche Werte jeweils nacheinander im Feld, m wird entsprechend für jeden neuen Wert um 1 erhöht
    • java.util.Arrays.sort ist auf alle Felder anwendbar, deren Basistyp das Comparable-Interface implementiert, somit ist es ein vergleichsbasiertes Verfahren und damit nicht in Linearzeit ausführbar
    Code C
    • es werden genau n Iterationen mit jeweils konstanten Kosten ausgeführt
    • offensichtlich wird die "Spannweite" berechnet (in einer der ersten Vorlesungen besprochen)
    Code D
    • Laufzeitfehler falls n=0
    • offensichtlich wird die "Spannweite" berechnet (in einer der ersten Vorlesungen besprochen)
    • es ist kein lineares Verfahren (siehe Begründung bei Code B)

Modulare Programmierung

Immer schön fit bleiben, oder: Bubblesort kann jeder (I1-ID: 2e89exj09pg0)

Programmieren Sie eine statische Methode zum aufsteigenden Sortieren eines int-Felds f, das als Argument übergeben wird. Verwenden Sie dabei diese algorithmische Idee:

  • solange wie nötig
    • tausche ungeordnete Nachbarn

Genauer:

Iteriere
  • Flag getauscht auf false setzen
  • vergleiche mit for-Schleife im ganzen Feld Komponenten i und i+1 und tausche sie bei Bedarf (in diesem Fall setze getauscht auf true)

solange getauscht==true

Entwerfen Sie im Texteditor ausführbaren Java-Code für folgenden Klassenrumpf, den Sie sich als Modul vorstellen sollten, der allerlei nützliche Algorithmen sammelt, die man hin und wieder für die Verarbeitung von Feldern braucht. Sehen Sie entsprechend in der main-Methode auch Code vor, der ausgiebige Tests Ihrer Methode ermöglicht (Dazu Kommandozeilenparameter als Feldlänge interpretieren und entsprechend viele Werte von der Kommandozeile einlesen.)

public class ArrayTools {
    ... // Ihre Methode
    public static void main(String[] args) {
        ... // Ihre Tests
    }
}

Nehmen Sie das sportlich, und setzen Sie sich das Ziel, den Code erst dann zu compilieren, wenn Sie 100%ig sicher sind, dass er auch richtig ist und Sie ihn auch als Lösung in einer Klausur abgeben würden.

Das wird vielleicht nicht gleich klappen. Dann also üben üben üben und nächste Woche das Ganze nochmal.

Strukturierte Daten

Weiteres zu Feldern

Ordnung ist das halbe Leben (I1-ID: 83ei4pl0i6i0)

  1. Ein Feld mit den Einträgen 5 6 3 1 8 2 7 4 soll aufsteigend sortiert werden. Notieren Sie den Zustand des Feldes nach den einzelnen Iterationen der äußeren Schleife dieser Algorithmen, solange es Änderungen gibt. D.h. wenn der Algorithmus z.B. schon nach Iteration 2 fertig ist, tragen Sie bei Iteration 3, …, 7 einfach Striche - - - - - - - - ein. Der Anfang ist bereits gemacht:

    nach Iteration Bubble Selection Insertion
    0 5 3 1 6 2 7 4 8 1 6 3 5 8 2 7 4 5 6 3 1 8 2 7 4
    1      
    2      
    3      
    4      
    5      
    6      
    7      
  2. Programmieren Sie nach dem Vorbild der Klassen Selection und Insertion eine Klasse Bubble mit einer Methode public static void sort(double[] a), die das übergebene Feld nach dem Bubblesort-Verfahren aufsteigend sortiert.
  3. Fügen Sie in die sort-Methode jeweils System.err.println()-Anweisungen ein (siehe Paragraphen 1.1-20 und 3.4-3), mit denen Sie die Richtigkeit Ihrer Eintragungen überprüfen können.

Spieglein, Spieglein an der Wand (I1-ID: chjj2bv0i6i0)

Programmieren und testen Sie eine statische Methode reverse, die ein char-Feld entgegenimmt, und seinen Inhalt "spiegelt". Also z.B. würde ein Feld mit Inhalt

b l a b a

nach Anwendung der Methode diesen Inhalt haben:

a b a l b

Versuchen Sie, das mit möglichst wenig "Tauschoperationen" zu programmieren.

Tipp für den Test: Paragraph 4.5-1 beachten.

Feldarbeit (I1-ID: 8b50bfu09mi0)

Welche Ausgabe erzeugt folgender Code?

public class Feldarbeit {
    public static void main(String[] args) {
        int[] a = { 0, 1, 2, 3, 4, 5, 6, 7};
        int N = a.length;
        for (int i = 0; i < N; i++) {
            a[i] = a[(i+4) % N];
        }
        for (int i = 0; i < N; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }
}

Verbunddaten

Schnitzeljagd (I1-ID: dam74qw0v6i0)

Angenommen x ist ein Knoten (genauer: eine Referenz auf einen Knoten) in einer einfach verketteten Liste nach dem Vorbild von [[http://www.stud.informatik.uni-goettingen.de/info1/java/Zahlspeicher.java][Zahlspeicher.java]]. Kreuzen Sie an, was der Aufruf des folgenden Codefragments bewirken kann:

x.next = x.next.next;
  • [ ] der auf x folgende Knoten wird aus der Liste entfernt.
  • [ ] der Knoten vor x.next wird aus der Liste entfernt.
  • [ ] Knoten x ist nicht mehr erreichbar vom Listenanfang aus.
  • [ ] die weiteren Knoten der Liste sind nicht mehr erreichbar.
  • [ ] einen Compilezeitfehler vom Typ "may not have been initialized".
  • [ ] einen Laufzeitfehler vom Typ "invalid reference".

Jägerschnitzel (I1-ID: gqh8c5x0v6i0)

Angenommen x ist ein Knoten (genauer: eine Referenz auf einen Knoten) in einer einfach verketteten Liste nach dem Vorbild von [[http://www.stud.informatik.uni-goettingen.de/info1/java/Zahlspeicher.java][Zahlspeicher.java]]. Auch t sei eine Knotenreferenz. Kreuzen Sie an, was der Aufruf des folgenden Codefragments bewirkt:

t.next = x.next;
x.next = t;
  • [ ] der Knoten t wird direkt nach x eingefügt.
  • [ ] der Knoten x wird direkt nach t eingefügt.
  • [ ] t ist Listennachfolger von x und umgekehrt.
  • [ ] t und x speichern die gleichen Werte.

Zusatzfrage: Warum bewirkt Nachstehendes Codefragment nicht das gleiche?

x.next = t;
t.next = x.next;

Referenzen als Ergebniswerte

Mischen possible? (I1-ID: yqpec491v2i0)

Programmieren und testen Sie eine Funktion, die zwei Argumente vom Typ int[] entgegennimmt, den Inhalt alternierend in einem neuen Feld speichert und die Referenz darauf liefert. Beispiel: werden [1,2,3] und [18,20,21] übergeben, soll im Ergebnis [1,18,2,20,3,21] stehen. Bei ungleicher Länge der Argumente soll mit RuntimeException abgebrochen werden.

Speicherorganisation

Alles an seinem Ort (I1-ID: hppcdc60x6i0)

Hier eine Variante der Klasse Person, die von der Skript-Version abweicht:

public class Person {
    private static int anzahl = 0;
    String name; 
    private int gebjahr;
    public Person(String name, int gebjahr) {
        this.name = name;
        this.gebjahr = gebjahr;
        anzahl++;
    }
    public String toString() { // Methode
        return name + " (" + gebjahr + ")"; 
    }
    public static void main(String[] args) { 
        Person[] p = new Person[3];
        p[0] = new Person("Max",1865);
        p[1] = new Person("Moritz",1865);
        p[2] = new Person("Witwe Bolte",1865);
        System.out.println("Es wurden " + anzahl + "Person-Objekte erzeugt:");
        for (int i = 0; i < anzahl; i++) {
            System.out.println(p[i]);
        }
    }
}

Ordnen Sie anzahl, args, p, p[0], p[0].gebjahr, i ihren Speicherorten zu:

  • Stack
  • Heap
  • Method Area.

Weiteres zu Strings

Ordnung ist auch das andere halbe Leben (I1-ID: 6e270yl0dji0)

Schreiben Sie eine statische Funktion mit einem String-Argument, die überprüft, ob die Zeichen im Argument alphabetisch sortiert sind.

Bevor Sie das machen, überlegen Sie, welche dieser Methodenköpfe für die Lösung in Frage kommen:

  • [ ] public static boolean alphabeticString(char[] arg)
  • [ ] public static boolean alphabeticString(String arg)
  • [ ] public boolean alphabeticString(char[] arg)
  • [ ] public boolean alphabeticString(String arg)
  • [ ] public String alphabeticString(char[] arg)
  • [ ] public static String alphabeticString(String arg)

Strings zu Fuß vergleichen (I1-ID: rtp12h7006i0)

Schlagen Sie nach, was es bedeutet, dass String s lexikographisch kleiner ist als String t (siehe z.B. Kapitel 7). Programmieren und testen Sie eine Methode public static boolean lexiLessThan(char[] s, char[] t), die die analoge Eigenschaft für char-Felder testet (siehe Paragraph 4.5-1).

Objektorientierte Programmierung

Klassentypen benutzen

Schwarz-Weiß-Malerei (I1-ID: vy0jdy30yji0)

Ergänzen Sie MyImageTools (siehe nvr0ke30yji0) um eine Methode threshold(String filename, double lum), die die angegebene Datei in einem Picture-Objekt ablegt und ein neues Picture-Objekt mit einem Bild anlegt: dessen Pixel weiß sind oder schwarz, je nachdem ob das Pixel im Originalbild eine Luminanz mindestens lum besitzt oder nicht.

Programmieren Sie modular, d.h. benutzen Sie auch die im Skript angegebene Luminanz-Bibliothek und legen Sie Ihre Klasse so an, dass ihre Funktionalitäten von anderen Klassen aus bequem benutzt werden können.

Ist \(\pi\) noch normal? (I1-ID: ii430g20yji0)

Nach Wikipedia: Eine reelle Zahl heißt normal, wenn unter ihren Ziffern für jedes \(k\) alle möglichen Ziffernblöcke der Länge \(k\) mit gleichen asymptotischen Häufigkeiten auftreten. D.h. in jedem genügend langen Anfangsabschnitt sind die Ziffern 0 bis 9 nahezu gleichhäufig, ebenso die Paare 00, 01, …, 99, die Tripel …, \(k\)-Tupel. Mit "asymptotisch" ist gemeint, dass diese Häufigkeiten mit wachsendem \(N\) gegen 1/10, 1/100, …, \(1/10^{k}\) konvergieren.

Überprüfen Sie, ob unter der ersten Million Ziffern von \(pi\) alle Ziffernpaare etwa gleichhäufig vorkommen. Kopieren Sie dazu https://introcs.cs.princeton.edu/java/data/pi-1million.txt in eine lokale Datei und programmieren Sie eine Java-Klasse, die

  • die Ziffernfolge in einen String einliest
  • ein \(char\)-Feld der Länge 100 anlegt und mit dem "Zähltrick" (siehe Skript) in einem Durchgang die vorkommenden Paare von Ziffern zählt
  • den Mittelwert und die Standardabweichung der ermittelten Häufigkeiten ausgibt (modular programmieren!: Methoden der Klasse StdStats benutzen, siehe Skript)

Was ist die Hauptstadt von … ? (I1-ID: 1cp6c210yji0)

Unter https://introcs.cs.princeton.edu/java/data/countries.csv finden Sie eine csv-Datei mit geopolitischen Daten. Legen Sie eine lokale Kopie dieser Datei an und programmieren Sie eine Klasse, die

  • diese Datei öffnet und den Inhalt in einen String einliest (In: readAll())
  • die Land/Hauptstadt-Angaben in ein zweidimensionales Feld von Strings einliest (eine lange Matrix mit zwei Spalten: eine für den Landes- und eine für den Hauptstadt-Namen), dazu die split(...)-Methode aus String verwenden
  • ein main-Methode enthält, die solange Eingaben geliefert werden, diese als Landesnamen interpretiert, in dem Feld sucht und den zugehörigen Hauptstadt-Namen ausgibt

Programmieren Sie prozedural, d.h. kapseln Sie die einzelnen Funktionalitäten in statischen Methoden.

Die Frage aller Fragen … (I1-ID: 1ew519x04hi0)

Weisen Sie durch eine Java-Programm nach, dass \[-80538738812075974^3+80435758145817515^3+12602123297335631^3 = 42.\]

Was daran so toll ist lesen Sie hier.

Wenn Java den Umgang mit so großen Zahlen verweigert, holen Sie sich hier Rat.

Kunterbunt (I1-ID: euzc58z03ki0)

https://www.w3schools.com/colors/colors_names.asp bietet eine Liste mit 140 HTML-Standardfarben. Beschaffen Sie sich diese Hexcodes und schreiben Sie ein Programm, das zu zufällig gewählten RGB-Werten eine möglichst nahe gelegene HTML-Standardfarbe findet. Stellen Sie die Zufalls- und die Standardfarbe geeignet mittels StdDraw.filledSquare(..) dar, um ein Gefühl dafür zu bekommen, wie "möglichst nahe gelegen" präzisiert werden kann.

Klassentypen implementieren

Wieder mal aufladen (I1-ID: kvt2s3e0yji0)

Entwickeln Sie eine Klasse VarCharge, die Teilchen mit veränderlicher Ladung modelliert. Sie soll im Prinzip so implementiert werden wie Charge, aber diese etwas breitere Schnittstelle bieten:

  public class VarCharge  
  VarCharge(double x0, double y0, double q0) Konstruktor
void increaseCharge(double diff) erhöht die Ladung des Teilchens um diff
double potentialAt(double x, double y) hervorgerufenes Potential bei \((x,y)\)
String toString() String-Darstellung

Der Testclient (also die main-Methode) soll Ladungsveränderungen wie folgt visualisieren:

public static void main(String[] args) {
    VarCharge[] a = new VarCharge[3];
    a[0] = new VarCharge(.4,.6,50);
    a[1] = new VarCharge(.5,.5,-5);
    a[2] = new VarCharge(.6,.6,50);
    int SIZE = 800;
    Picture pic = new Picture(SIZE, SIZE);
    for (int t = 0; t<100 ; t++) {

        // Bildberechnung - siehe Potential.java

        pic.show();
        a[1].increaseCharge(-2);
    }
}

Noch eine Ladung (I1-ID: 4786jqd02ki0)

Der folgende Code ist fehlerhaft. Was ist das Problem?

public class Charge {
    private double rx, ry; 
    private double q;
    public Charge(double x0, double y0, double q0) {
        double rx = x0;
        double ry = y0;
        double q = q0;
    }
    // ... Instanzmethoden usw.
}

Zeit müsste man haben (I1-ID: s4k9gxd02ki0)

[aus Sedgewick/Wayne]

Entwickeln Sie eine Klasse Zeit, die die Tageszeit modelliert. Stellen Sie Methoden getHour(), getMinute(), getSecond() Verfügung, die die aktuelle Stunde, Minute und Sekunde zurückliefern, zusätzlich eine Methode seconds(), die die Anzahl der sekunden seit Mitternacht liefert, sowie die Methoden toString() und compareTo(). Speichern Sie die Zeit intern in einem einzigen Wert, nämlich der Anzahl der Sekunden seit Mitternacht.

Statten Sie die Klasse außerdem mit einem Testclient aus, der die Funktionalitäten ausgiebig testet.

Die aktuelle Zeit kann man sich so beschaffen:

import java.util.Calendar;
import java.util.GregorianCalendar;

public class WieSpaetIstEs {
    public static void main(String[] args) {
        Calendar c = new GregorianCalendar();
        int h = c.get(Calendar.HOUR);
        int m = c.get(Calendar.MINUTE);
        int s = c.get(Calendar.SECOND);
        System.out.printf("%2d:%2d:%2d\n",h,m,s);
    }
}

Das gleiche oder das selbe? (I1-ID: sdja2qh0hji0)

Das folgende Codefragment wird ausgeführt.

String s1 = new String("Hi There");
String s2 = new String("Hi There");
String s3 = s1;

boolean a = (s1 == s2);
boolean b = (s1.equals(s2));
boolean c = (s1 == s3);
boolean d = (s2.equals(s3));

Welche Variablen sind nun true?

  • [ ] a und d
  • [ ] b, c und d
  • [ ] a, b, c und d
  • [ ] nur b
  • [ ] nur d

Ja, mir san mit’m Radl da (I1-ID: fjogkxq088i0)

Implementieren Sie eine Klasse Fahrrad, die folgenden Anforderungen genügen soll:

(a)
Der Zustand eines Fahrrad-Objekts wird durch seine Geschwindigkeit und die Anzahl der Gänge beschrieben. Benutzen Sie hierfür die Attribute speed und gears, beide vom Typ int. Ein Zugriff auf die Attribute ist von außerhalb der Klasse nicht möglich.
(b)
Die Klasse besitzt einen Standardkonstruktor, der die Geschwindigkeit mit 0 und die Anzahl der Gänge mit 1 initialisiert.
(c)
Die Klasse besitzt einen weiteren Konstruktor mit zwei Parametern zur Initialisierung der Attribute.
(d)
Die Klasse besitzt eine Methode zum Ändern der Geschwindigkeit. Die neue Geschwindigkeit wird als Parameter übergeben.
(e)
Die Klasse besitzt eine Methode zum Setzen der Anzahl der Gänge. Die Anzahl wird dabei als Parameter übergeben.
(f)
Auf die Klasse, die Konstruktoren und auf die Methoden kann von jeder anderen Klasse aus zugegriffen werden.

Uhrenfälscher (I1-ID: bweavr61w6i0)

Ergänzen Sie Stopwatch.java um eine Methode public Stopwatch copy(), die eine Kopie dieser Stopwatch liefert.

Vererbung

Biologisch dynamisch aktiv (I1-ID: 2v7hvu40x6i0)

Betrachten Sie folgende Klassen und beantworten Sie darunterstehenden Fragen ohne einen Computer zu Hilfe zu nehmen.

1: public class Katze {
2:     private String name;
3:     public Katze(String name) {
4:         this.name = name;
5:     }
6:     public String miezmiez() {
7:         return "Fauch!";
8:     }
9: }
1: public class Hauskatze extends Katze {
2:     private String name; 
3:     public Hauskatze(String name) {
4:         super(name);
5:     }
6:     public String miezmiez() {
7:         return "Miau Miau";
8:     }
9: }
 1: public class Tierfreund {
 2:     public static void main(String[] args) {
 3:         Hauskatze h = new Hauskatze("Schnurri");
 4:         Katze k = new Katze("Garfield");
 5:         System.out.println(((Katze)h).miezmiez());
 6:         System.out.println(((Hauskatze)k).miezmiez());
 7:         k = h;
 8:         System.out.println(((Hauskatze)k).miezmiez());
 9:     }
10: }
  1. In Tierfreund ist eine Zeile fehlerhaft. Welche Zeile ist es?
  2. Geben Sie an, welche Art Fehler die Zeile bewirkt (Compile- oder Laufzeitfehler).
  3. Welche Ausgabe erzeugt java Tierfreund wenn die fehlerhafte Zeile gestrichen wird?

Let me entertain you (I1-ID: 6aic7er088i0)

Medien.png Bücher besitzen einen Titel und einen Autor, Filme einen Titel und eine Spieldauer. Implementieren Sie die gezeigte Klassenhierarchie wie folgt:

  1. Implementieren Sie eine Klasse Medium. Sie definiert das Attribut title vom Typ String, zur Speicherung des Titels. Implementieren Sie einen Konstruktur zu seiner Initialisierung mit einem angegebenen Wert. Stellen Sie sicher, dass alle Erweiterungsklassen von Medium eine Methode void report() implementieren müssen, die Werte aller Attribute auf die Konsole ausgeben.
  2. Implementieren Sie die Erweiterungsklasse Buch mit dem zusätzlichen Attribut author vom Typ String, zur Speicherung des Autors. Implementieren Sie einen Konstruktur zur Initialisierung aller Attribute mit angegebenen Werten. Stellen Sie sicher, dass Buch-Objekte erzeugt werden können.
  3. Implementieren Sie die Erweiterungsklasse Film mit dem zusätzlichen Attribut duration vom Typ int, zur Speicherung der Spieldauer. Implementieren Sie einen Konstruktur zur Initialisierung aller Attribute mit angegebenen Werten. Stellen Sie sicher, dass Film-Objekte erzeugt werden können.

Rosarote Brille (I1-ID: rqt2xn013ki0)

Ergänzen Sie die folgende Klasse um eine toString-Methode, die den String der RGB-Werte um den Namen der Farbe ergänzt, falls bekannt.

import java.awt.Color; 

public class NamedColor extends Color {
    public NamedColor(int r, int g, int b) {
        super (r,g,b);
    }
}

Tipp: Mit ein bisschen Screenscraping einmalig eine Tabelle mit Farb-Hexcodes und zugehörigen Namen erzeugen und Nachsehen in der Tabelle mittels binärer Suche in toString() erledigen. Siehe dazu euzc58z03ki0.

Abstrakte Datentypen

Hochstapelei (I1-ID: g3q153t0dli0)

Ergänzen Sie das Interface StackOfInts durch die Spezifikation

public int size(); // liefert die Anzahl gespeicherter Elemente

und ergänzen Sie ArrayStackOfInts.java und EVLStackOfInts.java entsprechend, um das Interface wie im Kommentar beschrieben zu implementieren.

Queue aus zwei Stacks bauen (I1-ID: a4g40y31x4h0)

QueueAus2StacksMitText.png

Mit zwei Stacks kann man eine Queue implementieren:

  • enqueue(...) entspricht Einspeichern in inbox
  • dequeue() entspricht Ausspeichern aus outbox.

Unter Verwendung dieser API

public class Stack  
boolean empty() testet, ob dieser Stack leer ist
void push(String s) speichert s in diesem Stack
String pop() liefert zuletzt gespeicherten String aus diesem Stack und entfernt ihn

sähe die entsprechende Klasse z.B. so aus:

 public class ZSQueue { // Zwei-Stack-Queue
     private Stack inbox, outbox;     
     public ZSQueue() { ... }
     public boolean empty() { ... }        // Leerheitstest
     public void enqueue(String s) { ... } // einspeichern
     public String dequeue() {             // ausspeichern und liefern
         // Rumpf (Ihre Aufgabe)
     }
 }

Programmieren Sie den Rumpf der Methode dequeue():

  • ist die Queue leer, ist Ausspeichern nicht möglich!
  • teste ob outbox leer ist und fülle in diesem Fall den kompletten Inhalt von inbox um in outbox, dann ein Element aus outbox ausspeichern und liefern.

Stack aus einer Queue bauen (I1-ID: rr0faxt0dli0)

Das geht so:

  • empty() wird unverändert übernommen
  • enqueue(..) kann push(..) unmittelbar ersetzen
  • pop() wird simuliert durch eine geeignete Anzahl von x = q.dequeue(); q.enqueue(x);-Paaren, gefolgt von x = q.dequeue();

Überlegen Sie sich das mal.

Umstapeln (I1-ID: pmhgc6q0mtg0)

Auf einem Stack werden in gemischter Reihenfolge 10 Push- und 10 Pop-Operationen ausgeführt. Es ist bekannt, dass die Push-Operationen die Zahlen 0, 1, 2, …, 9 in dieser Reihenfolge einspeichern und dass bei jedem Pop der ausgespeicherte Wert ausgegeben wird. Geben Sie an, welche Ausgabelisten dabei möglich sind:

  • [ ] 4 3 2 1 0 9 8 7 6 5
  • [ ] 4 6 8 7 5 3 2 9 0 1
  • [ ] 2 5 6 7 4 8 9 3 1 0
  • [ ] 1 4 7 9 8 6 5 3 0 2

Durchschlängeln (I1-ID: 8d55b4p0krg0)

Auf einer Queue werden in gemischter Reihenfolge 10 Enqueue- und 10 Dequeue-Operationen ausgeführt. Es ist bekannt, dass die Enqueue-Operationen die Zahlen 0, 1, 2, …, 9 in dieser Reihenfolge einspeichern und dass bei jedem Dequeue der ausgespeicherte Wert ausgegeben wird. Geben Sie an, welche Ausgabelisten dabei möglich sind:

  • [ ] 4 6 8 7 5 3 2 9 0 1
  • [ ] 2 5 6 7 4 8 9 3 1 0
  • [ ] 0 1 2 3 4 5 6 7 8 9
  • [ ] 4 3 2 1 0 5 6 7 8 9

Compilerbau (I1-ID: bbve4zg0l6i0)

Nutzen Sie Evaluate als Codesteinbruch für einen "Infix2Postfix-Compiler":

  • Werte sofort ausgeben, nicht speichern
  • ( und Ops in Stack speichern, bei ) Stackinhalt bis vor ( ausgeben, die Klammern selbst jedoch nicht.

Klammeraffe (I1-ID: 1340g990m6i0)

Überzeugen Sie sich, dass Evaluate tatsächlich wie am Ende von Kapitel 5 behauptet, vollständig geklammerte Ausdrücke sowohl in Infix- als auch in Postfix-Schreibweise richtig verarbeitet.

Beispiel: ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) und ( 1 ( ( 2 3 + ) ( 4 5 * ) * ) + )

Wofür sind bei dieser Implementierung die Klammern im Postfix-Ausdruck noch nötig? Modifizieren Sie die Klasse so, dass Berechnungen bereits durch das Lesen eines Operators angestoßen werden (d.h. auch 1 2 3 + 4 5 * * + würde korrekt verarbeitet werden — Infix-Ausdrücke allerdings nicht mehr richtig).

Money, Money, Money, … (I1-ID: nzccrug0l6i0)

Programmieren Sie die Methode compareTo(..) für die Klasse Geld implements Comparable<Geld>.

Analyse von Algorithmen

Performance-Betrachtungen

Profiling (I1-ID: shr3p5e078i0)

Man kann die Ausführungs-Vielfachheit \(V(N)\) der Kernoperation durch das Programm selbst berechnen lassen! Hier ein Beispiel, bezogen auf ThreeSum.java:

Wie lautet der Wert von x nach Ausführung des folgenden Codefragments?

int x = 0;
for (int i = 0; i < N; i++) 
    for (int j = i+1; j < N; j++) 
        for (int k = j+1; k < N; k++) 
            x++;

Eine lehrreiche Studie (I1-ID: cl5kwza1o7i0)

[eine Anregung aus Sedgewick/Wayne (S. 520 in der deutschen Ausgabe von 2011) etwas ausgebaut]

  1. Studieren Sie den Quelltext TimePrimitives.java und überzeugen Sie sich davon, dass die Messmethodik im wesentlichen sinnvoll ist. Die int-Additionszeit wird auf zwei verschiedene Weisen gemessen (einmal am Anfang und einmal am Ende). Haben Sie eine Vermutung, welche der beiden verlässlichere Werte liefert?
  2. Führen Sie das Programm auf verschiedenen Rechnersytemen bzw. verschiedenen Java-Implementationen mehrfach aus. Erhöhen Sie dabei den Kommandozeilenparameter n soweit, bis sich die Messwerte stabilisieren. Bestätigt sich Ihre obige Vermutung?
  3. Beobachten Sie, dass für int-Subtraktion deutlich kürzere Zeiten bestimmt werden als für die Addition. Erklären Sie den Effekt anhand des Quelltextes (Tipp: Berechnung für kleine Werte von \(n\) nachverfolgen). Versuchen Sie Ihre Überlegungen durch weitere Experimente mit entsprechend veränderter Messmethodik (wenigstens teilweise) zu bestätigen.
  4. Stellen Sie den veränderten Quelltext so um, dass zunächst die Subtraktionszeit gemessen wird und dann die Additionszeit. Was beobachten Sie bei erneuter Ausführung? Haben Sie eine Erklärung?
  • Lösungsvorschlag
    1. Die erste der beiden Messmethoden wirkt verlässlicher, da bei der zweiten die Variable k in jeder Iteration der äußeren Schleife neu deklariert wird. Die Ausführung des Codes ähnelt dem Aufruf von Funktionen: Für jede Neuinkarnation der Variablen muss ein Stackframe angelegt werden. Der zusätzliche Verwaltungsaufwand für den Laufzeitstapel kann die Zeitmessung verfälschen, die Vermutung liegt nahe, dass bei der zweiten Messung höhere Werte ermittelt werden.
    2. Auf verschiedenen Systemen getestet scheinen sich die Messwerte bei Größenordnungen ab \(n\)~10000 zu stabilisieren. Allerdings bestätigt sich die Vermutung nicht! Mögliche Gründe werden unter 4. angesprochen.
    3. Die Zweierkomplement-Arithmetik (Paragraph ~2.1-12) lässt ähnliche Laufzeiten für Addition und Subtraktion von Ganzzahlen erwarten. Mit TimePrimitives gemessene Laufzeitunterschiede sind möglicherweise darauf zurückzuführen, dass k bei Messung der Addition etwa die Größe \(n^{2}/2\) erreicht, bei der Subtraktion jedoch nur \(n/2\), so dass bei letzterer entsprechend weniger Dualziffern zu verarbeiten sind. Folgende Modifikation bestätigt diese Erklärung wenigstens teilweise, denn sie bringt höhere Messwerte für die Subtraktionszeit:

             /***************************************************************
              * integer subtraction
              ***************************************************************/
              // ...
                      k = j - k;        // <--- anstelle k = j - k 
              // ...
      
    4. Wird bei dem so geänderten Code die Reihenfolge umgestellt (Subtraktion vor Addition), dann ist der umgekehrte Effekt zu beobachten: die Messwerte für die Additionszeit sind nun geringer als für die Subtraktionszeit. Erklärungsversuch: Ein Aspekt der Java-Virtual-Machine (JVM) ist, dass beim Interpretieren von Bytecode ja zunächst der stattdessen auszuführende native Maschinencode bestimmt werden muss (siehe Paragraphen 3.2-6 und 3.2-7). Dieses Prinzip nennt man Just-In-Time-Compilation (JIT) und ist sogar mehrfach nebenläufig organisiert, d.h. nach anfänglicher Analyse werden mehrere "JIT-Threads" gestartet für einzelne Abschnitte des Bytecodes. Dies ermöglicht, bereits bestimmten nativen Code bei nächster Gelegenheit wiederzuverwenden, also automatische Codeoptimierung zur Laufzeit. Es gibt gewisse Möglichkeiten, auf die JIT-Compilation Einfluss zu nehmen (siehe man java) und damit diese Begründung zu validieren.

      Optimierung zur Laufzeit kann eventuell auch den unter 2. erwähnten Effekt erklären. Ein weiterer Grund ist vielleicht auch die Code-Optimierung, die javac vornimmt. Der Compiler kann sicher feststellen, dass

      for (int i = 1; i <= n; i++) {
          int k;
          for (int j = 1; j <= n; j++) {
              k = i + j;
          }
      }
      

      gleichwertig ist zu

      {
          int k;
          for (int i = 1; i <= n; i++) {
              for (int j = 1; j <= n; j++) {
                  k = i + j;
              }
          }
      }
      

      und entsprechend effizienteren Bytecode bereitstellen (genauer ließe sich das durch Dissassemblierung überprüfen, siehe Aufgabe fwsets601ng0). Zusammen mit dem "Größeneffekt" (siehe 2.) und dem "JIT-Effekt" erklärt das die extrem kurzen Messzeiten für int-Addition nach dieser Methode.

Beck's exploit (I1-ID: rvn4zjz07ji0)

(nach Sedegwick/Wayne)

  1. Die Linux-Shell ignoriert mehrfache Slashes in Pfadangaben (sogenannte "null path components"), z.B.

    cd ~/info1////demo////v09// anstelle cd ~/info1/demo/v09/

    Überprüfen Sie das an einem kleinen Besipiel in ihrem Homeverzeichnis.

    Webserver (die allermeisten laufen auf Linux-Systemen) dürfen jedoch "null path components" nicht ignorieren: Wenn zum Beispiel die URL http://some.whe.re/over/the/rainb.ow nicht öffentlich sein soll, aber an Bevorrechtigte nach Passworteingabe ausgeliefert werden soll, so könnte ein einfacher Sicherheitsmechanismus unprivilegierte Anfragen danach ausfiltern. Aber auch maskierte Anfragen http://some.whe.re////over////the/rainb.ow müssten gefiltert werden.

  2. Der Apache Webserver unterstützt eine Funktion no2slashes, die in char-Feldern alle Slash-Gruppen durch einzelne Slashes ersetzt. So ähnlich sah eine frühe Implementation aus:

    void no2slashes(char[] name) {
        int N = name.length;
        for (int i = 0; i< N; ) {
            if (i > 0)
                if ((name[x-1] == '/') && (name[x] == '/' ))
                    for (int j = 0; j < N; j++) {
                        name[j-1] = name[i];
                    }
                else i++;
        }
    }
    
    • Überzeugen Sie sich, dass die Funktion das Gewünschte leistet.
    • Welches worst-case-Laufzeitverhalten hat die Funktion bezogen auf \(N\)?
  3. "Beck's exploit" (siehe https://www.redhat.com/archives/linux-security/1998-January/msg00001.html) ist eine Denial-of-Service-Attacke, die darin besteht, Webserver mit dieser Implementierung mit worst-case-Anfragen zu überfluten, so dass er schließlich überlastet ist.

    Geben Sie eine Implementierung mit \(O(N)\) Laufzeitverhalten an.

Wachstumsordnungen

Geschwindigkeitsrausch (I1-ID: 65f3v3b078i0)

Sind \(f, g\) Funktionen, die nur positive Werte annehmen so sagen wir \(f\) wächst langsamer als \(g\), falls \[\lim_{n\rightarrow\infty} \frac{f(n)}{g(n)} = 0.\] und wir schreiben dafür \(f\prec g\).

Ordnen Sie diese Funktionen von unten nach oben aufsteigend bezüglich \(\prec\):

  • \(\frac{1}{2}n\log n\)
  • \(n^2\)
  • \(\sqrt{n^3}\)
  • \(n^n\)
  • \(100n^2+10n^3\)
  • \(2\log n\)
  • \(n^4\)
  • \(\log \log n\)

(Logarithmen zur Basis 2.)

logloglog ist fast konstant (I1-ID: 8940xub078i0)

Die Anzahl der Atome im Universum wird auf \(< A = 10^{90}\) geschätzt.

  • Wie groß ist \(\log\log\log A\)?
  • Geben Sie das minimale \(n\) an, so dass \(\log\log\log10^{n}>4\).

(Logarithmen zur Basis 2.)

Ma-Tilda (I1-ID: plsh56c078i0)

Verwenden Sie die Tilde-Notation, um folgende Formeln zu vereinfachen und geben Sie jeweils die Wachstumsordnung an:

exakt asymptotisch Wachstumsordnung
\(N(N-1)(N-2)(N-3)/24\)    
\((N-2)(\log N-2)(\log N + 2)\)    
\(N(N+1)-N^2\)    
\(N(N+1)/2+N\log N\)    
\(\log((N-1)(N-2)(N-3))^2)\)    

Tilde- und andere Notationen (I1-ID: aed69s71bqg0)

Gesucht ist jeweils die Funktion \(g(n)\) einfachster Gestalt mit \(f(n)\sim g(n)\):

  1. \(f(n)\) ist der Wert von \(x\) nach Ausführung des folgenden Fragments:

      int x = 5;
      for (int i = 0; i < n; i++)
          x++;
    
  2. \(f(n)\) ist der Wert von \(x\) nach Ausführung des folgenden Fragments:

      int x = 2;
      for (int i = 0; i < n; i++)
          if ( i % 3 == 0)
              x++;
    
  3. \(f(n)\) ist der Wert von \(x\) nach Ausführung des folgenden Fragments:

      int x = 0;
      for (int i = 0; i < n; i++)
         for (int j = i + 1; j < n; j++)
             x++;
    

Wie kann man denn solche Funktionen mit der Tastatur notieren, sollte man mal in die Verlegenheit kommen … ;-)

Ganz einfach: z.B. für Potenzen \(n^2, n^3, ...\) schreibt man n^2, n^3, für Quadratwurzeln sqrt(n), für (Zweier)Logarithmen log(n) … ansonsten benutzt man Zahlen wie üblich und auch die üblichen Operatorzeichen +, *, -, / für Addition, Multiplikation, Subtraktion, Division aber keine Leerzeichen.

Euklid gegen Stein (I1-ID: xvub89y0m2i0)

Programmieren Sie den Steinschen Algorithmus. Verwenden Sie ihn in einem separat zu programmierenden Verdopplungstest sowohl für den Steinschen als auch für den Euklidischen Algorithmus und vergleichen Sie die Laufzeiten.

Welches asymptotische Laufzeitverhalten vermuten Sie für die beiden Algorithmen?

Hinweis: Anstatt die Anzahl der Eingaben zu verdoppeln, muss die Stellenzahl der Eingaben verdoppelt werden. Bilden Sie außerdem die mittlere Laufzeit über viele Läufe (ähnlich wie bei TimePrimitives.java).

Laufzeitvorhersagen

Clever gemacht (I1-ID: 9azg8hl0q7i0)

Programmieren Sie die Idee aus Paragraph 6.3-1 für einen quadratische Lösung für das 3-Sum-Problem.

Hinweis: https://en.wikipedia.org/wiki/3SUM

Schätzen Sie mal! (I1-ID: mz1eagc078i0)

Eingabegröße \(N\) Laufzeit
1000 5s
2000 20s
3000 45s
4000 80s
5000 ??
  • Was vermuten Sie? Ist der Algorithmus linear, loglinear, quadratisch, kubisch oder exponentiell?
  • Welche Laufzeit vermuten Sie für \(N=5000\)?

Ergänzungen

Ein weites Feld (I1-ID: to5760r069i0)

Beim Start der JVM kann man steuern, wieviel Heap-Speicher zur maximal zur Verfügung stehen soll. Beispiel:

java -mx2M <Applikation>

erlaubt maximal 2Mb Heap-Speicher (siehe man java für weitere Einstellungen).

Was bedeuten 2MB (oder eine andere Vorgabe) an Heap-Speicher für die Größe von Feldern, die angelegt werden können? Programmieren und testen Sie einen entsprechenden Verdopplungstest, bei dem Felder immer größerer Länge angefordert werden, bis das Programm mit OutOfMemoryError abbricht.

  • Lösungsvorschlag

Sortieren und Suchen

Bubble (I1-ID: 4u1e78l0q7i0)

Implementieren Sie Bubblesort aus Paragraph 2.3-6 Methode public static void sort(double[] f) in einem Modul Bubble.

Analysisieren Sie die Anzahl der Vergleiche bei Bubble-Sort asymptotisch, untersuchen Sie best-, worst- und average-case.

Bauen Sie zur Bestätigung der Analyse main als bequemen Testclient aus, der bei Aufruf ohne Parameter Verdopplungstests für best-, worst- und average-case Eingaben macht und berichtet.

Insertionsort andersrum (I1-ID: hldj1h80z5i0)

Bei Insertionsort (Kapitel 4) wird der sortierte Abschnitt verlängert, indem das neue Element an der richtigen Stelle eingefügt wird. Die Einfügestelle wird dabei "rückwärts" (nach links gehend) gesucht. Man könnte auch von vorn ausgehend "vorwärts" danach suchen.

Was sind in diesem Fall die best- und die worst-case-Eingaben? Überprüfen Sie Ihre Vermutung durch Programmierung dieser Variante mit zusätzlichen Anweisungen zum Zählen der Tauschoperationen.

Ringpuffer (I1-ID: 61qk69g0l6i0)

Implementieren und testen Sie einen Ringpuffer mit dynamischer Größenanpassung (ähnlich, wie bei ArrayStackOfInts)

Datum: <2022-01-11 Di>

Autor: Carsten Damm

Created: 2021-12-30 Do 14:24

Emacs 24.3.1 (Org mode 8.3.4)

Validate