Análise e Complexidade de Algoritmos

Descrição

Concursos Públicos IFS Mapa Mental sobre Análise e Complexidade de Algoritmos, criado por Izabella Rezende em 31-10-2016.
Izabella Rezende
Mapa Mental por Izabella Rezende, atualizado more than 1 year ago
Izabella Rezende
Criado por Izabella Rezende aproximadamente 8 anos atrás
20
1

Resumo de Recurso

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

                                                                                                                        Semelhante

                                                                                                                        OBJETIVOS E FINALIDADES DO INSTITUTOS FEDERAIS
                                                                                                                        ALOAN CABRAL0485
                                                                                                                        Guia para Estudar Física
                                                                                                                        Alessandra S.
                                                                                                                        Português para o ENEM
                                                                                                                        Alessandra S.
                                                                                                                        Descobrimento do Brasil
                                                                                                                        Alessandra S.
                                                                                                                        Plano de estudos ENEM - Parte 2 *Exatas/Biológicas
                                                                                                                        GoConqr suporte .
                                                                                                                        Anatomia: sistema esquelético I
                                                                                                                        Natália Abitbol
                                                                                                                        Nutrição para o Cérebro e a Memória
                                                                                                                        Joana Meira
                                                                                                                        Empreendedorismo - Contextualização da disciplina - Gestão
                                                                                                                        Ana Roberta Andrade
                                                                                                                        ANATOMOFISIOLOGIA - SISTEMA NERVOSO CENTRAL
                                                                                                                        Keyla Lima