advertisement

Algoritmo clique maximo - Analise de Algoritmos

50 %
50 %
advertisement
Information about Algoritmo clique maximo - Analise de Algoritmos
Technology

Published on March 8, 2014

Author: adilmar

Source: slideshare.net

Description

Algoritmo clique maximo - Analise de Algoritmos, definição, exemplos e teoria e razão de aproximação.
advertisement

Algoritmo Clique Máximo

O que é uma Clique? •Uma clique de um grafo G é um subgrafo completo de G.

O que é uma Clique Máxima? •Uma clique máxima é uma clique com a maior quantidade de vértices possível.

O Problema da Clique Máxima •O problema da Clique Máxima é encontrar, a partir de um grafo G, a clique de maior tamanho. •O tamanho (número de vértices) da maior clique de G é chamado número de clique, ω(G).

Dificuldades do Problema •O Problema da Clique Máxima é um problema importante de otimização combinatória

Aplicações •Telecomunicação •Bioinformática ▫Análise de DNA e RNA analisando e comparando proteínas e compostos menores através de grafos e cliques

Aplicações •Química Computacional ▫Emparelhamento de moléculas Hidrocarbonetos conhecidos como alcanos tem fórmula química CpH2p+2, onde C representa moléculas de carbono e H de hidrogênio. Os vértices que incidem apenas uma arestra são os átomos de Hidrogênio.

Exemplo prático •Suponha que, em um laboratório farmacêutico, seja necessário dimensionar o depósito de substâncias composto por alguns refrigeradores, tendo em mãos uma lista de pares de substâncias que não podem ser armazenadas em um mesmo refrigerador. Assim, o clique máximo do grafo formado por tais incompatibilidades é um limitante inferior para a quantidade de refrigeradores necessários para armazenar todas as substâncias.

Algoritmo Força Bruta •Pseudo Código clique_maxima_exato(Grafo g): todosConjuntos <- todasCombinacoes(g.Vertices) maxClique <- {} para cada conjunto s de todos Conjuntos se (formaClique(s) && (s.tamanho > maxClique.tamanho) maxClique <- s retorna maxClique

Algoritmo Força Bruta •Pseudo Código + Análise (n = |V|) clique_maxima_exato(Grafo g): todosConjuntos <- todasCombinacoes(g.Vertices) maxClique <- {} para cada conjunto s de todos Conjuntos se (formaClique(s) && (s.tamanho > maxClique.tamanho) maxClique <- s retorna maxClique

Algoritmo Força Bruta •Pseudo Código + Análise clique_maxima_exato(Grafo g): todosConjuntos <- todasCombinacoes(g.Vertices) O(2N) maxClique <- {} para cada conjunto s de todos Conjuntos se (formaClique(s) && (s.tamanho > maxClique.tamanho) maxClique <- s retorna maxClique

Algoritmo Força Bruta •Pseudo Código + Análise clique_maxima_exato(Grafo g): todosConjuntos <- todasCombinacoes(g.Vertices) O(2N) maxClique <- {} para cada conjunto s de todos Conjuntos O(2N) se (formaClique(s) && (s.tamanho > maxClique.tamanho) maxClique <- s retorna maxClique

Algoritmo Força Bruta •Pseudo Código + Análise clique_maxima_exato(Grafo g): todosConjuntos <- todasCombinacoes(g.Vertices) maxClique <- {} para cada conjunto s de todos Conjuntos se (formaClique(s) && (s.tamanho > maxClique.tamanho) maxClique <- s retorna maxClique O(2N) O(2N) O(N²)

Algoritmo Força Bruta •Pseudo Código + Análise clique_maxima_exato(Grafo g): todosConjuntos <- todasCombinacoes(g.Vertices) maxClique <- {} para cada conjunto s de todos Conjuntos se (formaClique(s) && (s.tamanho > maxClique.tamanho) maxClique <- s retorna maxClique Total : O(2^n *n^2) O(2N) O(2N) O(N²)

Algoritmo Aproximado •Pseudo Código clique_maxima_aproximada(Grafo g): conjuntoOrdenadoGrau <- ordenaVertice(V) maxClique <- conjuntoOrdenadoGrau(1) para cada vertice vi de i=2 até N se (formaClique(vi, maxClique)) maxClique = maxClique U vi retorna maxClique

Algoritmo Aproximado •Pseudo Código + Análise (n = |V|) clique_maxima_aproximada(Grafo g): conjuntoOrdenadoGrau <- ordenaVertice(V) maxClique <- conjuntoOrdenadoGrau(1) para cada vertice vi de i=2 até N se (formaClique(vi, maxClique)) maxClique = maxClique U vi retorna maxClique Total : O(n³) O(nlogn) O(n) O(n²)

Referência •http://www.ime.usp.br/~eufrasio/eufrasio/paulo eufrasioIC2009.pdf •http://ubiq.inf.ufpel.edu.br/arrsouza/lib/exe/fetc h.php?media=clique_de_um_grafo.pdf •http://lcavique.no.sapo.pt/publicacoes/Clique%2 0Tabu.pdf

Add a comment

Related presentations

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

In this presentation we will describe our experience developing with a highly dyna...

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

Un recorrido por los cambios que nos generará el wearabletech en el futuro

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

Related pages

Algoritmo clique maximo - Analise de Algoritmos - Technology

Algoritmo clique maximo - Analise de Algoritmos, definição, exemplos e teoria e razão de aproximação.
Read more

Algoritmos - exercicios resolvidos - Scribd

Analise o seguinte algoritmo de receita de ... Sempre que formos iniciar nossos algoritmos, usaremos a palavra ALGORITMO e ao final utilizaremos a palavra ...
Read more

Análise de Algoritmos: Índice remissivo - ime.usp.br

clique; clique grande; cobertura de ... (algoritmo) Corrige-Subindo (algoritmo) ... http://www.ime.usp.br/~pf/analise_de_algoritmos/
Read more

Parâmetros do Algoritmo (Suplementos de Mineração de Dados ...

... não precisa configurar o algoritmo ou os ... de Dados e clique em Parâmetros para controlar o comportamento dos algoritmos de ...
Read more

Problema do clique – Wikipédia, a enciclopédia livre

... então o clique Maximo encontrado em ... e escolhendo um clique de 2 vertices caso ambos os algoritmos falhem, Feige prove um algoritmo de ...
Read more

Algoritmos - Tópicos avançados

Apostila de algoritmo que aborda ... programação dinâmica etc by jsky10 in Types > Instruction manuals e Algoritmos ... Determinar a maior clique ...
Read more

13 introducao a analise de algoritmos - Technology

13 introducao a analise de algoritmos. by ricardo-bolanho. on Jun 23, 2015. Report Category: Technology
Read more

Aula01-Histórico e Definição de Algoritmos by Wagner L ...

histÓrico e definiÇÃo de algoritmos: perspectivas de linguagem situaÇÃo da realidade profissional o que é algoritmo? ...
Read more