Algoritmos

Algoritmos

1. Definição

   • Procedimento computacional que tem como entrada um/conjunto de valores e produz algum/conjunto de valores como saída
   • Uma ferramenta para resolver problema computacional

2. termos

   • permutação
     • reordenação
   • Instância
     • entrada necessária para calcular a solução
   • Problemas NP-completos
     • Problemas que não se conhece nenhuma solução eficiente
     • problema do caixeiro viajante

3. Eficiência em ordenação

   • Inserção
     • c1*n^2
     • insertion-sort
       • para cada elemento do vetor, apartir da segunda posição, ele verifica em que posição do vetor anterio r(numeros que já estão ordenados antes dele a ele deve ficar) esse número deve ficar
       • for j<- (2 to n)
         • para j recebendo de 2 a n
         • do key <- A[j]
           • i <- (j-1)
             • i vai percorrer o vetor para achar o lugar da key
             • while i > 0 and A[i] > key
               • passar pelo vetor de trás para frente/do maior pro menor
               • do A[i+1] <- A[i]
                 • i <- i-1
                   • A[i+1] = key
                 • inverte os valores pois A[i+1] é menor que A[i]
           • key é o numero que está sendo analisado
       • ordenação in-place
   • Intercalação
     • c2*n*lg(n)
     • magesort
       • Melhor que o insertionsort quando o n(intens a serem ordenados) é grande

4. Tipos de analises

   • Wort-case
     • é dado pela entrada que faz o programa executar a maior qntidade de operações possíveis
   • Best-case
     • é dado pela entrada que faz o programa executar a menor qntidade de operações possíveis
   • Average-case
     • Tem a ver com probabilidade

5. Invariantes de laços

   • Asserção lógica
   • usado para verificar se o algoritimo fez o desejado
   • Ex em puthon: assert new_queue not in self._list
   • Deve satisfazer 3 condições
     • Inicialização: é verdadeira antes da primeira iteração do laço
     • Manutenção: se ela é verdadeira antes de uma iteração de laço, então ela permanecerá verdadeira após a iteração
     • Terminação: quando o laço termina, a invariante fornece uma propriedade útil para provar que o algoritmo está correto

Images and files in the map