Paralleler Algorithmus

Ein paralleler Algorithmus ist ein Algorithmus, welcher zum Beispiel ein Problem der Komplexitätsklasse NC (Nick’s Class nach Nick Pippenger) in polynomieller Zeit lösen bzw. entscheiden kann.

Jeder parallele Algorithmus kann auch sequentiell abgearbeitet werden. Umgekehrt sind auch viele bekannte sequentielle Algorithmen parallelisierbar, so z. B. einige bekannte Sortieralgorithmen wie Bubblesort 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 Parallel Random Access Machine (PRAM).

Siehe auch

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.