Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.
  • 1
  • 2

Arne

ThI

  • "Arne" is male
  • "Arne" started this thread

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

1

Wednesday, March 17th 2004, 3:06pm

D&a

Skript Seite 2.13:
kann mir wer folgende mathematische Umformungen erklären?

sum^n_{u=1} sum^n_{o=u} sum^o_{i=u} 1
= sum^n_{o=1} sum^o_{u=1} (o - u + 1)
= sum^n_{o=1} sum^o_{k=1} k
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

2

Wednesday, March 17th 2004, 4:41pm

RE: D&a

Quoted

Original von vier
Skript Seite 2.13:
kann mir wer folgende mathematische Umformungen erklären?

sum^n_{u=1} sum^n_{o=u} sum^o_{i=u} 1
= sum^n_{o=1} sum^o_{u=1} (o - u + 1)
= sum^n_{o=1} sum^o_{k=1} k


Zuerst ein Zwischenschritt zwischen Zeile 1 und 2:

sum^n_{u=1} sum^n_{o=u} sum^o_{i=u} 1
= sum^n_{u=1} sum^n_{o=u} (o - u + 1)

Die Zahl 1 wird also in der letzten Summe einfach (o-u+1)-mal addiert.

Dann gilt ganz allgemein
sum^n_{u=1} sum^n_{o=u} f(o,u) = sum^n_{o=1} sum^o_{u=1} f(o,u)
Dies kann man durch Induktion über n recht einfach zeigen.

Damit haben wir also
sum^n_{u=1} sum^n_{o=u} (o - u + 1)
= sum^n_{o=1} sum^o_{u=1} (o - u + 1)

Jetzt fehlt nur noch die letzte Zeile, und die erhält man, indem man statt u eine neue
Laufvariable k mit der Eigenschaft k = o - u + 1 einführt.
Für u=o gilt dann k=1 und für u=1 gilt k=o.
Matthias Galota

This post has been edited 1 times, last edit by "Spike" (Mar 17th 2004, 4:43pm)

  • Send private message

Arne

ThI

  • "Arne" is male
  • "Arne" started this thread

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

3

Wednesday, March 17th 2004, 5:08pm

RE: D&a

Quoted

Original von Spike
Die Zahl 1 wird also in der letzten Summe einfach (o-u+1)-mal addiert.


Kann man das irgendwie aus den Summenformeln ableiten oder muss man das "sehen"? Ich konnte es mir eben an einer Tabelle klar machen, aber gibts da nirgends irgendwelche Regeln für solche Umformungen? :)
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

This post has been edited 1 times, last edit by "Arne" (Mar 17th 2004, 5:14pm)

  • Send private message

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

4

Wednesday, March 17th 2004, 5:16pm

RE: D&a

Quoted

Original von vier

Quoted

Original von Spike
Die Zahl 1 wird also in der letzten Summe einfach (o-u+1)-mal addiert.


kann man das irgendwie aus den Summenformeln ableiten oder muss man das "sehen"?


Das ist das, was die Summenformel aussagt. "sum^o_{i=u} 1" heißt doch: Wir haben einen Zähler i, der bei u beginnt und dann jeweils um 1 erhöht wird, bis er bei o ankommt, und in jedem Schritt wird 1 addiert. Also wird die Zahl 1 (o-u+1)-mal addiert.
Matthias Galota
  • Send private message

Arne

ThI

  • "Arne" is male
  • "Arne" started this thread

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

5

Wednesday, March 17th 2004, 5:20pm

ah ich hatte eben ein Brett vorm Kopf und dachte immer statt der 1 an ein "i" :). jo nun ist es klar!
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

Arne

ThI

  • "Arne" is male
  • "Arne" started this thread

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

6

Wednesday, March 17th 2004, 5:28pm

Wenn ich jetzt an dieser Stelle sage k=o-u+1:
sum^n_{u=1} sum^n_{o=u} (o-u+1), dann wäre dass doch eigentlich
sum^n_{k=o} sum^n_{k=1} (o-u+1) oder?

Der Schritt dann zu "sum^n_{o=1} sum^o_{k=1} k" ist mir noch nicht ganz klar, sorry aber hab da irgendwie nen Brett vorm Kopf :)
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

