Repetitorien vor der Klausur

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

Beitrag von Antragon »

Weitere Frage:

MergeSort:
In der Einleitungsvorlesung wird Mergesort ähnlich wie bei der Wikipedia erklärt, im Foliensatz 12 jedoch ist hier eine andere Bescheibung ("vorsortierung mit z.B. Quicksort" etc.).
1. Was ist nun das Mergesort das wir für die Klausur können müssen?
2. Eine generelle Erklärung zu Mergesort wäre auch nochmal praktisch, da sich aus den Folien der Algorithmus nicht nachvollziehen lässt und auch im Buch von Cormen nichts dazu steht.

Rookie
Erstie
Erstie
Beiträge: 16
Registriert: 5. Mai 2007 11:04

Beitrag von Rookie »

Ich habe eine Frage zum Dynamischen Hashing im Kapitel 13 Folie 93:

Wieso darf der leere Behälter nicht gelöscht werden? Darf die lokale Tiefe in dem Bucket drüber nicht bis auf 0 gesenkt werden?

Benutzeravatar
tudstudent
DON'T PANIC
Beiträge: 42
Registriert: 6. Jun 2005 10:55

Beitrag von tudstudent »

Rookie hat geschrieben:Ich habe eine Frage zum Dynamischen Hashing im Kapitel 13 Folie 93:

Wieso darf der leere Behälter nicht gelöscht werden? Darf die lokale Tiefe in dem Bucket drüber nicht bis auf 0 gesenkt werden?
IMHO, leerer bucket bleibt auf jeden fall stehen, da sich andernfalls globale und lokale tiefe reiben würden.
Zudem entsteht in seltenen fällen ein leerer bucket.

Benutzeravatar
oren78
BSc Spammer
BSc Spammer
Beiträge: 1373
Registriert: 17. Nov 2006 17:47
Wohnort: Darmstadt

Beitrag von oren78 »

Also, erstmal vielen Dank für die schnelle und verständliche Antwort...

So, genug gesäuselt - weitere Fragen:
------------------------------------------------------------------------------------

1.) Welche Datenstruktur (ausser der Hashtabelle) schafft es einen konstanten Zugriff zu ermöglichen?

2.) Gilt für ein Fibonacci Baum die folgenden Aussagen:

Fib.Baum ist auch ein (minimal besetzter) AVL Baum,
somit also auch ein Suchbaum,
fast vollständig,
hat eine Such-Komplexität von: O(log n)
ist (falls er gespiegelt wird) ein minimalbesetzter AVL-Baum,
der dann jedoch KEIN Fib.Baum mehr ist...?

3.) In der 4ten Übung, (Hausübung - Bellman Ford, Musterlösung) ist ein ungerichteter Graph skizziert über den dann der Bellman Algo ausgeführt werden soll, soviel ich weiß MUSS jedoch ein gerichteter Graph vorrausgesetzt werden, ehe man den Algo anwenden kann, oder ??

soweit fürs erste...

schon mal vielen Dank im Vorraus ;-)
"Unter allen menschlichen Entdeckungen sollte die Entdeckung der Fehler die wichtigste sein.", Stanisław Jerzy Lec

Can
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 223
Registriert: 17. Okt 2006 15:14
Kontaktdaten:

Beitrag von Can »

wach hat geschrieben:
Can hat geschrieben:Ich hätte noch eine Frage, zu der Aufgabe G 6.4. c (aus der 6. Übung).
Dort geht es um die mittleren Suchtiefen bei erfolglosen Suchen.

Man muss ja die Nullzeiger mitbetrachten, nur bekomme ich bei der Summe oben im Nenner, immer genau eine (Knotenstufe+1) weniger raus.
Also bei der i) statt 80 -> 89 und bei der ii) statt 41 -> 49.
Ich bekomme immer eine Knotenstufe+1 mehr raus.....
Kann es also sein, dass man die letzte dann bei der erfolglosen mittleren Suchtiefe weglässt?
Ist das damit nicht beantwortet?
http://www.fachschaft.informatik.tu-dar ... php?t=9261
ja, ist es.. vielen Dank :)

WaTz
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 9. Nov 2006 20:08
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von WaTz »

Man kann jeden ungerichteten Graphen als gerichteten Graphen interpretieren indem man jede ungerichtet Kante durch eine Hin- und Rückkante mit gleichem Gewicht ersetzt. Umgekehrt geht das jedoch nicht.

qveXx
Mausschubser
Mausschubser
Beiträge: 64
Registriert: 2. Dez 2005 19:02

Beitrag von qveXx »

Frage:
* Gibt es beim Mischen von Mehrwegbäumen nach dem Löschen, wenn ein Unterlauf entsteht, ein "algorithmisches" Vorgehen? *

Bis jetzt habe ich es mehr so aus dem Skript heraus verstanden, das Pi mal Daumen am Ende überall etwa gleich viele Elemente enthalten sein sollen und die Kriterien erfüllt (min. 2k-Nachfolger, höchstens ... etc)

Aber ein "algorithmisches" Vorgehen, wie bei den AVL-Bäumen, habe ich bis jetzt noch nicht bemerkt.

