Please enable JavaScript.

Coggle requires JavaScript to display documents.

INTRODUÇÃO - Coggle Diagram

- - - - Segundo Dijkstra, um algoritmo corresponde a uma descrição de um padrão de comportamento, expresso em termos de um conjunto finito de ações
      - Seqüência de ações executáveis para a obtenção de uma solução para um determinado tipo de problema
- - - - Análise do número de vezes que cada parte do algoritmo deve ser executada
      - Estudo da quantidade de memória necessária.
  - - - Coloca-se limites para a complexidade computacional dos algoritmos pertencentes à classe (otimização)
      - Procura-se identificar um que seja o melhor possível
      - Toda uma família de algorítimos é investigada
    - - Determinando o menor custo possível para resolver problemas de uma dada classe, temos a medida da dificuldade inerente para resolver o problema
      - Quando o custo de um algoritmo é igual ao menor custo possível, o algoritmo é ótimo para a medida de custo considerada
      - Se a mesma medida de custo é aplicada a diferentes algoritmos, então é possível compará-los e escolher o mais adequado
      - MEDIDA DO CUSTO DE UTILIZAÇÃO DE UM ALGORÍTIMO
        
        PELA EXECUÇÃO DE UM PROGRAMA
        
        Depende do compilador, que pode favorecer construções em detrimento de outras
        
        Depende do hardware
        
        Depende do aspecto memória
        
        São bastante inadequados e resultados não devem ser generalizados
        
        Caso a favor: quando existem vários algoritmos distintos para resolver um mesmo tipo de problema, todos com um custo de execução dentro de uma mesma ordem de grandeza. Assim os custos reais das operações são todos considerados, assim como os custos não aparentes tais como alocação de memória, indexação, carga, etc
        
        POR MEIO DE UM MODELO MATEMÁTICO
        
        Modelo matemático baseado em um computador idealizado
        
        Forma mais adequada de se medir o custo de utilização de um algoritmo
        
        Conjunto de operações e seus custos associados devem ser especificado
        
        Mais usual ainda é ignorar o custo de algumas das operações envolvidas e considerar apenas as operações mais significativas
        
        COMPLEXIDADE
        
        Para medir o custo de execução de um algoritmo é comum definir uma função de custo ou função de complexidade f
        
        Função de complexidade de tempo: f(n) mede o tempo necessário para executar um algoritmo em um problema de tamanho n
        
        Função de complexidade de espaço: f(n) mede a memória necessária para executar um algoritmo em um problema de tamanho n
        
        A complexidade de tempo, na realidade, não representa tempo diretamente, mas o número de vezes que determinada operação considerada relevante é executada
        
        TAMANHO DE ENTRADA DE DADOS
        
        A medida do custo de execução de um algoritmo depende principalmente do tamanho da entrada dos dados. Por isso é comum considerar-se o tempo de execução de um programa como uma função do tamanho da entrada
        
        ANÁLISE CENÁRIOS
        
        Melhor caso corresponde ao menor tempo de execução sobre todas as possíveis entradas de tamanho n.
        
        Caso médio (ou caso esperado) corresponde à média dos tempos de execução de todas as entradas de tamanho n. Nesta análise, uma distribuição de probabilidades sobre o conjunto de entradas de tamanho n é suposta, e o custo médio é obtido com base nesta distribuição.
        
        A análise do caso médio é geralmente muito mais difícil de obter do que as análises do melhor e do pior caso
        
        Pior caso corresponde ao maior tempo de execução sobre todas as entradas de tamanho n . Se f é uma função de complexidade baseada na análise de pior caso então o custo de aplicar o algoritmo nunca é maior do que ƒ(n).
        
        É comum supor uma distribuição de probabilidades em que todas as entradas possíveis são igualmente prováveis. Entretanto, na prática isto nem sempre é verdade
        
        ORÁCULO
        
        Informa o resultado de cada passo possível, que no nosso caso seria o resultado de cada comparação. Para derivar o limite inferior o oráculo procura sempre fazer com que o algoritmo trabalhe o máximo, escolhendo como resultado da próxima comparação aquele que cause o maior trabalho possível que é necessário para determinar a resposta final
        
        Teorema: Qualquer algoritmo para encontrar o maior e o menor elementos de um conjunto com n elementos não ordenados, n ≥ 1, faz pelo menos 3dn/2e − 2 comparações*
        
        técnica muito utilizada para obter o limite inferior para uma classe qualquer de algoritmos Dado um modelo de computação que expresse o comportamento do algoritmo o oráculo
        
        Prova: A técnica utilizada define um oráculo que descreve o comportamento do algoritmo por meio de um conjunto de n–tuplas, mais um conjunto de regras associadas que mostram as tuplas possíveis (estados) que um algoritmo pode assumir a partir de uma dada tupla e uma única comparação
        
        Uma 4–tupla, representada por (a, b, c, d), onde os elementos de:
        a → nunca foram comparados;
        b → foram vencedores e nunca perderam em comparações realizadas;
        c → foram perdedores e nunca venceram em comparações realizadas;
        d → foram vencedores e perdedores em comparações realizadas
        
        COMPORTAMENTO ASSINTÓTICOS DE FUNÇÕES
        
        O custo para obter uma solução para um dado problema aumenta com o tamanho n do problema. O tempo necessário para resolver o problema cresce quando n cresce
        
        A análise de algoritmos é realizada para valores grandes de n. Estuda-se o comportamento assintótico das funções de custo
        
        O comportamento assintótico de ƒ(n) representa o limite do comportamento do custo quando n cresce
        
        Definição: Uma função f(n) domina assintoticamente outra função g(n) se existem duas constantes positivas c e m tais que, para n ≥ m, temos |g(n)| ≤ c × |f(n)| .
        
        CLASSES DE COMPORTAMENTO ASSINTÓTICOS
        
        4 more items...