Liste von Sätzen der Informatik

C

F

H

  • Satz von Herbrand: Sei eine geschlossene Formel in Skolemform, dann ist genau dann unerfüllbar, wenn es eine endliche Teilmenge der Herbrand-Expansion gibt, die – im aussagenlogischen Sinn – unerfüllbar ist.
  • Hierarchiesätze: Zeit- und Raumkomplexitätsklassen bilden jeweils eine Hierarchie, können also in eine echte Teilmengenbeziehung gesetzt werden. Es gilt: und .

I

L

M

N

  • No-Free-Lunch-Theoreme: Es gibt keinen Suchalgorithmus, der für alle Probleme gleichermaßen der beste ist.
  • 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 aus dem zeitdiskreten Signal das Ursprungssignal ohne Informationsverlust rekonstruiert werden kann.

P

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

R

  • 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

Siehe auch