7

Wednesday, March 17th 2004, 6:14pm

Quoted

Original von vier
Wenn ich jetzt an dieser Stelle sage k=o-u+1:
sum^n_{u=1} sum^n_{o=u} (o-u+1), dann wäre dass doch eigentlich
sum^n_{k=o} sum^n_{k=1} (o-u+1) oder?


Nein, es wäre dann
sum^n_{u=1} sum^{n-u+1}_{k=1} k

Die zweite Summation "sum^n_{o=u} (o-u+1)" hat den Laufindex o,
der von u nach n geht und sieht so aus:

sum^n_{o=u} (o-u+1)
= (u-u+1) + (u+1-u+1)+(u+2-u+1) + ... + (n-1-u+1)+(n-u+1)
= 1 + 2 + 3 + ... + (n-u) + (n-u+1)

Wir wollen jetzt die Summe in der zweiten, einfacheren Form schreiben. Dazu
ändern wir den Laufindex von o nach k mit k=(o-u+1). Dann müssen wir Start und Ende der Summation ändern: Wenn o=u ist, dann ist k=u-u+1=1 und wenn o=n ist, dann ist
k=n-u+1.

Schließlich erhalten wir die Summenformel "sum^{n-u+1}_{k=1} k".

Da sich an der äußeren Summenformel nichts ändert, kommt insgesamt
sum^n_{u=1} sum^{n-u+1}_{k=1} k
heraus.


Quoted

Original von vier
Der Schritt dann zu "sum^n_{o=1} sum^o_{k=1} k" ist mir noch nicht ganz klar, sorry aber hab da irgendwie nen Brett vorm Kopf :)


Der Schritt ist deshalb nicht klar, weil so nicht geht. Du musst die Schritte in der Reihenfolge machen, in der sie angegeben sind:

Zuerst die letzte Summation zusammenfassen:

sum^n_{u=1} sum^n_{o=u} sum^o_{i=u} 1
= sum^n_{u=1} sum^n_{o=u} (o - u + 1)

Dann die innere und äußere Summation vertauschen:

sum^n_{u=1} sum^n_{o=u} (o - u + 1)
= sum^n_{o=1} sum^o_{u=1} (o - u + 1)

Und am Schluss den neuen Laufindex einführen:

sum^n_{o=1} sum^o_{u=1} (o - u + 1)
= sum^n_{o=1} sum^o_{k=1} k
Matthias Galota

This post has been edited 1 times, last edit by "Spike" (Mar 17th 2004, 6:16pm)

  • Send private message

Arne

ThI

  • "Arne" is male
  • "Arne" started this thread

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

8

Wednesday, March 17th 2004, 6:50pm

Quoted

Original von Spike
Und am Schluss den neuen Laufindex einführen:

sum^n_{o=1} sum^o_{u=1} (o - u + 1)
= sum^n_{o=1} sum^o_{k=1} k


Kannst du den Schritt nochmal ausführlich (wie oben) mal hinschreiben, weil irgendwie seh ichs nicht ;). Danke schonmal für deine super Hilfe!
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

9

Wednesday, March 17th 2004, 7:00pm

Quoted

Original von vier

Quoted

Original von Spike
Und am Schluss den neuen Laufindex einführen:

sum^n_{o=1} sum^o_{u=1} (o - u + 1)
= sum^n_{o=1} sum^o_{k=1} k


Kannst du den Schritt nochmal ausführlich (wie oben) mal hinschreiben, weil irgendwie seh ichs nicht ;). Danke schonmal für deine super Hilfe!


OK, es geht also nur um die innere Summation "sum^o_{u=1} (o - u + 1)"
Diesmal ist u der Laufindex. Er geht von 1 bis o und die Summe sieht so aus:

sum^o_{u=1} (o - u + 1)
= (o-1+1) + (o-2+1) + ... + (o-(o-1)+1) + (o-o+1)
= o + (o-1) + ... + 2 + 1
= 1 + 2 + ... + (o-1) +o

Wir wollen die Summe in der letzten, einfachen Form schreiben. Dazu
ändern wir den Laufindex von u nach k mit k=(o-u+1). Dann müssen wir Start und Ende
der Summation ändern: Wenn u=o ist, dann ist k= o-o+1 = 1 und wenn u=1 ist, dann ist
k= o-1+1 = o.

