Repetitorien vor der Klausur

Benutzeravatar
Antragon
Mausschubser
Mausschubser
Beiträge: 78
Registriert: 26. Okt 2005 13:09
Kontaktdaten:

Beitrag von Antragon »

Und noch eine Frage:

Was sind die Unterschiede zwischen Klassifikation und Clustering?

Zitat: (Wikipedia) "Die an verschiedene Anforderungen angepassten Verfahren der Clusteranalyse lassen sich zur automatischen Klassifikation [...] oder zum Data-Mining einsetzen."

Sehe ich das richtig? -> Clustering ist das Verfahren mit dem eine Klassifikation erstellt wird?

wach
Computerversteher
Computerversteher
Beiträge: 323
Registriert: 25. Okt 2004 09:08

Beitrag von wach »

Antragon hat geschrieben:Fragen:

* Auswahl der richtigen Variablen beim Hashing:
In der letzten Vorlesung wurde dies grob im Rahmen einer Aufgabe der Klausur aus SS06 erklärt. Leider ist dieser Foliensatz nirgends online zu finden -> Es wäre gut wenn dies somit nochmal (detailliert) erläutert werden könnte!
Könnten Sie hier die Fragen ein wenig konkreter Stellen? Das Haerderskript geht ausfuehrlich auf die Guete von Hashfunktionen ein. Letztlich ist es immer:

* Gleichverteilung
* Erreichen aller Plaetze
* Vermeiden von Primaer und Sekundaerclustern

Das war im SS06 und auch jetzt (wenn auch nicht so umfangreich) auch Gegenstand der Uebung.

Momentan koennte man diesen sehr pauschalen Wunsch dadurch erfuellen, in dem die Bereiche direkte Adressierung und Hashing mit ein paar Beispielen wiederholt werden. Das scheint mir nicht so wirklich im Verhaeltnis zu stehen. Wenn die Themen sonst nicht reichen, kein Thema, aber Sie formulieren generell eher sehr breite Wiederholungswuensche.

kechler
Mausschubser
Mausschubser
Beiträge: 46
Registriert: 21. Nov 2004 22:33
Wohnort: Darmstadt

Beitrag von kechler »

Hallo,

ich habe 2 Fragen zum Skript:

1. Vorlesung 10, Folie 34:
Nach welchen Kriterien splittet man beim B-Baum mit doppeltem Überlauf auf? Beim B-Baum mit m=1 würde man ja die 8 in den Elternknoten splitten, in diesem Fall ist es aber die 9...Eigentlich hätte man hier doch auch noch in den linken Knoten rotieren können, oder?

2. Vorlesung 13, Folie 43:
Wieso nimmt man die Reihenfolge "25, 32, 21, 8, 15" zum neu-hashen und nicht die Eingabe-Reihenfolge "32, 8, 25, 21, 15" ? Desweiteren müsste dann doch auf Folie 44 die "32" auf die Position 5 gehasht werden (für i = 1)?

@tudstudent:
Was genau meinst du damit, dass sich bei Vorlesung 13, Folie 93 die globale Tiefe mit der lokalen Tiefe reiben würde? Wenn man alle Zeiger für den Präfix 1*** auf das Bucket drüber zeigen lassen würde, würde hier die lokale Tiefe auf 0 reduziert werden. Ist das überhaupt zulässig oder darf man das nicht, da die Keys in diesem Bucket nicht mit 1*** anfangen und somit ein Verweis darauf sinnlos ist? Desweiteren würde ja bedeuten, dass bei einer lokalen Tiefe von 0 jeder Key in das Bucket dann eingelagert wird, oder?

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Beitrag von Red*Star »

Graphenalgorithmen, Folie 73 - Dijkstra-Varianten:
%u2022 Bestimmung des maximalen Weges, indem alle Kantenmarkierungen negiert werden.
%u2022 ABER: Nicht in polynomieller Zeit lösbar
%u2022 (NP-Vollständig)
Warum ist das Problem NP-vollständig? So wie ich das sehe ist es einfach eine "Invertierung" des Problems: aus - wird +, aus < wird >, Dijkstra drauf, fertig.

Demzufolge muss es ja mehr als eine Invertierung sein. Ich wüsste gerne, was hier gemeint ist.
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

Benutzeravatar
Antragon
Mausschubser
Mausschubser
Beiträge: 78
Registriert: 26. Okt 2005 13:09
Kontaktdaten:

Beitrag von Antragon »

