21 Dec 08 Kleine Zusatzaufgabe zur Landau-Notation
Ich weiß nicht, wer schon alles mit der Landau-Notation vertraut ist (und auch mit der Komplexitätstheorie von Algorithmen). Aber als kleine Zusatzaufgabe´ zur Hausaufgabe vom Blatt 6 (weil ich sie gerade korrigiere) folgendes:
Welche Laufzeiten (ala O(n), etc.) hat der Primzahltest normalerweise, wenn wir ihn so programmieren wie in der Musterlösung zur 1a)?
static boolean isPrime(int p ) {
for( int k = 2 ; k * k <= p ; k++ ) {
if( p % k == 0 ) {
return false;
}
}
return true;
}
[/sourcecode]
Fleißaufgabe:
Wie sieht's mit den Laufzeiten der anderen Funktionen aus?
Man kann die Lösung wahrscheinlich leicht mit Google finden, aber es an sich ganz nett da selber einmal darauf zukommen.
19 Dec 08 Blatt 8, Zusatzaufgaben
Zum Blatt 8 folgende Zusatzaufgaben:
Aufgabe 2:
j) Schreiben Sie in der Klasse TimeTable eine Methode
public int addTrainArrival( string nameOfTrain, Date arrivalTime ) { … }
welche zur gegebenen Zeit versucht ein freies Gleis für den Zug zu finden und falls dies möglich ist eine TrainConnection mit den Informationen erstellt und hinzugefügt. Die Methode gibt dies Nummer des Gleises zurück, falls ein Gleis gefunden wurde, ansonsten -1.
k) Schreiben Sie in der Klasse TimeTable eine Methode optimizeForTransitPassengers, die die TrainConnections in der TimeTable dahingehend optimiert, dass Passagiere von Zügen, die zu ähnlichen Zeiten ankommen, möglichst wenige Gleise von einem Zug zum nächsten laufen müssen, falls sie umsteigen wollen´.
Hinweis:
Es ist sinnvoll den Fahrplan um mehr TrainConnections zu erweitern – am besten mit einer For-Schleife weitere Einträge hinzufügen.
Aufgabe 3:
d) Natürlich die Potenzmenge bestimmen 
Also:
public staic <S> Set<Set<S>> powerSet( Set<S> s ) {…}
19 Dec 08 Blatt 8 – Eclipse Hilfen für den Anfang
Ein paar kleine Hilfsstellungen zum Einstieg, damit man vielleicht doch nicht ganz verloren ist:
12 Dec 08 Heuristiken zum Aufgabenlösen
Frisch aus der Übung von heute die Zusammenfassung der Heuristiken:
- Die Aufgebenstellung immer mehrmals lesen um sie auch wirklich voll zu erfassen
- Sich selbst Fragen zum Problem stellen und diese beantworten (dadurch kann man das Problem auch besser erfassen)
- Das Problem für Beispiele per Hand lösen
- Teilprobleme suchen und lösen
- Skizzen anfertigen
- Das Problem anders beschreiben:
- mit anderen Worten beschreiben
- Definitionen anwenden
- ein “mathematisches Modell” entwickeln (also versuchen das Problem mathematisch zu beschreiben)
- ein leichteres Problem (eine Vereinfachung) zuerst lösen und dann auf das schwerere Problem verallgemeinern
- Sonderfälle suchen und untersuchen
(z.B. sind oft die Sonder-/Extremfälle eines Problems gerade die Basisfälle eines rekursiven Lösungsansatzes
Meistens hilft wiederholtes Anwenden/Iteration und auch die Kombination solcher Ansätze um auf die Lösung zu stoßen.
Tags: Probleme lösen
12 Dec 08 Blatt 7 Aufgabe 3
Ein kleines “Gerüst” für die Aufgabe 3: aufgabe3.zip
Zusatzaufgabe:
d) Füge zuerst zu Lines eine Funktion hinzu
static void drawLine( double[][] image, double color,
double x1, double y1, double x2,
double y2, double width )
die eine Linie mit variabler Breite width zeichnet (linkes Teilbild unten) und dann eine Funktion
static void drawSmoothLine( double[][] image, double color,
double x1, double y1, double x2,
double y2, double width )
die analog zu drawLine eine weiche Line der Breite width einzeichnet. So wie die Linie auf dem rechten Teilbild:
Tags: Anti-Aliasing, Aufgabe 3, Blatt 7
12 Dec 08 For Each-Schleifen Beispiel
Hier ein einfaches Beispiel für das for each Schleifen-Konstrukt in Java:
public class ForEachExample { public static void main(String[] args) { int[] feld = new int[] { 1,2,3,4 }; for ( int eintrag : feld ) { System.out.println( eintrag ); } } }Tags: Blatt 7
12 Dec 08 Wiederholung: Arrays
Eine kurze Übersicht der wichtigsten Array-Befehle:
Deklarieren einer Array-Referenz/Variable:
int[] integerArray; // allgemein: // T[] tArray; // T kann selbst wieder vom Typ Array sein, also T := U[] usw..Erstellen eines neuen Array-Objektes:
integerArray = new int[5]; // Erstellen eines neuen Array-Objektes: integerArray = new int[5]; // geht leider nicht!!! // integerArray = new int[3] { 3, 1, 4 }; // oder: integerArray = new int[] { 3, 1, 4, 1, 5, 6, 9 }; // wo ist der Fehler (Achtung: Scherzfrage)Zugriff auf ein Element in einem Array
System.out.println( integerArray[0] + "," + integerArray[1] + integerArray[2] + integerArray[3] + " ist ca. \pi" ); // Zuweisen eines Wertes analog: integerArray[5] = 9; integerArray[6] = 2; // besser, eh?Abfragen der Länge eines Arrays:
// mit .length System.out.println( "\pi auf " + integerArray.length + " - 1 Stellen genau:" ); // man indiziert mit int Variablen dynamisch: System.out.print( "\pi ~ " + integerArray[0] + "," ); // wir fangen jetzt ab der ersten Nachkommastelle an (also 2. Element im Array) for( int i = 1 ; i < integerArray.length ; i++ ) { System.out.print( integerArray[i] ); } System.out.println(); [/sourcecode]</pre> Überprüfung auf Gleichheit: <pre> // wie bei Strings mit .equals int[] arrayA = new int[] {1, 2, 3, 3}; int[] arrayB = new int[] {3, 2, 1}; int[] arrayC = new int[] {1, 2, 3, 4}; System.out.println( arrayA.equals( arrayA ) ); // true System.out.println( arrayA.equals( arrayB ) ); // false System.out.println( arrayA.equals( arrayC ) ); // falseCode: ArrayExample.java
Tags: Blatt 7
10 Dec 08 Aufgaben zur prozeduralen Programmierung (TODO)
Hier ein paar Übungsaufgabe zur prozeduralen Programmierung. Vorab kann ich aber nur empfehlen die Aufgaben aus dem Praktikum auch zu wiederholen und zwar so lange, bis man die Schleifen-Konstrukte im Schlaf beherrscht und die Aufgaben auch so kein Problem mehr darstellen.
Außerdem empfiehlt es sich generell zusätzlich zu Vorlesungen noch weitere Literatur zu benutzen, in unserem Falle also einerseits ein Buch zum theoretischen Teil der Vorlesung (es empfiehlt sich wahrscheinlich das Buch von Prof. Broy) und eines für Java, wobei da wohl jedes Java-Buch gleichermaßen geeignet ist.
Die andere Darstellung der Inhalte ist oft hilfreich und man bekommt ein besseres Gefühl für die Sprache selber – wobei natürlich das Schreiben von Java-Code die beste Möglichkeit ist um die Sprache zu lernen!Code Convention für Java
Diese Aufgabe wird wahrscheinlich noch in einen eigenen Blogeintag erweitert werden, aber insbesondere in Hinblick auf die Klausur (für die Korrektur) und die Tatsache, dass wir jetzt langsam richtig in die Programmierung einsteigen, möchte ich eine Link posten, der für Anfänger hilfreich sein sollte und auch für diejenigen, die schon mehr Java programmiert haben, interessant sein kann:
Code Conventions for the Java Programming Language
Hierbei handelt es sich um ein ziemlich ausführliches Handbuch, wie der Java-Code von Sun (den Erfindern von Java) formatiert werden soll.
Man kann sich über die genaue Formatierung von Code streiten (in einschlägigen Foren finden sich mehr als genügend Beispiele dafür), aber auf jeden Fall sollte der Quellcode, den man schreibt einheitlich formatiert werden und auf eine Art und Weise, die sowohl übersichtlich ist als auch der Syntax der Sprache gerecht wird.Beim jetzigen Stand in den Übungen kann ich das Kapitel 1 Introduction (ein sehr kurzer Text) und das Kapitel 7 Statements empfehlen.
Ich bin selber nicht mit allem einverstanden, was teilweise in den anderen Kapiteln steht, aber dieses Dokument ist ein guter Einstiegspunkt und gibt gute Hinweise darauf, wie man seinen Code formatieren sollte.Als generelle $$\pi$$ mal Daumen-Regel kann ich ansonsten nur sagen: “Jede Anweisung in ihrer eigenen Zeile.”
Aufgaben
Texthaus
Als Vorbeitung empfiehlt sich die Aufgabe 2 vom Übungsblatt 6.
Ziel der Aufgabe ist es eine Prozedur zu schreiben, die ein Haus als Text ausgibt:
x x x x x x x x x xxxxxxxxx x x x x x x x x xxxxxxxxx
- Schreibe eine Prozedur, die in Abhängigkeit von einem positiven Integer-Parameter n > 1 (Wieso?) ein Haus (in der obigen Form) der Breite n mit System.print() und System.println() zeichnet und auf der Konsole ausgibt.
Hinweise:
Für ungerade n ist das Haus oben ein Beispiel – wie sieht das Haus für gerade n aus? (Lösungsskizze!)
Zusätzlich- Damit das Haus besser isoliert ist, soll das Innere des Dachs mit ^ und die Hauswand mit # ausgefüllt werden.
Außerdem sind Hochhäuser in, deswegen wäre es schön, wenn das Haus mehrere Stockwerke haben könnte – man füge also eine Parameter m > 0 hinzu, der angibt, wie viele Stockwerke das Haus haben soll und zeichne das Haus entsprechend.Permutationen
Permutationen sind sehr leicht mit Schleifen zu erzeugen, deswegen:
Man schreibe eine Funktion <T> Seq<Seq<T>> getPermutations( Seq<T> set ), die alle Permutationen von set zurückgibt.
Hinweise:
Es lohnt sich auf jeden Fall die übliche Vorgehensweise zu probieren, selbst wenn die Aufgabe abschreckend wirkt:Ein paar einfache Beispiele per Hand lösen, dann schauen, wie man die Lösungen in Teilprobleme zerlegen kann (also wie man eine Permutation mit Hilfe von Teilpermutationen bestimmen kann).
Hierbei können (wie so oft sonst auch) kleine Skizzen nützlich sein.Achtung:
PS: Dieser Eintrag ist TODO, d.h. ich werde hier wahrscheinlich noch ein paar Dinge anfügen, nur wollte ich, weil ich momentan einiges um die Ohren habe und die Klausur ansteht, auch zumindest diese beiden kleinen Aufgaben nicht vorenthalten.
Feedback ist, wie immer, erwünscht.
05 Dec 08 Blatt 6 Folien
Anbei ein paar (die wichtigesten) Folien von der heutigen Übung.
(more…)05 Dec 08 Blatt 6, Aufgabe 3e
Hier noch eine etwas elegantere Lösung zur Aufgabe 3e:
// save as fib.java public class fib { static public int fib(int n) { int f_old = 1, f_current = 0; for( int i = 0 ; i < n ; i++ ) { int f_old_old = f_old; f_old = f_current; f_current = f_old_old + f_old; } return f_current; } static public void main( String[] args ) { // small test for( int i = 0 ; i < 10 ; i++ ) { System.out.println( fib(i) ); } } } [/sourcecode]Was ist der Trick?
Tags: Blatt 6, Fibonacci-Folge, iterativer Ansatz
