Revisão do Projeto de Análise de Algoritmos - COM540

REVISÃO Projeto de Análise de Algoritmos COM540 Esta revisão está fortemente baseada na sequência de conteúdos tratados e discutidos nas videoaulas e nos textosbase que compõem o curso e busca extrair e sintetizar os principais tópicos e conceitos apresentados ao longo do curso Lembramos que somente a leitura deste material não é suficiente para o seu estudo Ele deve ser usado mais fortemente como um guia para relembráloa dos assuntos tratados O estudo dos materiais basetextosbase são de fundamental importância para que você possa ter um bom aproveitamento nas avaliações Bons estudos Semana 1 Na Semana 1 do curso foram discutidos diversos conceitos introdutórios como o conceito de algoritmo e exemplos de aplicações o conceito de tempo de execução de um algoritmo e o conceito de corretude Foram vistos diferentes modelos computacionais que podem ser utilizados para a análise de algoritmos Foi introduzida também a notação assintótica que é uma ferramenta matemática utilizada para a análise da complexidade de um algoritmo em termos de tempo de execução Assim temos que Algoritmos são utilizados para realização de tarefas resolução de problemas de uma forma sistemática e eficiente diminuindo o tempo para a realização de tarefas e gerando economia de custos possibilitando ainda em muitas situações a resolução de problemas complexos O tempo de execução de um algoritmo nos dá uma medida da eficiência do algoritmo e está associado ao número de passos gastos pelo algoritmo para nos fornecer uma saída para uma instância de entrada A corretude está associada ao fato de um algoritmo estar correto ou seja ser capaz de produzir uma resposta correta para qualquer instância de entrada válida Sendo que a prova de corretude muitas vezes é obtida através da análise das invariantes de laço quando o algoritmo possui laços Modelos Computacionais Foram vistos três modelos computacionais que podem ser utilizados na análise de algoritmos sendo mais conveniente a utilização de um ou outro modelo de acordo com a natureza do problema para o qual se quer fazer a análise Máquinas de Estados Finitos FSM aplicada a modelos de computadores com pouca memória Máquinas de Turing conseguem superar a limitação do número de estados das FSM por meio do uso de uma fita que permite ler e escrever caracteres possibilitando assim um recurso de armazenamento da informação Modelo RAM idealização de um computador com memória infinita e com um único processador em que as instruções são executadas de forma sequencial e o tempo de execução de uma operação básica é fixo e igual para qualquer operação básica Notação Assintótica Vimos que a notação assintótica nos permite estabelecer limitantes na forma de uma função do tipo C gn para o tempo assintótico Tn de execução de um algoritmo Sendo utilizada para medir a complexidade de um algoritmo Podendo também ser utilizada para comparar a eficiência entre algoritmos Notação Ω fornece um limitante inferior para o tempo de execução de um algoritmo C gn Tn para n n0 Notação Θ fornece um limitante inferior e superior para o tempo de execução de um algoritmo dizemos que o tempo de execução Tn está imprensado entre dois limitantes do tipo C1 gn Tn C2 gn para n n0 Notação O fornece um limitante superior para o tempo de execução de um algoritmo Tn C gn para n n0 Semana 2 Na Semana 2 do curso foi estudada a indução matemática e a sua aplicação no projeto de algoritmos A técnica da indução para o projeto de algoritmos tem como benefício a prova de corretude para algoritmo se aplicada corretamente Foram estudados também dois algoritmos de ordenação o algoritmo Insertion Sort e o algoritmo Merge Sort Foi apresentado o conceito de recorrência no qual a solução de problemas maiores pode ser obtida através do conhecimento da solução de problemas menores relacionados ao problema original Foi visto ainda que a recorrência pode auxiliar no cálculo do tempo de execução de um algoritmo recursivo Indução Matemática A sua aplicação resulta em algoritmos recursivos O processo de indução para construção de algoritmos recursivos consiste basicamente na aplicação do primeiro princípio da indução determinação do caso base e a aplicação da hipótese de indução pk verdadepk1 verdade então Pn é verdadeiro para qualquer n Ou no segundo princípio da indução determinação do caso base e a aplicação da hipótese de indução pr verdade para r com 1rkpk1 verdade então Pn é verdadeiro para qualquer n Algoritmos de Ordenação Ordenam uma sequência de entrada de números fornecendo com saída uma nova sequência na qual os números estão ordenados na ordem do menor para o maior número Insertion Sort utiliza a estratégia de inserção A cada passo um novo número é inserido a um vetor sequência já previamente ordenado começando com o vetor de comprimento 1 que naturalmente já está ordenado de tal forma a produzir um novo vetor ordenado Consistindo portanto na tarefa de buscar em qual posição do vetor previamente ordenado o novo valor deverá ser inserido Merge Sort utiliza a estratégia de intercalação Através de um processo de recursão combina vetores previamente ordenados formando um novo vetor ordenado partindo do caso base em que os vetores têm comprimento 1 que naturalmente já estão ordenados Obs o algoritmo Merge Sort tem tempo de execução assintótico Onlogn ao passo que o algoritmo Insertion Sort tem tempo de execução assintótico On2 sendo portanto mais eficiente computacionalmente que o Insertion Sort Recorrência Recorrência e indução matemática andam de mãos dadas pois a recorrência ajuda a resolver problemas maiores a partir do conhecimento da solução de problemas menores relacionados a esse problema sendo utilizada por exemplo na estratégia de divisão e conquista Quando um algoritmo contém uma chamada recursiva a si mesmo o tempo de execução pode frequentemente ser descrito por uma equação de recorrência Através de uma equação de recorrência foi possível por exemplo determinar o tempo de execução do algoritmo Merge Sort Semana 3 Divisão e Conquista Na Semana 3 do curso foi estudada a técnica de divisão e conquista que resolve problemas de forma recursiva em três etapas divisão divide o problema original em subproblemas menores conquista os subproblemas vão sendo resolvidos de forma recursiva combinação as soluções vão sendo combinadas para obtenção da solução do problema original Nem sempre o problema original será dividido em subproblemas de tamanhos iguais A divisão e conquista foi aplicada para o cálculo da multiplicação entre duas matrizes o algoritmo de Strassen permite o cálculo da multiplicação entre duas matrizes de forma eficiente De forma a se obter os limites assintdticos para o tempo de execucao do algoritmo trés métodos utilizando recorréncias podem ser aplicados Método da substituigao pode ser dividido em duas etapas Primeito supomos um limite assintotico para uma recorréncia depois usamos a inducao matematica para tentar provar que nossa suposicao estava correta Método da arvore de recursdo representa a recorréncia na forma de uma arvore de recursao em que cada no representa o custo de um unico subproblema no nivel correspondente de recursao Método mestre fornece limites para recorréncias na forma TaTnbfm com a 2 1 b 1 e ff uma fungao dada Sendo que 1 Se fn On9 para alguma constante 0entdo Tn On9 2 Se fn On99e entao Tn On94 lg n logpate n 3 Se fn 2nI nara alguma constante 0e se af cfn para alguma constante c 1e todos os n suficientemente grandes entao Tn Ofn Semana 4 Grafos A Semana 4 do curso foi dedicada ao estudo de algoritmos baseados em grafos uma vez que uma ampla variedade de problemas pode ser expressa com clareza e precisao através de grafos Grafos sao formados por um conjunto de vértices nds e arestas arcos A classificagao e as terminologias que definem as caracteristicas de um grafo em relacao aos nos vértices e caminhos formados é bastante extensa e de suma importancia para explorar suas propriedades e aplicagdes na solugao de problemas através do uso de algoritmos Computacionalmente os grafos geralmente serao representados por listas de adjacéncias para cada vértice existe uma lista com todos os vértices que estao conectados a ele vértices adjacentes ou através de uma matriz de adjacéncias na qual havera um valor 1 sempre que existir uma aresta conectando dois vértices na linhacoluna corresponde pata grafos nao dirigidos E um 1 quando houver uma aresta partindo de um vértice em uma linha para um vértice em uma coluna na matriz de adjacéncias para grafos dirigidos digrafos Foram estudados também dois procedimentos para busca em grafos busca em largura BFS e busca em profundidade DFS Busca em Largura BFS A busca em largura é utilizada em diversos algoritmos baseados no problema de se encontrar o caminho mínimo entre os vértices alcançáveis de um grafo eg algoritmo de Dijsktra A busca em largura se assegura de visitar vértices em ordem crescente de distância partindo de um vértice inicial O algoritmo estudado para busca em largura utilizou uma fila primeiro vértice a entrar primeiro vértice a sair para realizar a busca Foi visto também que a busca em largura é realizada em tempo linear OVE Busca em Profundidade A busca em profundidade faz incursões profundas no grafo retrocedendo somente quando não se tem mais nós novos para visitar Diferentemente do BFS o DFS irá realizar a descoberta progressiva em profundidade de novos vértices sempre que encontrar uma aresta no nó visitado para um outro nó ainda não visitado O algoritmo estudado para busca em profundidade utilizou uma pilha último vértice a entrar primeiro vértice a sair para realizar a busca Foi visto que assim como a busca em largura a busca em profundidade também é realizada em tempo linear OVE Semana 5 Algoritmos Gulosos A Semana 5 do curso foi dedicada ao estudo dos algoritmos gulosos Algoritmos gulosos são aplicados normalmente a problemas de otimização Na estratégia gulosa o algoritmo busca fazer escolhas localmente ótimas na tentativa de obter uma solução globalmente ótima Embora algoritmos gulosos sejam capazes de produzir soluções para diversos problemas nem sempre as soluções são globalmente ótimas O problema de seleção de atividades foi estudado o problema de otimização para a alocação do maior número de reuniões em diferentes horários em uma situação em que só existe uma sala de reunião como recurso disponível Através da estratégia gulosa a cada seleção o algoritmo seleciona a reunião de término mais cedo em que não houvesse sobreposição de horário com a última escolha Foi visto que essa estratégia conduz a uma solução ótima para esse problema Como dois exemplos de algoritmos que utilizam a estratégia gulosa foram estudados o algoritmo de Dijkstra para determinação do caminho mínimo em um grafo e o código de Huffman para compactação de dados de forma eficiente determinação de uma árvore ótima para codificação dos dados Algoritmo de Dijkstra O algoritmo de Dijkstra resolve o problema de determinação do caminho mínimo de peso mínimo entre dois vértices de um grafo conexo ou seja um grafo no qual partindo se de um vértice do grafo é possível chegar a qualquer outro vértice por meio de um caminho e com pesos positivos A determinação do caminho mínimo possui diversas aplicações em redes de computadores de telecomunicações e logísticas onde se quer a partir de um ponto de origem chegar a outro ponto da forma mais eficiente possível O algoritmo de Dijkstra forma um conjunto de vértices que inicialmente possui somente o vértice de origem e vai progressivamente incluindo vértices até que o de destino seja incluído quando o conjunto é completamente formado e o algoritmo encerra A estratégia gulosa utilizada a cada passo é incluir no conjunto em formação o vértice ainda não pertencente ao conjunto e que tenha a menor distância para se chegar ao nó de origem Uma vez formado o conjunto que contém o vértice de destino é possível então a partir dos vértices pertencentes ao conjunto determinar o caminho mínimo e a sua distância até o nó de origem O algoritmo de Dijsktra possui tempo de execução On2 Código de Huffman A codificação de Huffman trata do problema de otimização para a representação da informação O algoritmo de Huffman permite compactar dados de forma eficiente utilizando o fato de que um determinado conteúdo de informação representado através de um alfabeto pode apresentar símbolos com maior frequência do que outros Na codificação de Huffman os símbolos caracteres que ocorrem com maior frequência são codificados em palavras binárias de menor comprimento e os símbolos menos frequentes são codificados em palavras binárias de maior comprimento Assim o comprimento das palavras codificadas associadas a cada símbolo é proporcional à frequência de ocorrência do símbolo no arquivo a ser codificado O uso de palavras de comprimento desigual pode gerar ambiguidade na decodificação Dessa forma a codificação de Huffman utiliza código de prefixo Em um código de prefixo nenhuma palavra codificada é prefixo de outra palavra evitando assim a ambiguidade na decodificação A codificação de Huffman gera como saída uma árvore binária ótima e cada símbolo representa uma folha da árvore Para a obtenção do código palavra binária referente a um determinado símbolo folha da árvore percorrese a árvore da raiz até a folha Cada ramo à direita corresponde a um zero 0 e cada ramo à esquerda corresponde a um valor um 1 na palavra binária que representa o símbolo correspondente Como no exemplo da figura abaixo símbolo codificação A 0 B 100 C 101 D 11 A construção da árvore é realizada da base para a raiz da árvore Inicialmente cada um dos n símbolos representa um nó rotulado com a sua frequência de ocorrência A cada passo examinamos qual é o par de nós com a menor frequência de ocorrência estratégia gulosa esses nós serão os filhos de um novo nó que será inserido na árvore tendo como frequência a soma das frequências dos nós filhos Esse procedimento é repetido até chegarmos à raiz da árvore o que corresponde a n1 operações de intercalação O algoritmo de Huffman pode ser implementado usandose um heap mínimo binário que consiste em um algoritmo de ordenação em que cada nó da árvore corresponde a um elemento em uma fila de prioridades A ordenação ordem de prioridade será realizada de acordo com a frequência do nó Utilizandose o heap mínimo binário o tempo de execução do algoritmo é Onlgn Semana 6 Programação Dinâmica A Semana 6 do curso foi dedicada ao estudo da programação dinâmica De maneira similar aos algoritmos gulosos a programação dinâmica é aplicada em geral a problemas de otimização Ela também possui semelhança com o paradigma da divisão e conquista A programação dinâmica no entanto aplicase quando os subproblemas se sobrepõem ou seja quanto temos subproblemas que compartilham subproblemas Assim a grande diferença em relação à divisão e conquista é que na programação dinâmica cada subproblema é resolvido uma única vez sendo sua solução gravada em uma tabela memória que será acessada sempre que aquele subproblema aparecer evitando assim recalcular a resposta para um subproblema já resolvido A B C D 0 0 0 1 1 1 Representação através de árvore binária Algoritmos de programação dinâmica podem ser implementados de duas maneiras distintas utilizando uma abordagem topdown ou uma abordagem bottomup Implementação TopDown nesse tipo de implementação o algoritmo é escrito de forma recursiva natural como se estivesse aplicando divisão e conquista porém sempre que um subproblema é resolvido o seu resultado é salvo e a cada nova chamada recursiva o algoritmo primeiro verifica se já não existe uma solução para aquele subproblema Dizemos que o algoritmo utiliza memoização que consiste em salvar o resultado dos subproblemas resolvidos ou seja o algoritmo lembra de subproblemas já resolvidos e utiliza seus resultados Implementação BottonUp nesse tipo de implementação o algoritmo é escrito de forma iterativa resolvendo os subproblemas de tamanho menor para os de tamanho maior Assim sempre que o algoritmo vai resolver um subproblema todos os subproblemas menores já foram resolvidos não necessitando portanto de uma consulta à tabela para verificar se um subproblema já foi resolvido Foram estudados algoritmos para o cálculo do valor de um elemento da sequência de Fibonacci Utilizouse divisão e conquista e a seguir programação dinâmica Foi possível observar uma melhora significativa de desempenho quando a programação dinâmica é aplicada a esse problema tendo o tempo de execução passado de Ω1618n utilizando divisão e conquista para Θn quando a programação dinâmica foi aplicada Foram realizados também dois estudos de caso utilizando programação dinâmica o problema do corte de barras e o problema da multiplicação de cadeia de matrizes Problema do corte de barras O problema do corte de barras consiste em maximizar a receita na venda de cortes para barras de comprimento n n um inteiro em metros No problema uma barra de comprimento n pode ser cortada tomandose qualquer combinação de cortes com comprimentos múltiplos de um metro Sendo que cada corte possui um preço de venda fornecido por uma tabela de preços de venda A princípio existem 2n1 combinações possíveis de cortes o que torna um algoritmo do tipo força bruta pouco eficiente O problema é resolvido pela programação dinâmica observandose que uma vez executado o primeiro corte podemos considerar os dois pedaços resultantes como instâncias independentes do problema de otimização do corte da barra Sendo que a solução ótima global incorpora as soluções ótimas para os dois subproblemas relacionados maximizando a receita gerada por esses dois pedaços Podemos considerar cada subproblema relacionado ao corte da barra de comprimento n como segue uma primeira peça de comprimento i cortada da extremidade esquerda e o pedaço r que restou do lado direito com comprimento n i sendo que somente o pedaço r com comprimento n i pode continuar a ser dividido Então o problema consiste em determinar rn max 1i npirni Ou seja qual a combinação para o preço da peça de comprimento i pi e preço da barra de comprimento n i rni que maximiza a receita rn Assim aplicando essa expressão de forma recursiva é possível determinar a combinação de cortes que maximiza a receita solução ótima Problema da multiplicação de uma cadeia de matrizes O problema da multiplicação de cadeia de matrizes consiste em determinar qual a ordem parentização em que uma cadeia de matrizes deve ser multiplicada de forma a se obter o menor número de multiplicações de elementos das matrizes Conforme visto a ordem em que as matrizes são multiplicadas pode fazer uma diferença brutal no número de multiplicações entre elementos necessárias para multiplicar a cadeia Conforme a videoaula sobre multiplicação de cadeia de matriz para realizar por exemplo a multiplicação de uma cadeia de quatro matrizes A B C e D com dimensões 50x20 20x1 1x10 e 10x100 respectivamente a parentização A X B X C X D tem um custo computacional de 120200 multiplicações ao passo que o mesmo resultado é obtido com a parentização A X B X C X D que tem um custo computacional de 7000 multiplicações O problema da multiplicação de cadeia de matriz tem semelhança com o problema de cortes de barras porém neste caso tratase de um problema de minimização do custo computacional em termos de número de multiplicações Definindo o custo mínimo Cij custo ótimo para multiplicar uma cadeia de matrizes Ai A2 Aj com 1 i j n em que n é o tamanho da cadeia original Como Cij é um custo ótimo ele foi obtido por um produto ótimo de matrizes Então suponha que para algum k entre i e j as duas partes que representam as duas matrizes resultantes de produtos anteriores Ai x x Ak e Ak1 x x Aj possuem os respectivos custos ótimos Ci k e Ck1 j O custo de Ci j corresponde à soma desses dois custos ótimos mais o custo da multiplicação das duas matrizes correspondentes à obtenção desses custos Uma de dimensão mi1 x mk e a outra com dimensão mk x mj Então para qualquer Ci j com 1 i j n temos que Ci j Ci k Ck1 j mi1 mk mj De maneira similar ao que fizemos no problema de corte de barras precisamos determinar o valor de k que minimiza essa expressão para calcular o custo ótimo Assim aplicando essa expressão de forma recursiva é possível determinar a parentização que minimiza o custo computacional para o cálculo da multiplicação da cadeia de matrizes de comprimento n solução ótima Semana 7 Reduções e NPCompletude A Semana 7 do curso foi dedicada ao estudo da técnica de redução para o projeto de algoritmos e como ferramenta para obtenção de informações sobre a dificuldade na resolução de novos problemas a partir do conhecimento da dificuldade da solução de problemas conhecidos Foram também estudadas as classes de problemas P NP NP Completos e NPDifíceis Redução A técnica de redução pode ser utilizada para resolver um novo problema a partir do conhecimento de um algoritmo que resolve um problema semelhante Ou seja reduzir um problema A para um problema B significa utilizar um algoritmo que resolve B como parte do algoritmo que resolve A A fim de realizar a redução como normalmente as instâncias de entrada IA do algoritmo A ALGA são diferentes das instâncias de entrada IB do algoritmo B ALGB da mesma forma que as saídas SIA do algoritmo A são diferentes das saídas SIB do algoritmo B Então são utilizadas funções de transformação de entradasaída fg para realizar essas transformações de entradasaída como mostrado na figura abaixo Normalmente quando se utiliza a redução para determinação da dificuldade de resolução de novos problemas o tratamento é feito com base em problemas de decisão uma vez que usar a redução em um problema de decisão é mais simples que em um problema de otimização Problemas de decisão e de otimização relacionados são equivalentes e podem ser convertidos um no outro Em problemas de decisão a solução consiste simplesmente em responder sim ou não para uma dada pergunta Existem problemas que ainda não são resolvíveis em tempo polinomial ou seja não possuem um tempo de execução aceitável e outros problemas para os quais ainda não existe solução Nesse sentido para verificarmos se um determinado problema de fato não pode ser resolvido em tempo polinomial a redução é uma ferramenta importante ALGA Quando conseguimos reduzir em tempo polinomial um problema A para um problema B ou seja as funções de transformação possuem tempo polinomial de execução então as seguintes afirmações são verdadeiras Se existe um algoritmo eficiente para A não se pode afirmar nada sobre o algoritmo B Se não existe um algoritmo eficiente para B não podemos afirmar nada sobre um algoritmo para A Se existe um algoritmo eficiente para B então necessariamente existe um algoritmo eficiente para A Se não existe um algoritmo eficiente para A então não existe um algoritmo eficiente para B Note que no caso dos dois últimos resultados possíveis na aplicação da redução descritos nas afirmações acima se tivermos o conhecimento da dificuldade para solução de um problema podemos afirmar sobre a dificuldade para solução do outro problema Classes de Problemas Os problemas para os quais se propõe a resolução através de um algoritmo podem ser divididos em diferentes classes Classe de problemas P corresponde ao conjunto de todos os problemas que conseguimos resolver em tempo polinomial ou seja para o qual existe um algoritmo eficiente Classe de problemas NP corresponde ao conjunto de todos os problemas que são verificáveis em tempo polinomial ou seja conseguimos projetar um algoritmo de tempo polinomial que consegue verificar se uma determinada instância de entrada é solução para o problema Note que todo problema que é P também é NP Pois conseguimos escrever um algoritmo verificador em tempo polinomial para ele Classe de problemas NPCompletos corresponde aos problemas contidos na classe NP que possuem a propriedade de que todo problema em NP pode ser reduzido a este problema em tempo polinomial Os problemas NPcompletos não possuem solução conhecida em tempo polinomial Note que se conseguíssemos resolver um único problema NPcompleto em tempo polinomial resolveríamos todos os problemas NP em tempo polinomial uma vez que todos os problemas em NP se reduzem a ele em tempo polinomial Classe de problemas NPDifíceis corresponde ao conjunto de problemas para os quais existe um problema NPcompleto que seja redutível a ele em tempo polinomial Também todo problema em NP se reduz em tempo polinomial para esse problema Diferentemente de um problema NPcompleto um problema NPdifícil não precisa estar em NP Podemos dizer ainda que um problema NP completo é um problema NPdifícil que está em NP A figura abaixo mostra a interrelação entre as classes de problemas Note que P C NP Redução do problema 3SAT para o problema do CLIQUE Vimos que a operação de redução entre problemas pode ser composta isto é se um problema A se reduz para um problema B que se reduz para um problema C então A se reduz para C Então se conseguirmos reduzir um problema NPcompleto para o nosso problema como pela definição todos os problemas em NP se reduzem para o problema NP completo então todos os problemas em NP também se reduzem para o nosso problema e provamos que o nosso problema é NPcompleto O problema de decisão 3SAT consiste na pergunta se uma determinada fórmula booleana Φ em 3CNF normal 3conjuntiva é satisfazível Ou seja se existem valores booleanos para suas entradas literais para os quais a expressão retorna 1 é verdadeira Esse foi o primeiro problema que se provou ser NPcompleto O problema do CLIQUE consiste em encontrar um clique de tamanho máximo em um grafo sendo um clique é um subconjunto de vértices pertencente ao grafo tal que para todo par de vértices nesse subconjunto existe uma aresta entre eles Assim finalizamos o nosso curso examinando o problema do CLIQUE e verificando que se trata de um problema NPcompleto uma vez que conseguimos reduzir o problema 3SAT que é NPcompleto para o problema do CLIQUE Terminamos aqui o conteúdo desta revisão utilizea como uma fonte referência para o seu estudo mas não deixe de estudar os conteúdos vistos durante curso para a sua preparação Boa prova