Direkt zum Inhalt

Lexikon der Mathematik: Shannon-Effekt

Eigenschaft, die eine Menge \({{\mathfrak{M}}}_{n}\) von Booleschen Funktionen f : {0, 1}n → {0, 1} bzgl. eines auf den Booleschen Funktionen definierten Komplexitätsmäßes C (Boolesche Funktionen) haben kann.

Die Eigenschaft liegt vor, wenn fast alle Booleschen Funktionen f ∈ \({{\mathfrak{M}}}_{n}\) eine Komplexität C(f) haben, die größer gleich \begin{eqnarray}C({{\mathfrak{M}}}_{n})-\circ (C({{\mathfrak{M}}}_{n}))\end{eqnarray} ist. Hierbei ist \(C({{\mathfrak{M}}}_{n})=\max \{C(f)|f\in {{\mathfrak{M}}}_{n}\}\), gibt also die Komplexität der härtesten Booleschen Funktion aus \({{\mathfrak{M}}}_{n}\) an. Formal gilt der Shannon-Effekt genau dann, wenn der Grenzwert \begin{eqnarray}\mathop{\mathrm{lim}}\limits_{n\to +\infty}\frac{\,|\{f\in {{\mathfrak{M}}}_{n}\,|\,C({f})\ge C({{\mathfrak{M}}}_{n})-\circ (C({{\mathfrak{M}}}_{n}))\}|}{|{{\mathfrak{M}}}_{n}|}\end{eqnarray} gleich 1 ist.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos