程序代写代做代考 Java compiler algorithm Erlang javascript Praktikum: Grundlagen der Programmierung

29 a.f(b1); // Aufruf 1
30 a.f(b2); // Aufruf 2
31

1

35 (b2 = b3).f(a); // Aufruf 3
36 (b4 = c).t.f(a); // Aufruf 4
37 }
38 }

Geben Sie für jeden der markierten Aufrufe die Ausgabe an. Gehen Sie davon aus, dass
nur ein Aufruf im Programm vorhanden ist; die anderen seien jeweils auskommentiert.
Es kann jeweils auch ein Compiler- oder Laufzeitfehler auftreten. Geben Sie bei einem
Laufzeitfehler an, wo genau bzw. wieso dieser auftritt. Begründen Sie bei Aufruf 3 kurz
das Verhalten des Java-Compilers anhand eines Beispiels.

Aufgabe 8.3 (P) Exceptions
Betrachten Sie folgenden Ausschnitt aus der Klassenhierarchie von Exceptions in Java
und folgende Java-Implementierung der Klasse ExceptionTest:

Exception

IOException

EOFException FileNotFoundException

import java.io.*;
public class ExceptionTest {

public static void main (String[] args) {
try {

// …
}
catch (EOFException e) {

System.out.println(“EOFException”);
}
catch (IOException e) {

System.out.println(“IOException”);
}
catch (Exception e) {

System.out.println(“Exception”);
}
System.out.println(“ENDE”);

}
}

1. An der durch „…“ gekennzeichneten Stelle im try-Block stehe ein Programm-
stück, durch das Exceptions vom Typen EOFException, IOException oder aber
FileNotFoundException geworfen werden können.
Was wird bei Ausführung der main-Methode ausgegeben, falls dabei im try-Block

i) als erstes eine Ausnahme vom Typ EOFException geworfen wird,
ii) als erstes eine Ausnahme vom Typ FileNotFoundException geworfen wird,

oder
iii) gar keine Ausnahme geworfen wird?

2. Was wird bei Ausführung der main-Methode ausgegeben, falls dabei im try-Block
als erste Ausnahme eine Division durch 0 auftritt?

Aufgabe 8.4 (P) Rekursion: Quersumme
Schreiben Sie ein Programm Quersumme.java, das die Quersumme 1 einer einzugebenden

1Sehe http://de.wikipedia.org/wiki/Quersumme

2

http://de.wikipedia.org/wiki/Quersumme

Zahl zahl

1. iterativ in der Funktion static int quersummeIt(int zahl)
2. rekursiv in der Funktion static int quersummeRec(int zahl)

berechnet und anschließend ausgibt.

Hinweise:

• Der Modulo-Operator ist bei dieser Aufgabe sehr hilfreich.

• Zur Eingabe der Zahl können Sie Terminal.readInt() verwenden.

Aufgabe 8.5 (P) Rekursion: Leibniz-Reihe
Gegeben sei folgende Rekursionsgleichung zur Annäherung von π = 3, 1415 . . .

fn =



4
2∗n+1 + fn−1 : falls (n mod 2) ≡ 0
− 42∗n+1 + fn−1 : falls (n mod 2) ≡ 1

wobei f0 = 4.

• Schreiben Sie ein Programm, das nach Eingabe des Index n die Annäherung fn für
Pi rekursiv berechnet und ausgibt.

• Schreiben Sie ein Programm, das abhänig von einem Schwellwert � die Anzahl Schrit-
te n berechnet, so dass:

