Análise e Complexidade de Algoritmos

Izabella Rezende
Mind Map by Izabella Rezende, updated more than 1 year ago
Izabella Rezende
Created by Izabella Rezende over 4 years ago
12
1

Description

Concursos Públicos IFS Mind Map on Análise e Complexidade de Algoritmos, created by Izabella Rezende on 10/31/2016.

Resource summary

Análise e Complexidade de Algoritmos
  1. Procedimentos computacionais
    1. Entradas
      1. Saídas
      2. Algoritmo correto
        1. Resolve o problema
      3. Avaliar eficiência/desempenho
        1. Considerado tecnologia
          1. Tão importante como hardware
          2. Computador infinitamente rápido?
            1. Recursos limitados
              1. Processamento
                1. memória
              2. Ordenação
                1. Inserção
                  1. Exemplo do baralho
                    1. loop invariante
                      1. ao final de cada etapa uma parte da solução
                        1. provar a corretude
                          1. Inicialização
                            1. verdadeira antes da primeira iteração
                            2. manutenção
                              1. durante a execução
                              2. término
                          2. Complexidade de Algoritmos
                            1. Tempo
                              1. Depende da entrada
                                1. Qtd de itens
                                  1. custo linear
                                    1. melhor caso
                                      1. melhor caminho
                                        1. já ordenado
                                        2. loop
                                        3. custo quadrático
                                          1. maior tempo de execução
                                            1. executar todos os passos
                                              1. pior caso
                                              2. custo constante
                                                1. instruções simples
                                              3. Um algoritmo é melhor se o custo de pior caso for menor
                                              4. Comportamento
                                                1. Complexidade Assintótica
                                                  1. Comportamento de acordo com o crescimento da entrada
                                                    1. Tende ao infinito
                                                    2. Assintoticamente mais eficiente
                                                      1. um algoritmo que é assintoticamente mais eficiente será a melhor escolha para todas as entradas, exceto as muito pequenas
                                                      2. Medidas de complexidade/Custo
                                                        1. Melhor caso
                                                          1. Menor tempo de execução sobre todas as possíveis entradas de tamanho N
                                                          2. pior caso
                                                            1. maior tempo de execução
                                                            2. caso médio
                                                              1. média dos tempos de todas as as entradas
                                                            3. Descarta termos constantes
                                                          3. Prevê recursos neccessários
                                                            1. Resolver problemas computacionais
                                                              1. Divisão e conquista
                                                                1. Ordenação por intercalação
                                                                  1. Divide em 2 pedaços
                                                                    1. Classificar recursivamente
                                                                      1. Intercalar as 2 metades
                                                                    2. Custo: Equação de recorrência
                                                                      1. 2*T(n/2) --divisão + O(n) -Merge
                                                                    3. Recursividade
                                                                      1. Chamar a si mesmo
                                                                      2. Passos:
                                                                        1. Dividir
                                                                          1. Conquistar
                                                                            1. Combinar
                                                                              1. Merge
                                                                        2. QuickSort
                                                                        3. Estudar n. de vezes que operações são executadas
                                                                          1. Algoritmos Gulosos
                                                                            1. Busca resolver problemas de otimização
                                                                              1. caminho mínimo/menor custo
                                                                              2. Técnica de construção de algoritmos
                                                                                1. Preocupa-se a melhor opção LOCAL viável
                                                                                  1. Lembrar PACMAN/Come e não vomita
                                                                                    1. Algoritmos simples e de fácil implementação
                                                                                      1. Conjunto de candidatos
                                                                                        1. Escolhidos
                                                                                          1. Rejeitados
                                                                                          2. Passo
                                                                                            1. Escolhe qual elemento é mais viável
                                                                                              1. Sequencia de decisões para alcançar o prob.
                                                                                                1. Ou faz parte da decisão, ou é descartado
                                                                                              2. Lembrar do problema do troco
                                                                                            2. Backtracking
                                                                                              1. Busca exaustiva/completa
                                                                                                1. Método Sistemático
                                                                                                  1. Estratégia de resolução de problemas
                                                                                                    1. Se der errado, volta e escolhe outro caminho
                                                                                                    2. Medir eficiência
                                                                                                      1. Algoritmos diferentes resolvem o mesmo problema com a mesma eficiência?
                                                                                                        1. Complexidade computacional
                                                                                                          1. Custo = memória + tempo
                                                                                                            1. Análise
                                                                                                              1. Empírica
                                                                                                                1. Na execução
                                                                                                                  1. Analisa desempenho
                                                                                                                    1. custos não aparentes/alocação a memória
                                                                                                                      1. computadores e linguagens
                                                                                                                        1. resultado pode ser mascarado pelo hardware
                                                                                                                          1. pode existir outra execução no momento
                                                                                                                      2. Matemática
                                                                                                                        1. Estudo formal
                                                                                                                          1. Ideia por trás do algoritmo
                                                                                                                          2. Independente de hardware
                                                                                                                            1. Ignora detalhes de baixo nível (LP, hardware)
                                                                                                                              1. ident. como o algoritmo se comporta c entrada
                                                                                                                        Show full summary Hide full summary

                                                                                                                        Similar

                                                                                                                        OBJETIVOS E FINALIDADES DO INSTITUTOS FEDERAIS
                                                                                                                        ALOAN CABRAL0485
                                                                                                                        AQA Biology 8.1 structure of DNA
                                                                                                                        Charlotte Hewson
                                                                                                                        GCSE AQA Biology - Unit 3
                                                                                                                        James Jolliffe
                                                                                                                        Computer Systems
                                                                                                                        lisawinkler10
                                                                                                                        Bay of Pigs Invasion : April 1961
                                                                                                                        Alina A
                                                                                                                        1.11 Core Textiles
                                                                                                                        T Andrews
                                                                                                                        Characters in "An Inspector Calls"
                                                                                                                        Steve Whitmill
                                                                                                                        Conceptos Generales De Robótica
                                                                                                                        Cintia Mariuxi
                                                                                                                        COMUNICACION VERBAL Y NO VERBAL
                                                                                                                        ivan dreew
                                                                                                                        HABEAS CORPUS- CASO OLLANTA HUMALA Y NADINE HEREDIA
                                                                                                                        Silvia Maria Tito Ascue
                                                                                                                        Mapa Mental para Resumir y Conectar Ideas
                                                                                                                        Karol Gonzalez