Ich freue mich über die Mitteilung weiterer gefundener Fehler oder über Anregungen, wie das Skript noch besser werden kann !! hofmeist@ls2.cs.uni-dortmund.de

Skript-Upgrades

Ersatz für die Seiten 47-56.
(Einige Flußalgorithmen sind hier einfacher erklärt als in der alten Version).
Postscript, unzipped (280 K)
Postscript, ge-gzipped (70 K)

Ersatz für die Seiten 77-82. (Einige kleine kosmetische Verschönerungen).
Postscript, unzipped (240 K)
Postscript, ge-gzipped (60 K)

Ersatz für die Seiten 85-90. (Einige Vereinfachungen.)
Postscript, unzipped (240 K)
Postscript, ge-gzipped (60 K)

Fehlerliste zum Skript

Seite 8, 1. Zeile: Ersetze "Zusammenhangskomponenten" durch "Zweizusammenhangskomponenten"

Seite 13, Zeile 5 von unten: "Lemma 3.3.3" ==> "Lemma 2.3.3".

Seite 25, ca. Zeile 16: statt "monoton" : "streng monoton"

Seite 27: Zeile 4 nach Satz 3.3.3: "ebenfalls auf Lemma 4.3.1" muß heißen "ebenfalls auf Lemma 3.3.1".

Seite 42, Satz 6.1.10: Hier sollte es besser "eines optimalen" und "eines minimalen" heißen anstatt "des optimalen" und "des minimalen". ("des" suggeriert immer eine gewisse Eindeutigkeit)

Seite 43, Zeile 2 (die Formel): Unter dem ersten Summenzeichen muß es V_Q statt V_S heißen. Zeile 3: Kanten, die in V_Q verlaufen. Zweite abgesetzte Formel: Dort das, was unter den Summenzeichen steht, vertauschen.

Seite 44, Definition 6.2.1: Ersetze "des kürzesten" durch "eines kürzesten"

Seite 54: Zeile 2: Sollte heißen: "Also ist e(v)=0 für alle v ungleich Q,S."

Seite 54, Zeile 3 von unten (die Formel): Dort sollte unter dem Summenzeichen nicht "v aus A" sondern "v aus V" stehen.

Ca. Seite 63: 4 Zeilen vor Definition 7.1.4: Ersetze "Vorbemerkungen..." durch "Nach Satz 6.4.6, Teil 2"

Seite 70, Zeile 5: Muß heißen: v₁ < v₂ < ... und x₁ > x₂ > ...

Seite 74: letzte Zeile, ersetze "der kleinste" durch "ein kleinster"

Ca. Seite 77: Satz 8.1.7 sollte Lemma 8.1.7 heißen. In Algorithmus FastCut, Schritt 2: berechne einen minimalen ... Ebenso nach dem Beweis von Satz 8.1.9 sollte es "einen kleinsten Schnitt" heißen statt "den kleinsten".

Seite 80: Im Algorithmus muß die Schleife "while anzahl >= 2 " (und nicht 1) heißen.

Im Text vor Behauptung 9.1.1: "...sogenannte Gewicht dieser (partiellen)..." Hier sollte w(d1,...dm) durch w(d1,...,di) ersetzt werden.

Seite 83, Zeile 2 nach dem Beweis: "Diese sind..." Zeile 6 nach dem Beweis: Komma vor "hat", Zeile 7 nach dem Beweis: "Problems" statt "Problem".

Seite 88, Satz 9.4.3: Die Zahlen p_i müssen natürlich zwischen 0 und 1 liegen.

Seite 96: Definition der Ordnung (dritte Zeile): a sollte aus Z_n^* sein (und nicht aus Z_n).

Seite 96: In Satz 10.3.3 gehören Betragsstriche um das Z_p^*.

In Definition 10.4.1 sollte man beim Jacobi-Symbol fordern, da"s $a$ und $q$ teilerfremd sind.

Seite 102: Zeile 4 des ersten Beweises: Ergänze vor "Nach dem Chinesischen Restsatz...": "(So einen Nichtrest gibt es nach Satz 10.3.3.)". Weitere Anmerkung: p soll natürlich eine Primzahl sein.

Seite 102: Die vorletzte Zeile im Beweis zu Lemma 10.6.3: Nach ", also" muß es heißen: "a^(n-1)/2mod n = -1 mod n und somit a^(n-1)/2mod r = -1 mod r"

Seite 103: Letzte Zeile des Beweises oben: Komma vor "und" einfügen.

Seite 105: Am Anfang von Kapitel 11.2 wird 2mal auf Kapitel 4 verwiesen. Gemeint ist aber "Kapitel 2".

Seite 112: In Algorithmus 11.5.4, Schritt 3 muß es heißen: ...Algorithmus 11.5.2 (statt "11.2.3")

Nach Satz 12.7.7: Nach dem Beweis die zweite Zeile: Komma vor "wohl aber" einfügen