Informática Teórica
Engenharia da Computação
COMPLEXIDADE DE TEMPO

A escolha do modelo não afeta o poder: todos
são equivalentes:
– MT de uma única fita
– MT multifita
– MT não-determinística

Mas afeta a complexidade de tempo
– MT multifita O(t(n)) → MT única fita O(t2(n))
– MT não-determinística O(t(n)) → MT única fita
2O(t(n))
COMPLEXIDADE DE TEMPO

Diferenças polinomiais serão consideradas
pequenas
– MT multifita e MT com uma fita
– Polinomialmente equivalentes

Mas diferenças exponenciais serão tomadas
como grandes
– MT não-determinística e MT com uma fita
COMPLEXIDADE DE TEMPO

Algoritmos exponenciais
– Raramente são úteis
– Em geral surgem numa busca por força bruta
– Exemplo: fatoração

Algoritmos polinomiais
– Rápidos para muitos propósitos
– Computadores reais
– Vários modelos computacionais são
polinomialmente equivalentes
COMPLEXIDADE DE TEMPO

Já desprezamos fatores constantes
– Notação O-grande

Iremos desprezar diferenças polinomiais
– Nossa teoria não dependerá de um modelo de
computação específico
– São importantes, mas queremos olhar por uma
perspectiva diferente
CLASSE P
DEFINIÇÃO
 P é a classe de linguagens que são decidíveis
em tempo polinomial por uma MT determinística
de uma única fita
P   TIME (n k )
k
CLASSE P

P é matematicamente robusta
– Invariante para os modelos de computação
equivalentes à MT determinística de uma fita

P é relevante de um ponto de vista prático
– Problemas realisticamente solúveis em um
computador
CLASSE P – DESCRIÇÃO DOS ALGORITMOS

Algoritmos serão descritos em alto nível
– Não nos prenderemos em detalhes de um modelo
computacional específico
– Evitaremos detalhes relativos a fitas e movimentos
de cabeças

Descrição dos estágios
– Estágios serão enumerados (como antes)
– Um estágio em geral vai requerer muitos passos
numa MT
CLASSE P – DESCRIÇÃO DOS ALGORITMOS

Análise quanto à polinomialidade
– Entrada de comprimento n
– Dar um limitante superior polinomial para o
número de estágios que o algoritmo roda em
função de n
– Cada estágio deve ser implementável em tempo
polinomial num modelo determinístico razoável

Se os critérios acima forem respeitados, então o
algoritmo executa em tempo polinomial
– A composição de polinômios é um polinômio
CLASSE P – DESCRIÇÃO DOS ALGORITMOS

Codificação da entrada

Grafos
– Continuamos com  
– A codificação e a decodificação dos objetos devem
ser polinomiais (razoáveis)
– Exemplos: codificações que temos usados para
autômatos e grafos
– Matriz de adjacência: (i,j) é 1 sse existe aresta do
nó i para j
– Tempo calculado em função do número de nós
CLASSE P – PROBLEMAS

CAM = {<G,s,t> | G é um grafo direcionado que
tem um caminho de s para t }
CLASSE P – PROBLEMAS
TEOREMA
 CAM ∈ P

Estratégia força bruta
– Examina todos os caminhos potenciais em G
– Determinar se algum é um caminho direcionado de
s para t
– Caminho potencial: sequência de nós em G tendo
um comprimento de no máximo |V|
– Há aproximadamente |V||V| caminhos potenciais
– Tempo exponencial
CLASSE P – PROBLEMAS

IDÉIA DA PROVA: usar um método de busca no
grafo para evitar a força bruta.
– Busca em largura: marcamos sucessivamente
todos os nós que são atingíveis a partir de s por
caminhos de comprimento 1, depois 2, em
seguida 3 etc.
– Mostrar que a estratégia é polinomial

PROVA: o algoritmo seguinte M decide CAM em
tempo polinomial
CLASSE P – PROBLEMAS