Zu der Hashingfrage: Es geht vor allem darum nochmal zu zeigen wie man aus einer Aufgabenstellung (wie z.B. die Verteilung der Knöpfe auf dem Schaltbrett) auf die "richtigen" Variablen kommen kann...

Edoat
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 242
Registriert: 26. Feb 2007 15:10

Beitrag von Edoat »

Warum ist das Problem [Ermittlung maximaler Wege] NP-vollständig?
Laut Waldschmidt Skript, S.81 ist für die Bestimmung des maximalen Weges die Ermittlung eines Hamiltonschen Weges (knoteneinfacher Zyklus, der alle Knoten umfasst) erforderlich und dessen Bestimmung ist NP-vollständig.

wach
Computerversteher
Computerversteher
Beiträge: 323
Registriert: 25. Okt 2004 09:08

Beitrag von wach »

Red*Star hat geschrieben:Graphenalgorithmen, Folie 73 - Dijkstra-Varianten:
Warum ist das Problem NP-vollständig? So wie ich das sehe ist es einfach eine "Invertierung" des Problems: aus - wird +, aus < wird >, Dijkstra drauf, fertig.
HINT: Negative Kreise

Benutzeravatar
N_N
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 7. Jul 2005 14:29

Beitrag von N_N »

Hier meine Fragen:

- Wenn man die Komplexität von Algorithmen angeben soll, welchen Fall muss man dann angeben? best, averge oder worst case?

- Ü3 Aufgabe 3.2(d): Gilt für den Satz von Cayley auch die Voraussetzung, dass der Graph vollständig sein muss?

- Ü7 Aufgabe 7.7 (e): Die Frage hier ist, wieviele Schlüssel muss man mind. in einen AVL-Baum einfügen, damit dieser auf Stufe 2 vollständig ist. Die Antwort hierfür lautet: Man sucht einen AVL-Baum bei dem auf Stufe 2 genau ein Knoten fehlt... Ich verstehe nicht, wie der AVL-Baum noch vollständig sein kann, wenn man einen Knoten auf Stufe 2 weglässt?

- Ü7 Aufgabe 7.8 (b): Um einen B-Baum minimal zu befüllen, muss man die Einfügereihenfolge sortieren. Wie sieht die Vorgehensweise aus, um den B-Baum maximal zu befüllen?

Benutzeravatar
Red*Star
Kernelcompilierer
Kernelcompilierer
Beiträge: 510
Registriert: 28. Nov 2006 19:40

Beitrag von Red*Star »

wach hat geschrieben:HINT: Negative Kreise
Jein. Wenn ich einen Graphen mit positiven Markierungen habe und diese negiere - und dann nach dem maximalen Weg suche, habe ich eine zu Dijkstra isomorphe Problemstellung. Nur ist der _maximale_ Weg dann halt _negativ_ ("betragsmäßig am kleinsten").
Genau deshalb habe ich ja gefragt, ob ich da irgendwas auf der Folie missverstanden habe. (Hat sich die Folie überhaupt jemand von euch angeschaut, oder habt ihr einfach drauf losgeposted, ihr Schelme? ;) [Sprich so wie ich das auch immer mache :mrgreen:.])

Um negative Zyklen kann es eigentlich auch nicht gehen: Wenn negative Zyklen in normalen Graphen auftreten, wird die Sache mit dem SSSPP (single source shortest path problem) ja eh witzlos, weil dann der minimale Weg zu allen Knoten, über die man irgendwie über einen dieser negativen Zyklen kommen kann "-unendlich" ist. Mit NP hat das erstmal nichts zu tun, nur mit "Algorithmus baut Mist" (Dijkstra) bzw. "Algorithmus terminiert und sagt, er hat einen Zyklus entdeckt" (Bellman-Ford mit Negativzyklusdetektion).

Hat vielleicht doch Edoat recht und es geht eigentlich um das Hamilton-Weg-Problem, das dann ja wirklich in NP liegt?
Was Sonnenschein für das schwarze Erdreich ist,
ist wahre Aufklärung für die Verwandten des Erdreichs.

- N.F.S. Grundtvig

Benutzeravatar
corn
Ehemalige Fachschaftler
Beiträge: 28
Registriert: 17. Okt 2004 19:08
Wohnort: Groß-Umstadt
Kontaktdaten:

Beitrag von corn »

