Análise e Projeto de Algoritmos - Apresentação

Análise e Projeto de Algoritmos Márcia Cappelle e Hebert Coelho com slides dos Profs Humberto Longo e Hugo Nascimento Instituto de Informática Universidade Federal de Goiás 2022 INFUFG APA 20221 M Cappelle H Coelho 1 1 de 828 Algoritmo Definição 11 Conjunto finito de instruções composta de uma ou mais operações válidas com o objetivo de resolver um problema específico Um algoritmo pode ser visualizado como uma ferramenta para resolver um problema computacional bem especificado Uma instância de um problema consiste na entrada conforme restrições do problema necessária para se calcular uma solução para o problema INFUFG APA 20221 M Cappelle H Coelho Introdução 2 81 de 828 Problemas e algoritmos Problema E conjunto das possíveis entradas S conjunto das saídas desejadas RE S relação entre entradas e saídas desejadas Operações válidas Solução A algoritmo correto e E e s RE S e A s INFUFG APA 20221 M Cappelle H Coelho Introdução 3 81 de 828 Algoritmos Problemas Critérios de análise Eficácia Correção Eficiência Tempo Espaço SimplicidadeClareza Otimalidade Limitações Tratabilidade Computabilidade INFUFG APA 20221 M Cappelle H Coelho Introdução 4 81 de 828 Eficiência Estática Tamanho da descrição do algoritmo Dinâmica Uso dos recursos computacionais Tempo Espaço Medidas Empíricas Analíticas TratabilidadeIntratabilidade INFUFG APA 20221 M Cappelle H Coelho Introdução 5 81 de 828 Tempo de execução 1 operação 1 microsegundo Tamanho Complexidade 20 50 100 200 500 1000 1000N 02s 05s 1s 2s 5s 1s 1000N log N 09s 3s 6s 15s 45s 10s 100N2 04s 25s 1s 4s 25s 2m 10N3 02s 1s 10s 1m 21m 27h Nlog N 4s 11h 220d 125S 5 108S 2N3 0001s 1s 27h 3 104S 2N 1s 35a 3 104S 3N 58m 2 109S INFUFG APA 20221 M Cappelle H Coelho Introdução 6 81 de 828 BIG BANG Explosão combinatorial 100 Número com 158 dígitos Número de prótons no universo conhecido tem 126 dígitos Número de microsegundos desde o BIG BANG tem 24 dígitos 126 24 150 120 Número com 200 dígitos 150 Número com 264 dígitos 200 Número com 375 dígitos INFUFG APA 20221 M Cappelle H Coelho Introdução 7 81 de 828 Crescimento INFUFG APA 20221 M Cappelle H Coelho Introdução 8 81 de 828 Tempo máximo de resolução do problema 1 operação 1 microsegundo Tempo 1s 102s 104s 106s 108s 1010s Complexidade 17m 26h 12d 3a 3S 1000N 103 105 107 109 1011 1013 1000N log N 14 102 77 103 52 105 39 107 31 109 26 1011 100N2 102 103 104 105 106 107 10N3 46 21 102 103 46 103 21 104 105 Nlog N 22 36 54 79 112 156 2N3 59 79 99 119 139 159 2N 19 26 33 39 46 53 3N 12 16 20 25 29 33 INFUFG APA 20221 M Cappelle H Coelho Introdução 9 81 de 828 Impacto da evolução tecnológica Função de Computador Computador Computador Complexidade atual 100 vezes mais 1000 vezes mais qtd de operações rápido rápido n N1 100N1 1000N1 n2 N2 10N2 316N2 n3 N3 464N3 10N3 n5 N4 25N4 394N4 2n N5 N5 664 N5 997 3n N6 N6 419 N6 629 INFUFG APA 20221 M Cappelle H Coelho Introdução 10 81 de 828 Eficácia Problema Algoritmo VERIFICAÇÃO SIM Solução Correta NÃO Erro INFUFG APA 20221 M Cappelle H Coelho Introdução 11 81 de 828 Correção parcial Pontos de verificação Invariantes Propriedade que relaciona as variáveis de um algoritmo a cada execução completa do laço Relação entre valores de variáveis que vale no início de cada iteração e não se altera de uma iteração para outra Relações invariantes explicam o funcionamento do processo iterativo e permitem provar por indução que ele tem o efeito desejado INFUFG APA 20221 M Cappelle H Coelho Introdução 12 81 de 828 Correção Estratégia típica 1 Mostrar que o invariante é válido no início da primeira iteração 2 Supor que o invariante é válido no início de uma iteração qualquer e provar que é válido no início da próxima iteração 3 Concluir que se o algoritmo para e o invariante é válido no início da última iteração então o algoritmo está correto As duas primeiras etapas implicam que o invariante é válido no início de qualquer iteração do algoritmo ou seja corresponde exatamente ao método de indução matemática INFUFG APA 20221 M Cappelle H Coelho Introdução 13 81 de 828 Soma dos elementos de um vetor Exemplo 12 SomaVetorV 7 Entrada Vetor V1n de inteiros e inteiro n Saida Soma S dos elementos de V 1S50 2 parai 1 até n faca 3 Se SVil 4 retorna S Invariante da linha 2 k1 No inicio da iteracgdo k S Vii il o8 INFUFG APA 20221 M Cappelle H Coelho IntroducSo 14 81 de 828 Soma dos elementos de um vetor Correcdo do algoritmo 1 No inicio da primeira iteracdo k 1leSO0 al V i Logo o invariante é valido 2 Suponha que no inicio de uma iteracdo k qualquer o invariante é valido ou seja SSc5 Vi O algoritmo adiciona Vk a S no inicio da iteragdo k 1 S ea V i Este exatamente o invariante na iterado k 1 3 Na altima iteracdo k n 1 ea correcdo do algoritmo é evidente ou seja o invariante diz que S 7i Vi eS 9 INFUFG APA 20221 M Cappelle H Coelho Introducdo 15 81 de 828 Análise de um algoritmo Determinar os recursos que o algoritmo requer Tempo computacional memória comunicação portas lógicas Análise demanda um modelo matemático de computador Modelo RAM Random Access Machine Quantidade infinita de memória Instruções sequenciais sem concorrência Instruções com o mesmo tempo de execução Tempo de execução número de instruções RAM INFUFG APA 20221 M Cappelle H Coelho Introdução 16 81 de 828 Análise de um algoritmo Modelo RAM não é completamente realístico Memória não é recurso infinito Nem todos os acessos à memória gastam o mesmo tempo Nem todas as operações matemáticas gastam o mesmo tempo Pipeline de instruções Outros processos Em geral o modelo RAM é suficiente para fornecer resultados relativamente realísticos INFUFG APA 20221 M Cappelle H Coelho Introdução 17 81 de 828 Análise de um algoritmo Insertion Sort Tempo de execução depende de vários fatores o tamanho da entrada entrada parcialmente ordenada etc Em geral o interesse está no tempo de execução em função do tamanho da entrada Uma possibilidade é contar a quantidade de instruções RAM necessária para encontrar a solução e multiplicála pelo tempo de uma instrução Em um primeiro momento no entanto faremos uma análise mais detalhada INFUFG APA 20221 M Cappelle H Coelho Introdução 18 81 de 828 Insertion Sort Exemplo 13 0 1 2 3 4 5 6 7 8 9 10862 81068264 6102846 21048 16410 41611 1811161412 111814161214 14181216 1218 INFUFG APA 20221 M Cappelle H Coelho Introdução 19 81 de 828 Análise do insertionSort 1 v o i d i n s e r t i o n S o r t i n t v i n t n 2 3 i n t i 0 4 i n t j 1 5 i n t aux 0 6 w h i l e j n 7 8 aux v j 9 i j 1 10 w h i l e i 0 v i aux 11 12 v i 1 v i 13 i i 1 14 15 v i 1 aux 16 j j 1 17 18 Invariante da Linha 6 No início da iteração k a sequência v0 vk 1 está ordenada INFUFG APA 20221 M Cappelle H Coelho Introdução 20 81 de 828 Correção do insertionSort Demonstração por indução em k Base Para k 1 claramente verdadeiro HI Suponha que no início de uma iteração k qualquer o invariante é verdadeiro ou seja a sequência v0 vk 1 está ordenada Note que k j e que quando o teste da Linha 10 falha então i 0 ou vi aux Nos dois casos a sequência vi 1 vk 1 já ordenada está deslocada uma posição para vi 2 vk aux na posição i 1 Linha 15 deixa a sequência v0 vk ordenada Logo no início da iteração k 1 a sequência v0 vk 1 1 está ordenada Na última iteração k j n e o invariante diz que o vetor v0 vn 1 está ordenado INFUFG APA 20221 M Cappelle H Coelho Introdução 21 81 de 828 Analise do insertionSort P ciC1g custo de execucdo das Linhas 118 respectivamente Tn tempo de execucdo para n elementos t mr de vezes que a condicdo da Linha 10 é verificada para o valor j Tn c3c44 05 c6n cgn 1 c9n 14 n1 n1 n1 C10 t C12 t 1 13 t 1 jl jl jl C15n aad 1 Cign oa 1 cg c4 65 cgn cg 9 C15 Cign 1 n1 n1 cio Dy ty cz e13 do tj D jl j1 28 9 INFUFG APA 20221 M Cappelle H Coelho Introducdo 22 81 de 828 Analise do insertionSort Custo por linha 1 void insertionSort int v int n Custo 2 0 3 int i 0 c3 4 int j 1 C4 5 int aux 0 C5 6 while j n cen 7 0 8 aux vj cgn 1 9 i j 1 cgn 1 10 while i 0 vi aux c10 eo ty 11 0 12 vi 1 vi e12 Fa ty 1 13 ii 1 nlyy a O i t 1 15 vi 1 aux c1sn 1 16 sith c1en 1 17 0 ig 0 e S 9 INFUFG APA 20221 M Cappelle H Coelho Introduc3o 23 81 de 828 Análise do insertionSort Custo por linha melhor caso tj 1 j 1 v o i d i n s e r t i o n S o r t i n t v i n t n 2 3 i n t i 0 4 i n t j 1 5 i n t aux 0 6 w h i l e j n 7 8 aux v j 9 i j 1 10 w h i l e i 0 v i aux 11 12 v i 1 v i 13 i i 1 14 15 v i 1 aux 16 j j 1 17 18 Custo 0 c3 c4 c5 c6n 0 c8n 1 c9n 1 c10n 1 0 0 0 0 c15n 1 c16n 1 0 0 INFUFG APA 20221 M Cappelle H Coelho Introdução 24 81 de 828 Análise do insertionSort Custo por linha pior caso tj j 1 j 1 v o i d i n s e r t i o n S o r t i n t v i n t n 2 3 i n t i 0 4 i n t j 1 5 i n t aux 0 6 w h i l e j n 7 8 aux v j 9 i j 1 10 w h i l e i 0 v i aux 11 12 v i 1 v i 13 i i 1 14 15 v i 1 aux 16 j j 1 17 18 Custo 0 c3 c4 c5 c6n 0 c8n 1 c9n 1 c10nn 12 1 0 c12nn 12 c13nn 12 0 c15n 1 c16n 1 0 0 INFUFG APA 20221 M Cappelle H Coelho Introdução 25 81 de 828 Análise do insertionSort Custo por linha caso médio tj j2 1 j 1 v o i d i n s e r t i o n S o r t i n t v i n t n 2 3 i n t i 0 4 i n t j 1 5 i n t aux 0 6 w h i l e j n 7 8 aux v j 9 i j 1 10 w h i l e i 0 v i aux 11 12 v i 1 v i 13 i i 1 14 15 v i 1 aux 16 j j 1 17 18 Custo 0 c3 c4 c5 c6n 0 c8n 1 c9n 1 c10nn 14 n 1 0 c12nn 14 c13nn 14 0 c15n 1 c16n 1 0 0 INFUFG APA 20221 M Cappelle H Coelho Introdução 26 81 de 828 Análise do insertionSort 1 tj j 1 j 1 n 1 Melhor Caso sequência ordenada tj 1 j Tn c3 c4 c5 c6n c8 c9 c10 c15 c16n 1 an b para constantes a b Pior Caso sequência em ordem inversa tj j 1 j Tn c3 c4 c5 c6n c8 c9 c15 c16n 1 c10nn 12 1 c12 c13nn 12 an2 bn c para constantes a b c Caso Médio sequência em ordem qualquer tj j2 1 j Tn c3 c4 c5 c6n c8 c9 c15 c16n 1 c10nn 14 n 1 c12 c13nn 14 an2 bn c para constantes a b c INFUFG APA 20221 M Cappelle H Coelho Introdução 27 81 de 828 Análise do insertionSort Se c1 c2 c18 1 1 tj j 1 j 1 n 1 Melhor Caso sequência ordenada tj 1 j Tn c3 c4 c5 c6n c8 c9 c10 c15 c16n 1 6n 2 Pior Caso sequência em ordem inversa tj j 1 j Tn c3 c4 c5 c6n c8 c9 c15 c16n 1 c10nn 12 1 c12 c13nn 12 32n2 94n 1 Caso Médio sequência em ordem qualquer tj j2 1 j Tn c3 c4 c5 c6n c8 c9 c15 c16n 1 c10nn 14 n 1 c12 c13nn 14 34n2 214n 2 INFUFG APA 20221 M Cappelle H Coelho Introdução 28 81 de 828 Livros Texto T H Cormen C E Leiserson e R L Rivest Introduction to Algorithms McGrawHill New York 1990 C H Papadimitriou U V Vazirani e S Dasgupta Algoritmos McgrawHill Brasil 2009 U Manber Algorithms A Creative Approach AddisonWesley 1989 D E Knuth The Art of Computer Programming Volume 1 Fundamental Algorithms Addison Wesley 1998 D E Knuth The Art of Computer Programming Volume 2 Sorting and Searching Addison Wesley 1998 N Ziviani Projeto de Algoritmos com Implementações em Pascal e C Editora Thomson 2a Edição 2004 INFUFG APA 20221 M Cappelle H Coelho Bibliografia 828 828 de 828