Analise de Tempo de Execução

UFV Florestal

AEDS

Trabalho prático 2
Avaliação de tempo de execução

Angelo Bernar T. Morelo – EF01278
Caio Mello – EF01291

Sumário

Introdução.............................................................................................................. 2

Objetivo:................................................................................................................ 3

O trabalho:............................................................................................................. 4

O algoritmo de combinação:........................................................................................ 5

A implementação do código:....................................................................................... 6

Tempo de execução................................................................................................... 8

UFV Florestal

AEDS 1

Introdução
Na análise de algoritmos temos um assunto que é tratado com grande recorrência, que é o impacto causado pelo desempenho de um algoritmo. O problema apresentado é conhecido como 3-FNC-SAT que é uma redução do problema de satisfabilidade original.

UFV Florestal

AEDS 2

Objetivo:
O objetivo deste trabalho é avaliar as mudanças de desempenho de um algoritmo considerado intratável, isto é: não executa em tempo polinomial. O problema a ser tratado é de ordem de complexidade exponencial. Algoritmos da ordem exponencial normalmente não executam em tempo razoável para encontrar soluções, normalmente são recomendados para problemas que tratam de pequenas entradas.

UFV Florestal

AEDS 3

O trabalho:
A implementação deste trabalho consiste em três simples passos, a primeira a pesquisar um algoritmo que gere todas as combinações para N valores lógicos, em seguida o algoritmo deverá ser adaptado de forma que se possa comparar a entrada proposta pelo trabalho com as combinações a fim de decidir se a combinação a satisfaz.
Finalmente deveremos dividir os problemas em duas formas: Interativa,