Teoria informacji/TI Ćwiczenia 14: Różnice pomiędzy wersjami

Wersja z 21:02, 25 sie 2006

Ćwiczenie 1 [Nieobliczalność $Ω$ ]

{{{3}}}

{{cwiczenie|2 [Uniwersalny test Martina-Lofa]|Ćwiczenie 2| Definicja [Test]

Funkcję

δ : {0, 1}^{*} \to N

nazwiemy testem, jesli dla każdych

m, n,

\frac{| {w \in {0, 1}^{n} : δ (w) \geq m} |}{2^{n}} \leq \frac{1}{2^{m}}

Ponadto zakładamy, że istnieje algorytm częsciowy, który dla każdej pary $w, m,$ takiej, że

δ (w) \geq m,

zatrzymuje się i daje odpowiedź TAK, natomiast gdy

δ (w) < m,

algorytm daje odpowiedź NIE lub się zapętla. (Natomiast funkcja

δ

nie musi być obliczalna.

Zauważmy, że dla każdego

Dowiedź, że istnieje

@@ Linia 33: / Linia 33: @@
 </div>
 }}
+{{cwiczenie|2 [Uniwersalny test Martina-Lofa]|Ćwiczenie 2|
+{{definicja|[Test]|test|Funkcję <math>\delta : \{ 0,1 \}^* \to N </math> nazwiemy '''testem''', jesli dla każdych <math>m,n, </math>
+<center><math>
+\frac{|\{ w \in \{ 0,1 \}^n : \delta (w) \geq m \} |}{2^n} \leq \frac{1}{2^m}
+</math></center>
+Ponadto zakładamy, że istnieje algorytm częsciowy, który dla każdej pary <math>w,m, </math> takiej, że
+<math> \delta (w) \geq m, </math> zatrzymuje się i daje odpowiedź '''TAK''', natomiast gdy <math> \delta (w) < m, </math> algorytm daje odpowiedź '''NIE''' lub się zapętla. (Natomiast funkcja <math>\delta </math> nie musi być obliczalna.}}
+Zauważmy, że dla każdego
+: Dowiedź, że istnieje