Fragen

[Matthias Lederhofer]

Hier noch ein paar Fragen von mir die sich beim lernen aufgeworfen
haben (koennen sowohl gerne direkt hier beantwortet werden oder auch
morgen in der Fragestunde).

1. In der Folie zu Hashing steht in den letzten beiden Faellen etwas
von j'. Was ist j'? (Dort steht bei verfeinertem quadratischen
Sondieren: j = j' mod 2 bzw. j != j' mod 2)

2. Spricht man bei Algorithmen die rekursiv arbeiten aber ansonsten
keinen Speicher abhaengig von der Eingabegroesse benoetigen auch von
in situ? Rekursion benoetigt schliesslich auch Speicher auf einem
Stack bzw. auch Variablen die in der Funktion genutzt werden werden ja
mehrfach (abhaengig von der Eingabegroesse) erstellt.

3. Ist f(n) * O(g(n)) = O(f(n) * g(n))? Falls die Gleichheit nicht
gilt waere ich an einem Gegenbeispiel interessiert.
Wie ist zudem f(n) * O(g(n)) definiert? Ich wuerde es als
{ f(n) * h(n) | h(n) in O(g(n)) } interpretieren.

4. Wie geht man bei Substitution bei Rekursionsgleichungen vor?
Bzw. im speziellen: wie wurde T(n) = 2 * T(abgerundet(wurzel(n))) +
ld(n) geloest (ich kann gerade meine Mitschrift nicht mehr
nachvollziehen).

5. Bei Priority Queues hat (wenn nicht anders angegeben) das kleinste
Element hoechste Prioritaet?

[Florian Weingarten]

Post by Matthias Lederhofer
2. Spricht man bei Algorithmen die rekursiv arbeiten aber ansonsten
keinen Speicher abhaengig von der Eingabegroesse benoetigen auch von
in situ? Rekursion benoetigt schliesslich auch Speicher auf einem
Stack bzw. auch Variablen die in der Funktion genutzt werden werden ja
mehrfach (abhaengig von der Eingabegroesse) erstellt.

Ich würde sagen ja, da z.B. QuickSort rekursiv arbeitet, in der Vorlesung bzw.
im Skript IIRC aber als in-situ definiert wurde.

Post by Matthias Lederhofer
3. Ist f(n) * O(g(n)) = O(f(n) * g(n))? Falls die Gleichheit nicht
gilt waere ich an einem Gegenbeispiel interessiert.
Wie ist zudem f(n) * O(g(n)) definiert? Ich wuerde es als
{ f(n) * h(n) | h(n) in O(g(n)) } interpretieren.

Würde sagen die Gleichheit gilt..

Post by Matthias Lederhofer
5. Bei Priority Queues hat (wenn nicht anders angegeben) das kleinste
Element hoechste Prioritaet?

Wuerde auch hier sagen, dass das stimmt :-)


Flo

[Friedrich Gretz]

Post by Florian Weingarten

Post by Matthias Lederhofer
2. Spricht man bei Algorithmen die rekursiv arbeiten aber ansonsten
keinen Speicher abhaengig von der Eingabegroesse benoetigen auch von
in situ? Rekursion benoetigt schliesslich auch Speicher auf einem
Stack bzw. auch Variablen die in der Funktion genutzt werden werden ja
mehrfach (abhaengig von der Eingabegroesse) erstellt.

Ich würde sagen ja, da z.B. QuickSort rekursiv arbeitet, in der Vorlesung bzw.
im Skript IIRC aber als in-situ definiert wurde.

Es geht ja nicht darum welche Hilfsvariablen oder Instanzen etc.. das
Programm anlegt, sondern lediglich darum, ob ich die Eingabedaten lese,
mir eine neue Datenstruktur anlege, dort alle Operationen ausführe und
das Ergebnis zurückschreibe
ODER
ob ich direkt alle Operationen des Algorithmus auf der
Eingabedatenstruktur ausführe

==> Quicksort arbeitet auf dem Eingabearray ==> in situ
==> Merge Sort legt neue Arrays an, in die die Eingabedaten kopiert
werden und zusammengeschnipselt werden, dann wird das Ergebnis
zurückgeschrieben ==> nicht in situ

So denke ich mir das.
Gruß,
Friedrich

[Matthias Lederhofer]