Red*Star hat geschrieben: Wenn ich einen Graphen mit positiven Markierungen habe und diese negiere - und dann nach dem maximalen Weg suche, habe ich eine zu Dijkstra isomorphe Problemstellung.
Ich denke du hast da was falsch Verstanden. In der Folie geht es darum ob man Dijkstra nutzen kann um in einem gegebenen Graphen (mit positiven Kantengewichten) einen maximalen Weg zu berechnen.

Naiver Ansatz: Alle Kantengewichte mit (-1) multiplizieren und danach einen standard Dijkstra anwenden (also einen der in dem neuen Graph den kützesten Weg sucht).
Hatte der Algorithmus im original Graph z.B. die Wahl (1, 4, 7) hätte er zunächst die Kante mit dem Gewicht 1 gewählt, im neuen Graphen nun aber (-7, -4, -1) würde er die -7 (da kleinste Zahl) zuerst wählen. Also könnte man denken, dass man am Ende der Berechnung der nun so ermittelten Weg dem längsten Weg im original Graphen entspricht. Was so aber nicht der Fall ist.

Das heisst schlicht und ergreifend: Dijkstra taugt so nicht zum ermitteln eines maximalen Weges.

Benutzeravatar
corn
Ehemalige Fachschaftler
Beiträge: 28
Registriert: 17. Okt 2004 19:08
Wohnort: Groß-Umstadt
Kontaktdaten:

Beitrag von corn »

Passend dazu: :-)

Im erste Repetitorium wird es um Graphen und Graphenalgorithmen gehen. Damit ich das vernünftig Vorbereiten kann sollten alle Fragen die am Dienstag berücksichtigt werden bis spätestens heute 16:00 hier in diesem Thread gesammelt sein. Spätere Fragen können dann nicht mehr berücksichtigt werden.

tgp
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 268
Registriert: 15. Nov 2006 21:41

Beitrag von tgp »

G 4.4 b) Lösungshinweise:

Wieso ermittelt Dijkstra für den Weg von A nach C die Länge 2? Wenn ich das mit dem im fünften Foliensatz vorgestellten Dijkstra mache, wird der (mit 1 bessere) Weg über B trotzdem gefunden.

Eine Möglichkeit wäre, dass ein Algorithmus den direkten Weg von A nach C (Länge 2) gefunden hat, und es dann nicht mehr über B versucht, da die Kante mit Länge 4 schon zu lang ist. Das wäre dann aber nicht mehr Dijkstra, denn beim "single-source shortest path"-Problem müsste diese trotzdem betrachtet werden, um den kürzesten Weg von A nach B zu finden.

Ondori
Mausschubser
Mausschubser
Beiträge: 89
Registriert: 28. Okt 2006 19:50

Beitrag von Ondori »

Fragen, die ich gerne beantwortet hätte:

- Wie überprüfe ich die geschlossene Form einer Rekurrenzgleichung, die T(n/2)
enthält, mittels vollständiger Induktion (Bsp. G1.3 e) )?
- Wie funktioniert ein Zyklentest mit Breitensuche?
- (Zur 1. Probeklausur Aufg. 2 b) )
Kann man einen zunehmenden Fluss bei Ford-Fulkerson (besser) durch DFS oder
BFS bestimmen?
- Muss die halbsequentielle Darstellung eines Baumes immer in Vorordnung sein oder ist das optional?

Themen, die ich gerne wiederholt hätte:

- Wie funktioniert Radixsort?
- Zu geom. Datenstrukturen:
Linearisierung des mehrdim. Raumes durch raumfüllende Kurven.
Speicherung eines Punktes im kd Trie (durch Bit interleaving)

Vielen Dank

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Beitrag von MisterD123 »

flusszunahme mit BFS weil dann kürzere wege für den zunehmenden fluss gefunden werden, weniger rückkanten, schnellere terminierung.

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Beitrag von marlic »

Frage zu Binären Radix / Patricia / Binären Suchbäumen:

Wir haben nie wirklich einen bestimmten Aufbau Algorithmus besprochen und auch in den Lösungen wurde munter Sortiert, bevor der Baum Aufgebaut wurde.

Sehe ich es richtig, dass wir uns - falls wir einen dieser Bäume bauen sollen, einfach irgendeinen solchen Baum der die Informationen enthält ausdenken, solange er den Spezifikationen des Baumes entspricht und die korrekten Daten zurück liefert?
"Copy & Passed"

Wahlspruch der Plagiatoren

Antworten

Zurück zu „Archiv“