Also haben wir die Summenformel "sum^o_{k=1} k".
Beachte, dass die neue Summe "umgekehrt" läuft. Der Anfang der alten Summe ist
also das Ende der neuen und umgekehrt.

Das war die Umformung der inneren Summe. Insgesamt erhalten wir also
sum^n_{o=1} sum^o_{k=1} k
Matthias Galota
  • Send private message

NullAhnung

Erfahrener Schreiberling

  • "NullAhnung" is female

Posts: 332

Date of registration: Apr 28th 2003

10

Thursday, March 18th 2004, 1:15pm

Kann mir jemand dies zuschicken?

Std-Übung 3
Std-Übung 4
Std-Übung 6
Std-Übung 7


Fragen:
Blatt 6 (Std-Übung)
Warum geht hier nicht der Baum?
Wurzel E Kinder A,B Kinder von A: C,D

Blatt 8 (Std-Übung)
Wie genau funktioniert das Double-Hashing? Bitte in gaaanz einfachen Worten ;)

Blatt 11 (Std-Übung)
Ginge für den Tiefendurchlauf auch folgender Stammbaum? Wenn nicht, warum nicht.
Wurzel 8, Kinder 6,7 Kind von 6: 2 und die restlichen untereinander.
  • Send private message

Benjamin

Segelnder Alter Hase

  • "Benjamin" is male

Posts: 3,827

Date of registration: Oct 1st 2002

Location: Region Hannover

Occupation: Alumni

11

Thursday, March 18th 2004, 1:19pm

Quoted

Original von NullAhnung
Kann mir jemand dies zuschicken?

Std-Übung 3
Std-Übung 4
Std-Übung 6
Std-Übung 7


Alle Übungen mit Musterlösungen sowie die Stundenübungen gibt es doch im Web.

edited: in den PDFs der Stundenübungen sind auch Lösungen dazu
Es gibt nur eine bessere Sache als auf dem Wasser zu sein: Noch mehr auf dem Wasser sein.

This post has been edited 1 times, last edit by "Benjamin" (Mar 18th 2004, 1:28pm)

  • Send private message

Arne

ThI

  • "Arne" is male
  • "Arne" started this thread

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

12

Thursday, March 18th 2004, 1:20pm

Quoted

Original von NullAhnung
Blatt 8 (Std-Übung)
Wie genau funktioniert das Double-Hashing? Bitte in gaaanz einfachen Worten ;)

Du hast 2 hash-Funktionen. Mit h1 berechnest du das Feld an welcher Stelle die Zahl dann hinkommt. Ist dort schon eine Zahl kommt h2 ins Spiel. Der Wert dieser hash-Funktion gibt an, um wieviele Felder die Zahl nach rechts verschoben wird (wird so oft wiederholt bis das Feld frei ist).
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

This post has been edited 2 times, last edit by "Arne" (Mar 18th 2004, 1:27pm)

  • Send private message

skl

Praktikant

  • "skl" is male

Posts: 20

Date of registration: Apr 15th 2003

13

Thursday, March 18th 2004, 3:21pm

Quoted

Original von NullAhnung
Fragen:
Blatt 6 (Std-Übung)
Warum geht hier nicht der Baum?
Wurzel E Kinder A,B Kinder von A: C,D


Du hast recht. Der Lösungshinweis ist hier nicht vollständig. Es wird dort nur eine mögliche Lösung vorgestellt. Denkbar sind wohl alle Bäume, die nicht höher als 3 sind.

skl
  • Send private message

Benjamin

Segelnder Alter Hase

  • "Benjamin" is male

Posts: 3,827

Date of registration: Oct 1st 2002

Location: Region Hannover

Occupation: Alumni

14

Thursday, March 18th 2004, 7:39pm

Am Ende von Kapitel 2 im Skript stehen jene "verwandte Notationen" für die asymptotische Analsyse. Irgendwie fällt mir gerad auf, dass ich das nicht ganz kapier.

