Paralleler Algorithmus

Paralleler Algorithmus

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 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 PRAM (Parallel Random Access Machine).

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Simplex-Algorithmus — Das Simplex Verfahren läuft von einer Ecke eines LP Polyeders zur nächsten, bis keine Verbesserung mehr möglich ist. Das Simplex Verfahren (auch Simplex Algorithmus) ist ein Optimierungsverfahren der Numerik zur Lösung linearer… …   Deutsch Wikipedia

  • PRAM — Als PRAM oder Parallel Random Access Machine bezeichnet man ein Maschinenmodell zur Analyse paralleler Algorithmen. Es handelt sich um eine Registermaschine, die um die Möglichkeit zur parallelen Verarbeitung von Befehlen erweitert wurde. Wie… …   Deutsch Wikipedia

  • Asymptotische Laufzeit — Unter der Zeitkomplexität eines Problems versteht man die Anzahl der Rechenschritte, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. Man spricht hier auch von der asymptotischen… …   Deutsch Wikipedia

  • Laufzeitkomplexität — Unter der Zeitkomplexität eines Problems versteht man die Anzahl der Rechenschritte, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. Man spricht hier auch von der asymptotischen… …   Deutsch Wikipedia

  • Worst-Case-Laufzeit — Unter der Zeitkomplexität eines Problems versteht man die Anzahl der Rechenschritte, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. Man spricht hier auch von der asymptotischen… …   Deutsch Wikipedia

  • Load-Link/Store-Conditional — (LL/SC) (engl. etwa „Referenz Laden/bedingt Schreiben“) ist ein Paar von Prozessor Befehlen, die eine read modify write Operation implementieren. Der LL Befehl lädt eine Speicherstelle, ihr Inhalt kann verändert werden, und der SC Befehl schreibt …   Deutsch Wikipedia

  • Nebenläufige Programmierung — Nebenläufigkeit liegt vor, wenn mehrere Ereignisse in keiner kausalen Beziehung zueinander stehen, sich also nicht beeinflussen. Ereignisse sind nebenläufig, wenn keines eine Ursache des anderen ist. Oder anders ausgedrückt: Aktionen können… …   Deutsch Wikipedia

  • Nichtsequentielle Programmierung — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Parallele Programmierung ist ein Programmierparadigma. Damit ist… …   Deutsch Wikipedia

  • Nichtsequenzielle Programmierung — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Parallele Programmierung ist ein Programmierparadigma. Damit ist… …   Deutsch Wikipedia

  • Parallele Programmierung — ist ein Programmierparadigma. Es umfasst zum einen Methoden, ein Computerprogramm in einzelne Teilstücke aufzuteilen, die nebenläufig ausgeführt werden können, zum anderen Methoden, nebenläufige Programmabschnitte zu synchronisieren. Dies steht… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”