Paralleler Algorithmus
aus Wikipedia, der freien Enzyklopädie
Ein paralleler Algorithmus ist ein Algorithmus, welcher ein Problem der Komplexitätsklasse NC (Nick's Class nach Nick Pippenger) lösen bzw. entscheiden kann. Jeder parallele Algorithmus kann auch sequentiell abgearbeitet werden. Umgekehrt sind auch viele bekannte Algorithmen parallelisierbar, so z.B. einige bekannte Sortieralgorithmen wie Mergesort oder Quicksort. Es gehört jedoch zu den offenen Fragen der theoretischen Informatik ob alle Algorithmen, welche Probleme der Klassen P oder NP entscheiden, auch parallelisierbar sind. Für viele dieser Algorithmen wurde noch kein entsprechender paralleler Algorithmus gefunden, so dass die meisten Forscher heute davon ausgehen, dass dieses nicht der Fall ist. Zur Untersuchung paralleler Algorithmen verwendet man in der Regel ein spezielles Maschinenmodell, das von der Registermaschine abgeleitet ist, die PRAM (parallel random access machine).