MvS
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 26. Okt 2005 20:33

Beitrag von MvS »

Fragen fürs Repititorium:

1) Die Erweiterung im "neuen" Skript von Bellmann im Kapitel 9 nochmal erklären.
Bisher ist mir nicht 100%ig klar wie ich die Tabellen am günstigsten erstelle

2)Dynamische Programmierung mit Beispiel nochmal vorstellen

3)Quicksort mit Trace (nachdem der Algo in den Folien murks ist)

4)Erklärung der verschiedenen Klassen bei B-Bäumen.(wie kommt man von einer
Notation zu anderen.)

5)Nach welchem Schema entstehen die Leerfelder bei der Feldbaum/Vater/verkettete/halbsequenzielle/sequenzielle Darstellung von Bäumen in Tabellen

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

Beitrag von MisterD123 »

rotieren wenn möglich, wenn nicht möglich ist zusammenlegen möglich => das machen.
(möglich heißt so viel wie ein nachbarknoten hat noch mehr elemente als die minimale zahl pro knoten, bei zusammenlegen haben beide minimale knotenzahl so dass sie zusammengelegt in einene knoten passen.)

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

Beitrag von wach »

qveXx hat geschrieben:Frage:
* Gibt es beim Mischen von Mehrwegbäumen nach dem Löschen, wenn ein Unterlauf entsteht, ein "algorithmisches" Vorgehen? *
Bei B- und B+ Bäumen ist das genau spezifiziert. Siehe Härder.

Bei höheren Splitfaktoren ist das nicht genau spezifiert und wird folglich auch nicht auf "genau" eine Art erwartet.

Gruß,
Christian

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

Beitrag von wach »

MvS hat geschrieben: 2)Dynamische Programmierung mit Beispiel nochmal vorstellen
Das algorithmische Prinzip oder ein bestimmter Algorithmus?

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

Beitrag von wach »

MvS hat geschrieben: 3)Quicksort mit Trace (nachdem der Algo in den Folien murks ist)
Ist er nicht. Die Variante in der Vorlesung arbeitet mit Terminalen an den Rändern und funktioniert. Wer nicht in der Vorlesung war und das Beispiel nicht mitgeschrieben hat, weiss kann das natürlich schlecht wissen.

Im Zweifel tuts

Code: Alles auswählen

import java.util.Arrays;
public class Quicksort {
	
	public static int getPivotIndex(int[] arr, int left, int right){
		//Nimmt das linke Element als Pivot
		return left;
	}
	
	public static void swap(int[] arr, int x, int y){
		int tmp=arr[x];
		arr[x]=arr[y];
		arr[y]=tmp;
	}
	
	public static void quicksort(int[] arr, int left, int right){
		if (left >= right)
			return;
		
		//Finde Pivot und tausche es an den rechten Rand
		int pivot_index = getPivotIndex(arr, left, right);
		int pivot = arr[pivot_index];
		swap(arr,pivot_index,right);
		pivot_index=right;
		
		int i = left;
		int j = right-1;
		
		do {
			swap(arr,i,j);		
			while (i < right && arr[i]<pivot) {i++;}
			while (j > left && arr[j]>=pivot) {j--;}
			
		} while (i < j);
		//Tausche das Pivot zwischen die beiden Listen
		//Das Element, das auf dieser Position steht ist
		//größer und gehört daher in die rechte Teilliste
		swap(arr,pivot_index,i);
		quicksort(arr, left, i-1);
		quicksort(arr, i+1, right);
	}
	
	
	public static void main(String[] argv){
		int[] foo = {23452,342,33,11,232,3,2134,17};
		
		quicksort(foo, 0, foo.length -1);
		System.out.println(Arrays.toString(foo));
	}

}

X-Out
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 14. Mai 2007 19:06

Beitrag von X-Out »

G8.3 Einfügereihenfolge bei B-Baum

Gibt es da ein festes Schema oder hilft da nur "rumprobrieren"?
Wie füllt man ein Baum maximal (Schema?)?
Minimal befüllt es er doch, wenn ich die Daten vorher durchsortiere oder?

Über ein Bespiel mit dem erweiterbaren hashing würd ich mich auch freuen ..:) das mit der lokalen und globalen tiefe ist mir noch nicht so ganz klar.

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

Beitrag von Antragon »

X-Out hat geschrieben: Über ein Bespiel mit dem erweiterbaren hashing würd ich mich auch freuen ..:) das mit der lokalen und globalen tiefe ist mir noch nicht so ganz klar.
Wäre ich auch nochmal dran interessiert ;-)

Weitere Frage:
* Bei Quadtree und k-d tree: Was heißt in diesem Zusammenhang "Parallelisierbar"?

MvS
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 26. Okt 2005 20:33

Beitrag von MvS »

wach hat geschrieben:
MvS hat geschrieben: 2)Dynamische Programmierung mit Beispiel nochmal vorstellen
Das algorithmische Prinzip oder ein bestimmter Algorithmus?
Das algorithmische Prinzip am Beispiel der Aufgaben G9.1/G9.2 aus den Übungen wäre vielleicht keine schlechte Idee denke ich.

Antworten

Zurück zu „Archiv“