Liste von Sätzen der Informatik

Inhaltsverzeichnis A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

C

• 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.

H

• Satz von Herbrand: Sei F eine geschlossene Formel in Skolemform, dann ist F genau dann unerfüllbar, wenn es eine endliche Teilmenge der Herbrand-Expansion E(F) gibt, die – im aussagenlogischen Sinn – unerfüllbar ist.

M

• Satz von Myhill-Nerode: Es existiert genau dann ein deterministischer endlicher Automat, der die formale Sprache L akzeptiert, wenn der Index der zugehörigen Nerode-Relation endlich ist. (Unter dieser Bedingung ist L also regulär.)

N

• 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 f_max muss mit einer Frequenz von mindestens $2 \cdot f_ {max}$ abgetastet werden, damit man aus dem zeitdiskreten Signal das Ursprungssignal ohne Informationsverlust rekonstruieren kann.

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 gibt kein allgemeines Verfahren, das für jeden Algorithmus feststellen kann, ob die von ihm beschriebene Funktion eine gewünschte Eigenschaft hat.

S

• Satz von Savitch: Ein von einer nichtdeterministischen Turingmaschine mit einer bestimmten Platzkomplexität lösbares Problem ist auf einer deterministischen Turingmaschine mit einer quadratisch höheren Platzschranke lösbar. Daraus ergibt sich die Gleichheit von PSPACE und NPSPACE.

Siehe auch

• Liste von Pionieren der Informatik