O( g(n) ) ist klar die maximal Größenordnung, also die Abschätzung nach oben.
\Omega ( g(n) ) ist die mindeste Größenordnung, also qausi die Abschätzung nach unten.
DOCH wie soll ich denn dann \Theta( g(n) ) verstehen? Das ist sowohl O(g(n)) als auch \Omega(g(n)) ? Wie soll ich mir das vorstellen? irgendwie blick ich das gerade nicht.
Es gibt nur eine bessere Sache als auf dem Wasser zu sein: Noch mehr auf dem Wasser sein.
  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

15

Thursday, March 18th 2004, 8:03pm

Quoted

Original von metalhen
O( g(n) ) ist klar die maximal Größenordnung, also die Abschätzung nach oben.
\Omega ( g(n) ) ist die mindeste Größenordnung, also qausi die Abschätzung nach unten.
DOCH wie soll ich denn dann \Theta( g(n) ) verstehen? Das ist sowohl O(g(n)) als auch \Omega(g(n)) ? Wie soll ich mir das vorstellen? irgendwie blick ich das gerade nicht.
Beispiel:

f(n) := 3 * n^4 + 2 * n + 100

Dann gilt:

f(n) = O(n^4)
f(n) = O(n^5)
f(n) = O(n^6)
...

f(n) = Omega(n^4)
f(n) = Omega(n^3)
f(n) = Omega(n^2)
...

O(...) sind obere Schranken, Omega(...) untere Schranken und Theta(...) ist beides. Im Beispiel gilt daher nur f(n) = Theta(n^4), da f(n) = O(n^4) und f(n) = Omega(n^4).

Theta(...) ist also sowas wie eine größenordnungsmäßig kleinste obere Schranke.
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962

This post has been edited 2 times, last edit by "Joachim" (Mar 18th 2004, 8:05pm)

  • Send private message

NullAhnung

Erfahrener Schreiberling

  • "NullAhnung" is female

Posts: 332

Date of registration: Apr 28th 2003

16

Friday, March 19th 2004, 8:14pm

Quoted

Original von vier

Quoted

Original von NullAhnung
Blatt 8 (Std-Übung)
Wie genau funktioniert das Double-Hashing? Bitte in gaaanz einfachen Worten ;)

Du hast 2 hash-Funktionen. Mit h1 berechnest du das Feld an welcher Stelle die Zahl dann hinkommt. Ist dort schon eine Zahl kommt h2 ins Spiel. Der Wert dieser hash-Funktion gibt an, um wieviele Felder die Zahl nach rechts verschoben wird (wird so oft wiederholt bis das Feld frei ist).


Zähle ich, wenn ich die zweite Hashfunktion benutze, das Feld wo ich anfange mit? Und wenn ich ende und da steht schon ne Zahl, zählt das Feld dann auch mit?
  • Send private message

Arne

ThI

  • "Arne" is male
  • "Arne" started this thread

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

17

Friday, March 19th 2004, 11:19pm

Quoted

Original von NullAhnung
Zähle ich, wenn ich die zweite Hashfunktion benutze, das Feld wo ich anfange mit? Und wenn ich ende und da steht schon ne Zahl, zählt das Feld dann auch mit?

Nein du zählst das Feld wo du bist nicht mit. du zählst dann einfach weiter, wie im Beispiel auf Skript Seite 4.56
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

NullAhnung

Erfahrener Schreiberling

  • "NullAhnung" is female

Posts: 332

Date of registration: Apr 28th 2003

18

Sunday, March 21st 2004, 2:44pm

Und noch ein paar Fragen zum Thema ;)

Folie 3.3
Vorfahr ist also v selbst und der Elternknoten und der Elternknoten vom Elternknoten usw. bis zur Wurzel?

Woher weiß ich wann ich eine einfache und wann eine doppelte Rotation benutze?

Ist die Störstelle immer der Knoten mit der größeren Höhe?

Was sind B*- und B+ - Bäume?

Wie funktioniert InPlace-Quick-Sort?

Was ist inzident? Wie soll ich mir das vorstellen: Kante stößt an Knoten?

Folie 6.39
Wann schreibt man unendlich in die Tabelle D? Ist dies, wenn es keine direkte Verbindung vom Knoten zur Wolke gibt?