M = “Sobre a entrada <G, s, t> onde G é um
grafo direcionado com nós s e t:
– 1. Marque o nó s.
– 2. Repita o passo seguinte até que nenhum nó
adicional seja marcado
 3. Para cada aresta (a,b) de G: se a for um nó
marcado e b não estiver marcado, marque b.
– 4. Se t estiver marcado, aceite. Senão, rejeite.”
CLASSE P – PROBLEMAS

Número de passos de M
– Os passos 1 e 4 executam apenas uma vez
– O passo 3 executa no máximo |V| vezes: no pior
caso, apenas um nó é marcado a cada vez, exceto
a última

Complexidade dos passos de M
– Os passos 1 e 4 são facilmente implementados em
tempo polinomial
– O passo 3 varre cada aresta e executa um teste
para ver se um nó está marcado
CLASSE P – PROBLEMAS

Conclusão da prova
– M executa uma quantidade de passos polinomial
na entrada
– Todos os passos de M rodam em tempo polinomial
na entrada
– Logo, M é polinomial
– CAM ∈ P

Exercício do livro: 7.8
CLASSE P – PROBLEMAS

PRIM-ES = {<x, y> | x e y são primos entre si}

Dois números são primos entre si quando 1 é o
maior inteiro que divide ambos

<10, 21> ∈ PRIM-ES
<10, 22> ∉ PRIM-ES

CLASSE P – PROBLEMAS
TEOREMA
 PRIM-ES ∈ P

Estratégia força bruta
– Procurar entre todos os possíveis divisores de
ambos os números
– Aceita se o único divisor comum entre eles for 1
– A magnitude de um número representado em
qualquer base maior ou igual a 2 é exponencial no
comprimento da representação
– Então a busca é feita entre um número
exponencial de potenciais divisores
CLASSE P – PROBLEMAS

IDÉIA DA PROVA: usar o algoritmo de Euclides
para computar o máximo divisor comum
– Calcular o MDC de x e y
– Se o resultado for 1, x e y são primos entre si

Função mod: retorna o resto da divisão do
primeiro número pelo segundo
– 10 mod 3 = 1
– 28 mod 4 = 0
CLASSE P – PROBLEMAS

PROVA: definiremos o algoritmo E para computar
o MDC. Em seguida, definiremos o algoritmo R
para decidir PRIM-ES
CLASSE P – PROBLEMAS

E = “Sobre a entrada <x, y>, onde x e y são
números naturais em binário:
– 1. Repita até que y = 0:
 2. x := x mod y
 3. Troque os valores de x e y
– 4. Retorne x”

R = “Sobre a entrada <x, y>, onde x e y são
números naturais em binário:
– 1. Execute E sobre <x, y>
– 2. Se E retornou 1, aceite. Senão, rejeite.”
CLASSE P – PROBLEMAS

Complexidade de E
– O passo 2 reduz o valor de x no mínimo pela
metade (exceto possivelmente na 1ª vez: se x ≤ y)
– Após o passo 2 temos x < y e depois do passo 3
temos x > y: a cada iteração do loop, um valor é
reduzido no mínimo pela metade e o outro não
– Então o número máximo de execuções do loop é o
mínimo entre 2log2x e 2log2y
– Como x e y são representados em binário, a
quantidade de passos de E é O(n)
– Os passos de E são facilmente implementáveis em
tempo polinomial. Logo, o algoritmo é polinomial
CLASSE P – PROBLEMAS

Complexidade de R
– R = “Sobre a entrada <x, y>, onde x e y são
números naturais em binário:
 1. Execute E sobre <x, y>
 2. Se E retornou 1, aceite. Senão, rejeite.”
– Como E roda em tempo polinomial, então R
também é polinomial

Exercícios do livro: 7.3 e 7.12
CLASSE P – PROBLEMAS

AGLC = {<G, w> | G é uma GLC que gera a cadeia
w}

Uma MT que decide AGLC
S = “Sobre a entrada <G, w>, onde G é uma GLC
e w uma cadeia de comprimento n:

