Ferramentas para Síntese Conteúdo: primeira parte ...johann/cmp241/aula06.problems.algorithms.ppt.pdf · CMP241 - Ferramentas para Síntese Automática de CIs - Reis/Johann - UFRGS

1

Aula 06 : Slide 1CMP241 - Ferramentas para Síntese Automática de CIs - Reis/Johann - UFRGS 2009/1

Ferramentas para SínteseAutomática de Circuitos IntegradosProfs: Ricardo Reis e Marcelo Johann

ComplexidadeComputabilidade e TratabilidadeAlgoritmos e Abordagens para

Otimização de Problemas


Conteúdo: primeira parte

Teoria: Computabilidade Prática: Tratabilidade Medidas de Complexidade Crescimento de Funções Redução de Problemas Classes de Problemas Problemas de Decisão e Otimização


Teoria da Computabilidade Nem todo problema bem formulado pode ser

computado por um algoritmoGödel’s incompleteness theorem

Existem estruturas de conjuntos para asquais é provado que não pode haver umalgoritmo que sempre termine com aresposta.

MAS isso somente vale para conjuntosinfinitos


Medidas de ComplexidadeNotação Assintótica

Função O: f(n) = O(g(n)) se f é limitada acima por gassintoticamente, com fator constante

Função Ω: f(n) = Ω(g(n)) se f é limitada abaixo por gassintoticamente, com fator constante

Função Θ: f(n) = Θ(g(n)) se f é limitada abaixo e acimapor g assintoticamente, com fatores constantes


Crescimento de funções

> 10500> 105009 * 101572 * 10183 * 1067202n!

> 105001030110301061036442n

10181091068 * 1031032168n3

10121061044 * 102102364n2

6 * 1063 * 1032 * 10226104.70.6n log10 n

3 * 1063 * 1033 * 10260301863n

106103102201062n

n = 106n = 103n = 102n = 20n = 10n = 6n = 2function

too small: not a concern do need a computer!

Bad

!Po

lyno

mia

l


Complexity vs SpeedComplexity vs Speed

Both are important in practice

Complexity When the problem’s instance size increases

Speed When the problem’s instance size is

bounded

2


Redução de ProblemasProblema A

Problema BAula 06 : Slide 8CMP241 - Ferramentas para Síntese Automática de CIs - Reis/Johann - UFRGS 2009/1

Classes de Problemas

Classe P Determinístico Polinomial



Classe NP Não-determinístico Polinomial



Classe NP-Completo Problemas relacionados Qualquer um pode ser reduzido ao outro Se houver solução para um, há para todos “são o mesmo”



Classe NP-Difícil Problemas pelo menos tão difíceis quanto os

mais difíceis da classe NP Todos NP se reduzem a NP-Hard


Relacionamento das classes

Venn Diagram

3


Relacionamento das Classes

Wikipedia

http://en.wikipedia.org/wiki/Complexity_classhttp://en.wikipedia.org/wiki/NP-hard

Complexity Zoo


Problemas de Decisão

Resposta deve ser SIM ou NÃO


Problemas de Pesquisa

Encontrar uma entrada para a qual aresposta é SIM


Problemas de Otimização

Há um mérito (número) associado à cadapossível valor de entrada: encontrar o menorou maior valor


Satisfiability

The Boolean SATisfiability game: http://www.cril.univ-

artois.fr/~roussel/satgame/satgame.php?level=1&lang=eng


Bad news:Most CAD problems are NP-complete or NP-Hard

So, How do we solve them???

SEGUNDA PARTE…

4


Conteúdo: segunda parte

Otimização Convexa (MODELO)Pesq. Oper., Progr. linear, quadrática, geométrica

Mecanismos de BuscaGuloso, Backtrack, Local, Exaustiva, Branch-and-bound,Programação Dinâmica, Tabu, GRASP

Algoritmos Randomizados e Meta-HeurísticasSA, TA, GA, MA, AC


Problem Problem and Solutionand Solution SpaceSpace


How How is is this cost functionthis cost function??


Modelos lineares


Modelos lineares

X1 é o espaço de soluções, X2 é o valor a otimizar…Mas… Só existe uma variável no problema?