Post by Friedrich Gretz
Es geht ja nicht darum welche Hilfsvariablen oder Instanzen etc..
das Programm anlegt, sondern lediglich darum, ob ich die
Eingabedaten lese, mir eine neue Datenstruktur anlege, dort alle
Operationen ausführe und das Ergebnis zurückschreibe
ODER
ob ich direkt alle Operationen des Algorithmus auf der
Eingabedatenstruktur ausführe
==> Quicksort arbeitet auf dem Eingabearray ==> in situ
==> Merge Sort legt neue Arrays an, in die die Eingabedaten kopiert
werden und zusammengeschnipselt werden, dann wird das Ergebnis
zurückgeschrieben ==> nicht in situ

Wir hatten in situ in der Vorlesung nicht so genau definiert.
Zumindest so wie ich es verstanden hatte ging es darum, dass der
Speicherbedarf nicht von der Eingabegroesse abhaengen darf (also O(1)).
Nach Wikipedia[1] ist auch noch eine Speicherplatzkomplexitaet von
O(log(n)) in situ. Dort steht auch weiter, dass Quicksort nicht in
situ ist, weil es eine Speicherplatzkomplexitaet von O(log(n)*log(n))
hat.

[1] http://en.wikipedia.org/wiki/In-place#In_computational_complexity

[Christian Plahl]

Hallo Zusammen,

Post by Matthias Lederhofer
2. Spricht man bei Algorithmen die rekursiv arbeiten aber ansonsten
keinen Speicher abhaengig von der Eingabegroesse benoetigen auch von
in situ? Rekursion benoetigt schliesslich auch Speicher auf einem
Stack bzw. auch Variablen die in der Funktion genutzt werden werden ja
mehrfach (abhaengig von der Eingabegroesse) erstellt.

Ein Algorithmus arbeitet "in situ" oder "in place", falls er auf den
Eingabedaten arbeitet und nicht weitere Datenstrukturen anlegt, auf
denen dann die weiteren Verarbeitungsschritte stattfinden.
Somit ist Quicksort in situ, Mergesort hingegen nicht.

Post by Matthias Lederhofer
3. Ist f(n) * O(g(n)) = O(f(n) * g(n))? Falls die Gleichheit nicht
gilt waere ich an einem Gegenbeispiel interessiert.
Wie ist zudem f(n) * O(g(n)) definiert? Ich wuerde es als
{ f(n) * h(n) | h(n) in O(g(n)) } interpretieren.

die Aufgabe ist so zu verstehen, dass wir mit f+O(g) die MENGE der
Funktionen meinen, die durch jeweilige Addition von f und den
"f(n) + O(g(n))" = { h: h=f+g' mit g' \in O(g) }
Zur Aufgabenstellung: Man muss zeigen (bzw. widerlegen), dass die
beiden Mengen links und rechts des Gleichheitszeichens identisch
sind.

4. Wie geht man bei Substitution bei Rekursionsgleichungen vor?
Bzw. im speziellen: wie wurde T(n) = 2 * T(abgerundet(wurzel(n))) +
ld(n) geloest (ich kann gerade meine Mitschrift nicht mehr
nachvollziehen).

Substituiert wird z.B. mit k = ld(n) <=> n = 2^k
Man erhält damit dann S(k) = T(2^k) = 2 S(0.5*k)+k
Dies kann man mit Hilfe des Mastertheorem lösen. Am Ende refolgt dann
noch die Rücksubstitution.

Post by Matthias Lederhofer

Hallo zusammen,
von einem Tutor haben wir eben die Rückmeldung bekommen, dass die
Substitution noch nicht ganz klar ist.
Daher nochmal der Ansatz, so wie er in der FÜ angesprochen wurde (die
Diskussion im Anschluß betraf nicht das allgemeine Verfahren, sondern
nur das konkrete Beispiel).
Wir wählen eine Variable t als die Substitution von d(n), also zum
Beispiel t := \log_k n
Dann ist n = k^t
Eine Substitutionsfunktion
S(t) = T(k^t) = T(n)
= a T(n^{1/x}) + \log_k n
= a S(t/x) + t
hilft bei der Lösung der Aufgabe (Resubstitution bei der Lösung nicht
vergessen).

5. Bei Priority Queues hat (wenn nicht anders angegeben) das kleinste
Element hoechste Prioritaet?

Ja, das kleinste Element hat die höchste Priorität (Min-Heap).

Gruß Christian

[Gregor Leusch]

Hallo,

