imported>Gak69: 🦓Reference-Tag eingefügt

2025-01-26T06:29:39Z

🦓Reference-Tag eingefügt

Neue Seite

{{Belege}}

Ein '''paralleler Algorithmus''' ist ein [[Algorithmus]], welcher zum Beispiel ein Problem der [[Komplexitätsklasse]] [[NC (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 [[Parallelisierbarkeit (Informatik)|parallelisierbar]], so z. B. einige bekannte Sortieralgorithmen wie [[Bubblesort]] oder [[Quicksort]]. Es gehört jedoch zu den offenen Fragen der [[Theoretische Informatik|theoretischen Informatik]], ob ''alle'' Algorithmen, welche Probleme der Klassen [[P (Komplexitätsklasse)|P]] oder [[NP (Komplexitätsklasse)|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).<ref>{{Internetquelle |url=https://www.spektrum.de/lexikon/mathematik/paralleler-algorithmus/9414 |titel=paralleler Algorithmus |sprache=de |abruf=2025-01-25}}</ref>

== Siehe auch ==
* [[Nichtsequenzielle Programmierung]]
* [[Nebenläufigkeit]]
* [[Parallelisierung]]
* [[Parallelrechner]]

== Einzelnachweise ==
<references />

[[Kategorie:Algorithmus]]
[[Kategorie:Parallelverarbeitung]]

Paralleler Algorithmus - Versionsgeschichte

imported>Gak69: 🦓Reference-Tag eingefügt