|π′ − π| < � wo π′ ist die berechnete Annäherung von π. Führen Sie Ihre Implementierung einmal mit � = 0.01 und einmal mit � = 0.001 aus. • Nach wievielen Schritten ist die Annäherung π′ auf die ersten sieben Nachkommas- tellen genau? Aufgabe 8.6 (P) Rekursion: Binomialkoeffizient Der Binomialkoeffizient ( n k ) gibt an, auf wieviele verschiedene Arten man k Elemente aus einer Menge von n verschiedenen Elementen auswählen kann (ohne Zurücklegen und ohne Beachtung der Reihenfolge). Für 0 ≤ k ≤ n gilt: ( n k ) = ( n− 1 k − 1 ) + ( n− 1 k ) ; ( 0 0 ) = 1; ( n n ) = ( n 0 ) = 1 Schreiben Sie ein Programm Binom.java. 1. Es soll eine Funktion static long binom(int n, int k) enthalten, welche ( n k ) rekursiv berechnet und das Ergebnis zurückgibt. 3 2. Erweitern Sie Ihr Programm um eine Funktion static double sechsRichtige(), welche die Wahrscheinlichkeit zurückgibt, 6 Zahlen aus der Menge {1...49} richtig zu tippen. Die Hausaufgabenabgabe erfolgt über Moodle. Bitte geben Sie Ihren Code als UTF8- kodierte (ohne BOM) Textdatei(en) mit der Dateiendung .java ab. Geben Sie keine Projektdateien Ihrer Entwicklungsumgebung ab. Geben Sie keinen kompilierten Code ab (.class-Dateien). Sie dürfen Ihren Code als Archivdatei abgeben, dabei allerdings ausschließlich das ZIP-Format nutzen. Achten Sie darauf, dass Ihr Code kompiliert. Hausaufgaben, die sich nicht im vorgegebenen Format befinden, werden nur mit Punkt- abzug oder gar nicht bewertet. Aufgabe 8.7 (H) Mathematische Ausdrücke [3 Punkte] In dieser Aufgabe sollen auf der Grundlage der in der Vorlesung behandelten Klassen- hierarchie mathematische Ausdrücke in Form von Ausdrucksbäumen repräsentiert und berechnet werden. Diese mathematischen Ausdrücke sollen zusätzlich zu den bereits im- plementierten arithmetischen Ausdrücken (binäres +,−, ∗, /; unäres −) nun auch logische Operatoren (binäres und (∧), oder (∨); unäre Negation (¬)) umfassen. Ausgangspunkt hierzu ist die abstrakte Klasse Expression, die einen (abstrakten) mathematischen Aus- druck repräsentiert, der sowohl arithmetischer als auch logischer Natur sein kann. Misch- formen zwischen arithmetischen und logischen Operatoren sind zunächst nicht erlaubt (s. nächste Aufgabe). Zusätzlich zur abstrakten Oberklasse sollen zwei abstrakte Unterklas- sen implementiert werden, die binäre Operationen (Klasse BinOp) und unäre Operationen (Klasse UnOp) repräsentieren. Außerdem soll es eine konkrete Unterklasse für Konstanten geben (Klasse Const), die sowohl Integers als auch Booleans repräsentieren können muss. Die abstrakte Oberklasse Expression soll lediglich über abstrakte Methode evaluate() und toString() verfügen, die jeweils erst in den Unterklassen eine Implementierung er- halten. Die Methode evaluate() wertet einen (arithmetischen oder logischen) Ausdruck aus und gibt das Ergebnis auf der Konsole aus. 1. Machen Sie sich klar, dass in dieser Aufgabe gleichzeitig zwei Arten von Expressions behandelt werden müssen, nämlich arithmetische (mit Integers parametriert) und logische (mit Booleans parametriert). Benutzen Sie deshalb bei der Definition von Expression sowie deren Unterklassen einen entsprechenden Typparameter. Definieren Sie dann die drei genannten abstrakten und eine konkrete Klasse und implementieren Sie die jeweiligen Konstruktoren. Beachten Sie, dass Konstanten nun Integers oder Booleans sein können. Beachten Sie auch, dass abstrakte Klassen durchaus über Konstruktoren verfügen können und dass, wenn Konstruktoren in einer abstrakten Klasse C explizit implementiert sind, Sie in den Unterklassen von C ggf. explizite Konstruktoren definieren müssen, die den Konstruktor von C explizit als erste Zeile aufrufen. 2. Spezialisieren Sie dann für jeden arithmetischen (+, -, *, /) und jeden logischen (∧, ∨, ¬) Ausdruck die abstrakten Klassen BinOp und UnOp in jeweils eine konkrete Unterklasse. Überlegen Sie sich, wie Sie die Konstruktoren dieser Klassen möglichst einfach halten können. 4 3. Für die Implementierung der evaluate()-Methode in den Unterklassen der Klasse Expression gibt es mindestens zwei Möglichkeiten. • Die einfache Möglichkeit besteht darin, die evaluate()-Methode in jeder kon- kreten Unterklasse von Expression zu implementieren, also in Const sowie den konkreten Unterklassen von UnOp und BinOp. • Eine andere Möglichkeit besteht darin, evaluate() in den abstrakten Klas- sen UnOp und BinOp unter Zuhilfenahme einer neuen abstrakten Funktion fun zu implementieren, die erst in den Unterklassen von UnOp und BinOp imple- mentiert wird. fun(o1,o2) könnte dann für arithmetische binäre Ausdrücke dahingehend definiert werden, dass o1 + o2, o1 - o2, o1 * o2 oder o1/o2 zurückgegeben wird. Für binäre logische Ausdrücke sollte o1 && o2 bzw. o1 || o2 berechnet werden. Für die arithmetische Negation sollte eine Methode fun(o) entsprechend -o zurückgeben und für die logische Negation !o. Für Const müssen Sie natürlich eine explizite Implementierung angeben. Implementieren Sie eine der beiden Möglichkeiten, sodass Sie danach mit der Me- thode evaluate() beliebige arithmetische oder logische Ausdrücke berechnen und ausgeben können. Beispiel: (new MulOp(new Const(3), new AddOp(new
Const(1), new Const(2)))).evaluate()

