Zum Inhalt springen
L

Wikipedia · einfach zusammengefasst · Stand

Paralleler Algorithmus

Umgekehrt sind auch viele bekannte sequentielle Algorithmen parallelisierbar, so z. B. einige bekannte Sortieralgorithmen wie Bubblesort oder Quicksort. Es …

Lesen · 2 Abschnitte Original auf Wikipedia
Inhalt2 Abschnitte
  1. 1. Parallele Algorithmen
  2. 2. Grenzen und Untersuchung

Parallele Algorithmen

Ein paralleler Algorithmus ist ein Algorithmus, der zur Bearbeitung eines Problems mehrere Recheneinheiten gleichzeitig nutzen kann. Als Beispiel nennt der Artikel Probleme der Komplexitätsklasse NC („Nick’s Class“ nach Nick Pippenger), die in polynomieller Zeit gelöst oder entschieden werden können.

Jeder parallele Algorithmus kann auch sequentiell, also Schritt für Schritt auf einer einzelnen Recheneinheit, abgearbeitet werden. Umgekehrt lassen sich viele bekannte sequentielle Algorithmen parallelisieren. Genannt werden Sortieralgorithmen wie Bubblesort und Quicksort.

Grenzen und Untersuchung

Eine offene Frage der theoretischen Informatik ist, ob alle Algorithmen für Probleme aus den Klassen P oder NP parallelisierbar sind. Für viele dieser Algorithmen wurde bislang kein paralleler Algorithmus gefunden. Daher gehen die meisten Forschenden laut Artikel davon aus, dass nicht alle Algorithmen aus P oder NP parallelisierbar sind.

Zur Untersuchung paralleler Algorithmen verwendet man meist ein besonderes Maschinenmodell: die Parallel Random Access Machine (PRAM). Sie ist von der Registermaschine abgeleitet.

Weiterlesen

Algorithmus Algorithmen bestehen aus endlich vielen, wohldefinierten Einzelschritten. ... Damit können sie zur Ausführung in ein Computerprogramm implementiert, aber auch in … Komplexitätsklasse Eine Komplexitätsklasse ist eine Menge von Problemen, welche sich in einem bestimmten ressourcenbeschränkten Berechnungsmodell berechnen lassen. Zusammenhang … Bubblesort Bubblesort (auch Sortieren durch Aufsteigen oder Austauschsortieren) ist ein Algorithmus, der vergleichsbasiert eine Liste von Elementen sortiert. Quicksort Quicksort (englisch quick ‚schnell' und to sort ‚sortieren') ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile … Theoretische Informatik Ihre Inhalte sind die Automatentheorie, die Theorie der formalen Sprachen, die Berechenbarkeits- und Komplexitätstheorie, aber auch die Logik und formale … P (Komplexitätsklasse) Diese Problemklasse wird allgemein als die Klasse der „praktisch lösbaren“ Probleme betrachtet. Eine Verallgemeinerung von P ist die Klasse NP. Die Probleme aus … NP (Komplexitätsklasse) In der Informatik bezeichnet NP (für nichtdeterministisch polynomielle Zeit) eine fundamentale Komplexitätsklasse aus dem Bereich der Komplexitätstheorie. Registermaschine Die Registermaschine (RM) ist eine abstrakte Maschine der theoretischen Informatik. Registermaschinen sind Turing-vollständig, das heißt, … Nebenläufigkeit Die Nebenläufigkeit, mitunter auch Parallelität (englisch concurrency) genannt, ist in der Informatik die Eigenschaft eines Systems, mehrere Aufgaben, … Parallelrechner Pipelining. Bearbeiten. Problemstellungen, bei denen größere Datenmengen in mehreren aufeinander folgenden Schritten verarbeitet werden, sogenanntes Pipelining.