introdução a sistemas de computação digital€¦ · tópico 1 – introdução a sistemas de...
TRANSCRIPT
Introdução a Sistemas de Computação Digital 1 Preliminares ....................................................................................................................................................................1 2 Visão Geral da Organização de um Computador ...........................................................................................................2 3 O papel da computação...................................................................................................................................................6 4 Computação digital.........................................................................................................................................................6
4.1 Duas imagens digitalizadas (o compromisso do espaço)...........................................................................................7
4.2 Analógico × Digital....................................................................................................................................................8 4.3 Princípios de computação analógica ..........................................................................................................................9 4.4 O determinismo do mundo digital ...........................................................................................................................12
5 Algoritmos ....................................................................................................................................................................14 5.1 Exemplo de um procedimento que não é um algoritmo ..........................................................................................15
6 Especificação de algoritmos e fluxo de controle ..........................................................................................................16 7 Resolução de um problema usando computador ..........................................................................................................19 8 Computabilidade...........................................................................................................................................................21 9 Factibilidade computacional.........................................................................................................................................22 10 Complexidade computacional: temporal e espacial .....................................................................................................23
10.1 Problemas NP e NP-completos..........................................................................................................................26 10.2 Quantificando a razoabilidade temporal e espacial ...........................................................................................32
10.3 O produto de duas matrizes N × N.....................................................................................................................34 10.4 O problema do caixeiro viajante........................................................................................................................35 10.5 O problema da mochila (knapsack problem).....................................................................................................37
11 O que fazer frente a um problema NP-completo ..........................................................................................................38 11.1 O problema do quadrado mágico.......................................................................................................................41
12 Cálculo de complexidade computacional temporal......................................................................................................44 13 Referências ...................................................................................................................................................................51
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 1
1 Preliminares
• objetivo: familiaridade com a organização, arquitetura e fluxo de informação
em computadores digitais.
• enfoque: genérico, sem evidenciar uma máquina específica ou uma linguagem
de programação em particular.
• resultado esperado: entender o computador como uma ferramenta de
processamento de informação de propósito geral e de aplicação praticamente
irrestrita, embora com potencial finito.
• conseqüência prática: maior capacidade de análise e uso de recursos
computacionais no contexto de atividades que envolvem processamento de
informação, simulação, modelagem e solução de problemas.
• lema: “Conhecer para conquistar.”
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 2
2 Visão Geral da Organização de um Computador • computador = unidade central de processamento + memória principal +
interface de entrada/saída
• unidade central de processamento (UCP) = processador da máquina
• periféricos: teclado, monitor, disco rígido (memória secundária), mouse, impressora, modem, etc.
Computador(processamento earmazenagem de
informação)
Linhas decomunicação com
os periféricos
Figura 1: O computador (nível 3)
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 3
• arquitetura padrão von Neumann: memória e processamento em dispositivos físicos distintos, mas com armazenagem de instruções e dados no mesmo dispositivo de memória.
Computador
Computador
I/O
Barramentos dosistema
MemóriaPrincipal
Unidade Centralde Processamento
Figura 2: O computador (nível 2)
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 4
Computador
Unidade Central deProcessamento
Registradores
Barramentosinternos
Unidade deControle
UnidadeAritmética e
Lógica
UCPI/O
Memória
Barramentos
Figura 3: O computador (nível 1)
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 5
UCP
Unidade deControle
Lógicaseqüencial
Registradorese decodificadores
Memóriade
Controle
UC
Registra-dores
UAL
Barramentos
Figura 4: O computador (nível 0)
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 6
3 O papel da computação
• no princípio: cálculo (realização de operações aritméticas);
• hoje: máquina virtual (cálculo, simulação, lógica, armazenagem e
processamento de informação, automação industrial, lazer, etc).
4 Computação digital
• um computador digital é uma máquina que recebe informação do mundo
exterior, converte esta informação na forma binária e a processa de acordo
com um conjunto predeterminado de operações, fornecendo como saída a
informação processada.
• recursos multimídia: armazenagem, transmissão e processamento de informação em representação binária.
! Como digitalizar uma imagem ou seqüência sonora?
! Sinais analógicos (por que analógico?) × digitais (por que digitais?)
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 7
4.1 Duas imagens digitalizadas (o compromisso do espaço)
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 8
4.2 Analógico × Digital
• relógio analógico: a hora é indicada por uma analogia entre a posição angular contínua dos ponteiros e a escala de horas e minutos definida ao longo dos 360o (informação fornecida por uma medida de uma grandeza física que tem com uma segunda grandeza física uma relação biunívoca).
• relógio digital: um contador binário é empregado para atualizar o estado (emitindo ou não emitindo luz) dos leds que compõem o mostrador numérico.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 9
4.3 Princípios de computação analógica
• considere o seguinte circuito elétrico:
• trata-se de um sistema dinâmico que apresenta uma determinada função de
transferência de entrada-saída.
• considere agora o seguinte sistema hidráulico, composto por tanques
comunicantes:
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 10
onde Q e iH (i=1,2) são fluxo e altura em estado estacionário.
• é possível mostrar que as funções de transferência do sistema hidráulico e do
circuito elétrico são (quase) idênticas, mesmo tratando-se de sistemas
dinâmicos de natureza distinta.
• há também uma correspondência um-para-um entre alguns de seus
parâmetros.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 11
• sendo assim, dado um dos sistemas dinâmicos apresentados, existem valores
que podem ser adequadamente definidos para os parâmetros do outro sistema
de modo que, para uma mesma condição inicial, o comportamento ao longo
do tempo seja idêntico para ambos os sistemas.
• além disso, o circuito elétrico apresenta as seguintes propriedades quando
comparado ao sistema hidráulico (e a muitos outros sistemas dinâmicos):
# é muito mais simples e econômico de ser implementado;
# seus parâmetros podem ser ajustados com grande precisão e sem muito
esforço ou custo;
# as variáveis que retratam a evolução de seu estado no tempo podem ser
facilmente medidas.
• logo, é possível estudar o comportamento dinâmico do sistema hidráulico (e
de muitos outros sistemas), por analogia. → Computação Analógica
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 12
4.4 O determinismo do mundo digital
• os computadores se comportam de modo diferente do cérebro humano devido
à sua organização e não apenas pelo fato de representarem informação na
forma binária.
• o computador digital é a mais determinística das máquinas inventadas pelo
homem: existe um domínio praticamente completo sobre o estado da máquina
e sua evolução no tempo.
• bits → redundância → insensibilidade a alterações físicas dos componentes.
• computadores digitais: executam automaticamente, a cada passo do processo de computação, correções da trajetória de seu estado físico por meio da representação binária do estado interno de seus componentes.
• computadores analógicos: não são capazes de realizar correção de trajetória, sendo que a relevância dos resultados produzidos é diretamente proporcional à acurácia dos componentes e inversamente proporcional à extensão dos cálculos.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 13
• neurocomputadores: embora executem cálculos analógicos, a trajetória do estado interno dos neurocomputadores é apreendida em uma base local e atraída pela solução do problema (associada àquela base). Embora muitos resultados já tenham sido obtidos, o desenvolvimento de neurocomputadores ainda se encontra em seus primórdios.
Computadores digitais Computadores analógicos
Neurocomputadores
trajetóriaideal
trajetória real comcorreção
estadoinicial
estado final= solução
um passocomputacional
trajetóriaideal
trajetória real semcorreção
estadoinicial
estado final= solução
trajetóriaideal
trajetória real é atraídapelo estado final
estadoinicial
estado final= solução
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 14
5 Algoritmos
Como implementar o processamento computacional?
• um computador digital só pode realizar tarefas previamente definidas;
• procedimento: conjunto finito de operações ordenadas, sendo estas operações
também finitas.
• propriedades importantes de um procedimento (ou uma seqüência de
procedimentos):
# a descrição do procedimento deve ser finita;
# a tarefa genérica de qualquer procedimento é processar dados: dados de
saída são produzidos a partir do processamento dos dados de entrada;
# um procedimento pode ser subdividido em operações atômicas,
denominadas instruções, passíveis de execução em tempo finito.
• algoritmos: procedimentos que terminam após um número finito de passos.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 15
5.1 Exemplo de um procedimento que não é um algoritmo
• cálculo do somatório de números inteiros de 0 até m (m deve ser par!).
m = número x = 0
soma = 0
x = m?
soma = soma + (x+1) + (x+2)
x = x + 2
fim sim
não
início
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 16
6 Especificação de algoritmos e fluxo de controle
• fluxo de controle: seqüência, seleção e repetição
seqüência seleção repetição
instrução 1
instrução 2
instrução n
.
.
.
instrução 1
seleção
instrução 2.2 instrução 2.1
.
.
.
.
.
.
instrução ou grupo de intruções p
instrução p+1
.
.
.
seleção
.
.
.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 17
• todo algoritmo já concebido, em concepção e a ser concebido para o tratamento de problemas computáveis é passível de descrição com base em composições destes 3 módulos de fluxo de controle.
Teste condicional (ramificação, seleção)
• possibilidade de selecionar (optar) entre comandos exclusivos: IF condição THEN comando_1; ELSE comando_2;
Seleção de alternativas
• o valor atribuído a uma variável causará a seleção de um dentre um certo número de comandos opcionais:
CASE variável [variável = estado_1] THEN comando_1; [variável = estado_2] THEN comando_2; ⋅⋅⋅ [variável = estado_n] THEN comando_n;
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 18
Iteração
• repetição de blocos de comandos até que uma condição seja satisfeita:
REPEAT comando_1; comando_2; ⋅⋅⋅ comando_n; UNTIL condição
Recursão
• um algoritmo recursivo é um algoritmo que chama a si próprio.
• Exemplo clássico:
fatorial(N)
IF N=0,
THEN N=1; ELSE N=N*fatorial(N−1);
END
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 19
Modularidade
• divisão das etapas do algoritmo em módulos ou blocos funcionais.
• este é um dos objetivos da Engenharia de Software, responsável pela redução
de custos na implementação e manutenção de produtos de software, que
geralmente correspondem a projetos de grande escala, contando com o
envolvimento de várias equipes de profissionais. Embora as equipes interajam,
a maior parte do tempo devem operar de modo independente.
7 Resolução de um problema usando computador
• definir um algoritmo que resolva o problema (computabilidade);
• verificar a factibilidade da execução do algoritmo (complexidade);
• expressar o algoritmo em uma linguagem processável pelo computador;
• executar o programa no computador.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 20
Algoritmo
Programa dealto nível
programa emlinguagem
de máquina
Execução
concepção
Resolução conceitual do problema
Linguagem padrão (procedural ou não-procedural)
Linguagem específica do computador (procedural)
Hardware (circuitos e sinais físicos)
Decodificação (hardware ou firmware)
Tradução (compilador, interpretador)
programação
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 21
8 Computabilidade
• um problema é computável se existe um procedimento que o resolva em um
número finito de passos, ou seja, se é possível fornecer um algoritmo que leve
à sua solução.
• para mostrar que a solução de um dado problema não é computável, é
necessário mostrar que não existe nenhum algoritmo capaz de obtê-la.
• um dos mais surpreendentes resultados da teoria de algoritmos é que existem
problemas claramente definidos que não podem ser resolvidos em
computador, ou seja, não existe nenhum algoritmo de solução para eles.
• exemplos de problemas não-computáveis (dentro da própria computação):
# decidir se um programa é livre de laços infinitos para qualquer conjunto de dados de entrada;
# verificar a equivalência de dois algoritmos para qualquer conjunto de dados de entrada.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 22
9 Factibilidade computacional
• não basta assegurar que um algoritmo termine em um número finito de passos. É necessário que este número finito de passos possa ser executado em um tempo razoável e ocupe uma quantidade razoável de memória, levando à factibilidade computacional.
• a noção de razoabilidade está bem definida dentro da teoria de complexidade computacional, levando aos conceitos de complexidade temporal e espacial.
Todos os problemas
Problemas computáveis
Problemasfactíveis
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 23
10 Complexidade computacional: temporal e espacial
• a análise de complexidade computacional é fundamental no processo de
definição de algoritmos mais eficientes para a solução de um dado problema.
• apesar de parecer contraditório, mesmo com o aumento da velocidade e
capacidade de memória dos computadores, torna-se cada vez mais importante
desenvolver algoritmos mais eficientes. Isto se deve ao aumento continuado
do “tamanho” dos problemas a serem resolvidos, conduzindo a uma ampliação
sem precedentes da taxa de requisição por mais e mais capacidade de
processamento e memória.
• a complexidade computacional está relacionada ao desempenho de um
algoritmo em relação à utilização de recursos computacionais (tempo de
processamento e espaço de memória).
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 24
• como a requisição de processamento e memória pode ser função dos dados de
entrada, a complexidade vai estar associada ao pior caso.
• complexidade intrínseca: lida com as questões fundamentais na determinação
da dificuldade intrínseca de problemas computáveis, em termos de uso de
recursos computacionais (processamento e memória).
• complexidade algorítmica: está associada à complexidade dos algoritmos
empregados na solução de um problema computável. Podem existir
algoritmos com diferentes complexidades computacionais, mas desenvolvidos
para produzir a solução de um mesmo problema.
• um algoritmo ótimo é aquele cuja complexidade (complexidade algorítmica)
iguala a complexidade intrínseca do problema.
• o melhor algoritmo para a solução de um dado problema é aquele com a menor
complexidade (algorítmica), dentre os algoritmos já propostos.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 25
• deste modo, toda complexidade algorítmica (seja ela temporal ou espacial) vai
ser maior ou igual à respectiva complexidade intrínseca de um problema
computável.
complexidade crescente complexidade intrínseca
do problema (pode não ser conhecida)
complexidade de um algoritmo proposto para
resolver o problema
complexidade de um outro algoritmo proposto para
resolver o problema
melhor algoritmo já concebido
limite inferior para a complexidade algorítmica
(algoritmo ótimo)
• repare que a complexidade intrínseca de um problema computável pode ser
conhecida mesmo sem se conhecer um algoritmo ótimo para a solução.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 26
10.1 Problemas NP e NP-completos
• para se medir a complexidade de um algoritmo, é necessário definir
inicialmente o “tamanho” N do problema computável.
• exemplos de valores de N para alguns problemas: número de linhas de uma
matriz quadrada a ser invertida, comprimento de uma lista a ser pesquisada ou
ordenada, etc.
• é possível dizer que um problema é computacionalmente tratável se existe um
algoritmo de solução que, quando recebe uma entrada de tamanho N, encontra
a solução do problema executando, no pior caso, uma quantidade de instruções
simples que é um polinômio em N.
• vale ressaltar que esta definição não considera o esforço associado à
concepção do algoritmo a ser implementado.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 27
• além da complexidade temporal, existe a questão do uso de memória
(complexidade espacial), que deve obedecer a critérios análogos para garantir
a tratabilidade ou factibilidade computacional.
• por outro lado, uma das maneiras mais aceitas de provar que um problema é
computacionalmente intratável é demonstrar que ele é redutível a um problema
da classe NP-completo, conforme as definições a seguir:
# problema não-deterministicamente polinomial (NP): a melhor solução até
então conhecida está associada a algoritmos de complexidade exponencial
ou até superior. No entanto, não se sabe se existem algoritmos de solução
mais rápidos, capazes de resolver o problema em tempo polinomial;
# problema não-deterministicamente polinomial completo (NP-completo): é
um problema representante de uma classe de problemas NP tal que todo
problema NP da classe pode ser redutível a ele em tempo polinomial.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 28
Assim, um algoritmo para um problema NP-completo é universal, no
sentido de poder ser utilizado como uma subrotina para qualquer problema
NP de sua classe.
• para mostrar que um novo problema é NP-completo, é suficiente mostrar que
ele é um problema NP e que um problema qualquer já sabido ser NP-completo
é redutível a ele em tempo polinomial.
• dado um candidato à solução de um problema NP, a comprovação de que ele é
realmente uma solução ocorre em tempo polinomial. Portanto, o termo não-
determinístico aqui não implica aleatoriedade, mas apenas a ausência de regras
que tomem a própria solução como o candidato a ser testado.
• um problema A é dito ser redutível a um problema B se o problema A puder ser
resolvido usando um algoritmo que resolve o problema B.
• quando A é redutível a B em tempo polinomial, pode ocorrer o seguinte:
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 29
# se existir um algoritmo em tempo polinomial para resolver o problema B, então o problema A também terá um algoritmo em tempo polinomial;
# se for comprovado que o problema A não pode ser resolvido em tempo polinomial, então o problema B também não poderá ser resolvido em tempo polinomial.
• logo, se um algoritmo de complexidade polinomial puder ser encontrado como
solução para um problema NP-completo de uma dada classe, então todos os
problemas NP desta classe deixam de ser NP e passam a ser problemas com
complexidade polinomial.
• por outro lado, se for provado que um dos problemas NP de uma dada classe
requer um algoritmo de solução que apresente complexidade maior que a
polinomial (ou seja, tem complexidade intrínseca maior que a polinomial),
então todos os problemas desta classe irão requerer ao menos esta mesma
complexidade, deixando de ser problemas NP.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 30
• o conceito de NP-completude foi formulado por COOK (1971), que demonstrou
que a verificação da veracidade de uma fórmula lógica é um problema NP-
completo. KARP (1972) estendeu o conjunto de problemas NP, identificando
outros 20 problemas de interesse prático. Hoje, milhares de problemas já
foram identificados como sendo NP (GAREY & JOHNSON, 1979).
complexidade crescente complexidade intrínseca do
problema é desconhecida (não se sabe se é polinomial
ou maior que polinomial)
complexidade de um algoritmo proposto para
resolver o problema (maior que polinomial)
complexidade de um outro algoritmo proposto para
resolver o problema (maior que polinomial)
?
Figura 5: Complexidades intrínseca e algorítmica para problemas NP
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 31
NP
NP-completo
NP
NP NP
NP NP
NP
NP NP
NP-completo
NP-completo
NP-completo
NP-completo
NP-completo
NP-completo
NP-completo
Classe 1 Classe 2
Figura 6: Problemas NP e classes de problemas NP-completos (as setas indicam ‘redutível a, em tempo polinomial’)
• para classificar qualquer um dos problemas NP ainda não classificados, basta
reduzir um problema qualquer dentre os NP-completos ao problema NP em
questão, em tempo polinomial.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 32
10.2 Quantificando a razoabilidade temporal e espacial
• seja N uma grandeza que expressa o tamanho de um problema e c uma
constante (que pode assumir um valor não negativo arbitrário). Pode-se então
definir, em relação ao tempo de máquina e/ou espaço de memória requerido
pelos respectivos algoritmos de solução:
# problemas computacionalmente tratáveis: o melhor algoritmo de solução apresenta complexidade polinomial O(Nc) ou menor, como por exemplo O(log2N);
# problemas computacionalmente intratáveis: o melhor algoritmo de solução apresenta complexidade exponencial O(cN), fatorial O(N!), ou até maior. São tratáveis apenas para valores pequenos de N.
• repare que, dentre os problemas computacionalmente intratáveis, encontram-
se os problemas não-deterministicamente polinomiais (NP) e problemas já
sabidos terem complexidade intrínseca maior que polinomial, ou seja,
problemas não-polinomiais.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 33
• considerando que existe um tempo específico para se executar uma operação
em um computador digital, a tabela a seguir mostra como evoluem os tempos
de execução hipotéticos (em segundos) para problemas com diferentes
complexidades computacionais.
N O(log2N) O(N) O(N2) O(2N)
10 0,003322 0,01 0,1 1,024
100 0,006644 0,1 10 1,2677×1027
1000 0,009966 1 103 1,0715×10301
10000 0,013288 10 105 −
100000 0,016610 100 107 −
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 34
• para qualquer c > 1, O(N!) > O(cN) > O(Nc) para valores de N suficientemente
elevados. Ou seja, com o aumento do tamanho dos problemas, algoritmos com
complexidade fatorial se tornam seguramente mais difíceis de resolver em
computador que algoritmos com complexidade exponencial, enquanto estes
últimos se tornam mais difíceis que algoritmos com complexidade polinomial.
• a notação big-Oh indica complexidade assintótica, de modo que algoritmos
com requisição de tempo e/ou memória, por exemplo, na forma
7N3+4N+log3N, são de complexidade O(N3).
10.3 O produto de duas matrizes N × N
• problema com complexidade polinomial • clássico: O(N3); atual O(N2,376); limite inferior O(N2) • clássico (exemplo para N = 2):
⋅+⋅⋅+⋅⋅+⋅⋅+⋅
=
⋅
=⋅2222122121221121
2212121121121111
2221
1211
2221
1211
qpqpqpqp
qpqpqpqp
pp
ppQP
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 35
10.4 O problema do caixeiro viajante
• problema de decidibilidade (NP-completo): dados um conjunto de cidades, a
matriz de custos de se viajar de uma cidade a outra e uma constante X, existe
uma rota de custo inferior a X que parta da cidade de origem, passe por todas
as demais cidades uma única vez e retorne em seguida à cidade de origem?
• problema de otimização associado (NP-difícil): dados um conjunto de cidades
e a matriz de custos de se viajar de uma cidade a outra, qual é a rota de custo
mínimo dentre todas as que partem da cidade de origem, passam por todas as
demais cidades uma única vez e retornam em seguida à cidade de origem?
• exemplos de casos práticos: onde posicionar depósitos para distribuição de
produtos, como organizar os componentes em um chip, como maximizar a
eficiência de empresas que trabalham com expedição de produtos, etc.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 36
Problema do Caixeiro Viajante (Traveling Salesman Problem)
0 20 40 60 80 1000
10
20
30
40
50
60
70
80
90
100
0 20 40 60 80 1000
10
20
30
40
50
60
70
80
90
100
0 20 40 60 80 1000
10
20
30
40
50
60
70
80
90
100
0 20 40 60 80 1000
10
20
30
40
50
60
70
80
90
100
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 37
10.5 O problema da mochila (knapsack problem)
• problema de decidibilidade (NP-completo): dados uma lista de números e o
tamanho de uma mochila, existe algum subconjunto de números da lista cuja
soma produza o tamanho da mochila?
Exemplo 1: Lista de Números: 4 7 13 18 25 32 42 49 Tamanho da mochila: 89 Solução: Sim. O subconjunto é dado por: 4 18 25 42
Exemplo 2: Lista de Números: 4 7 13 18 25 32 42 49 Tamanho da mochila: 90 Solução: Não.
• problema de otimização associado (NP-difícil): dados uma lista de números e
o tamanho de uma mochila, encontre o subconjunto de números da lista cuja
soma é máxima, sob a condição de não exceder o tamanho da mochila.
• exemplo de casos práticos: alocação de recursos a projetos de pesquisa e
desenvolvimento; aquisição de produtos com limite de crédito, etc.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 38
11 O que fazer frente a um problema NP-completo
• existem abordagens alternativas:
1. quando os problemas práticos são de tamanho pequeno: desenvolver um
algoritmo que seja suficientemente rápido para problemas de tamanho
pequeno, embora possa se tornar muito ineficiente com o aumento do tamanho
do problema.
2. quando existem casos especiais de importância prática: desenvolver um
algoritmo rápido, dedicado à solução de casos especiais do problema, mas que
podem não resolver o problema em sua formulação genérica.
3. quando algumas instâncias do problema apresentam características peculiares
que podem ser exploradas: desenvolver um algoritmo capaz de resolver
rapidamente instâncias do problema que apresentam estas peculiaridades,
embora possa ser ineficiente na ausência delas.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 39
4. quando o problema é de otimização: desenvolver um algoritmo de
aproximação que sempre apresenta um execução rápida, mas que produz uma
solução que não necessariamente é a ótima. Em alguns casos, é possível obter
um limitante de pior caso, levando aos chamados algoritmos de aproximação
com custo garantido.
5. quando nenhuma das hipóteses anteriores for válida: desistir do tratamento do
problema.
• em resumo, a NP-completude elimina a possibilidade de se obter um algorit-
mo completamente satisfatório. Uma vez frente a um problema NP-completo,
é necessário direcionar esforços no sentido de objetivos mais factíveis.
• as estratégias de tratamento que vêm recebendo mais atenção nos últimos anos
estão vinculadas à alternativa 4, ou seja, aos algoritmos de aproximação na
forma de meta-heurísticas (GLOVER & KOCHENBERGER, 2003)
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 40
• a linha de argumentação acima está voltada para a necessidade de viabilizar a
solução de problemas práticos. No entanto, existem aplicações dentro da
computação que buscam justamente explorar a dificuldade algorítmica de
certos problemas NP-completos, no sentido de que quanto mais difícil for
chegar à solução, melhor.
• como um exemplo deste tipo de aplicação, podem ser mencionadas as
estratégias de criptografia que vinculam a quebra de código a algoritmos NP-
completos, de modo que a quebra de código se torna uma tarefa infactível.
• na verdade, muitos progressos realizados nos primórdios da computação
estiveram associados a mecanismos de criptografia e quebra de código
criptografado, destacando-se aqui as contribuições de Alan Turing,
considerado um dos pais da computação juntamente com von Neumann.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 41
11.1 O problema do quadrado mágico
• há muitos séculos atrás, os chineses já haviam demonstrado que, para
quadrados de qualquer dimensão N, é possível encontrar uma permutação dos
inteiros de 1 a N2, nos campos do quadrado, de modo a garantir que as
seguintes somas sejam idênticas:
! soma dos elementos de uma linha qualquer;
! soma dos elementos de uma diagonal qualquer;
! soma dos elementos de uma coluna qualquer.
Exemplo: Quadrado 5 × 5 (todas as somas produzem 65)
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 42
• na literatura, é possível encontrar vários algoritmos capazes de resolver casos especiais
de quadrados mágicos, embora nenhum destes algoritmos valha para dimensões
genéricas. Todos estes algoritmos engenhosos, mas específicos, são exemplos práticos
da alternativa 2 apresentada acima.
• o único algoritmo exato e genérico o suficiente para valer para qualquer dimensão N é o
seguinte: teste todas as permutações possíveis, e fique com aquela que produza soma
idênticas (são duas possibilidades, visto que o transposto da solução também é solução).
• a complexidade algorítmica deste algoritmo exato é O([N2]!), levando à intratabilidade
para valores suficientemente elevados de N.
• a solução apresentada a seguir para o problema do quadrado mágico com dimensão
N = 30 foi obtida por uma meta-heurística associada à computação evolutiva
(RECHENBERG, 1994). Todas as somas produzem 13.515.
• note que, embora não garantam obter a solução, os algoritmos de aproximação podem
levar à solução de problemas estupidamente intratáveis por parte de algoritmos exatos.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 43
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 44
12 Cálculo de complexidade computacional temporal
• dado um problema computável, o cálculo de sua complexidade inerente, quando possível, se dá por intermédio de processos indutivos;
• dado um algoritmo de solução para um problema computável, sua complexidade algorítmica é calculada pela detecção de etapas do processamento que correspondem a “gargalos” do processo de execução.
Exemplo 1: a xii
i
N−
=
+
∑ 1
1
1
BEGIN FOR i=1 to N DO BEGIN potencia_de_x = 1.0; N FOR j=1 to i DO potencia_de_x = potencia_de_x * x; N(N-1)/2 ← END term[i] = a[i+1]* potencia_de_x; N END soma = a[1]; FOR i=1 to N DO soma = soma+term[i]; N END
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 45
Busca linear em uma lista não-ordenada de tamanho N
• melhor caso: 1 teste
• média:
Seja pi a probabilidade de encontrar o elemento procurado após testar i
(i=1,...,N) elementos da lista. Como a probabilidade de um elemento qualquer da
lista ser o elemento procurado é dada por N
1 , então N
ipi = . Isto implica que o
número médio de elementos testados vai ser dado pela somatória das
probabilidades de se testar cada elemento da lista, usando busca linear. Isto
implica que: média = 2
1
1
+=∑=
N
N
iN
i
testes.
• pior caso: N testes.
• conclui-se então que a complexidade do algoritmo de solução é dada por O(N1).
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 46
Busca binária em uma lista ordenada de tamanho N
• estratégia (algoritmo):
1. fazer lista original ser a lista em vigor;
2. comparar o número procurado com o elemento central da lista em vigor;
3. Se for igual, FIM.
4. Se for menor, lista em vigor passa a ser a metade inferior da lista.
5. Se for maior, lista em vigor passa a ser a metade superior da lista.
6. Retorne ao item 2.
• se k é o número de comparações, então é necessário que NN k
k≥⇒≤ 21
2.
• isolando-se k, resulta: NkNk222 loglog2log ≥⇒≥ .
• assim, o número máximo de comparações vai ser dado por N2log1+ .
• conclui-se então que a complexidade do algoritmo de solução é dada por O( N2log ).
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 47
0 2 4 6 8 100
1
2
3
4
5
6
7
8
9
10
N
O(N
1) e O(log2(N))
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 48
Multiplicação de dois números de N dígitos, onde N é potência de 2
• hipótese: o produto é uma operação bem mais custosa (computacionalmente)
que a soma.
• algoritmo clássico: complexidade O(N2)
• algoritmo alternativo (a, b, c, d são números com 2N dígitos):
caxN
+= 210 dbyN
+= 210
( ) cdbcadabxyNN +++= 21010
O problema foi reduzido ao cálculo de ab, cd, e
( ) ( )( ) cdabdbcabcad −−++=+
Sejam:
$ kN: tempo para calcular as somas necessárias, com k > 0 e constante;
$ T(N): tempo para calcular o produto de dois números com n dígitos.
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 49
$ logo:
kNN
TNT +
≅
23)(
243
2
Nk
NT
NT +
≅
483
4
Nk
NT
NT +
≅
...
Fazendo as substituições em T(N) resulta:
585.13log2log
232
22
3312
3
2
3...
2
3
2
3
2
3
233
2
3
4833
2
3
23
2433
23)(
22
kNkNkN
kNkNkNN
TkNkNN
kn
T
kNkNN
TkNN
kN
TkNN
TNT
N
≅≅
++
++
≅
++
+
=++
+
≅
++
=+
+
≅+
≅
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 50
• conclui-se então que a complexidade do algoritmo de solução é dada por
O(N1.585).
• exemplo:
79 7 × 4 = 28
× 43 9 × 3 = 27
237 (7+9)*(4+3) − 7*4 + 9*3 = 57
+ 316
3397 28
57
27 +
3397
EA869 – Prof. Von Zuben DCA/FEEC/Unicamp
Tópico 1 – Introdução a Sistemas de Computação Digital 51
13 Referências
COOK, S.A. “The Complexity of Theorem-Proving Procedures”, Proc. Third ACM Symposium on Theory of Computing, 151-158, 1971. DALTRINI, B.M., JINO, M. & MAGALHÃES, L.P. “Introdução a Sistemas de Computação Digital”, Makron Books do Brasil Editora Ltda., 1999. GAREY, M.R. & JOHNSON, D. “Computers and Intractability: A Guide to the Theory of NP-Completeness”, Freeman and Co., 1979. GLOVER, F. & KOCHENBERGER, G.A. “Handbook of Metaheuristics”, Kluwer Academic Publishers, 2003. KARP, R.M. “Reducibility Among Combinatorial Problems”, in R.E. Miller & J.W. Thatcher (eds.) Complexity of Computer Computations, pp. 85-104, Plenum Press, 1972. LAWER, E.L., LENSTRA, J.K., RINNOOY KAN, A.H.G. & SHMOYS, D.B. “The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization”, Wiley-Interscience, 1985. LEWIS, H.R. & PAPADIMITRIOU, C.H. “Elements of the Theory of Computation”, Prentice-Hall, 1998. PAPADIMITRIOU, C.H. & STEIGLITZ, K. “Combinatorial Optimization: Algorithms and Complexity”, Prentice-Hall, 1982. RALSTON, A. & REILLY, E.D. “Encyclopedia of Computer Science”, Third Edition, IEEE Press, 1993. RECHENBERG, I. “Evolution Strategy”, in Zurada, J.M., Marks II, R.J., Robinson, C.J. (eds.) Computational Intelligence: Imitating Life, IEEE Press, pp. 147-159, 1994.