Funções multi-dimensionais

5


Modelos Quadráticos


Programação Geométrica

Tutorial DATE 2005 Stephen Boyd

http://www.stanford.edu/~boyd/papers/date05.htmlhttp://www.stanford.edu/~boyd/papers/gp_tutorial.html


Algoritmos Gulosos (Greedy)

Tomam cada decisão conforme a melhoropção local

Percorrem da raiz a uma folha diretamente Geralmente não encontram o mínimo global, Pois os problemas não possuem em geral

decisões independentes entre sí


Backtracking

Consiste em desfazer decisões tomadas etomar novas.

Equivale a percorrer a árvore emprofundidade (DFS)


BUSCA LOCAL

Muito semelhante a backtracking Consiste simplesmente em partir de uma

solução e ir verificando as soluções“vizinhas”, especialmente as de menor custo

Mas pode ser multidimensional, baseado emalterações

Mas objetivo principal é visitar os vizinhosmais “baratos”


Busca Exaustiva

É o Resultado de uma backtracking completo,ou DFS completo

Pode ser empregado, lembrem, quando oproblema é limitado (bounded) - entradastêm tamanho pequeno

6


Branch-and-Bound

Consiste em avaliar a melhor solução de umasub-árvore e podá-la caso uma soluçãomelhor já tenha sido encontrada

Igualmente, no contexto de backtracking

Uma variante interessante é o aprendizadodinâmico. Ex: SAT


Programação Dinâmica Quando o problema possui a propriedade de

que toda a solução ótima somente pode sercomposta por trechos ótimos (ex: caminhos)

Mas, em situações intermediárias, não sesabe quais caminhos alternativos ganham

Progr. Dinâmica faz uma coleção de soluçõesparciais e as filtra assim que pode compará-las. Exemplos: Saco do ladrão, buffers


Randomizados e Meta-Heurísticas

Randomized Algorithms

SA - Simulated Annealing TA - Threshold Accepting GA - Genetic Algorithm MA - Memetic Algorithm AC - Ant Colony


Three basic functions: Temperature Schedule (above), Cost(wire length) and Perturbation (changes in current solution).

PerturbationCost

Reject / Accept

thanks to Renato Hentschke

AnnealingAnnealing


In a In a NutshellNutshell

While (temp*=0.99 > finalvalue) make_perturbation(); if ( newcost < actualcost || rand() < e^(-deltacost / temp) ) accept(); else reject();

Simulated annealing does:


Threshold AcceptingThreshold Accepting

While (threshold*=0.99 > finalvalue) make_perturbation(); if ( newcost < actualcost + threshold ) accept(); else reject();

Threshold Accepting is solely:

It is easier and more efficientbut Why???

7


Threshold AcceptingThreshold Accepting1) Integrating a constant distribution leads to the same normal distribution of perturbations

2) It is easier to advance:


Threshold AcceptingThreshold Accepting

Results 1 - 10 of about 1,870,000 for"simulated annealing". (0.26 seconds)

Results 1 - 10 of about 28,000 for"threshold accepting". (0.18 seconds)

Results 1 - 10 of about 145 for"bachelor acceptance". (0.26 seconds)


Understanding Understanding S.A. S.A. and and T.A.T.A.S.A. and T.A. are random walks in the

space stateThe more you walk, more likely you end upclose to the optimal…

Requires some tuning and expertiseAppletshttp://www-lehre.inf.uos.de/~sborggre/SimulatedAnnealing.html

http://www.duke.edu/~jmu2/color/gc.html


Algoritmos GenéticosOu Evolução Simulada

População Qualidade do Indivíduo define sobrevivência Cruzamento Mutação Elitismo e Importância da Morte

Memória


Algoritmos Meméticos

Os individuos aprendem durante a vida A aprendizagem é transmitida em DNA

mitocondrial


Próxima aula

ParticionamentoPosicionamentoFloorplanning

Documents

Ferramentas para Síntese Conteúdo: primeira parte ...johann/cmp241/aula06.problems.algorithms.ppt.pdf · CMP241 - Ferramentas para Síntese Automática de CIs - Reis/Johann - UFRGS