Baixe Algoritmos e outras Notas de estudo em PDF para Algoritmos, somente na Docsity! 28/2/2007 22:39 Algoritmos 1 ALGORITMOS Parte I: 1. O que são? 2. O que os caracteriza Parte II: 3. Algoritmos e computadores 4. O processo de compilação 5. Algoritmos e linguagens de programação Parte III: 6. Algoritmos resolvendo problemas 7. Algoritmos e correção 8. Resolvem qualquer problema? 9. Adianta executá-los? 10.Nossa ignorância 28/2/2007 22:39 Algoritmos 2 Algoritmos O que são? • Algoritmo é uma receita para resolução de um problema • Exemplo: Problema: preparar “bifes à milaneza” Algoritmo: precisamos descrever a receita 28/2/2007 22:39 Algoritmos 5 Algoritmos O que são? • Objetos “produzidos” (saída): • bifes • Objeto que “controla” o processo (receita): • algoritmo 28/2/2007 22:39 Algoritmos 6 Algoritmos O que são? Idéia AlgoritmoProblema Algoritmo Hardware entrada saída 28/2/2007 22:39 Algoritmos 7 Algoritmos O que são? Século IX (800-899 DC), península arábica/Pérsia: Matemático Mohammed al-Khowârizmî Cria regras passo-a-passo para se fazer aritmética com algarismos decimais Em latim: al-Khowârizmî algorismus algoritmo, algorithm, . . . Primeiro algoritmo: Euclides (300 . . . 400 BC): algoritmo para obter o máximo divisor comum de dois inteiros positvos 28/2/2007 22:39 Algoritmos 10 Algoritmos O que são? Executando a receita: caso particular onde M=36 e N=21 Passo M N Comentários --- 36 21 1 36 21 36 <> 21 2 15 21 36 - 21 = 15 1 15 21 15 <> 21 2 15 21 não executado: 15 < 21 3 15 6 21 - 15 = 6 1 15 6 15 <> 6 2 9 6 15 - 6 = 9 1 9 6 9 <> 6 2 3 6 9 – 6 = 3 1 3 6 3 <> 6 2 3 6 3 < 6; não executado 3 3 3 6 - 3 = 3 1 3 3 MDC é 3. Páre. 1. Se M=N, então MDC é M (ou N); páre 2. Caso a): se ( M>N ) então substitua M por (M-N) e repita a partir do passo 1 3. Caso b): se ( N>M ) então substitua N por (N-M) e repita a partir do passo 1 Algoritmo 28/2/2007 22:39 Algoritmos 11 Algoritmos O que caracteriza? 1. Algoritmo é formado por um texto finito: É a receita dada. 28/2/2007 22:39 Algoritmos 12 Algoritmos O que caracteriza? 2. O texto é composto por instruções elementares: Elementar depende do contexto: – “ ... juntar dois ovos ...” é elementar para um cozinheiro – “ ... substituir M por (M-N) ...” é elementar para quem domina aritmética básica – “ ... se hoje você puder provar que a cotação do dólar vai subir 10% no próximo mês, compre $ 1.000,00 ...” não é elementar para mortais normais 28/2/2007 22:39 Algoritmos 15 Algoritmos O que caracteriza? Exemplo: algoritmo do MDC sempre pára quando M >= 1 e N >= 1: – Cada execução dos passos 2 ou 3, M ou N diminuem; logo (M+N) diminui. – M e N sempre são >= 1 iniciam assim; M - N >= 1, se M > N N - M >= 1, se N > M – Não podemos passar de M=N=1 Nesse caso, MDC = 1 e pára. 1. Se M=N, então MDC é M (ou N); páre 2. Caso a): se ( M>N ) então substitua M por (M-N) e repita a partir do passo 1 3. Caso b): se ( N>M ) então substitua N por (N-M) e repita a partir do passo 1 28/2/2007 22:39 Algoritmos 16 Algoritmos O que caracteriza? Exemplo: e com dados inválidos? Iniciando com M = 3 e N = -1 Passo M N Comentários 1 3 -1 -1 <> 3 2 4 -1 3 > -1; 3 - (-1) = 4 1 4 -1 -1 <> 4 2 5 -1 4 <> -1; 4 - (-1) = 5 1 5 -1 -1 <> 5 2 6 -1 5 <> -1; 5 - (-1) = 6 . . . repete esse padrão não pára não vai parar nunca 1. Se M=N, então MDC é M (ou N); páre 2. Caso a): se ( M>N ) então substitua M por (M-N) e repita a partir do passo 1 3. Caso b): se ( N>M ) então substitua N por (N-M) e repita a partir do passo 1 28/2/2007 22:39 Algoritmos 17 Algoritmos ... e computadores • Algoritmo: programa, software ... • Computador, HD, disquete, ... : hardware, executores, atores • Entrada: teclado, mouse, sensores, ... • Saída: monitor, impressora, ... 28/2/2007 22:39 Algoritmos 20 Algoritmos ... e computadores Exemplo: Problema: dado um número N >= 0, calcular 2^N entrada N >= 0 idéia ?? 2^N saída 28/2/2007 22:39 Algoritmos 21 Algoritmos ... e computadores Exemplo (cont): N vezes Idéia: 2^N = 1x2x2x . . . x2 Algoritmo: 1. Copie o valor de N para Z 2. Copie o valor 1 para P 3. Enquanto (Z > 0) faça 3.1 Novo valor de P é 2x(valor atual de P) 3.2 Novo valor de Z é (valor atual de Z) - 1 (quando N = 0, 2^0 = 1) 4. Resposta está em P; páre 28/2/2007 22:39 Algoritmos 22 Algoritmos ... e computadores Exemplo (cont): Escrevendo texto numa LP, p. ex. em C 1. Copie o valor de N para Z 2. Copie o valor 1 para P 3. Enquanto (Z > 0) faça 3.1 Novo valor de P é 2x(valor atual de P) 3.2 Novo valor de Z é (valor atual de Z) - 1 . . . . Z = N; P = 1; while (Z>0) do { P = 2xP; Z = Z – 1; } . . . . 4. Resposta está em P; páre 28/2/2007 22:39 Algoritmos 25 Algoritmos ... e compilação Arquitetura básica simplificada (cont): • Formado por memória (grande), processador e circuitos de entrada e de saída • Processador executa instruções elementares específicas dessa máquina – inclusive armazenamento e recuperação de dados da memória • Processador e circuitos de e/s recebem dados das entradas e exibem dados nas saídas 28/2/2007 22:39 Algoritmos 26 Algoritmos ... e compilação Compilação: • Processo de traduzir programas escritos em uma particular LP para código em instruções básicas de uma máquina específica • Tradução de LP para linguagem de máquina: – Dificuldades: processo laborioso, entediante e sujeito a erros. – Solução: Escrever um programa para fazer a tradução compiladorEsse programa é um 28/2/2007 22:39 Algoritmos 27 Algoritmos ... e compilação Existem milhares de LPs: – FORTRAN: científica, mais antiga – ALGOL, C, PASCAL: estruturadas, generalistas – C++, C#, JAVA : lidam com tecnologia de objetos – LISP, PROLOG: voltadas para IA – . . . (muitas outras) Para cada LP e cada computador (processador), um compilador específico 28/2/2007 22:39 Algoritmos 30 Algoritmos ... e linguagens de programação • Pessoas codificam algoritmos em LPs • Que tipos de instruções (em geral) estão presentes em uma LP? – Atribuição: A = E; – Seqüenciamento: . . . faça A; faça B; . . . . . . faça A; faça B; . . . 28/2/2007 22:39 Algoritmos 31 Algoritmos ... e linguagens de programação • Tipos de instruções (em geral) em uma LP (cont): – Desvio condicional: . . . se (A é verdade) então (faça B) senão (faça C); . . . . . . se (A é verdade) então (faça B); . . . – Iterações: . . . faça A exatamente N vezes; . . . . . . repita A até que (Q seja verdade); . . . . . . enquanto (Q é verdade) faça A; . . . – Inúmeras outras, mais sofisticadas, dependendo da LP 28/2/2007 22:39 Algoritmos 32 Algoritmos ... e linguagens de programação Como dados são representados e manipulados em LPs? • Valores dos dados são armazenados na memória • A memória é referenciada através de variáveis: – Variável: um nome simbólico que designa uma, ou mais, posições na memória • Exemplo: X, Z, D3, CASA_DE_PEDRA, . . . – A cada variável está associado um tipo de dados • O número de posições de memória ocupadas pela variável depende do seu tipo • As operações e manipulações permitidas com o valor e uma variável dependem de seu tipo 28/2/2007 22:39 Algoritmos 35 Algoritmos ... e linguagens de programação Problema: temos um vetor de dimensão N, onde cada cela contém um número inteiro. Devemos ordenar o vetor em ordem crescente, i.e., os valores contidos nas celas crescem da esquerda para a direita Exemplo: 712181015 54321 X 181512107 54321 X entrada saída Idéia: ?!? 28/2/2007 22:39 Algoritmos 36 Algoritmos ... e linguagens de programação Se 3 primeiras celas ordenadas: 712181510 54321 X atual=3 1. Próximo valor no vetor é X[atual+1] = 12 2. Procura posição de 12 na parte já ordenada: deve entrar na posição 2 712181510 54321 atual=3 procura=2 28/2/2007 22:39 Algoritmos 37 Algoritmos ... e linguagens de programação 4. Desloca bloco para direita: 712181510 54321 atualprocura 3. Salva valor de X[atual+1] na variável PROX: PROX = X[atual+1] = 12 712181510 54321 atual procura 718151510 54321 atualprocura 28/2/2007 22:39 Algoritmos 40 Algoritmos ... e linguagens de programação Traduzindo numa LP: (assumindo tamanho do vetor é N >= 1) atual = 1; faça { prox = x[atual+1]; procura = 1; enquanto (prox > x[procura]) faça procura = procura+1; se (procura <= atual) então { desloca = atual; enquanto (desloca >= procura) faça { x[desloca+1] = x[desloca]; desloca = desloca-1; } } x[procura] = prox; } exatamente (N-1) vezes; 28/2/2007 22:39 Algoritmos 41 Algoritmos ... resolvendo problemas • Entender bem o problema a ser resolvido: – separar dados de entrada válidos de inválidos – definir como será representada a solução na saída • Criar uma idéia para resolver o problema – desenvolver o algoritmo – processo criativo, rascunho, lápis e papel ... – simular execução do algoritmo em casos de fronteira – verificar correção e término • Traduzir a idéia para uma LP, escrevendo um programa – restrito aos comandos e tipos de dados da LP • ==> Criar o algoritmo adaptado à LP – estruturas que correspondam a tipos de dados da LP – ações facilmente programáveis na LP • Editar/compilar/executar o programa – processo iterativo para retirar erros (algoritmo e código) 28/2/2007 22:39 Algoritmos 42 Algoritmos ... correção O algoritmo corretamente soluciona o problema? Provar um teorema (como em matemática) mostrando que o algoritmo é correto: – processo de “convencimento dos pares” – possível exibir uma “prova formal” da correção? – Dificuldades: • precisão e rigor ao descrever a execução do algoritmo • especificar formalmente dados de entrada e a saída – Solução: • prover uma semântica (descrição formal dos efeitos dinâmicos) para as instruções da LP • usar linguagens de especificação de dados (lógicas, ...) 28/2/2007 22:39 Algoritmos 45 Algoritmos ... correção Exemplo (simplificado): problema da ordenação do vetor Semântica das instruções da LP: alteram a memória Memória: posições (variáveis) usadas no programa [(n, v1, ..., vn), (atual, desloca, prox, procura)] Cada instrução da LP altera a memória [(n, v1, ..., vn), (atual, desloca, prox, procura)] instrução [(n´, v1´, ..., vn´), (atual´, desloca´, prox´, procura´)] 28/2/2007 22:39 Algoritmos 46 Algoritmos ... correção Exemplo: instrução atual = 1 [(n, v1, ..., vn), (atual, desloca, prox, procura)] atual = 1 [(n´, v1´, ..., vn´), (atual´, desloca´, prox´, procura´)] n´=n; vi´=vi, 1 ≤ i ≤ n; desloca´=desloca; prox´=prox; procura´=procura atual´=1; Outras instruções da LP: transformações mais sofisticadas, porém semelhantes 28/2/2007 22:39 Algoritmos 47 Algoritmos ... correção Execução correta do programa: [(n, v1, ..., vn), (atual, desloca, prox, procura)] instruções do programa [(n´, v1´, ..., vn´), (atual´, desloca´, prox´, procura´)] n ∈ Ν vi ∈ Ζ, 1 ≤ i ≤ n n´= n v´i ≤ v´(i+1), 1 ≤ i < n v´1, . . .,v´n é uma permutação de v1,. . . ,vn (configuração final da memória) (configuração inicial da memória) 28/2/2007 22:39 Algoritmos 50 Algoritmos ... resolvem qualquer problema? Questão: Dado um problema P, sempre haverá um algoritmo que resolva P corretamente? • P deve ser um problema prático, fácil de enunciar - ordenar um vetor de números, - calcular produto de matrizes, . . . • O algoritmo A que resolve P deve funcionar corretamente em todas as (infinitas) entradas de P - todos os vetores, carregados com inteiros quaisquer - quaisquer duas matrizes de quaisquer dimensões compatíveis entre si 28/2/2007 22:39 Algoritmos 51 Algoritmos ... resolvem qualquer problema? A Ciência da Computação tem a resposta para a questão NÃO. Há problemas para os quais NÂO EXISTE algoritmos capazes de resolve-los corretamente. SURPRESA ! ! ! Com mais tecnologia (computadores mais rápidos, mais memória) e dado tempo suficiente para rodar o programa, poderemos resolver esses problemas, no futuro, certo? NÃO Computador nenhum vai resolver esses problemas, nem hoje, nem amanhã, nem nunca; nem aqui, nem em Marte, em lugar algum; rodando qualquer programa por quanto tempo quiser (anos,séculos, ...) 28/2/2007 22:39 Algoritmos 52 Algoritmos ... resolvem qualquer problema? Um problema indecidível (insolúvel) [Harel, “Computers Ltd.”]: Dado um conjunto finito T de ladrilhos quadrados: Problema: podemos ladrilhar qualquer grade quadrada com ladrilhos de tipo T, casando as cores das faces que se tocam? SIM ou NÃO? • pode usar quantos ladrilhos quiser, de cada tipo • os ladrilhos não podem ser girados 28/2/2007 22:39 Algoritmos 55 Algoritmos ... resolvem qualquer problema? Um problema decidível (solúvel) [Harel, “Computers Ltd.”]: Dado um conjunto finito T de ladrilhos quadrados: Problema: podemos ladrilhar um caminho na grade, partindo de “I” e chegando em “F”, com ladrilhos de tipo T, e casando as cores das faces que se tocam? SIM ou NÃO? • pode usar quantos ladrilhos quiser, de cada tipo • os ladrilhos não podem ser girados Dadas duas posições (“I” e “F”) na grade infinita do plano 28/2/2007 22:39 Algoritmos 56 Algoritmos ... resolvem qualquer problema? Exemplo: I F Com esses ladrilhos Com essas posições I e F SIM! 28/2/2007 22:39 Algoritmos 57 Algoritmos ... resolvem qualquer problema? Problema de ladrilhar um caminho entre duas posições: EXISTE um algoritmo que decide se há, ou se não há, o caminho entre as duas posições dadas, usando ladrilhos do conjunto dado Podemos exibir o algoritmo e mostrar sua correção e terminação, não importa qual o conjunto T dado e não importa quais as posições I e F dadas 28/2/2007 22:39 Algoritmos 60 Algoritmos ... resolvem qualquer problema? Outro exemplo: verificador de “loops” em programas em C programa P esp. de entr. E ALGORITMO [?!] SIM: P sempre pára para todas as entr. válidas NÃO: P não pára com algumas das entr. válidas 28/2/2007 22:39 Algoritmos 61 Algoritmos ... resolvem qualquer problema? Problema de verificar “loops” com entradas válidas: NENHUM computador JAMAIS vai conseguir testar se, dado um programa qualquer P (escrito em C), dada uma especificação das entradas válidas para P, SE EXISTE alguma entrada válida que force P a não parar (P entraria em “loop”) quando executa com aquela entrada. Podemos demonstrar isso, matematicamente! O algoritmo (programa verificador) não existe! 28/2/2007 22:39 Algoritmos 62 Algoritmos ... adianta executá-los? Dado um problema P, e conseguido um algoritmo A para P, então podemos resolver qualquer instância de P, com dados de entrada E, executando A sobre os dados E. CORRETO? NEM SEMPRE: – ao executar sobre E, o algoritmo A pode precisar de um tempo muito longo (anos, séculos, milhões de séculos, ...) – ao executar sobre E, o algoritmo A pode precisar de um muita memória (vários GBs, muitos milhões de GBs, ...) Nesses casos, A é um algoritmo imprestável! 28/2/2007 22:39 Algoritmos 65 Algoritmos ... adianta executá-los? Problema: Será que o jogador J1 tem uma estratégia vencedora? Regras de movimentos: – J1 inicia; depois os jogadores e alternam. – Em um movimento, um jogador pode percorrer qualquer trecho (concatenado) de mesma cor, partindo de uma posição ocupada por si • não pode passar por intersecções ocupadas (por si ou pelo adversário) • ponto final deve estar também desocupado – Vencedor: aquele jogador que chegar a um ponto final primeiro I1 I1 I2 I2 F1 F1 F2 F2 J1 TEM estratégia (seq. de movimentos) sempre vencedora Nesse mapa, nessas posições iniciais e finais 28/2/2007 22:39 Algoritmos 66 Algoritmos ... adianta executá-los? Jogo do bloqueio: Algoritmo A: – De forma sistemática, tente todas as possibilidades de seqüências alternadas de movimentos, começando com J1 Possível: – número finito de possibilidades Dificuldade: – o número de possibilidades é enorme • para cada movimento de J1, deve tentar todos os movimentos de J2 • para cada movimento de J2, deve tentar todos os movimentos de J1 28/2/2007 22:39 Algoritmos 67 Algoritmos ... adianta executá-los? Estimando o tempo de execução do algoritmo A: Uma quantidade, N, mede o “tamanho” (num. de bits na representação) da entrada -- por exemplo, N pode ser o número de intersecções, ou o número de vias, ou .... Tempo de execução dado pela contagem do número de passos elementares que A executa, no pior caso, para entradas de tamanho N é dado pela função f(N) = 2^N. 28/2/2007 22:39 Algoritmos 70 Algoritmos ... adianta executá-los? séculos 445 dígitos séculos 185 dígitos séculos 70 dígitos 3,3 trilhões anos 2,8s séculos 45 dígitos séculos 400 trilhões 35,7anos1s1ms 3,7dias2,8h5,2m3,2s0,1s 40s10ms2,5ms0,4ms0,1 ms 200100502010N f(N) N^N 2^N N^5 N^2 com um milhão de passos por segundo 28/2/2007 22:39 Algoritmos 71 Algoritmos ... adianta executá-los? Tempos de execução, de pior caso: • Polinomiais: resultam em algoritmos eficientes • Exponenciais: resultam em algoritmos não eficientes Problemas tratáveis: têm algoritmos polinomiais Problemas intratáveis: não têm algoritmos polinomiais Problema do bloqueio: é intratável 28/2/2007 22:39 Algoritmos 72 Algoritmos ... nossa ignorância Dado um problema P, como saber se é tratável? SURPRESA!!! Para muitos problemas de grande interesse prático, não sabemos se são tratáveis ou não! Essa é um das maiores questões em aberto em Ciências da Computação! 28/2/2007 22:39 Algoritmos 75 Algoritmos ... nossa ignorância 3 6 10 4 7 5 4 7 9 9 3 10 4 2 8 I F 3+6+10+4+2+3 = 28K=29 3 6 4 3 10 2 I F SIM 28/2/2007 22:39 Algoritmos 76 Algoritmos ... nossa ignorância 3 6 10 4 7 5 4 7 9 9 3 10 4 2 8 I F Com esse custo não é possível K=25 I F NÃO ??? 28/2/2007 22:39 Algoritmos 77 Algoritmos ... nossa ignorância Algoritmos para o problema do caixeiro viajante: • Partindo da posição I, tente todas as possibilidades que fiquem dentro do custo K – Se achar um caminho até F, responda SIM – Se não achar, responda NÃO • Número de possibilidades é finito – algoritmo corretamente resolve o problema • Número de possibilidades é muito grande – tempo de execução é exponencial no número de cidades • O algoritmo é impraticável