Grundlagen Flashcards
Repräsentation und Information (Definition)
Information bezeichnet den abstrakten Gehalt (Bedeutungsinhalt, Semantik) eines Dokuments, einer Aussage, Beschreibung, Anweisung, Nachricht oder Mitteilung. Die äußere Form der Darstellung heißt Repräsentation (konkrete Form der Nachricht). Interpretation bezeichnet den (häufig nur gedanklichen) Übergang von der Repräsentation zur abstrakten Information, d.h. die Deutung der Repräsentation.
Algorithmus (Definition)
Ein Algorithmus ist ein Verfahren mit einer präzisen in einer eindeutigen Sprache abgefassten, endlichen Beschreibung unter der Verwendung effektiver (d.h. tatsächlich ausführbarer), elementarer Verarbeitungsschritte zur Lösung eines Problems.
Effektivität (Definition)
Ein Verarbeitungsschritt heißt effektiv, wenn er im Prinzip von einer realisierbaren Maschine oder z.B. in endlicher Zeit von einem Menschen mit Bleistift und Papier unter Befolgung genauer Vorschriften ausführbar ist.
Korrektheit und Terminierung (Definition)
Die Beschreibung einer gewünschten Berechnung sei gegeben in Form einer funktionalen Spezifikation F.
- Ist ALG ein Algorithmus, der die gewünschte Berechnung durchführt, so nennt man ALG partiell korrekt bezüglich F, wenn ALG für alle erlaubten Eingaben bei Terminierung als Antwort den entsprechenden Funktionswert von F ausgibt.
- Ein Algorithmus ALG heißt terminierend genau dann, wenn ALG für alle erlaubten Eingaben nach endlich vielen Schritten endet. Gelten (1) und (2), so heißt ALG total korrekt .
deterministisch vs. determiniert
- Ein Algorithmus heißt deterministisch genau dann, wenn die Reihenfolge der Verarbeitungsschritte stets eindeutig festgelegt ist, in der Auswahl der Verarbeitungsschritte also keine Wahlmöglichkeit besteht.
- Ein Algorithmus heißt determiniert genau dann, wenn das Ergebnis der Abarbeitung für alle Eingaben eindeutig festgelegt ist.
sequentiell vs. parallel
- Ein Algorithmus heißt sequentiell, wenn zu jedem Zeitpunkt nur ein elementarer Arbeitsschritt ausgeführt werden kann.
- Ein Algorithmus heißt parallel, wenn Arbeitsschritte nebeneinander (zur gleichen Zeit) ausgeführt werden können.
Rechensysten / System (Definition)
Prozess in eine System (Definition)
sequentielle und parallele Prozessoren (Definition)
Ein sequentieller Prozessor ist ein deterministisches System
(Q,R) mit endlich vielen Zuständen Q und einer durch R festgelegten
endlichen Menge von möglichen Aktionen, wobei zu einem
bestimmten Zeitpunkt maximal eine Aktion (ungestört) ausgeführt
werden kann.
Ein Multi-Prozessor entsteht durch Kombination von neN deterministischen,
in sich sequentiellen Prozessoren, wobei die Zustandsmenge
Q des Gesamtsystems sich aus der Kombination der
n Einzelzustände Q1xQ2x…xQn ergibt. Durch R ist sowohl die
endliche Menge der Aktionen jedes einzelnen Prozessors bestimmt
wie auch festgelegt, welche Prozessoren welche Aktionen gemeinsam
oder unabhängig voneinander ausführen können.
Ausführung einer Menge von Prozessen (Definition)
