MAC 828 Tópicos em Complexidade Computacional

Conteúdo das Aulas durante o mês de novembro

• Aula 22 (4 de novembro) Marcio
  • Self-delimiting information complexity.
  • Lema K(x) \leq H(x) \leq K(x) + 2 \log_m (K(x)) + O(1).
  • Lema
    1. \sum_x m^{K(x)} = +\infty.
    2. \sum_x m^{H(x)} \leq 1.
    ($m$ é o tamanho do alfabeto.)
  • Lema Seja $\mathcal{L}$ uma linguagem tal que nenhuma de suas palavras é um prefixo da outra. Sela $m$ o tamanho do alfabeto. Então $\sum_{y \in \mathcal{L} m^{-|y|} \leq 1.$
  • Coding Theorem Seja $p$ uma disctribuição de probabilidades computável sobre $\Sigma_0^*$. Então para cada palavra $x$ temos que $H(x) \leq -\log_m p(x) + O(1)$. [Shannon-Fano Coding]
• Aula 23 (9 de novembro) Marcio
  • Noção de seqüência aleatória.
  • Lema O número de seqüências $x$ de 0's e 1's de comprimento $n$ com $K(x) \leq n - k$ é menor ou igual a 2^{n-k+1}.
  • Corolário A complexidade de 99% das seqüências de $n$ digitos 0-1 é maior do que $n-8$. Se escolhemos uma seqüência de 0-1 de comprimento $n$ uniformemente ao acaso então |K(x) - n| \leq 100 com probabilidade 1 - 2^{100}.
  • Lema Se o número de 1's em uma 0-1-seqüência $x$ de comprimento $n$ é $k$ então $K(x) \leq \log_2 \comb{n}{k} + 2 \log_2 n + 2 \log_2 k + O(1).
  • Seqüências fracamente e fortemente aleatórias.
• Aula 24 (16 de novembro) Marcio
  • Teorema Se uma seqüência infinita $x$ de 0's e 1's é contruída escolhendo-se um 0 ou um 1 com probabilidade 1/2 então esta seqüência é fortemente aleatória com probabilidade 1.
  • Complexidade de Kolmogorov e entropia (H(p) = \sum_i -p_i \log p_i).
  • Complexidade de Kolmogorov e coding.
• Aula 25 (23 de novembro) Carlos
• Aula 26 (25 de novembro) Carlos
• Aula 27 (30 de novembro) Carlos