Hat jemand den Schöning über Theoretische Informatik? [Archiv]

Archiv verlassen und diese Seite im Standarddesign anzeigen : Hat jemand den Schöning über Theoretische Informatik?

Senior Sanchez

2008-06-08, 23:20:00

Hi,

Ich schreibe gerade an einer Seminararbeit und nehme dazu auch Bezug auf das Rucksackproblem und das Travelling-Salesman-Problem. Dazu würde ich gerne eine Referenz zum Nachlesen reichen und da ich Herrn Schöning kenne und er denke ich auch gute Bücher schreibt, wollte ich sein Buch referenzieren.

Kann mir da jemand sagen, wie gut er diese beiden Sachen dort behandelt und wenn ja, auf welchen Seiten die Themen jeweils stehen?

Danke

Byteschlumpf

2008-06-09, 00:38:05

Hi, das Rucksackproblem ist dort (vierte Auflage, Sommer 2000) auf Seite 164 und das TSP auf Seite 165 aufgeführt (Kapitel 3.3 Weitere NP-Vollständige Probleme).

Senior Sanchez

2008-06-09, 07:53:22

Hey, super, vielen Dank :)

Aquaschaf

2008-06-10, 21:10:29

Beides wird dort allerdings nur sehr knapp behandelt.

Senior Sanchez

2008-06-10, 22:41:21

Beides wird dort allerdings nur sehr knapp behandelt.

Hm, aber das beide Probleme NP-vollständig sind, wird erwähnt, denke ich, oder?

Stone2001

2008-06-10, 23:16:28

Man findet sie unter dem Kapitel: 3.3 Weitere NP-vollständige Probleme von daher...

P.S.: Der Satz und der zugehörige Beweis, dass Rucksack NP-Vollständig ist, findet sich auf Seite 171. Der für Traveling Salesman auf Seite 178.

Senior Sanchez

2008-06-11, 00:04:21

Vielen Dank :)
Ihr habt mir sehr geholfen.

Aquaschaf

2008-06-11, 17:40:10

Hm, aber das beide Probleme NP-vollständig sind, wird erwähnt, denke ich, oder?

Es steht für beides ein knapper Beweis der NP-Vollständigkeit drinnen. Aber das war's auch. Ich finde das Buch ehrlich gesagt nicht so prall. Alles recht knapp, zum Nachschlagen ist es weniger geeignet.