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.

Torrero

Senior Schreiberling

  • "Torrero" is male
  • "Torrero" started this thread

Posts: 854

Date of registration: Oct 16th 2003

Location: Laatzen

Occupation: Angewandte Informatik

1

Tuesday, October 18th 2005, 11:55am

Datenstrukturen und Algorithmen - Allgemein

Könnte mir jemand, der gestern bei der Stundenübung war, sagen, was das Thema war ?
  • Send private message

6oeser6u6e

Junior Schreiberling

  • "6oeser6u6e" is male

Posts: 217

Date of registration: Mar 10th 2004

Location: Wolfsburg; Wohnort: Hannover-Nordstadt

Occupation: um Abstand zu der dämlichen Masse zu gewinnen... naja und wegen Geld ;P

2

Tuesday, October 18th 2005, 12:48pm

Pseudocode, ADTs Vector, List und Sequence
Unwissenheit ist ein Segen
  • Send private message

Torrero

Senior Schreiberling

  • "Torrero" is male
  • "Torrero" started this thread

Posts: 854

Date of registration: Oct 16th 2003

Location: Laatzen

Occupation: Angewandte Informatik

3

Monday, October 24th 2005, 3:37pm

Fangen die Übungen am Dienstag um 13.00 oder um 13.15h an ?
  • Send private message

sos1981

Alter Hase

  • "sos1981" is male

Posts: 1,562

Date of registration: Oct 28th 2003

Location: Wolfsburg

Occupation: Testentwickler

4

Monday, October 24th 2005, 8:32pm

F435 bei Richard Guercke beginnt um 13:15h
Der Einzigste ist noch viel einziger als der Einzige!
  • Send private message

Torrero

Senior Schreiberling

  • "Torrero" is male
  • "Torrero" started this thread

Posts: 854

Date of registration: Oct 16th 2003

Location: Laatzen

Occupation: Angewandte Informatik

5

Friday, August 25th 2006, 3:22pm

Kann mir jemand an diesem Beispiel erklären wie der TSP-Algorithmus funktioniert, ich ralle da irgendwie garnix.


edit : bild ist irgendwie klein, aber wenn man draufklickt, ist es größer.

This post has been edited 1 times, last edit by "Torrero" (Aug 25th 2006, 3:22pm)

  • 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)

6

Friday, August 25th 2006, 5:04pm

Quoted

Original von Torrero
Kann mir jemand an diesem Beispiel erklären wie der TSP-Algorithmus funktioniert, ich ralle da irgendwie garnix.
Wenn Du mir noch verrätst, welcher Algorithmus in dieser Vorlesung mit TSP1 bezeichnet wurde, schaue ich mir das gerne mal an.
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message

iriania

Junior Schreiberling

  • "iriania" is female

Posts: 222

Date of registration: Nov 24th 2003

Location: Waqwaq

Occupation: Wie? Ich studiere? seit wann denn?

7

Friday, August 25th 2006, 5:14pm

Traveling salesman problem?
...und sie dreht sich doch!
  • Send private message

Markus

the one and only Unterstrich!

Posts: 2,571

Date of registration: Oct 9th 2003

8

Friday, August 25th 2006, 5:22pm

Quoted

Original von iriania
Traveling salesman problem?


Das ist das zu lösende Problem, nicht der Lösungsweg ;)

Edit: Sollen das an den Kanten Gewichtungen sein? Da es sich bei TSP1 laut Bild um einen GreedyAlgorithmus handelt würde ich vermuten, der Algorithmus startet bei einem Knoten und wählt als nächsten Knoten den Knoten der mit der kleinsten Gewichtung zu erreichen ist (falls dieser nicht schon besucht wurde).
Edit2: Offensichtlich falsch, s.u, :P
Charmant sein? Hab ich längst aufgegeben. Glaubt mir doch eh keiner...
  • Send private message

DrChaotica

Senior Schreiberling

  • "DrChaotica" is male

Posts: 714

Date of registration: Jan 22nd 2005

Location: SHG

Occupation: SW-Entwickler

9

Friday, August 25th 2006, 5:23pm

Travelling Salesman Problem (TSP) — Kürzeste Rundreisen

Problem: In einem ungerichteten, zusammenhängenden Graphen wird
ein Zyklus über alle Knoten (Rundreise ohne Wiederholung von Knoten,
eine sogenannte “Tour”) mit minimalen Gesamtkosten gesucht.

Source code

 
1
2
3
4
5
6
7
8
9

algorithm TSP1 (Eingabe: Graph G mit n Knoten), Ausgabe: Kantenmenge :
	K <- {};
	while |K|<n and not G.isEmpty() do
		entnehme billigste restliche Kante (u, v) aus G;
		if ( (u, v) führt zusammen mit den Kanten aus K
			• an keinem Knoten zum Grad  3
			• außer für |K|=n-1 nicht zum Zyklus ) then
		füge (u, v) zu K hinzu;
	if |K|<n then exception(”keine Tour möglich”) else return K .