soll 9 ausgeben und

(new AndOp(new Const(true),new OrOp(new
Const(false), new Const(true)))).evaluate()

soll true ausgeben.

4. Implementieren Sie die toString()-Methode, so dass alle mathematischen Aus-
drücke richtig geklammert ausgegeben werden.

5. Betrachten Sie das in Abbildung 1 dargestellte Beispiel und schreiben Sie eine
main-Methode in einer Klasse ATest, die mindestens drei weitere Aufrufbäume in-
stanziiert. Die Aufrufbäume sollen jeweils aus mindestens fünf Objekten vom Typ
Expression bestehen. Testen Sie auf diesen Aufrufbäumen die Methoden evaluate()
und toString().

5

*”

3″ +”

1″ 2″

&&”

1″ ||”

0″ 1″

Abbildung 1: Beispiel für einen mathematischen Ausdruck in Form eines Ausdrucksbau-
mes.

Dateien zur Abgabe:
Expression.java, Const.java, BinOp.java, UnOp.java, AddOp.java, MulOp.java,
DivOp.java, SubOp.java, AndOp.java, NegOp.java, OrOp.java, ATest.java

Aufgabe 8.8 (H) Relationale Operatoren [3 Punkte]
Erweitern Sie die Implementierung dahingehend, dass auch relationale Operatoren (<,>
,==) behandelt werden können. Machen Sie sich klar, dass diese relationalen Operatoren
einen Rückgabetypen (etwa Boolean) haben, der unterschiedlich von den Argumenttypen
(etwa Integer) ist, im Gegensatz zu arithmetischen und logischen Ausdrücken, bei denen
Argument- und Rückgabetypen identisch sind (etwa Integer bzw. Boolean). Benennen
Sie alle Klassen für Ausdrücke, abstrakte und konkrete logische und arithmetische Opera-
toren um, indem Sie ein Präfix ZA voranstellen. Implementieren Sie dann drei zusätzliche
konkrete Klassen ZAGTOp für die Implementierung von >, ZALTOp für < und ZAEQOp für == in den Dateien ZAGTOp.java, ZALTOp.java und ZAEQOp.java. Betrachten Sie das in Abbildung 2 dargestellte Beispiel und schreiben Sie eine main- Methode in einer Klasse ZATest, die mindestens drei weitere Aufrufbäume instanziert. Die Aufrufbäume sollen jeweils aus mindestens fünf Objekten vom Typ Expression be- stehen. Testen Sie auf diesen Aufrufbäumen die Methoden evaluate() und toString(). Beispiel: (new EQOp(new MulOp(new Const(3), new
AddOp(new Const(1), new Const(2))), new

Const(9)).evaluate()

soll true ausgeben.

6

==”

*”

+”

1″ 2″

3″

9″

Abbildung 2: Beispiel für einen mathematischen Ausdruck mit relationalen Operator in
Form eines Ausdrucksbaumes.

Dateien zur Abgabe:
ZAExpression.java, ZAConst.java, ZABinOp.java, ZAUnOp.java, ZAAddOp.java,
ZAMulOp.java, ZADivOp.java, ZASubOp.java, ZAAndOp.java, ZANegOp.java,
ZAOrOp.java, ZAGTOp.java, ZALTOp.java, ZAEQOp.java, ZATest.java.

Aufgabe 8.9 (H) PageRank Rekursiv [6 Punkte]
Ziel dieser Aufgabe ist die Implementierung des PageRank Algorithmus, der durch Google
allgemeine Bekanntheit erlangt hat. PageRank bewertet dabei nicht die Ähnlichkeit einer
Suchanfrage zu den erfassten Dokumenten. Stattdessen ist PageRank ein Verfahren, mit
dem die verschiedenen Seiten (bzw. Dokumente) an Hand ihrer Struktur bewertet bzw.
gewichtet werden. Hierzu wird jedem Dokument ein Gewicht zugeteilt, das sich aus der
Linkstruktur zwischen den Dokumenten berechnet. PageRank analysiert also alle ein- und
ausgehenden Links der Dokumente und gewichtet die einzelnen Dokumente auf Grundlage
dieser Links. Das Grundprinzip dabei lautet: je mehr Links auf ein Dokument verweisen,
desto höher ist das Gewicht dieses Dokumentes. Je höher dabei das Gewicht des verwei-
senden Dokumentes ist, desto größer ist auch das Gewicht der Seite auf die verwiesen
wird. Dokumente auf die von vielen anderen Dokumenten verwiesen wird haben somit ein
größeres Gewicht und damit eine höhere Popularität.

Implementieren Sie daher die rekursive Methode

public double pageRankRec(int[][] C, int i, double d, int recDepth)

in der Klasse LinkedDocumentCollection, die die PageRank-Werte der LinkedDocuments
der LinkedDocumentCollection annähert und ein Array dieser PageRank Werte als
Rückgabewert hat. Bezüglich der Parameter ist C die Übergangsmatrix, i der Index des
Dokuments, für welches der PageRank-Wert zu berechnen ist, d ein Dämpfungsfaktor
und recDepth die Rekursionstiefe des aktuellen Methodenaufrufs. Die Parameter werden
später genauer erläutert. Nähern Sie die PageRank Werte gemäß den folgenden Ausfüh-
rungen so lange an die korrekten PageRank Werte an, bis diese auf 10−6 mit den korrekten
Werten übereinstimmen. Finden Sie dafür eine geeignete maximale Rekursionstiefe, die

7

als Abbruchbedingung dienen soll und gleichzeitig der Anforderung hinsichtlich Genauig-
keit Rechnung trägt. Beachten Sie außerdem, dass das Programm bis zur Terminierung
auf handelsüblichen Computern nicht länger als eine Minute zur Berechnung dauern darf.
Außerdem soll die Methode von außen über eine einfachere Methode

public double[] pageRankRec(double d)

aufgerufen werden, welche so zu implementieren ist, dass sie die zu übergebenen Parameter
entweder weiterreicht oder, sofern notwendig, sinnvoll initialisiert und jeweils übergibt.

Die folgenden Ausführungen zu PageRank beruhen auf den Ausführungen der Webseite
“PageRank Algorithm – The Mathematics of Google Search”2.

Das Prinzip des PageRank-Algorithmus wird im Folgenden an Hand eines Beispiels er-
klärt. Hierfür gehen wir davon aus, dass es vier Dokumente A, B, C und D gibt, deren
Fließtext die folgenden Links enthält:

A
link:B link:C

B
link:A link:C link:D

C
link:D

D
link:C

Hiermit ergibt sich die Linkstruktur aus Abbildung 3a.

A B

C D
(a) Linkstruktur

Abbildung 3

Jedes Dokument kann also auf andere Dokumente verweisen, woraus sich die Verlinkungs-
matrix C wie folgt ergibt:

A B C D

C =




0 1 0 0
1 0 0 0
1 1 0 1
0 1 1 0




A
B
C
D

Jede Matrixzelle ci,j enthält hier die Information, ob eine Verlinkung von Dokument j auf
Dokument i vorliegt (1) oder nicht (0). Insofern enthält eine Spalte die ausgehenden und
eine Zeile die eingehenden Verlinkungen pro Dokument.

2 http://www.math.cornell.edu/∼mec/Winter2009/RalucaRemus/Lecture3/lecture3.html

8

http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture3/lecture3.html

Beachten Sie: Verweist ein Dokument auf kein anderes Dokument (d.h. das Dokument
hat 0 ausgehende Links), so wird dieses Dokument so behandelt als ob es Links zu allen
anderen Dokumenten hätte.
Zusätzlich wird ein sogenannter Dämpfungsfaktor d, ein Wert zwischen 0 und 1, einge-
führt. Dieser ist notwendig, da nicht notwendigerweise alle Dokumente über Links zusam-
menhängen müssen. In diesem Fall sorgt der Dämpfungsfaktor dafür, dass tatsächlich alle
Dokumente einen PageRank Wert > 0 erhalten. Der Dämpfungsfaktor hat üblicherweise
den Wert 0.85.
Setzt man die gegebenen Variablen in die rekursive Formel 3

PRi =
1− d
n

+ d ·
∑
j∈Li

PRj∑n−1
k=0 Ck,j

ein, so erhält man für den PageRank-Wert vom i-ten LinkedDocument einen neuen PageRank-
Wert PRi. Hierbei ist Li die Menge der Indizes der Dokumente, die einen Link aufs i-te
Dokument beinhalten. PRj selber ist wiederum ein rekursiver Verweis auf die Formel
selbst.
Die PageRank Werte der Dokumente werden in einem Vektor PR dargestellt und zu
Beginn auf dieselben Werte ( 1

n
) gesetzt, im Beispiel ist also der PageRank Vektor PR zu

Beginn

PR =




0.25
0.25
0.25
0.25


 .

Aktualisiert man nun mehrfach in rekursiver Abfolge jeden Wert von PR mittels der
angegebenen Formel, so nähert sich das Ergebnis dieser Rekursion einem Vektor PR∗ an.
Dieser Vektor PR∗ entspricht den PageRank-Werten der Dokumente.
Im Beispiel entspricht dieser Ergebnisvektor

PR∗ =




0.0547
0.0607
0.4485
0.4359


 .

Das bedeutet dass A ein PageRank-Gewicht von 5, 47%, B von 6, 07%, C von 44, 85% und
D von 43, 56% hat.
Auf der Webseite “PageRank Explained with Javascript”4 können Sie spielerisch eine
Linkstruktur zwischen Dokumenten erstellen und die PageRank Werte der Dokumente
berechnen lassen. N.B. Ziel dieser Aufgabe ist PR∗ zu annähren bis für alle i ∈ {1, …, n}
die folgende Bedingung erfüllt ist:

|PRi − PR′i| ≤ 10
−6.

Dateien zur Abgabe: Author.java, Date.java, DocumentCollectionCell.java,
DocumentCollection.java, Document.java, LinkedDocumentCollection.java,
LinkedDocument.java, Review.java, WordCount.java, WordCountsArray.java

3https://de.wikipedia.org/wiki/PageRank
4https://www2.cs.duke.edu/csed/principles/pagerank/

9

https://de.wikipedia.org/wiki/PageRank
https://www2.cs.duke.edu/csed/principles/pagerank/

Aufgabe 8.10 (H) PageRank Iterativ (Nikolaus-Nuss) [3 Bonuspunkte]
Ziel dieser Aufgabe ist die iterative Implementierung des PageRank-Algorithmus. Dies
bedeutet, dass hier der Algorithmus entgegen seiner ursprünglichen Definition nicht re-
kursiv berechnet wird. Dies ist insofern hilfreich, als dass der rekursive Algorithmus bei
großen Dokumentzahlen zu langsam konvergiert und der hier zu implementierende itera-
tive Algorithmus im Allgemeinen effizienter ist.

1. Um den PageRank der LinkedDocuments einer LinkedDocumentCollection zu be-
rechnen, werden wir später Matrizen mit Vektoren multiplizieren müssen. Kopieren
Sie daher den Code für die Methode

private static double[] multiply(double[][] matrix, double[] vector)

aus Aufgabe 5.8 (H) in die Klasse LinkedDocumentCollection.

2. Schreiben Sie in der Klasse LinkedDocumentCollection die Methode

public double[] pageRank(double dampingFactor),

die die PageRank Werte der LinkedDocuments der LinkedDocumentCollection an-
nähert und ein Array dieser PageRank Werte als Rückgabewert hat. Der Parameter
dampingFactor ist dabei ein Dämpfungsfaktor, der in der vorhergehenden Aufga-
be bereits eingeführt wurde. Nähern Sie die PageRank Werte gemäß den folgenden
Ausführungen so lange an die korrekten PageRank Werte an, bis diese auf � = 10−6
genau sind.
In Ergänzung zu den Erklärungen und dem Beispiel von der vorhergehenden Aufgabe
werden im Folgenden zusätzliche Formeln und Definitionen eingeführt, welche die
iterative Umsetzung unterstützen sollen.

A B

C D

1/3

1/3

1/3

1/1

1/1

1/2

1/2

(a) Linkstruktur mit Gewichtung
in Erweiterung zu Abbildung 3a

Abbildung 4

Jedes Dokument verteilt gemäß Abbildung 4a sein Gewicht gleichmäßig auf alle von
ihm verlinkten Dokumente. So verweist A auf zwei Dokumente, die jeweils beide
mit 12 gewichtet werden. B verweist dagegen auf drei Dokumente, die jeweils mit

1
3

gewichtet werden. Allgemein gilt: Hat ein Dokument k ausgehende Links, so wird

10

jedes der k verlinkten Dokumente mit 1
k
gewichtet. Dies resultiert im Beispiel in den

Gewichtungen in Abbildung 4a.
Diese Gewichtungen bilden die Übergangsmatrix A:

A B C D

A =




0 13 0 0
1
2 0 0 0
1
2

1
3 0 1

0 13 1 0




A
B
C
D

So besagt beispielsweise die erste Spalte der Matrix, dass Dokument A jeweils mit
Gewicht 12 auf die Dokumente B und C verweist und mit Gewicht 0 (also gar nicht)
auf die Dokumente A und D. Die dritte Spalte besagt dagegen, dass Dokument C mit
Gewicht 1 auf Dokument D verweist und sonst auf keine weitere Dokumente. Eine
Person die nach dem Zufallsprinzip einem der Verweise in Dokument A folgt, wählt
demnach mit Wahrscheinlichkeit 12 entweder den Verweis zu Dokument B oder C.
Beachten Sie: Verweist ein Dokument auf kein anderes Dokument (d.h. das Do-
kument hat 0 ausgehende Links), so wird dieses Dokument so behandelt als ob es
Links zu allen anderen Dokumenten hätte.
Mit dem aus der vorhergehenden Aufgabe eingeführten Dämpfungsfaktor d berech-
net sich die PageRank Matrix M als

M = d · A+ 1−d
n
· En.

Dabei ist n die Anzahl der Dokumente und En eine Matrix mit n Zeilen und n
Spalten, die an jeder Position eine 1 enthält. Der Wert der Matrix M in Zeile i und
Spalte j, Mij berechnet sich daher als

Mij = d · Aij + 1−dn

Im Beispiel ist die PageRank Matrix

M =




0.0375 0.3208 0.0375 0.0375
0.4625 0.0375 0.0375 0.0375
0.4625 0.3208 0.0375 0.8875
0.0375 0.3208 0.8875 0.0375




Die PageRank-Werte der Dokumente werden so initialisiert und dargestellt wie in
der vorhergehenden Aufgabe bereits erwähnt. Multipliziert man nun mehrfach die
Matrix M mit sich selbst und anschließend mit dem Vektor v, d.h. Mkv, so nä-
hert sich das Ergebnis dieser mehrfachen Multiplikation einem Vektor v∗ an. Dieser
Vektor v∗ entspricht den PageRank Werten der Dokumente. 5

Ziel dieser Aufgabe ist, so wie in der vorhergehenden Aufgabe auch, v∗ zu annähren
bis für alle i ∈ {1, …, n} es gilt:

|(Mk+1v)i − (Mkv)i| ≤ � = 10−6.
5Die Matrix Mk drückt die Wahrscheinlichkeit aus, mit der nach k Schritten einem bestimmten Verweis

in einem bestimmten Dokument gefolgt wird. Dies werden Sie noch ausführlich in anderen Vorlesungen
behandeln.

11

Dateien zur Abgabe: Author.java, Date.java, DocumentCollectionCell.java,
DocumentCollection.java, Document.java, LinkedDocumentCollection.java,
LinkedDocument.java, Review.java, TestIt.java, WordCount.java,
WordCountsArray.java

Aufgabe 8.11 (H) Sortieren der Suchergebnisse [3 Punkte]
Auf den vorherigen Übungsblättern wurde die Ähnlichkeit zwischen Dokumenten und
einer Suchanfrage. Damit eine Suchmaschine gute Resultate liefert, müssen Ähnlichkeit
und PageRank sinnvoll kombiniert werden. Auf diese Weise stehen diejenigen Dokumente
in der Trefferliste oben, die sowohl eine große Ähnlichkeit mit der Suchanfrage, als auch
eine hohen PageRank Wert haben. Diese Kombination aus Ähnlichkeit zur Suchanfrage
und PageRank-Wert nennen wir “Relevanz”.

Für ein LinkedDocument d, eine Suchanfrage q und eine LinkedDocumentCollection dc
(d ∈ dc) sei die Ähnlichkeit zwischen d und q gegeben durch similarity(d, q, dc) (vgl.
Übung 4). Der PageRank Wert von d in der LinkedDocumentCollection dc ist gegeben
durch pageRank(d, dc). Dann berechnet sich die Relevanz des LinkedDocuments d als

relevance(d, q, dc) = g · similarity(d, q, dc) + (1− g) · pageRank(d, dc)

Dabei ist g (0 ≤ g ≤ 1) ein Gewichtungsfaktor, der den Einfluß der Ähnlichkeit bzw. des
PageRank Wertes auf die Relevanz beeinflusst. Der Gewhichtungsfaktor hat üblicherweise
den Wert 0.6.

Setzen Sie daher in der Suchmaschinenimplementierung folgendes um;

1. Implementieren Sie in der Klasse LinkedDocumentCollection die Methode

private double[] sortByRelevance(double dampingFactor, double
weightingFactor),

welche die LinkedDocumentCollection nach der Relevanz der darin enthaltenen
LinkedDocuments absteigend sortiert und die Relevanz der Dokumente zurückgibt.

2. Ändern Sie das Kommando query in der Klasse TestIt so ab, dass die Dokumente
sortiert nach ihrer Relevanz ausgegeben werden.

Dateien zur Abgabe: Author.java, Date.java, DocumentCollectionCell.java,
DocumentCollection.java, Document.java, LinkedDocumentCollection.java,
LinkedDocument.java, Review.java, WordCount.java, WordCountsArray.java

Aufgabe 8.12 (H) Die TestIt-Klasse [1 Punkte]
Erweitern Sie die main-Methode der Klasse TestIt der vorherigen Übung (Hausaufga-
benblatt 7) wie folgt:

1. Testen Sie Ihre main-Methode ähnlich dem unten stehenden Beispiel. Führen Sie
Tests mit mindestens zwei unterschiedlichen Dokumentenstrukturen mit jeweils min-
destens fünf Dokumenten durch. Schreiben Sie ein Protokoll der Ein- und Ausgabe
Ihres Programmes als Kommentar in die Datei TestIt.java.

12

Beispiel: Seien die Dateien a.txt, c.txt, d.txt, e.txt wie folgt gegeben:

a.txt
es war einmal link:b.txt link:c.txt

c.txt
once upon a time link:d.txt

d.txt
erase una vez link:c.txt

e.txt
c era una volta link:b.txt

Die Ausführung der main-Methode in der Klasse TestIt sieht dann wie folgt aus:
> add b.txt:link:a.txt link:e.txt
> crawl
> pageRank
b.txt; PageRank: 0.14897680763983684
a.txt; PageRank: 0.0933151432469308
c.txt; PageRank: 0.34291508382082525
d.txt; PageRank: 0.32147782204547976
e.txt; PageRank: 0.0933151432469308
> query einmal
1. a.txt; Relevanz: 0.285917709527423
2. c.txt; Relevanz: 0.1371660335283301
3. d.txt; Relevanz: 0.1285911288181919
4. b.txt; Relevanz: 0.05959072305593474
5. e.txt; Relevanz: 0.03732605729877232
> exit
Dateien zur Abgabe: TestIt.java

Aufgabe 8.13 (H) Rekursive Determinantenberechnung [4 Punkte]
In Aufgabe 5.9 (H) haben Sie einen iterativen Algorithmus zur Determinantenberechnung
implementiert. Ziel der vorliegenden Aufgabe ist eine rekursive Implementierung, das heißt
die Verwendung von Prozeduren, welche sich selbst aufrufen, bis eine Abbruchbedingung
erfüllt ist. Erstellen Sie dafür zunächst eine Klasse RecursiveDeterminant, welche die
im Folgenden definierten Funktionen enthalten soll. Gehen Sie anschließend wie folgt vor:

1. Implementieren Sie die Methode

public static int det2x2(int[][] matrix),

welche die Determinante einer 2×2-Matrix berechnet. Die dafür erforderliche Formel
6 lautet

|A| =
∣∣∣∣∣a bc d

∣∣∣∣∣ = ad− bc. (1)
6 Quelle: https://en.wikipedia.org/wiki/Determinant

13

https://en.wikipedia.org/wiki/Determinant

2. Implementieren Sie die Methode

public static int det3x3(int[][] matrix),

welche die Determinante einer 3×3-Matrix nach dem folgenden Prinzip 6 berechnet:

|A| =

∣∣∣∣∣∣∣
a b c
d e f
g h i

∣∣∣∣∣∣∣ = a
∣∣∣∣∣∣∣
� � �
� e f
� h i

∣∣∣∣∣∣∣− b
∣∣∣∣∣∣∣
� � �
d � f
g � i

∣∣∣∣∣∣∣+ c
∣∣∣∣∣∣∣
� � �
d e �
g h �

∣∣∣∣∣∣∣ (2)
= a

∣∣∣∣∣e fh i
∣∣∣∣∣− b

∣∣∣∣∣d fg i
∣∣∣∣∣+ c

∣∣∣∣∣d eg h
∣∣∣∣∣ (3)

Erstellen Sie zu diesem Zweck zwei Hilfsmethoden

public static int[][] removeRow(int[][] matrix, int rowIndex)

sowie

public static int[][] removeColumn(int[][] matrix, int colIndex),

welche die übergebene Matrix matrix kopieren, die i-te Zeile bzw. Spalte von der
Kopie entfernen und ebendiese Kopie zurückgeben. Verwenden Sie diese Hilfsmetho-
den, um die Matrix wie angegeben von 3× 3 auf 2× 2 zu verkleinern.
Anmerkung: Die Hilfsmethoden sollen auch in der Lage sein, quadratische n × n-
Matrizen entsprechend auf (n− 1)× (n− 1) zu verkleinern.

3. Erstellen Sie die Methode detNxN(). Die Methode soll die Determinante einer be-
liebigen quadratischen n×n-Matrix berechnen. Ihr Algorithmus sollte so vorgehen,
dass die Methode detNxN() sich selbst aufruft, um die Determinante einer Subma-
trix der Größe (n− 1)× (n− 1) zu berechnen. Eine Submatrix gewinnen Sie, indem
Sie jeweils eine Zeile und eine Spalte wie vorhergehend erläutert entfernen.

Testen Sie Ihre Implementierung in einer geeigneten main()-Methode.

Dateien zur Abgabe: RecursiveDeterminant.java

14