Changelog zum Skript Algorithmentechnik ITI Wagner Stand: 6.2.07 Revision 4.2 - Random-Sat ausgebessert - Random MinCut ausgebessert - diverse Kleinigkeiten - Union Find: einige Erklärungen und Lemmas zum Rang aufgeräumt - Kruskal umsortiert - Prozedur Delete verbessert Stand: 7. April 2006 Revision 4.1 -- 1. Juni 2006 Beweisumgebungen versch�ert (ntheorem) Revision 4.0 -- 8. Mai 2006 viele kleine �derungen (Robert) Revision 3.8 -- 7. April 2006 S.10 MERGE hat also eine Laufzeit hat ("hat" zuviel) S.15 Schema von Strassen nicht ganz korrekt (Meiner Meinung nach ist P6=(a2-a4)*(b3+b4) und P7=(a1-a3)*(b1+b2) S. 22 Modifikation 1 (zwischen den und "gr�eren" sollte eine Lehrzeile, nach 1.4 muss ein Punkt kommen) S. 24 Algorithmus 15 (Zeilen sind verrutscht) S. 38 lim sup (beim dritten lim sup sollte es auch j->unendlich hei�n) S. 52 Formal (Leerzeichen zwischen jeweils und v) S. 80 zweiter Satz (zwischen e_i und Die Menge mu�ein Punkt) S. 85 k=1 (bei S_11 fehlt das Komma zwischen den 1en) S. 92 Beispiel 6.3 (Quelle c sollte wohl Quelle s hei�n) S. 93 das primales Programm (primale) S. 97 Satz 7.1 (c:M -> N_0) S. 98 Algorithmus 44 (ist kursiv im Gegensatz zu den Anderen Algorithmen) S. 99 Satz 7.3 (Zul�sigkeit mit zwei s) S. 108 Beispiel 7.19 (X=(x1,..xg) sollte xq hei�n) S. 116 Definition 8.3.3 (polynomialen Algorithmus A gibt, so dass) S. 117 8.2.1 (Punkt zwischen Multigraph und Gesucht) Revision 3.7 -- 22. M�z 2006 Nicht mehr nachvollziehbare, gesammelte Petitessen Revision 3.6 -- 6. M�z 2006 (Auszug der wichtigsten �derungen) Beweis Lemma 5.12 erster Fall, Indizes korrigiert. "Krzester Kreis" bedeutet in Kapitel 5 stets "Kreis minimalen Gewichts" Diverse Kleinigkeiten... Revision 3.5 -- 2. M�z 2006 (Auszug der wichtigsten �derungen) Beispiel 4.1 ausgebessert Algorithmus von Prim neue Zeile 13 eingefgt Bild bei grner Invariante ausgebessert Vor Satz 3.6: ...wurde nun nun gezeigt dass... c(S_v,v) <= c(....) Sortieren mit der konvexen Hlle: Beschreibung korrigiert, Widerspruch erkl�t Revision 3.4 -- 27. Feb. 2006 Die Seitenangaben beziehen sich auf die Nummerierung der PDF-Seiten, also incl. Deckblatt, Inhalts- und Abbildungsverzeichnis. Stellen, an denen sich auch inhaltliche Fehler ergeben, sind mit einem Ausru- fungszeichen am Zeilenanfang markiert. Kapitel 0 S. 15, Algorithmus 2, Zeile 2: 'x' statt 'X' S. 25, Bemerkung 0.13: 'Satz 0.12' statt 'Satz 1.2' S. 28, 1. Absatz: !* 'T(max(|A1|,|A2|))+cn' statt 'T(max(|A1|,|A2|)+cn)' * unvollst�diger Satz: "Somit l�st sich wobei fr max(|A1|,|A2|) gilt:" * gleich darunter, 3. Zeile der Ungleichung: '=' statt '>' Kapitel 1 S. 35, Beobachtung 1.7: evtl. anmerken, dass 'p[v]' Vorg�ger von v ist S. 36, Fall 1, erste Ungleichung, 2. Zeile: ein '>='-Zeichen zuviel ebenso bei Fall 2 S. 37, unmittelbar vor Beobachtung 1.10: 'eine' statt 'ein' S. 38, Beweis, 1. Zeile: 'Absch�zung 4' statt 'Absch�zung 6' S. 39, OFFLINE-MIN-Problem, * 1. Zeile: 'eine Folge' statt 'ein Folge' !* 4. Zeile: 'i aus der Menge {1,2,...,n}' statt 'o.B.d.A. i eine positive ganze Zahl'; bei unbeschr�ktem i werden im Algorithmus 17 nicht alle EXTRACT-MIN-Operationen bercksichtigt S. 40, Algorithmus 16 steht unter 1.2.2, geh�t jedoch zu 1.2.1 S. 41, Beispiel 1.15, Beispiel 1.16: * Indizierung der Automaten inkonsistent mit der in Abb. 1.7 bis 1.9 !* Automaten A_2 und A_3 sind NICHT �uivalent, Beweis: w=0010 wird von A_3 akzeptiert, von A_2 nicht. Wenn man dem Test auf S. 44 nachgeht, stellt man fest, dass folgende Kanten von A_3 falsch gerichtet sind: (v,z), (y,v) S. 43, Algorithmus 18, Zeile 1: 'S:=� statt 'S:=0' !S. 44, vorletzter Punkt: 3. Position auf S, also '(a,v)', ist zu viel S. 45, 1.3: bei DELETE, INSERT, MAKEHEAP fehlen die Argumente S. 47, 1.3.2: inkonsistente Bezeichnung der Menge M -> ersetze 'S' durch 'M' S. 48, Bemerkung 1.21: im limsup 'j' statt 'n' und 'j' statt 'i' S. 49, letzter Absatz, 1. Zeile: 'genaue' oder 'genauere' statt 'genau' 2. Zeile: 'Etwa' statt 'Etwas' S. 50, Zeile unter Algorithmus 25: 'Vergleiche' statt 'Vergleich' gleiche Zeile: '2*n*logn' statt '2*logn' Kapitel 2 S. 55, Satz 2.6: Kommasetzung: "Die F�bungsmethode, angewandt auf einen zusammenh�genden Graphen, erh�t die F�bungsinvariante." S. 57, 2.5.1, 3. Zeile: 'ein Kandidat' statt 'eine Kandidat', gleiche Zeile: Freizeichen hinter "f�be grn" fehlt, gleiche Zeile: 'ein Endknoten' statt 'eine Endknoten' S. 58, Datenstrukturen: GR�[v]: * 1. Punkt: 'deren' statt 'aber' * 2. Punkt: Freizeichen nach "Grnf�bung" fehlt S. 58, Algorithmus 29, !* Zeile 14: 'DECREASEKEY(H,w,c({v,w}))' statt 'DECREASEKEY(H,w,key[w])' !* Zeile 15: 'v <- DELETEMIN(H)' geh�t noch in die Schleife aus Zeile 4 Kapitel 3 S. 63, Abbildung 3.2 inmitten von Beispiel 3.4, geh�t jedoch nicht dazu S. 66, Laufzeit:, Zeile 8: entweder ist 'der' zu viel oder es fehlt ein Wort in '..., jeweils entsprechend der erh�t und die Knoten dann...' S. 67, 1. Zeile: 'induzierten' statt 'induzierte' Revision 3.3 -- 27. Feb. 2006 - Details zu Quicksort ausgebessert und klarifiziert. - Beobachtung 1.7 ausgebessert - Beweis zu Stoer und Wagner Tippfehler korrigiert - Kapitel 4: einige Details&Tippfehler ausgebessert Revision 3.2 -- 21. Feb. 2006 - S.96 ...jedes I von Pi... - Diverse Sonderzeichen repariert - S.2 Definition der c_i - kleinere Rechtschreib- und Zeichensatzkorrekturen Revision 3.1 -- 20. Feb. 2006 - "L-Ungleichung" auf Seite 90 korrigiert Revision 3 -- 17. Feb. 2006 - Kapitel 6-8 hinzugefügt Revision 2 -- 30. Jan. 2006 - Kapitel 5 (Kreisbasen) hinzugefügt. Revision 1 -- 4. Jan. 2006 - Abschnitt 0.5, Seite 15 oben: SELECT findet $k$-kleinstes Element. - Abschnitt 1.1, Seite 23 unten: Definition von r(v) und Beobachtung 1.7 mit Beweis korrigiert. - Abschnitt 2.1: Definition von Weg bzw. Pfad - Abschnitt 2.6, Seite 47: Definition von Optimierungsproblem über Unabhängigkeitssystem - Abschnitt 3.1, Seite 54: Ergänzung zur Laufzeit von MINSCHNITTPHASE - Kapitel 4: Viele Änderungen Revision 0 -- 23. Dez. 2005 - Erste Version des Skripts bis enschließlich Kapitel 4. Korrekturgelesen bis enschließlich Kapitel 3.