Análise e Complexidade de Algoritmos

Description

Concursos Públicos IFS Mind Map on Análise e Complexidade de Algoritmos, created by Izabella Rezende on 31/10/2016.
Izabella Rezende
Mind Map by Izabella Rezende, updated more than 1 year ago
Izabella Rezende
Created by Izabella Rezende about 8 years ago
20
1

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
                                                                                                                        Psychology | Unit 4 | Addiction - Explanations
                                                                                                                        showmestarlight
                                                                                                                        AQA GCSE Physics Unit 2.5
                                                                                                                        Matthew T
                                                                                                                        Enzymes and Respiration
                                                                                                                        I Turner
                                                                                                                        FORM AND STRUCTURE: ROMEO AND JULIET
                                                                                                                        Sarah Soler
                                                                                                                        Astronomy Practice Quiz
                                                                                                                        cbruner
                                                                                                                        Ancient China - Glossary of Terms
                                                                                                                        Ms M
                                                                                                                        Contract Law
                                                                                                                        sherhui94
                                                                                                                        EXAM 1 - ENABLING FEATURES
                                                                                                                        kristinephil558
                                                                                                                        What are they doing?
                                                                                                                        Tamara Urzhumova
                                                                                                                        A child with a stiff neck
                                                                                                                        fatima alkhateeb