Complexidade de Algoritmo


Evaluando propuestas
Descripción:
Trabalho consiste em basicamente pergundas semelhantes as abaixo, caso interesse mando todo o material, beem simples

Em relação ao projeto de algoritmos relacione a coluna 1 com a coluna 2.
Coluna 1:
Tentativa e erro.
Divisão e conquista.
P Gulosa.
P Dinâmica.
Aproximado.
Heurístico.
Coluna 2:
( )O algoritmo gera soluções cujo resultado encontra-se dentro de um limite para a razão entre a solução ótima e a solução produzida pelo algoritmo.
( )O algoritmo constrói por etapas uma solução. Em cada passo, seleciona o melhor elemento viável na entrada e o inclui na solução parcial. Depois de uma sequência de decisões, alcança uma solução para o problema.
( )O algoritmo divide o problema a ser resolvido em partes menores e encontra soluções ótimas para essas partes. Depois as combina para obter uma solução ótima global.
( )O algoritmo decompõe o processo em um numero finito de subtarefas parciais que devem ser exploradas.
( )O algoritmo pode produzir um bom resultado ou mesmo uma solução ótima, mas também pode produzir uma solução ruim ou até mesmo não obter solução.
( )O algoritmo divide o problema a ser resolvido em partes menores, encontra soluções para as partes e então combina as soluções obtidas em uma solução global.

Questão 02:

Seja π o problema da cobertura de vértices que consiste em, dado um grafo G(V, A), responder se existe nele uma cobertura de vértices de tamanho k.
Uma cobertura de vértices para o grafo não dirigido G(V, A) é um subconjunto de vértices V-1, com V1 está contido em V, tal que cada aresta do grafo G é incidente a, pelo menos, um vértice do subconjunto V1.
Problema π: existe uma cobertura de vértices de tamanho k ?
Entrada: um Grafo G(V, A) e um inteiro k.
Saída: sim ou não.
Resolva:
Apresente um algoritmo Q polinomial não determinístico para o problema π.
O algoritmo Q prova que o problema π é NP-dificil? Justifique.
Supondo que o problema π pertença à classe P, é correto afirmar que a versão de localização desse problema também pertence à P?
Prove que π é NP-completo.
Dica: é sabido que o problema  da cobertura de arestas é NP-completo. Uma cobertura de arestas para o grafo não dirigido G(V, A) é um subconjunto de arestas A1, onde A1 está contido em A, tal que cada vértice do Grafo G é incidente a, pelo menos, uma aresta do subconjunto A1.

Questão 03:

Para cada proporção a seguir, responda V ou F e Justifique TODAS suas respostas:
( ) Se P1  P2 e P2 é NP-dificil, é possível que o algoritmo P1 não exista.
( ) Se P1  NP então SAT  P1.
( ) Se P1  P2 e P1 é NP-dificil então P2 é NP-dificil.
( ) Se P1 é um problema cuja solução depende do resultado de uma função randômica então P1 é indecidível.
( ) Se P1  A1, onde A1 é um algoritmo de rede neural, então P1 é NP-Completo.
( ) Se P = NP então NP-completo = NP-dificil.
( ) Se P1  ...  Ph e Ph é diferente NP, podemos afirmar que P1 é diferente de Ph.

Questão 04:

Seja  o problema da árvore de Steiner que consiste em dado um grafo valorado G(V, A) e um conjunto de vértices T e um inteiro k, responder se existe uma árvore S que é um subgrafo de G e cuja soma dos pesos de suas arestas é menor ou igual a k.

Uma árvore de Steiner para um grafo valorado não dirigido G(V, A), dado um conjunto de vértices T, com T contido em V, é um subgrafo S de G que é acíclico, conexo e contem todos os vértices de T.
Problema : existe uma árvore de Steiner S com peso menor ou igual a k?
Entradas: um grafo não dirigido G(V, A), um vetor P contendo os pesos inteiros das arestas de A, e um inteiro k.
Saída: sim ou não.

Resolva:
Prove que  pertence a NP.
Mostre que   STOP, onde STOP é o problema da parada.



Categoria: IT & Programação
Subcategoria: Programação
Qual é o alcance do projeto?: Bug ou alteração pequena
Isso é um projeto ou uma posição de trabalho?: Um projeto
Tenho, atualmente: Eu tenho especificações
Disponibilidade requerida: Conforme necessário
Funções necessárias: Desenvolvedor, Outro

C

Abierto

Presupuesto

4

Propuestas

16

Freelancers interesados

Publicado: Hace 4 meses

Plazo: No definido

Crea tu propio proyecto

¿Buscas un freelancer para realizar un proyecto similar? Crea tu propio proyecto y recibirás ofertas de los mejores freelancers.


Freelancers que ya aplicaron para este trabajo

roberto m. 15 anos atuando com Informática. pos graduado em design instrucional EaD. atualmente conteudista na Delinea Educacional elaborando materiais didáticos de pós graduação + detalles

Selton F. Estudante de sistemas de informação á procura de alguns trabalhos + detalles

Eduardo F. Formado em engenharia de computação e em busca de desafios + detalles

Samuel Rocha Freelancer em tempo parcial e com mais de 8 anos de experiência na área de T.I., incluindo infra-estrutura, suporte, segurança da informação e desenvolvimento. Meu intuito utilizando esta plataforma é conseguir desta... + detalles