Es geht anscheinend um diesen Algorithmus (Quelle: DuA-Skript WS2005/2006).
Torrero, wo hast Du Probleme?

This post has been edited 2 times, last edit by "DrChaotica" (Aug 25th 2006, 5:25pm)

  • Send private message

kritop

Junior Schreiberling

  • "kritop" is male

Posts: 223

Date of registration: Sep 22nd 2003

Location: Bochum

10

Friday, August 25th 2006, 5:25pm

Ich glaub er meint diesen hier:

algorithm TSP1 (Graph G mit n Knoten): Kantenmenge :
K <- null;
while |K|< n and not G.isEmpty() do
entnehme billigste restliche Kante (u, v) aus G;
if ((u, v) führt zusammen mit den Kanten aus K
• an keinem Knoten zum Grad >= 3
• außer für |K|=n-1 nicht zum Zyklus )
then füge (u, v) zu K hinzu;
if |K|<n then exception(”keine Tour möglich”) else return K .
Wer es gelernt hat, sich von der Herrschaft des Ärgers zu befreien, wird das Leben viel lebenswerter finden. Bertrand Russel
  • Send private message

taormina

Praktikant

Posts: 11

Date of registration: Nov 29th 2005

Occupation: Math Sr Inf

11

Friday, August 25th 2006, 5:32pm

Quoted

Original von Torrero
Kann mir jemand an diesem Beispiel erklären wie der TSP-Algorithmus funktioniert, ich ralle da irgendwie garnix.




Der Greedy-Algorithmus sagt aus, dass man immer die "billigste restliche Kante" (geringstes Gewicht) zur Lösungsmenge dazu nehmen soll,
wobei:
- keine Knoten mit Grad >=3 erzeugen
- keine Zyklen erzeugen, bevor alle Knoten aufgenommen sind

Zum Beispiel:
Kante 1 nehmen
Kante 2 nehmen
Kante 3 würde bei Knoten B Grad 3 erzeugen
Kante 4 würde bei Knoten B Grad 3 erzeugen
Kante 5 nehmen
Kante 6 würde bei Knoten C Grad 3 erzeugen
Kante 7 würde Zyklus B-C-E-D erzeugen
Kante 8 würde bei Knoten C Grad 3 erzeugen
Kante 9 nehmen
Kante 10 nehmen

-> 1+2+5+9+10 = 27

Allerdings ist die Lösung beim TSP1-Algorithmus nicht immer optimal, wie hier auch. Optimal: 4+2+7+5+6 = 24
  • Send private message

kritop

Junior Schreiberling

  • "kritop" is male

Posts: 223

Date of registration: Sep 22nd 2003

Location: Bochum

12

Friday, August 25th 2006, 5:33pm

jetzt aber alle auf einmal ;-)
Wer es gelernt hat, sich von der Herrschaft des Ärgers zu befreien, wird das Leben viel lebenswerter finden. Bertrand Russel
  • Send private message

Hummel

Praktikant

  • "Hummel" is female

Posts: 16

Date of registration: Nov 16th 2004

Location: Hannover

Occupation: Informatik

13

Thursday, September 14th 2006, 4:13pm

die Klausurergebnisse sind raus :)
"Die Ergebnisse der Klausur vom 28. August 2006 hängen ab sofort neben dem Eingang zum Fachgebiet Datenbanksysteme aus. Die eigene Note kann auch in iLAM eingesehen werden. Der Einsichtstermin ist auf den 18. September, 14 bis 16 Uhr, verschoben."
  • Send private message

Currywurst mit Pommes

Erfahrener Schreiberling

Posts: 438

Date of registration: Oct 14th 2002

14

Sunday, October 15th 2006, 9:57am

Kann mir jemand sagen ob Dienstag schon eine Übung für Datenstrukturen und Algorithmen (Wolter) stattfindet. Leider überschneidet sich die Vorlesung bei mir mit einer anderen.

Auf der Stud E-Learning Seite gibts noch keine Infos zu Skript oder ähnlichem. Wird das angeboten werden?

Danke.
  • Send private message

BLUESCREEN

Junior Schreiberling

  • "BLUESCREEN" is male

Posts: 244

Date of registration: Oct 11th 2005

15

Sunday, October 15th 2006, 2:37pm

Quoted

Original von Currywurst mit Pommes
Kann mir jemand sagen ob Dienstag schon eine Übung für Datenstrukturen und Algorithmen (Wolter) stattfindet. Leider überschneidet sich die Vorlesung bei mir mit einer anderen.

In Stud.IP steht, dass die Übungen frühestens am 17. Oktober beginnen.

Quoted

Original von Currywurst mit Pommes
Auf der Stud E-Learning Seite gibts noch keine Infos zu Skript oder ähnlichem. Wird das angeboten werden?

Irgendwann ab der nächsten Woche soll man die Folien runterladen können.

PS: Der Thread hier ist ja noch von letztem Jahr O.o

This post has been edited 1 times, last edit by "BLUESCREEN" (Oct 15th 2006, 2:38pm)

  • Send private message