Folien Internet-Algorithmen 2007

• 11: Definition schwacher Zusammenhang korrigiert.
• 55: Stammfunktion (1/2)log(2t) + c -> (1/2)log t + c.
• 52ff: Neue Erklärung für Anfangsbedingung im BA-Modell.
• 61: Modelliere Gewichtsverteilung für einzelnen Knoten unter der Bedingung, dass dieser überhaupt existiert -- diese Bedingungen sind bei den Erwartungswerten auf der Folie nach wie vor weggelassen. (Leider ist für den "mean field"- bzw. "rate equation"-Ansatz hier ein zunehmend stärkerer Glaube notwendig, dass er noch das Richtige abbildet...)
• 107: Folie neu, anfragebasierte/anfrageunabhängige Rangvergabe.
• 114ff: Lemma über Nichtnegativität des Eigenvektors zum größten Eigenvektor in Konvergenzbeweis (Satz 3.9) integriert.
• 152: Sackgassen-Definition statt Bild mit Friedhof.
• 166: M -> A in Satz 3.22.
• 173: Bemerkung zu Konvergenz & Sackgassen im Bianchini-Paper.
• 176: E(S) = 2 - ... in Beispiel 3 (statt = 1 - ...).
• 251: Ergänzt, dass zufälliger Vektor gleichverteilt über Einheitsspäre.
• 255: Im sim-Maß Ungleichheit zwischen Hashwerten durch Gleichheit ersetzt.
• 268: Ergänzt, dass Träger der Zielverteilung Teilmenge des Trägers der Stichprobenverteilung.
• 271: Beweis von Proposition 3.39 ergänzt (Ergebnis von Übungsaufgabe).
• 339: i aus {1...s+1} -> i aus {1...t+1}.
• 409: Gesamte Gleichung für den Erwartungswert quadrieren und Ausnutzen, dass E(N(0,1)^2) = 1.
• 437, 449: Ausgegeben werden alle Elemente mit Häufigkeit größer als (1+ε)f_k.
• 460: Bedingung für Zwischenpunkt nur, falls d_i+1 > d_i+1
• 463: Gesonderte Behandlung des (trivialen) Falles, dass x = d_i^(k) für irgendein d_i^(k).
• 608: Korrektur der Definition der Nash-Flüsse.