Dr. Annette Bieniusa
Mathias Weber, M. Sc.
Peter Zeller, M. Sc.
TU Kaiserslautern
Fachbereich Informatik
AG Softwaretechnik
Übungsblatt 9: Software-Entwicklung 1 (WS 2015/16)
Ausgabe: in der Woche vom 21.12. bis zum 22.12.15
Abgabe: in der Woche vom 10.01. bis zum 16.01.2016
Aufgabe 0 Vorlesungsumfrage
Füllen Sie bitte die Vorlesungsumfrage (https://vlu.cs.uni-kl.de/teilnahme/) aus, falls Sie dies
noch nicht getan haben sollten. Wir sind besonders an konstruktiven Kommentaren interessiert.
Aufgabe 1 Objektorientierte Programmierung (Präsenzaufgabe)
Dies ist eine Aufgabe aus der letzten SE1-Klausur. Lösen Sie diese Aufgabe handschriftlich, um zu testen,
wie gut Sie auf die Probeklausur vorbereitet sind. In der Klausur waren für diese Aufgabe etwa 10 Minuten
Bearbeitungszeit vorgesehen.
interface Kuehlschrank {
void add( String produkt );
boolean remove ( String produkt );
int count ( String produkt );
}
interface SmartKuehlschrank
extends Kuehlschrank {
void setOH( OnlineHandel o);
}
class SimpleKuehlschrank
implements Kuehlschrank {
...
}
interface OnlineHandel {
void bestellen ( String produkt );
}
Die Schnittstelle Kuehlschrank beschreibt einen einfachen Kühlschrank, in den man Produkte, die hier als
String repräsentiert werden, hineinstellen kann (Methode add) und wieder heraus nehmen kann (Methode
remove). Die Methode remove gibt true zurück, wenn das Produkt noch vorhanden war, ansonsten false.
Zusätzlich gibt es noch eine Methode count, welche die Anzahl für ein Produkt im Kühlschrank zurück gibt.
Die Klasse SimpleKuehlschrank gibt eine Implementierung (hier nicht abgedruckt) für diese Schnittstelle an.
Moderne Kühlschränke haben natürlich einen Internet-Anschluss und können selbsständig Produkte nachbestellen, wenn diese aufgebraucht sind. Dazu bietet die Schnittstelle SmartKuehlschrank eine Methode setOH,
mit der man eine Verbindung zu einem Online-Handel angeben kann.
a) Implementieren Sie eine Klasse Coolomat, welche die Schnittstelle SmartKuehlschrank implementiert.
Dabei soll die Klasse von SimpleKuehlschrank erben und wo möglich dessen Funktionalität verwenden,
um Redundanz zu vermeiden.
Wenn ein Online-Handel eingestellt ist und die Anzahl eines Produktes durch einen Aufruf von remove
auf 0 fällt, dann soll mit der Methode bestellen des Online-Handels das Produkt nachbestellt werden.
b) Implementieren Sie einen Konstruktor für die Klasse Coolomat, welcher einen OnlineHandel als Parameter
nimmt und diesen als initialen Online-Handel für den erstellten Kühlschrank setzt.
Aufgabe 2 Effizienz von Algorithmen (21 Punkte)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* requires ar != null
*
&& ar. length >= 2
*
&& fuer alle int i und int j mit i != j gilt:
*
ar[i] != ar[j]
* ensures \ result != null
*
&& \ result . length == 2
*
&& es gibt int i und int j mit i != j, so dass:
*
ar[i] == \ result [0]
*
&& ar[j] == \ result [1]
*
&& fuer alle int i und int j mit i != j gilt:
*
Math.abs(ar[i] + ar[j]) <= Math.abs (\ result [0] + \ result [1])
*/
public static int [] mp(int [] ar) {
int [] res = {0 ,0};
int max = -1;
for (int i=0; i<ar.length -1; i++) {
for (int j=i+1; j<ar. length ; j++) {
int sum = Math.abs(ar[i] + ar[j]);
if (sum > max) {
max = sum;
res [0] = ar[i];
res [1] = ar[j];
}
}
}
return res;
}
a) Geben Sie eine Funktion an, welche die Anzahl der ausgeführten Zuweisungs-Operationen und InkrementOperationen bei der Ausführung der Prozedur mp in Abhängigkeit von N = ar.length angibt. Sie können
dabei wie in der Vorlesung vereinfacht die Zuweisungen in der if-Anweisung von Zeile 20 immer mit
zählen. Außerdem können Sie davon ausgehen, dass Math.abs keine Zuweisungen verwendet.
Geben Sie eine genaue Rechnung mit Erklärung und mit Zwischenschritten ab.
b) Schätzen Sie die Komplexität der Funktion aus Teil a) mit der O-Notation ab. Geben Sie dafür eine
geschlossene Form für die in Teil a) aufgestellte Formel an, in der keine Summen-Zeichen vorkommen.
c) Schreiben Sie eine neue Prozedur, welche auch die oben angegebene Spezifikation erfüllt, aber effizienter arbeitet. Ihre Implementierung soll eine Laufzeit linear in der Länge des Eingabe-Arrays haben, also
eine Komplexität von O(N) haben.
Erklären Sie in Kommentaren die Idee hinter Ihrer Implementierung.
d) Analysieren Sie die Laufzeit Ihrer Prozedur analog zu den Aufgabenteilen a) und b), wieder mit genauer
Erklärung.
Aufgabe 3 Performanz-Messungen (21 Punkte)
In dieser Aufgabe sollen Sie mit Performanz-Messungen mit Hilfe der Objekt-Orientierung modellieren.
a) Schreiben Sie ein Interface Experiment, welche ein bestimmtes Experiment darstellt, für das Messungen durchzuführen sind. Die Schnittstelle soll eine Methode void prepare(int size) und eine Methode
void execute() haben. Dabei dient die Methode prepare dazu, Testdaten mit einer gegebenen Größe
vorzubereiten. Die Methode execute führt dann einen Durchlauf des Experiments aus.
b) Schreiben Sie eine Klasse ExperimentExecutor, welche dafür verantwortlich ist Experimente auszuführen. Diese Klasse soll die folgenden Methoden haben:
1. public long run(Experiment e, int size, int repeats)
Diese Methode nimmt ein Experiment (e), eine Größe für die Eingaben (size) und eine Anzahl von
Wiederholungen (repeats). Die Methode soll das Experiment e mehrmals ausführen, wobei pro
Durchlauf jeweils zuerst das Experiment mit der prepare-Methode vorbereitet und dann mit der
execute-Methode ausgeführt wird. Der Parameter size wird dabei einfach an die prepare-Methode
weiter gereicht.
Während der Durchläufe soll jeweils die Zeit gemessen werden, die von der execute-Methode
des Experiments verwendet wird. Benutzen Sie dazu die Prozedur System.nanoTime(), welche die
aktuelle Zeit in Nanosekunden als long zurückgibt. Die Zeit für die prepare-Methode soll nicht mit
gemessen werden.
Am Ende soll die Prozedur die Zeit in Nanosekunden zurückgeben, die von der execute-Methode
durchschnittlich gebraucht wurde.
2. public long[] runSeries(Experiment e, int[] sizes, int repeats)
Diese Methode soll ein Experiment mit einer Reihe von Eingabegrößen durchführen. Dazu bekommt die Methode ein Array sizes von Eingabegrößen. Die anderen Parameter sind analog zur
Methode run.
Am Ende soll die Prozedur ein Array mit durchschnittlichen Zeiten in Nanosekunden für jede
Eingabegröße zurückgeben.
c) Schreiben Sie eine Experiment-Klasse, welche den Sortier-Algorithmus “Sortieren durch Auswahl auf
Arrays” aus der Vorlesung testet. In der prepare-Methode soll dazu ein Array der Länge size angelegt und mit zufälligen Zahlen gefüllt werden. Das Array soll dann in einem Attribut data gespeichert
werden, damit es von execute benutzt werden kann.
Die execute-Methode ruft dann einfach die sort-Methode für das Array data auf.
d) Schreiben Sie eine main-Methode, welche das Experiment mit Hilfe der Methode runSeries aus Teil b)
mit den Eingabegrößen 0, 100, 200, . . . , 10000 und jeweils 10 Wiederholungen durchführt. Die Laufzeiten sollen dann Zeilenweise ausgegeben werden.
e) Schreiben Sie eine weitere Experiment-Klasse, die statt dem Sortier-Algorithmus aus der Vorlesung den
Sortier-Algorithmus von Java verwendet. Diesen Können Sie zum Beispiel mit folgender Zeile aufrufen:
java.util.Arrays.sort(data);
f) Verwenden Sie ein Programm zum Zeichnen von Diagrammen (zum Beispiel Microsoft Excel oder
LibreOffice Calc) um die Ergebnisse der beiden Experimente zu visualisieren. Dabei soll auf der xAchse die Eingabegröße und auf der y-Achse die Laufzeit stehen. Geben Sie die Diagramme für die
beiden Experimente als Bild-Datei (.svg, .png, oder .jpg) oder als PDF-Datei ab.
Aufgabe 4 Objekte, Kapselung, Fehlerbehandlung (Weihnachtsaufgabe)
Wir betrachten eine Klasse Secret, die einen geheimen Wert enthält, auf den von außerhalb nicht zugegriffen
werden darf. In Java kann das Attribut dazu mit dem Schlüsselwort private annotiert werden:
final public class Secret {
private String password ;
private String secret ;
private long accessCount = 0;
public Secret ( String password ,
public long getAccessCount () {
public String getSecret (char []
public String getSecret ( String
}
String secret ) { ... }
... }
password ) throws WrongPasswordException { ... }
password ) throws WrongPasswordException { ... }
Die Methode getSecret bietet Zugriff auf den geheimen Wert, insofern man das richtige Passwort als String
oder als char-Array übergibt. Ist das Passwort falsch, wird eine WrongPasswordException geworfen. Es gibt
verschiedene Arten dieser Ausnahme, welche durch folgende Klassen definiert sind:
abstract class WrongPasswordException extends RuntimeException {}
class PasswordTooLongException extends WrongPasswordException {}
class PasswordTooShortException extends WrongPasswordException {}
class InvalidCharException extends WrongPasswordException {}
class PasswordWasNullException extends WrongPasswordException {}
class WrongCharsException extends WrongPasswordException {
private int dist;
WrongCharsException (int dist) { this.dist = dist; }
/** gibt die Distanz zum korrekten Passwort an */
public int getDistance () { return dist; }
}
Eine PasswordTooLongException wird geworfen, wenn das übergebene Passwort zu lang ist, eine
PasswordTooShortException, wenn es zu kurz ist. Die InvalidCharException wird geworfen, wenn das Passwort ein Zeichen enthält, das kein Buchstabe zwischen ’a’ und ’z’ ist. Die PasswordWasNullException wird
geworfen, wenn null als Passwort übergeben wurde. Die WrongCharsException wird geworfen, wenn die
Länge des Passworts korrekt ist, aber die Zeichen nicht übereinstimmen. Diese Ausnahme enthält auch
noch Informationen darüber, wie weit das übergebene Passwort vom richtigen Passwort entfernt ist. Diese
Distanz ist die sogenannte Manhatten-Distanz und berechnet sich für Strings a und b der Länge N wie folgt:
dist(a, b) =
N−1
X
|ai − bi |
i=0
Leider handelt es sich hierbei wohl um eins der schlechtesten Sicherheits-Mechanismen aller Zeiten, da
jeder vergebliche Versuch eine Menge an Informationen über die richtige Kombination preisgibt.
Laden Sie sich das Archiv “Secret.zip” von der Vorlesungsseite und entwickeln Sie eine Klasse
UncleKracker, welche die in den Vorlagen vorgegebene Schnittstelle CodeCracker implementiert. Dabei soll
die Methode getName einen von Ihnen gewählten Team-Namen zurückgeben und die Methode crack soll
ein Secret-Objekt nehmen und dieses Knacken. Rückgabewert der Methode crack soll das gespeicherte
Geheimnis sein.
Zum Knacken soll die Methode crack die öffentliche Schnittstelle von Secret verwenden, also im wesentlichen die Methode getSecret. Fangen Sie alle möglichen Ausnahmen entsprechend ab und reagieren Sie
sinnvoll darauf, so dass Sie nach einer endlichen Anzahl an Iterationen das Geheimnis geknackt haben.
Die Klasse Secret protokolliert die Anzahl der Zugriffe auf die Methode getSecret. Optimieren Sie Ihren
Algorithmus zum Knacken von Geheimnissen, um im Mittel über viele zufällige Beispiele (mit PasswortLänge von 0 bis 256) eine möglichst niedrige Zahl zu erreichen!
Extra-Punkte gibt es für die 20 besten Lösungen: 21 Punkte für den ersten Platz, 20 Punkte für den zweiten
Platz und so weiter. Wir werden den String, den Sie in der Methode getName zurückgeben in einer Bestenliste
verwenden.
Sie können Ihre Implementierung mit den JUnit-Tests in der vorgegebenen Datei CodeCrackerTest testen.
© Copyright 2024 ExpyDoc
