Limitações dos Computadores
Baseado em Computers Ltd. – What they really can’t do,
David Harel. Oxford University Press, 2000.
Computadores e Redes de Comunicação
Mestrado em Gestão de Informação, FEUP 2004/07
Sérgio Sobral Nunes
mail: [email protected]
web: www.fe.up.pt/~ssn
Algoritmos
Contexto
• Os computadores são máquinas poderosas. Permitem
controlar aviões, instalações complexas, elevados fluxos de
dados em redes de comunicação.
• Apesar da elevada complexidade, todos os computadores
podem ser vistos como uma grande colecção de interruptores
(ou bits), ligados ou desligados.
• Estes interruptores são controlados por algoritmos, programas
ou processos computacionais, que respondem a dados
recebidos.
Sérgio Nunes
Comunicações e Redes de Computadores
3
Algoritmo - Analogia
Entrada
Ingredientes
Software
Hardware
Receita
Forno
Utensílios
Bolo
Saída
Sérgio Nunes
Comunicações e Redes de Computadores
4
Problemas Algorítmicos
• Os algoritmos são desenhados para resolver
problemas algorítmicos.
Qualquer
entrada legal
Especificação
de todas as
entradas legais
+
Algoritmo
Caracterização
da saída
desejada como
função da
entrada.
Sérgio Nunes
A saída
pretendida
Comunicações e Redes de Computadores
5
Exemplos de Problemas
• Entrada: Dois inteiros, A e B.
• Saída: O número A + 4B
• Entrada: Um inteiro positivo N.
• Saída: O somatório dos inteiros de 1 a N.
• Entrada: Um inteiro positivo N.
• Saída: “Sim” se N é primo e “Não” se não é.
• Entrada: Dois textos em português.
• Saída: Uma lista das palavras comuns aos dois textos.
Sérgio Nunes
Comunicações e Redes de Computadores
6
Validação dos Algoritmos
• Validar um algoritmo é uma tarefa complexa.
• Validação parcial não é aceitável, é necessário validar o
algoritmo para todas as entradas legais.
• Erros de sintaxe – a escrita dos programas contém erros.
• Erros de lógica – a estratégia gizada no algoritmo está errada.
Sérgio Nunes
Comunicações e Redes de Computadores
7
Máquina de Turing
• Em 1936, Alan Turing apresentou o modelo conceptual de um
computador especialmente pensado para a análise da natureza
e limites da computação.
• A Máquina de Turing é composta por uma fita infinita com
posições e uma cabeça de leitura/escrita. A fita pode ser
deslocada em ambas as direcções e cada posição pode ser lida
ou escrita.
Sérgio Nunes
Comunicações e Redes de Computadores
8
Máquina de Turing
• A Máquina de Turing tornou-se o modelo teórico base para o
desenvolvimento de uma teória da computação.
• Apesar de serem extremamente simples (facilitando o
desenvolvimento de teorias), as Máquinas de Turing capturam
tudo o que pode ser feito computacionalmente.
• Tudo o que pode ser feito num computador actual, pode ser
feito numa Máquina de Turing. Nenhum computador físico
existente consegue fazer mais do que uma Máquina de Turing.
• Se uma Máquina de Turing consegue resolver um problema, o
problema designa-se de computável. Caso contrário é um
problema não computável.
Sérgio Nunes
Comunicações e Redes de Computadores
9
Problemas Impossíveis
Problemas Impossíveis
• Existem problemas que não podem ser resolvidos por
nenhum computador, presente ou futuro, qualquer que seja o
programa a ser executado, mesmo com recursos ilimitados
(tempo, armazenamento, outros).
• O conjunto de todos os problemas algorítmicos pode ser
dividido em dois subconjuntos: problemas computáveis e
problemas não computáveis.
• Todos os problemas com um conjunto finito de entradas são
computáveis. No limite podemos escrever a saída a apresentar
para cada entrada.
Sérgio Nunes
Comunicações e Redes de Computadores
11
Problemas Não Computáveis
• Problema da Paragem, 1936 (Halting Problem)
• “Dada a descrição de um programa e a entrada inicial,
determinar se o programa, quando executado com a entrada
definida, alguma vez termina (halts) ou, alternativamente,
executa para sempre.”
• Demonstra-se que não existe um algoritmo para este problema.
• Teorema da Incompletude de Gödel, 1931
• “Num sistema lógico formal consistente, existem afirmações
verdadeiras que não podem ser provadas.”
Sérgio Nunes
Comunicações e Redes de Computadores
12
Problema da Paragem
•
O problema da paragem permite explicar porque é que os computadores não
conseguem prever problemas e evitar crashes ou bloqueios.
•
“Existe um programa que, para uma qualquer máquina de Turing e uma
qualquer entrada de dados, determine se a máquina pára (halts)?”
•
Prova
–
Assume-se a existência de um algoritmo Halt(p,d) que determina se o programa p
perante a entrada d pára (“sim”) ou não, entrando em ciclo infinito (“não”).
–
Um outro algoritmo Trouble(p) invoca o algoritmo Halt usando a entrada recebida e
escreve “sim” se o Halt(p,p) determinar “não”, caso contrário entra num ciclo infinito.
–
Correspondendo T ao algoritmo Trouble, o que acontece com Halt(T,T)?
–
–
Se Halt(T,T)=“não” Touble(T)=“sim” Halt(T,T) deveria ter sido “sim”.
Se Halt(T,T)=“sim” Touble(T) entra em ciclo Halt(T,T) deveria ter sido “não”.
Sérgio Nunes
Comunicações e Redes de Computadores
13
Problemas Não Viáveis
Problemas Não Viáveis
• Mesmo que o problema seja computável, e um algoritmo
correcto exista, a execução pode ser demasiado dispendiosa no
uso dos recursos, tornando-se impraticável.
• Um programa de computador consume recursos,
nomeadamente tempo (acções executadas) e espaço
(armazenamento dos dados utilizados).
• Diferentes algoritmos para o mesmo problema podem variar
significativamente nos recursos consumidos.
• A diferença entre funções polinomiais (N2) e funções
exponenciais (2N) é crucial.
Sérgio Nunes
Comunicações e Redes de Computadores
15
Ordens de Complexidade
• Algoritmo para Ordenação – O(N2)
Ordenar de forma crescente um conjunto de números.
– Percorrer a lista de números e obter o menor.
– Trocar este valor com aquele na primeira posição.
– Voltar ao primeiro passo excluindo o elemento inicial.
– http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html
• Caixeiro Viajante – O(N!)
Para um conjunto de cidades, descobrir qual é a ordem de visitas que permite
percorrer um caminho total mais curto visitando cada cidade apenas uma vez?
– Testar todas as combinações possíveis e verificar qual a mais
curta.
Sérgio Nunes
Comunicações e Redes de Computadores
16
Complexidade de um Algoritmo
•
O(N) - linear
–
para todos os N fazer
•
140
Instrução
120
•
O(N2) – polinomial
–
100
desde 1 até N fazer
•
desde 1 até N fazer
–
Instrução
O(N)
80
O(N^2)
O(2^N)
•
O(2N) – exponencial
–
•
60
para um número, testar todas as
combinações de dois números (A,B)
em que AxB=N
40
20
0
O(N!) – factorial
–
O(N!)
1
2
3
4
5
para N elementos testar todas as
combinações possíveis
Sérgio Nunes
Comunicações e Redes de Computadores
17
Problema do Caixeiro Viajante
• Dado um conjunto de cidades e o custo de viajar entre cada par
de cidades, determinar o percurso mais barato de modo a
visitar todas as cidades apenas uma vez e voltar ao ponto de
origem.
• A abordagem simples requer a análise de n! permutações.
• Considerando um milisegundo para analisar cada permutação.
–
–
–
–
–
5 cidades 0.1 segundos
10 1 hora
15 41 anos
20 3.000.000 anos
23 mais do que a idade do universo
Sérgio Nunes
Comunicações e Redes de Computadores
18
Criptografia
• Problemas difíceis de resolver em tempo útil são importantes na
área da criptografia.
• O método RSA, uma implementação do conceito de
criptografia com chaves públicas, recorre a dois conceitos
chave: factorização de um número e verificação da primalidade
de um número.
• Enquanto que o teste é possível ser realizado de forma rápida.
A factorização de números grandes é um problema para o
qual não existem soluções rápidas.
Sérgio Nunes
Comunicações e Redes de Computadores
19
Riscos da Criptografia
• Mecanismos como o da criptografia têm por base duas
assunções fundamentais:
– Os computadores são demasiado lentos.
– Somos ignorantes para lidar com estes problemas.
• Quando houver uma mudança significativa numa destas áreas,
os sistemas que utilizam criptografia estão em risco.
• A invenção de novos paradigmas pode trazer novas
abordagens aos problemas actuais. O aumento no desempenho
dos computadores pode tornar viável as soluções actuais.
Sérgio Nunes
Comunicações e Redes de Computadores
20
Novas Abordagens
• Novos paradigmas para o desenvolvimento de algoritmos
tentam ultrapassar (minimizar) estas limitações.
• Computação Paralela
•
Múltiplos computadores a trabalhar em paralelo sobre o mesmo problema.
• Computação Aleatória
•
Utilização de valores aleatórios durante os passos do algoritmo.
• Computação Quântica
•
Abordagem baseada nos conceitos da mecânica quântica.
• Computação Molecular
•
Utilização de moléculas para a resolução de problemas.
Sérgio Nunes
Comunicações e Redes de Computadores
21
“A questão sobre se os computadores sabem ou não pensar é
equivalente à questão sobre se os submarinos sabem ou não nadar.”
E. W. Dijkstra
Bibliografia
• Principal
– David Harel – Computers Ltd. – what they really can’t do. Oxford
University Press, 2000.
– A. K. Dewdney – The New Turing Omnibus. A. K. Freeman, 1993.
Sérgio Nunes
Comunicações e Redes de Computadores
23