View
5
Download
0
Category
Preview:
Citation preview
Pontifícia Universidade Católica do Rio Grande do SulInstituto de Informática (II-PUCRS)Grupo de Apoio ao Projeto de Hardware - GAPH
Projeto Lógico Automatizado deSistemas Digitais Seqüenciais 2 - Fundamentação Teórica
Ney Laert Vilar Calazans*
Julho, 1998
*Com o apoio do Conselho Nacional de Desenvolvimento Científico eTecnológico (CNPq) e da Fundação de Amparo à Pesquisa do Estado do RioGrande do Sul (FAPERGS).
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
Sumário
H 1 - Estruturas Algébricas
H 2 - Grafos
H 3 - Funções
H 4 - Representações de Funções Discretas
H 5 - Análise de Complexidade de Algoritmos
H 6 - Problemas Formais
Escola98
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
1 - Estruturas Algébricas - conceitos básicos
H Conjuntos:– cardinalidade, elementos, conjunto potência, ∅ ;
– relações entre elementos ou conjuntos e conjuntos:» ∈, ∉, ⊃, ⊆, ∩, ∪, etc.
H Produto Cartesiano: S×T: (s,t) | s∈ S, t∈ T;– conceito expansível para S×T×U…
H Faltam operadores para expressar:– ordenamento, equivalência/compatibilidade.
H Problema: usar conjuntos para expressar isto.
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
1 - Estruturas Algébricas - exemplo e definição
H Exemplo: Naturais (N) eInteiros (Z)– 3 ∈ N, -25 ∉ N, 6/3 ∈ N;
– 3 ∈ Z, -25 ∈ Z, 1/3 ∉ Z;
– Z ⊄ N, N ⊂ Z;
H Contudo, como expressarque 25≤ 39, ou então que -25 ≤ 25?
H Solução: associar novasrelações e conseqüentesoperadores aos conjuntos!
H Estrutura Algébrica -coleção de conjuntos erelações n-árias sobreestes;
H Notação: <S,T,…,r,δ,...>;
H Base - relação binária.
N
Z
0 1 2 3 4 5 6
-3-2-1 0 1 2 3
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
1 - Estruturas Algébricas - relações binárias
H Tripla <S,T,r>, onde S é domínio, T é ocodomínio e r é o grafo, r ⊆ S×T;
H Imagem r(s) de elemento do domínio é t | t∈ T,(s,t)∈ r, extensível a qquer subconjunto de S.
H Estrutura do grafo determina tipos de relação:– completamente especificada - r(s)≠∅ , para todo s;
– sobre - r(S)=T (também dita cobertura de T);– funcional - para todo s ∈ S, |r(s)|≤1;
– um-para-um - para todo s≠s’, r(s)∩r(s’)=∅ ;
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
1 - Relações binárias - exemplos
sobre
funcional um-para-um
completamente especificada
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
1 - Relações binárias - partição
H Combinações depropriedades ->importantes relações;
H Partição: uma relaçãobinária sobre e um-para-um;
H Partição: coberturaonde blocos (classes)disjuntos dois a dois.
partição
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
1 - Relações Binárias sobre um Conjunto
H Aquelas onde S=T;
H Propriedades adicionais -> novos tipos:– reflexiva - r(s) ⊆ s, para todo s ∈ S;
– simétrica - se r(s) ⊆ t, então r(t) ⊆ s, paraqualquer s e qualquer t;
– antissimétrica - se para algum s e t, r(s) ⊆ t, etambém r(t) ⊆ s, então s=t;
– transitiva - para todo s, t, e u em S, se r(s) ⊆ t, er(t) ⊆ u, então r(s) ⊆ u;
H Como antes, propriedades são ortogonais!
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
1 - Relações binárias sobre conjunto- exemplos
reflexiva simétrica
antissimétrica transitiva
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
1 - Relações binárias - relações de ordem
H Uma relação bináriareflexiva e transitiva érelação de pré-ordem;
H Relação de pré-ordemantissimétrica é relaçãode ordem;
H Se para todo s t, umdentre (s,t) e (t,s) fazparte da relação deordem, ordem é total,senão, é parcial.
relação de ordem
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
1 - Relações de ordem - diagrama de Hasse
H Forma gráfica ilustrando relação de ordem;
H Grafo dirigido, com menor número de arestas;H Relação de ordem representada: < S2, ≤ >;
H Vértices - elementos de S, Arestas - relação.a,b,c
a,b a,c b,c
a b c
Ø
30
6 10 15
2 3 5
1
3
2
1
Exemplos
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
Sumário
√ 1 - Estruturas Algébricas
H 2 - Grafos
H 3 - Funções
H 4 - Representações de Funções Discretas
H 5 - Análise de Complexidade de Algoritmos
H 6 - Problemas Formais
Escola98
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
2 - Grafos - conceitos básicos
H Formalmente, G=<V,E>, com conjunto V devértices e relação binária E sobre V, E=<V2,r>,elementos de r são arestas;
H Dependendo de E, grafos podem ser dirigidos,não-dirigidos, ter laços ou não, etc;
H Conceitos importantes: incidência de arestas,adjacência entre vértices, grau de um vértice,completude, caminho entre vértices, ciclicidade,conexidade, decomposição em subgrafos,isomorfismo, planaridade, árvores, etc, etc.
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
2 - Grafos - exemplos
c
fe
b
d
agrafo não-dirigido
c
fe
b
d
a
grafo dirigido
c
f
ba
grafo dirigido
subgrafo de
três componentesconexos
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
Sumário
√ 1 - Estruturas Algébricas
√ 2 - Grafos
H 3 - Funções
H 4 - Representações de Funções Discretas
H 5 - Análise de Complexidade de Algoritmos
H 6 - Problemas Formais
Escola98
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
3 - Funções
H aqui - funções são relações binárias!
H função parcial - relação binária funcional;
H função completa - relação binária funcional ecompletamente especificada;
H função no presente contexto = função parcial.
função parcial função completa não é função
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
3 - Funções especiais
H injeção - função um-para-um;
H sobrejeção - função sobre;
H bijeção - função sobre e um-para-um
H função discreta - domínio e codomínio finitos.
injeção bijeçãosobrejeção
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
Sumário
√ 1 - Estruturas Algébricas
√ 2 - Grafos
√ 3 - Funções
H 4 - Representações de Funções Discretas
H 5 - Análise de Complexidade de Algoritmos
H 6 - Problemas Formais
Escola98
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
4 - Representações de Funções discretas
H Uma forma simples - vetor valor– ordena-se elementos do domínio e usa-se vetor de
imagens, indexado pelos elementos do domínio;» Exemplo: E de duas entradas - ordem de enumeração
natural após conversão de base 2 para base 10.
» Solução: [0 0 0 1]
H Outras formas - tabela verdade, mapas deKarnaugh, soma de mintermos, produto demaxtermos, diagramas de decisão binária,diagramas de Hasse.
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
4 - Tabelas Cúbicas para Funções discretas
H Introdução via exemplo:– Sejam I1=a,b,c, I2=d,e, O1=g,h e O2=i,j,k
conjuntos. Seja S= I1× I2 e seja F= f1,f2 um conjunto defunções discretas onde f1:S--> O1 e f2:S--> O2.
H As tabelas cúbicas para estas funções podem ser:
1 2 3Cj Dj Cj Dj Cj Dj
I1 I2 f1 f2 I1 I2 f1 f2 I1 I2 f1 f2
a - h ∅ a,b d h k a,b,c d h k- d ∅ k - d ∅ k b,c e g j
a e ∅ i a e h i a e h ib d h ∅ b e g -b e g - c e g jc e g j
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
4 - Diagramas de Decisão Binária
H Existem há muito tempo, mas desde 1986 muitoexploradas -> Bryant introduz forma canônica;
H Forma muito compacta para manipular funções econjuntos.
Índice=2
Índice=1
Índice=3
0 0 1 0 1 1 1 1
a
b bb
c c c c
0 1
0 1 0 1
0 1 0 1 0 1 0 1
0 1
b
a
c
0
1
0
1
1 0
0 1
c
a a
b
0 1
01 0
1
01
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
Sumário
√ 1 - Estruturas Algébricas
√ 2 - Grafos
√ 3 - Funções
√ 4 - Representações de Funções Discretas
H 5 - Análise de Complexidade de Algoritmos
H 6 - Problemas Formais
Escola98
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
5 - Análise de Complexidade de Algoritmos
H Dados dois algoritmos A e B para resolverum problema, qual deles é melhor?– principais critérios: tempo, armazenamento;
H Escalabilidade - “medida da capacidade detécnica p/ lidar com instâncias de tamanhocrescente de problema”;
H Lembrar-se da lei de Moore! Exemplo:– em 1995, unidade de controle P6: 105 portas;
– em 2000, Pn: 108 portas!
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
5 - Análise de Complexidade de Algoritmos
H Definições importantes:– problema, algoritmo e tamanho da entrada (te);
H Em geral, determinação de função decrescimento de uso de recursos é muito difícil,senão inviável!
H Solução para projetar e analisar algoritmos:– conjunto de funções conhecidas e composição que
aproxima crescimento do algoritmo;
– classes de complexidade de problemas;
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
5 - Crescimento Assintótico de Funções
H Notações assintóticas Ο,Ω, e Θ: limites superior,inferior e estrito (duplo);
H Algoritmo f(n) é Ο(g(n)),ou f(n)= Ο(g(n)) se– 0 ≤ f(n) ≤ c1g(n), para
todo n ≤ n0;
H Restantes é análogo;
H O é conjunto de funções.n1
Consumo deRecursos
Tamanho daEntrada
c2g(n)
c1g(n)
f(n)
n0n2
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
5 - Crescimento de Funções - operações
H Tabela dá conjunto de funções de base;
H Constantes normalmente pequenas;
H Coeficientes constantes pequenos;
H Linha divisória de complexidade - polinômios!
log n n n log n n2 n3 2n 3n n!1 2 2 4 8 4 9 22 4 8 16 64 16 81 243 8 24 64 512 256 6560 403204 16 64 256 4096 65536 ~107 ~1013
5 32 160 1024 32768 ~109 ~1015 ~1035
10 1024 10240 ~106 ~109 ~10308 ~10488 ~102639
20 ~106 ~107 ~1012 ~1018 ? ? ?
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
5 - Crescimento de Funções - exemplo temporal
H Supondo uma máquina de 100MIPs dedesempenho coeficientes constantes unitários;
H Para instâncias de entradas com três ordens degrandeza de diferença;
H Lei de Moore - em 15 anos, algoritmo cúbicolevaria 4 meses para executar sobre instância 106.
n f(n)=n f(n)= n log n f(n)=n2 f(n)=n3 f(n)=2n
103 10µs 100µs 10ms 10s ~10285 anos106 10ms 0,2s 2,7h 317anos ?
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
5 - Classes de Complexidade de Problemas
H Problema abstrato: relação binária do conjuntode instâncias sobre o conjunto de soluçõesQ=<I,S,p>;
H Problema de decisão: solução é sim ou não;
H Problema de otimização: com valor amaximizar ou a minimizar;
H Problema concreto: resulta de codificar embinário o domínio de um problema de decisãoabstrato.
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
5 - Classes de Complexidade de Problemas
H Classe NPC: subconjunto de problemas em NPtal que qualquer elemento de NP pode serreduzido a qualquer elemento de NPC;
H Classe NPH: conjunto de problemas de decisãoconcretos tais que qualquer problema da classeNP pode ser reduzido a qualquer elemento seu;
H Obviamente, NPC ⊆ NPH.
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
5 - Classes de Complexidade de Problemas
H Relação suposta como a mais provável entre asclasses de complexidade acima:
Problemas Concretos
P
NP
NPC
NPH
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
Sumário
√ 1 - Estruturas Algébricas
√ 2 - Grafos
√ 3 - Funções
√ 4 - Representações de Funções Discretas
√ 5 - Análise de Complexidade de Algoritmos
H 6 - Problemas Formais
Escola98
http:/ /www.inf.pucrs.br/~gaph gaph@kri ti.i nf.pucrs.br
6 - Problemas Formais
H Dois exemplos, caminhos mais curto e maislongo entre dois vértices em um grafo:
H Caminho_mais_curto (_mais_longo análogo):– Instância: grafo não-dirigido G, peso natural l(e)
para cada aresta e, dois vértices a,b e natural B.
– Questão: existe um caminho simples de a para bem G que tem comprimento total B ou menos?
H Problemas concretos associados: Pertence àclasse P (mais_curto) e NPC (mais_longo)!
Recommended