Internet-Algorithmen
Sommersemester 2007
|
| Veranstalter: | | Martin Sauerhoff
|
| Termine: | | Montag | | 12:15-13:45 Uhr | | OH 14, 304
|
| | | Mittwoch | | 14:15-15:45 Uhr | | OH 14, 304
|
| Übungen: | | Freitag | | 10:15-11:45 Uhr | | OH 14, 304
|
| Beginn: | | 2. April 2007
|
Die Vorlesung ist beendet.
Inhalt der Vorlesung
Was wurde wann gemacht?
Begleitmaterial (Folien & Übungsblätter)
Information zu den Übungen
Hinweise zu Prüfungen
Literatur und nützliche Links
Begleitmaterial:
Begleitmaterial (Folien & Übungsblätter)
Liste der inhaltlichen Änderungen an den Folien nach der Vorlesung
Übungen:
- Ausgabe der Übungsblätter jeweils mittwochs hier im Netz.
- Abgabe bis spätestens zum Ende der Vorlesung am Mittwoch.
Kriterien für die Scheinvergabe:
Erreichen von mindestens 50% der Gesamtpunktzahl sowie
aktive Teilnahme an den Übungen, inklusive dem Vorstellen
der eigenen Lösungen.
Prüfungsform:
Mündlich (6 SWS, 9 LP),
Schwerpunktgebiete:
"Algorithmen, Komplexität und formale Modelle", "Verteilte Systeme".
Literatur und nützliche Links:
Momentan gibt es noch kein passendes Lehrbuch, das die Themen der Vorlesung komplett abdeckt.
Einige Lehrbücher zu speziellen Themen (soweit schon erschienen und mir bekannt) sind
im Folgenden aufgelistet. Zu den einzelnen Kapiteln wird es jeweils aktualisiert auch
einige exemplarische Originalarbeiten geben, die den Stoff aus der Vorlesung
vertiefen.
Es gibt außerdem ein
Skript
zur Vorlesung "Internet Algorithmen" (2005) in Frankfurt von Georg Schnitger
mit ähnlicher Themenauswahl (kein offizielles Begleitmaterial unserer
Vorlesung).
2. Der Webgraph
- P. Baldi, P. Frasconi, P. Smyth.
Modeling the Internet and the Web: Probabilistic Methods and Algorithms.
Wiley, 2003.
Bei amazon.de.
- A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener.
Graph structure in the web.
Proc of 9th WWW Conference, 309-320, 2000.
- D. Donato, L. Laura, S. Leonardi, S. Millozzi.
Large scale properties of the Webgraph.
European Physical Journal B, 38(2):239-243, 2004.
- R. Durrett.
Random Graph Dynamics. Cambridge University Press, 2006.
Bei amazon.de.
- S. Milgram.
The small-world problem.
3. Suchmaschinen
- A. Arasu, J. Cho, H. Garcia-Molina, A. Paepcke, S. Raghavan.
Searching the Web. ACM Trans. on Internet Technology, 1(1):2-43, 2001.
- S. Brin, L. Page.
The Anatomy of a Large-Scale Hypertextual Web Search Engine.
Proc. of 7th WWW Conference, 107-117, 1998. Das Google-Paper.
- L. A. Barroso, J. Dean, U. Hölzle.
Web Search for a Planet: The Google Cluster Architecture.
IEEE Micro, 23(2):22-28, 2003.
- J. M. Kleinberg.
Authoritative Sources in a Hyperlinked Environment.
Journal of the ACM, 46(5):604-632, 1999.
- L. Page, S. Brin, R. Motwani, T. Winograd.
The PageRank Citation Ranking: Bringing Order to the Web.
Technischer Bericht, Stanford University, 1998.
- A. Farahat, T. Lofaro, J. C. Miller, G. Rae, L. A. Ward.
Authority Rankings from HITS, PageRank, and SALSA: Existence, Uniqueness, and Effect of Initialization.
SIAM Journal on Scientific Computing, 27(4):1181-1201, 2006.
Räumt mit einigen Mythen und Legenden zur Analyse der genannten Algorithmen auf.
- A. N. Langville und C. D. Meyer.
Deeper Inside PageRank.
Internet Mathematics, 3(1):335--380, 2003.
Enthält einfachen Beweis zu Satz 3.22 aus der Vorlesung
- M. Bianchini, M. Gori, F. Scarselli.
Inside PageRank.
ACM Transactions on Internet Technology, 5(1):92-128, 2005.
Arbeit zur Energieinterpretation des PageRanks.
- M. Sobek.
Überblick über das PageRank-Verfahren der Suchmaschine Google.
Online-Manuskript, 2006.
Enthält einige weitere einfache Mini-Web-Beispiele zur Berechnung
des PageRanks wie in Abschnitt 3.3.11 der Vorlesung.
- M. Henzinger.
Finding Near-Duplicate Web Pages: A Large-Scale Evaluation of Algorithms.
Proc. of SIGIR 2006, 284--291.
- Z. Bar-Yossef und M. Gurevich.
Random sampling from a search engine's index.
Proc. of 15th WWW Conference, 367-376, 2006.
(Es gibt auch ein Video von Zivs Konferenzvortrag -- einfach mal nach dem Titel
der Arbeit bei Google suchen.)
5. Datenstromalgorithmen
6. Algorithmische Spieltheorie
- S. P Hargreaves Heap, Y. Varoufakis.
Game Theory: A Critical Introduction. Routledge (2004).
Bei amazon.de bzw. bei eBookMall.
- E. Koutsoupias, Ch. Papadimitriou.
Worst-case Equilibria.
Proc. of 16th STACS, LNCS 1563, 404-413, 1999.
- Ch. H. Papadimitriou.
Algorithms, Games, and the Internet.
Proc. of 33rd STOC, 749-753, 2001. Zusammenfassung eines Einführungsvortrags.
- N. Nisan, A. Ronen.
Algorithmic Mechanism Design.
Proc. of 31st STOC, 129-140, 1999. Einführende Arbeit.
- M. Osborne, A. Rubinstein.
A Course in Game Theory.
MIT Press, 1994.
Bei amazon.de.
- Ch. Papadimitriou, T. Roughgarden.
The Price of Anarchy.
Tutorial EC '04.
- D. C. Parkes.
Iterative Combinatorial Auctions: Achieving Economic and Computational Efficiency.
PhD Dissertation, 2001. Mit guten Einführungskapiteln.
- T. Roughgarden, E. Tardos.
How bad is Selfish Routing?
Journal of the ACM:49(2), 236-259, 2002.
M. Sauerhoff