Post by Matthias Lederhofer
1. In der Folie zu Hashing steht in den letzten beiden Faellen etwas
von j'. Was ist j'? (Dort steht bei verfeinertem quadratischen
Sondieren: j = j' mod 2 bzw. j != j' mod 2)

Aeh ... das ist nicht "die Folie zu Hashing", sondern *eine* Folie, die
bei den Beweisen fuer die Bedingungen an die Groesse der Hashtabelle bei
den verschiedenen Sondierverfahren als roter Faden dienen sollte.
Die ist nie dafuer gedacht gewesen, ohne Erlaeuterungen und
ausserhalb der Uebung verstaendlich gewesen zu sein.

Genauer gesagt, ging es um Beweise, dass die verschiedenen
Sondierverfahren nur bei bestimmten Tabellengroessen zuverlaessig alle
Positionen sondieren koennen. Diese Bedingungen, und die an die
Hashfunktionen selbst, sind ueberigens durchaus klausurrelevant, wie Sie
in der Probeklausur gesehen haben sollten. Die Beweise jedoch nicht (auch
wenn Sie sicherlich weniger Schwierigkeiten mit den Bedingungen und mit
Hashing an sich haben duerften, wenn Sie auch die Beweise verstanden
haben).

Bei m moeglichen Sondierungsschritten (also genau die 0 <= j <= m-1) kann
ein Sondierverfahren also genau dann immer alle Tabellenplaetze sondieren,
wenn es niemals fuer ein bel. x gueltige j, j' mit j != j' gibt, so dass
h(x,j) = h(x,j') (klar?).

Der Fall "alternierendes quadratisches Sondieren funktioniert fuer m prim
mit m == 3 \mod 4" wird, des einfacheren Beweises wegen, mit einer
Fallunterscheidung behandelt:
14. Es gibt kein x, j, j' mit (0 <= j != j' <= m-1) und (j == j' \mod 2)
so dass h(x,j) = h(x,j')
15. Es gibt kein x, j, j' mit (0 <= j != j' <= m-1) und (j !== j' \mod 2)
so dass h(x,j) = h(x,j')

Der Beweis zu 14 folgt direkt aus dem zu 11 (klar?).

Der Beweis zu 15 braucht, wie auch der zu 13, einiges an Zahlentheorie.
Da mir damals die Zeit nicht gereicht hat, habe ich eine Skizze auf die
Webseite gestellt:
http://www-i6.informatik.rwth-aachen.de/web/Teaching/Lectures/SS06/Datenstrukturen/uebungen/frontaluebung-2006-06-20-fehlende-beweise.pdf
bzw.
http://tinyurl.com/nhgzb

Beachten Sie bitte, dass das "vereinfachte", nichtalternierende
quadratische Sondieren ohnehin nur m/2 verschiedene Tabellenplaetze und
daher nur die Haelfte der Tabelle sondieren kann, was auch ein Grund ist,
es in der Praxis nicht zu verwenden.


Soweit jetzt alles klar?


Gruss

Gregor Leusch

[Christian Plahl]

Hallo,

Post by Matthias Lederhofer
1. In der Folie zu Hashing steht in den letzten beiden Faellen etwas
von j'. Was ist j'? (Dort steht bei verfeinertem quadratischen
Sondieren: j = j' mod 2 bzw. j != j' mod 2)
2. Spricht man bei Algorithmen die rekursiv arbeiten aber ansonsten
keinen Speicher abhaengig von der Eingabegroesse benoetigen auch von
in situ? Rekursion benoetigt schliesslich auch Speicher auf einem
Stack bzw. auch Variablen die in der Funktion genutzt werden werden ja
mehrfach (abhaengig von der Eingabegroesse) erstellt.
3. Ist f(n) * O(g(n)) = O(f(n) * g(n))? Falls die Gleichheit nicht
gilt waere ich an einem Gegenbeispiel interessiert.
Wie ist zudem f(n) * O(g(n)) definiert? Ich wuerde es als
{ f(n) * h(n) | h(n) in O(g(n)) } interpretieren.
4. Wie geht man bei Substitution bei Rekursionsgleichungen vor?
Bzw. im speziellen: wie wurde T(n) = 2 * T(abgerundet(wurzel(n))) +
ld(n) geloest (ich kann gerade meine Mitschrift nicht mehr
nachvollziehen).
5. Bei Priority Queues hat (wenn nicht anders angegeben) das kleinste
Element hoechste Prioritaet?

Gruß Christian