Fakultät für Informatik der Technischen Universität München Lehrstuhl für Effiziente Algorithmen

Internet-Algorithmik (SS 04)

Aktualisiertes Skriptum bis Abschnitt 3.1 online

• Dozent:
  Prof. Dr. Ernst W. Mayr
  Dr. Sven Kosub

• Bereich:
  4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
  Vertiefende Vorlesung im Bereich Algorithmen

• Zeit und Ort:
  Dienstag, 11:15-12:45, MI 00.04.011
  Mittwoch, 12:15-13:45, MI 00.04.011

• Übung:
  2 SWS Übung zur Vorlesung
  Dienstags, 13:15 - 14:45 Uhr, Raum MI 00.13.037
  Übungsleitung: Moritz G. Maaß
  

• Hörerkreis:
  Studierende im Hauptstudium der Informatik
  Studierende mit Nebenfach Informatik
  

• Voraussetzungen:
  Stoff des Informatik-Grundstudiums
  Vorlesung Effiziente Algorithmen und Datenstrukturen I
  Vorlesung Internetprotokolle vorteilhaft, aber nicht notwendig

• Empfehlenswert für:
  Erweiterte Kenntnisse im Bereich Algorithmen
  Erweiterte Kenntnisse im Bereich Rechnernetze

• Inhalt:
  1. Einleitung
     1. Internet: Begriffe und Definitionen
     2. Internet-Anwendungen
     3. Kombinatorische Probleme
     4. Algorithmische Techniken
     5. Themenübersicht
  1. Internet-Analytik
  2. Datenanalyse
     1. Texte
        1. Definitionen und Notationen
        2. Ein einfacher Algorithmus für exakte Suche in Texten
        3. Der Algorithmus von Knuth, Morris und Pratt
        4. Der Algorithmus von Boyer und Moore
        5. Approximative Suche in Texten
     2. Hypertexte
        1. Das Hypertext-Modell von Manber und Wu
        2. Exakte Suche in Hypertext
        3. Approximative Suche in Hypertexten
        4. Der Algorithmus von Navarro
     3. Datenströme
        1. Verarbeitungsmodelle und Komplexitätsmaße
        2. Der Algorithmus von Fischer und Salzberg
        3. Schätzung von Häufigkeitsmomenten
     4. Monitore
        1. Verarbeitungsmodelle
        2. Exponenzielle Histogramme
        3. Varianzenapproximation
  3. Netzwerkanalyse
     1. Rekonstruktion von Netzwerktopologien
        1. Dimensionierung von Monitorsystemen
        2. Graphenrealisierung aus Gradfolgen
        3. Graphenrealisierung aus Abstandsmatrizen
     2. Strukturelle Zentralität
        1. Strukturindizes
        2. Abstandszentralitäten
        3. Rückkopplungszentralitäten
     3. Internet-Hierarchien
     1. Ein abstraktes Modell für BGP
     2. Kombinatorische Inferenz von Beziehungstypen

  Weitere Themenkomplexe (in zukünftigen Semestern):
  2. Effiziente Gestaltung des Internetbetriebs
  3. Informationsverteilung im Internet
  4. Informationsgewinnung im Internet
  5. Internet-Sicherheit

• Weiterführende bzw. verwandte Vorlesungen:
  Effiziente Algorithmen und Datenstrukturen

• Skriptum: [PostScript] [gzipped PostScript] [PDF] (letzte Änderung: 29.01.2005)

• Literatur:
  Die Vorlesung verwendet aktuelle Forschungsarbeiten, die noch nicht in Buchform zusammengefasst sind. Eine Reading-Liste ist in Vorbereitung.

• Sprechstunde:
  nach Vereinbarung