Start

Schrumpfgraph

Approximationsalgorithmen

Scheduling unabhängiger gewichteter Jobs auf parallelen Maschinen

Viele kleine Jobs

Untere Schranken

Der Approximationsfaktor

Diese Schranke ist bestmöglich

Mehr zu Scheduling

Nichtapproximierbarkeit des Handlungsreisendenproblems

Hamilton Cycle

TSP mit Dreiecksungleichung

2-Approximstion durch minimalen Spannbaum

Pseudopolynomielle Algorithmen

Fully Polynomial Time Approximation Scheme

Fixed Parameter Algorithmen

VERTEX Cover

Fixed parameter tractable

Naive tiefenbeschränkte Suche

Kernbildung für Vertex Cover

Warum Parallelverarbeitung

Modell Nachrichtengekoppelte Parallelrechner

Kostenmodell für Nachrichtenaustausch

Warum kein Multicore-Modell?

Analyse paralleler Algorithmen

Pseudocode

Weniger ist mehr

Hyperwürfel

Hyperwürfelaulgorithmus

Paralleles Quicksort

Theoretiker-Parallelisierung

Onlinealgorithmen

Competitive analysis

A typical online problem: Ski rental

Paging

Comparison of algorithms

Discussion

Stringology

Strings Sortieren

Naives Pattern Matching

Knuth-Morris-Pratt

Volltextsuche von Langsam bis Superschnell

Invertierter Index

Etwas ""Stringology""-Notation

Suffixe Sortieren

Volltextsuche

Suffix-Baum

SA mit Präfix Verdopplung

Ein erster Teile-und-Herrsche-Ansatz

SA berechnen

Rekursion

LCP-Array

Datenkompression

Wörterbasierte Textkompression

Lempel-Ziv Kompression

Burrows Wheeler Transformation

Geometrische Algorithmen

Plane-Sweep-Algorithmen

Verallgemeinerung

Mehr Linienschnitt

Kleine einschließende Kugel