Verstehe nicht wie ich auf die transitive Hülle komme!??? :(

Kommen die Folien 6.11 bis 6.98 auch dran?
  • Send private message

Arne

ThI

  • "Arne" is male
  • "Arne" started this thread

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

19

Sunday, March 21st 2004, 7:28pm

Quoted

Original von NullAhnung
Und noch ein paar Fragen zum Thema ;)

Gerne doch :rolleyes:

Quoted

Original von NullAhnung
Folie 3.3
Vorfahr ist also v selbst und der Elternknoten und der Elternknoten vom Elternknoten usw. bis zur Wurzel?

"Ein Vorfahr (ancestor) eines Knotens v ist entweder v selbst...". D.h. v wäre Root.
"...oder ein Vorfahr des Elternknotens von v." Erklärt sich von selber oder? ;)

Quoted

Original von NullAhnung
Woher weiß ich wann ich eine einfache und wann eine doppelte Rotation benutze?


SingleRotation wenn "alle in einer Richtung dranhängen" (also entweder nur rechte oder linke Kinder).
Doppelte Rotation wenn ein "Zickzack" vorliegt (also Knoten, dann rechts Kind, was links ein Kind hat oder umgekehrt).

Quoted

Original von NullAhnung
Ist die Störstelle immer der Knoten mit der größeren Höhe?

Kommt darauf an, wie du Störstelle definierst. Aus meiner Sicht, ist die Störstelle der Knoten, der eben das unballanced auslöst, was in dem Fall der zuletzt angefügt Knoten wäre.

Quoted

Original von NullAhnung
Was sind B*- und B+ - Bäume?


Bei B*-Bäumen werden die Nutzdaten (oder Verweise auf Stammdaten) nur in Blättern gespeichert (Bsp: Telefonbuch).
Wann hatten wir "B+" Bäume? Ich persönlich kann mich nur noch an B'-Bäume erinnern.. Meintest Du die?

Quoted

Original von NullAhnung
Wie funktioniert InPlace-Quick-Sort?


Das rechts liegende Element ist Pivot. An Stelle 0 fängt l und an Stelle n-2 (vorletzte) r an zu scannen.
Zuerst bewegt sich r schrittweise bis zum mittleren Element (bzw. n/2) und vergleicht in jedem Schritt sein Element mit dem von l. Ist das Element von l größer als das Pivot und das Element von r kleiner als das Pivot so werden beide Items geswapt, sonst nicht. Wenn l an der Mitte angekommen ist, geht l auf die Mitte (bzw. bis auf das Element vor r) zu und vergleicht wie vorher. Zum Schluss wird das Element wo r steht mit dem Pivot geswapt...

Quoted

Original von NullAhnung
Was ist inzident? Wie soll ich mir das vorstellen: Kante stößt an Knoten?

Inzident sind die Kanten die an einen Knoten stoßen, korrekt.

Quoted

Original von NullAhnung
Folie 6.39
Wann schreibt man unendlich in die Tabelle D? Ist dies, wenn es keine direkte Verbindung vom Knoten zur Wolke gibt?


Ja.

Quoted

Original von NullAhnung
Verstehe nicht wie ich auf die transitive Hülle komme!??? :(


In dem du jeden Knoten mit den restlichen aus dem Graphen verbindest, mit denen er noch nicht verbunden war.

Quoted

Original von NullAhnung
Kommen die Folien 6.11 bis 6.98 auch dran?

Jein. Nur die Abschnitte 6.11 und 6.12 sind ausgeschlossen.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

This post has been edited 1 times, last edit by "Arne" (Mar 21st 2004, 7:29pm)

  • Send private message

NullAhnung

Erfahrener Schreiberling

  • "NullAhnung" is female

Posts: 332

Date of registration: Apr 28th 2003

20

Tuesday, March 23rd 2004, 1:06pm

Kann mir wer den Algorithmus von Floyd-Warshall erklären? Folien 6.82 und 6.83. Da muss ich wohl irgendwie gefehlt haben als das dran kam ;)
Das kommt auch bei Std Übung 14 dran. Wäre vielleicht ganz schön, wenn das an diesem Bsp erklärt würde
Danke schonmal
  • Send private message
  • 1
  • 2