Liste von Sätzen der Informatik

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen


C[Bearbeiten | Quelltext bearbeiten]

  • Satz von Cook: Es existiert eine Teilmenge von NP, auf die sich alle Probleme aus NP polynomiell reduzieren lassen. Diese Teilmenge heißt NP-vollständig.

F[Bearbeiten | Quelltext bearbeiten]

H[Bearbeiten | Quelltext bearbeiten]

I[Bearbeiten | Quelltext bearbeiten]

M[Bearbeiten | Quelltext bearbeiten]

N[Bearbeiten | Quelltext bearbeiten]

  • No-Free-Lunch-Theoreme: Alle Suchalgorithmen sind im Durchschnitt gleich gut.
  • Nyquist-Shannon-Abtasttheorem: Ein kontinuierliches, bandbegrenztes Signal mit einer Minimalfrequenz von 0 Hz und einer Maximalfrequenz muss mit einer Frequenz größer als abgetastet werden, damit man aus dem zeitdiskreten Signal das Ursprungssignal ohne Informationsverlust rekonstruieren kann.

P[Bearbeiten | Quelltext bearbeiten]

  • Das Pumping-Lemma: Eigenschaft bestimmter Klassen formaler Sprachen, geeignet um nachzuweisen, dass eine formale Sprache nicht regulär bzw. nicht kontextfrei ist.

R[Bearbeiten | Quelltext bearbeiten]

  • Rekursionssatz (Fixpunktsatz von Kleene): Zu einem gegebenen Quelltext-Modifikationsprogramm lässt sich immer ein Quelltext finden, dem die Modifikation nichts ausmacht.
  • Satz von Rice: Es ist im Allgemeinen nicht möglich, für einen gegebenen Algorithmus irgendeinen Aspekt seines funktionalen Verhaltens algorithmisch nachzuweisen.

S[Bearbeiten | Quelltext bearbeiten]

Siehe auch[Bearbeiten | Quelltext bearbeiten]