Análise e projeto de algoritmos

Análise e Projeto de Algoritmos

Raquel de Souza Francisco Bravo e-mail: [e-mail] 02 de maio de 2012

Raquel de Souza Francisco Bravo

Análise e Projeto de Algoritmos

Árvores de Decisão • O conhecimento de limites inferiores para um problema algorítmico é um dado essencial para que se possa avaliar a dificuldade de resolver o problema.

Raquel de Souza Francisco Bravo

Análise e Projeto de Algoritmos

Árvores de Decisão • O conhecimento de limites inferiores para um problema algorítmico é um dado essencial para que se possa avaliar a dificuldade de resolver o problema. • Uma técnica utilizada que permite o cálculo de limites inferiores dá-se através das árvores de decisão.

Raquel de Souza Francisco Bravo

Análise e Projeto de Algoritmos

Árvores de Decisão • O conhecimento de limites inferiores para um problema algorítmico é um dado essencial para que se possa avaliar a dificuldade de resolver o problema. • Uma técnica utilizada que permite o cálculo de limites inferiores dá-se através das árvores de decisão. • Ex.: Vamos utilizar a técnica no Problema de ordenação

Raquel de Souza Francisco Bravo

Análise e Projeto de Algoritmos

Árvores de Decisão • Seja P um problema e α um algoritmo que resolve P, de tal modo que a operação dominante em α seja a comparação. Isto é, o número de comparações que α executa no processo exprime sua complexidade.

Raquel de Souza Francisco Bravo

Análise e Projeto de Algoritmos

Árvores de Decisão • Seja P um problema e α um algoritmo que resolve P, de tal modo que a operação dominante em α seja a comparação. Isto é, o número de comparações que α executa no processo exprime sua complexidade. • Cada comparação é de natureza binária: admite exatamente 2 alternativas como resposta.

Raquel de Souza Francisco Bravo

Análise e Projeto de Algoritmos

Árvores de Decisão • Seja P um problema e α um algoritmo que resolve P, de tal modo que a operação dominante em α seja a comparação. Isto