– 1. Converta G para a forma normal de Chomsky
– 2. Liste todas as derivações com 2n-1 passos (se
n = 0, liste todas as derivações com 1 passo)
– 3. Se alguma derivação gerou w, aceite. Senão,
rejeite.”
CLASSE P – PROBLEMAS

S roda em tempo polinomial?
– Qualquer derivação de uma cadeia |w| = n tem 2n1 passos (se a gramática está na forma normal de
Chomsky)
– S tenta todas as derivações com 2n-1 passos para
verificar se alguma gera w
– Como o número de derivações com k passos pode
ser exponencial em k, S não é polinomial
– Logo, S não prova que aceitação de LLC é
polinomial

Existe algum algoritmo polinomial para
aceitação de LLC?
CLASSE P – PROBLEMAS
TEOREMA
 IDÉIA DA PROVA
– Utilizar programação dinâmica: guardar
informações sobre subproblemas menores
– Subproblema: determinar se cada variável da GLC
gera cada subcadeia de w
– Usar uma tabela n x n para guardar as soluções
dos subproblemas
– (i, j): se i ≤ j, então a célula guarda as variáveis
que geram a subcadeia wiwi+1...wj. As posições
com i > j não serão utilizadas
– Preenche a tabela para as subcadeias de
comprimento 1, depois 2, ... Até a de tamanho n
CLASSE P – PROBLEMAS

IDÉIA DA PROVA (continuação)
– Suponha que o algoritmo já tenha resolvido o problema
para todas as subcadeias de tamanho k
– Para saber se alguma variável A gera uma subcadeia
específica de tamanho k+1:
 Dividir a subcadeia de tamanho k+1 em duas partes
não vazias (há k possibilidades de divisão)
 Para cada divisão, o algoritmo passa por cada regra
do tipo A → BC
 Se B gera a primeira subcadeia e C gera a segunda,
então A gera a subcadeia de tamanho k+1
 Adicionamos A à entrada associada da tabela
– Iniciamos com as cadeias de tamanho 1 e analisando
as regras do tipo A → b
CLASSE P – PROBLEMAS
TEOREMA
 PROVA: algoritmo que recebe uma gramática na
forma normal de Chomsky e uma cadeia w (S é a
variável inicial da gramática)

D = “Sobre a entrada w = w1w2...wn
– 1. Se w = ε e S → ε for uma regra, aceite
– 2. Para i=1 até n:
 3. Para cada variável A:
– 4. Teste se A → wi é uma regra
– 5. Se for, adicione A em tabela(i, i)
CLASSE P – PROBLEMAS

D (continuação)
– 6. Para l = 2 até n
 7. Para i=1 até n-l-1
 8. j := i+l-1
 9. Para k=i até j-1
[l é o comprimento da subcadeia]
[i é a posição inicial da subcadeia]
[j é a posição final da subcadeia]
[k é onde ocorre a divisão]
– 10. Para cada regra A → BC
– 11. Se tabela(i, k) contém B e tabela (k+1,j) contém C
 Coloque A em tabela(i, j)
– 12. Se S estiver em tabela(1, n), aceite. Senão,
rejeite
CLASSE P – PROBLEMAS

Complexidade de D
– Todo os passos são implementados em tempo polinomial
– A quantidade de passos é polinomial: O(n3) + O(n) = O(n3)
 O passo 1 roda apenas uma vez
 Os passos 4 e 5 rodam no máximo n*v (onde v é o número
de variáveis): O(n)
 O passo 6 roda no máximo n vezes
– Para cada vez que o 6º roda, o passo 7 roda no máximo n vezes
– Para cada vez que o 7º roda, os passos 8 e 9 rodam no máximo
n vezes
– Cada execução do 9º, o passo 10 roda r vezes (onde r é uma
constante fixa)
 Logo, o passo 11 roda O(n3) vezes

Exercício do livro: 7.4
Informática Teórica
Engenharia da Computação