MAC 722 Introdução à Teoria da Complexidade Computacional
Horário: segundas-feiras das 16:00 às 18:00 e quartas-feiras das 14:00
às 16:00.
Local: sala 267 do bloco A.
Conteúdo das Aulas durante o mês de março
- Aula 1 (2 de março)
- Estória do supervisor (como fazer para não peder o
emprego).
- Por que Artur mandou que Merlin fosse aprisionado (Parte
I).
(A Parte II fica para MAC 828 Tópicos em Complexidade
Computacional.)
- O Problema do st-caminho: problemas de decisão; algoritmo
quadrático para o problema; análise de espaço.
- Um critério de eficiência: Algoritmos polinomiais e
problemas intratáveis.
- Aula 2 (4 de março)
- O Problema do Fluxo Máximo: problemas de otimização; o
problema de decisão associado; o Método do Caminhos
Aumentantes de Ford & Fulkerson; algoritmos
pseudopolinomiais; algoritmos fortemente polinomiais.
- Emparelhamento em grafos bipartidos: redução; uso perverso
de reduções.
- O Problema do Caixeiro Viajante: um problema aparentemente
intratável; o problema de decisão associado.
- Aula 3 (9 de março)
- Máquinas de Turing: visão informal; formalização; máquina
de Turing para "deslocar um string"; configurações; máquina
de Turing para calcular o sucessor de um número binário;
máquina de Turing para reconhecer palíndromos.
- Máquinas de Turing como algoritmos: linguagens; linguagens
decidida por uma máquina de Turing (e.g. palindromos);
linguagens recursivas e recursivamente enumeráveis.
- Problemas e linguagens: esquemas de codificação;
representações para um grafo (lista de arestas e matriz de
adjacência); esquemas de codificação "aceitáveis"
(blá-blá-blá); a relação entre problemas de decisão e
linguagens.
- Aula 4 (11 de março)
- Máquinas de Turing com vários strings: visão informal e
formal; uma 2-string máquina de Turing que decide palíndromos
sobre o alfabeto {0,1}; configurações.
- Tamanho da entrada de uma máquina de Turing = número de
símbolos do string dado.
- Complexidade de tempo: uma máquina de Turing M opera em
tempo f(n) se, para cada entrada x, o tempo gasto por M para
computar M(x) é no máximo (pior caso) f(|x|).
- Classes de complexidade: se L é uma linguagem decidível
por uma máquina de Turing M que opera em tempo f(n) então
dizemos que L pertence a TIME(f(n)). TIME(f(n)) contém as
linguagens que podem ser decididas por uma máquina de
Turing em tempo limitado por f(n). Chamamos TIME(f(n)) de
uma classe de complexidade.
- É razoável assumir que f(n) é pelo menos n+2, uma vez
que o tempo necessário apenas para ler a entrada e
verificar que o final foi atingido é n+2.
- Teorema Dada uma k-string máquina de Turing M
operando em tempo f(n) > n+1 , podemos construir uma
1-string máquina de Turing M' operando em tempo O(f(n)^2)
tal que M(x) = M'(x) para toda entrada x. (Insistindo, note
a hipótese de f(n) ser maior que n+1.) (Resumo: o número de
strings da máquina não é documento.)
- Aula 5 (16 de março)
- Avisos A primeira prova será no dia 15 de abril das
13:00 às 16:00. Não sabemos ainda em qual sala será.
- Entrega da primeira lista de exercícios.
- Teorema (Linear Speedup).
Seja L uma linguagem em TIME(f(n)). Então, para cada eps > 0,
L pertence a TIME(f'(n)), onde f'(n) = eps * (f(n) + n) + n + 11.
- Aula 6 (18 de março)
- Complexidade de espaço: alternativas para medir o espaço
gasto por um algoritmo (soma dos comprimentos dos strings ou
comprimento do maior string: as duas alternativas diferiam
por um fator constante); máquina de Turing que usa espaço
O(log n) para decidir palíndromo.
- Máquina de Turing com entrada e saída e k strings (na
string de entrada só podemos ler cada símbolo uma vez e na fita
de saída depois que um símbolo é escrito ele não pode ser mais
apagado).
- Proposição Seja M uma máquina de Turing com k
strings operando em tempo f(n). Então existe uma máquina de
Turing com entrada e saída e k+2 strings equivalente operando
em tempo O(f(n) + n). (Moral da história: strings exclusivos
para entrada e saída não sobrecarregam """muito""" o tempo de
computação.)
- Definição de espaço usado por uma máquina de Turing. Se a
máquina de Turing for uma máquina de entrada e saída o
espaço usado será a soma dos comprimentos dos strings da
máquina que não sejam nem de entrada e nem de saída.
- Classe de complexidade SPACE(f(n)): é o conjunto de
linguagens decididas por uma
máquina de Turing deterministica com entrada e saída que opera
em espaço limitado por f(n).
- Teorema Se L pertence a SPACE(f(n)) então existe uma
máquina de Turing com entrada e saída e 3 fitas que decide L
e opera em espaço f(n). (Ver o livro de Hopcroft & Ullman.)
- Teorema (Exercício) Se L pertence a SPACE(f(n))
então, para qualquer eps > 0 temos que L pertence a
SPACE(c + eps * f(n)), onde c é uma constante (talvez 2 ou
3).
- Modelo RAM (Ver o livro de Aho,
Hopcroft & Ullman.):
o modelo, complexidade de tempo de um programa RAM (custo
unitário e custo logarítmico).
- Aula 7 (23 de março)
- Complexidade de programas RAM: custo unitário e custo
logarítmico.
- Teorema
Uma máquina de Turings M opera em tempo f(n) >= n+2 pode ser
simulada por um programa RAM operando em tempo
O(f(n)*log(f(n))), onde a complexidade de tempo do do
programa RAM é medida usando o critério de custo logarítmico.
- Teorema (Ver o Teorema 1.3 livro de Aho, Hopcroft & Ullman.)
Seja P um programa RAM que opera em tempo f(n) sob o
critério de custo logarítmico. Se P não usa nem
multiplicações nem divisões, então P pode se simulado por
uma máquina de Turing M operando em tempo O(f^2(n)).
- Aula 8 (25 de março)
- Tese de Church Toda função computável pode ser
computada por uma máquina de Turing.
- Teorema Os modelos RAM sob custo logarítmico e o
modelo de Máquina de Turing são relacionados polinomialmente.
- Máquinas de Turing não-determinísticas.
- Linguagens decididas por um máquina de Turing
não-determinística. Dizemos que uma máquina de Turing não
determinística decide L se, para entrada x, x está em L se e
somente se existe uma computação que leva a máquina N com
entrada x da configuração inicial a uma configuração de
aceite (SIM,u,w) para algum u e w.
- Dizemos que uma máquina de Turing não-determinística N
opera em tempo f(n) se qualquer computação de N termina em
tempo f(|x|) passos para qualquer entrada x.
- Classe de complexidade NTIME(f(n)): o conjunto de todas as
linguagens decididas por uma máquina de Turing
não-determinística operando em tempo no máximo f(n).
- Teorema Se L está em NTIME(f(n)) então L está
em TIME(c^{f(n)}), onde c>1 é uma constante que depende
somente da máquina de Turing não deterministica que decide
L.
- Aula 9 (30 de março)
- Entrega da segunda lista de exercícios.
- Definição Uma máquina de Turing não determinística N
opera em espaço f(n) se, para cada possível entrada x, N nunca,
em nenhuma das possíveis computações para x, gasta espaço maior
do que f(|x|).
- Classe de complexidade NSPACE(f(n)): é o conjunto das
linguagens decididas por alguma máquina de Turing
não-deterministica operando em
espaço f(n). Exemplo: máquina de Turing não-determinística
para o problema do st-caminho que opera em espaço O(log
n). Logo, st-caminho pertence a NSPACE(log n + 3). Será que
st-caminho pertence a SPACE(log n)?
- (Capítulo 3 do livro de Papadimitriou) Máquina de Turing
Universal. Objetivo: definir uma máquina de Turing U que, com
entrada M e x produz como saída M(x) (M é uma máquina de Turing
qualquer.)
- Problema da Parada: H = { M;x | M pára com entrada x}, onde
M;x é uma codificação da máquina M e da entrada x.
- Proposição H é recursivamente enumerável.
- Proposição Se H é recursiva, então R = RE.
- Comentário sobre o que é uja linguagem completa para uma
classe.
MAC 722's Home Page.
Last modified: Mon Aug 24 08:27:22 EST 1998