Projeto e Análise de Algoritmos

Projeto e Análise de Algoritmos fatimafigpucminasbr Pontifícia Universidade Católica de Minas Gerais Instituto de Ciências Exatas e Informática Departamento de Ciência da Computação Mestrado em Informática Projeto de Algoritmos Paradigmas Parte 3 B Força Bruta Busca Exaustiva ou Enumeração Total Força Bruta Consiste em enumerar todos os possíveis candidatos de uma solução e verificar se cada um satisfaz o problema 3 Incremental Incremental A ordenação por inserção utiliza uma abordagem incremental tendo ordenado o subarranjo A1j1 inserimos o elemento isolado Aj em seu lugar apropriado formando o subarranjo ordenado A1j 5 Incremental 6 INSERTIONSORTA for j 2 to n do chave Aj i j 1 A0 chave sentinela while Ai chave do Ai1 Ai i i1 Ai1 chave Algoritmos Tentativa e Erros Backtracking Backtracking Algoritmo para encontrar todas ou algumas soluções de um problema computacional que incrementalmente constrói candidatas de soluções e abandona uma candidata parcialmente construída tão logo quanto for possível determinar que ela não pode gerar uma solução válida 8 Branch and Bound Branch and Bound Referese a um tipo de algoritmo usado para encontrar soluções ótimas para vários problemas de otimização Problemas de otimização podem ser tanto de maximização quando de minimização 10 Divisão e Conquista 12 O paradigma divisão e conquista consiste em dividir o problema a ser resolvido em partes menores encontrar soluções para as partes e então combinar as soluções obtidas em uma solução global Divisão e Conquista Programação Dinâmica 14 Programação Dinâmica Divisão e Conquista Problema é partido em subproblemas que se resolvem separadamente A solução é obtida por combinação das soluções É topdown Programação Dinâmica Resolvemse os problemas de pequena dimensão e guardamse as soluções A solução de um problema é obtida combinando as de problemas de menor dimensão É bottomup Calcula a solução para todos os subproblemas partindo dos subproblemas menores para os maiores armazenando os resultados em uma tabela A vantagem é que uma vez que um subproblema é resolvido a resposta é armazenada em uma tabela e nunca mais é recalculado Algoritmos Gulosos 16 Algoritmos Gulosos Para resolver um problema um algoritmo guloso escolhe em cada iteração a melhor opção para o momento A opção escolhida passa a fazer parte da solução que o algoritmo constrói O algoritmo faz uma escolha ótima local esperando que esta o leve a uma solução ótima global Um algoritmo guloso jamais se arrepende ou volta atrás as escolhas que faz em cada iteração são definitivas