Algoritmos

...2007 22:39 Algoritmos 29Algoritmos e compilação Codificação/compilação/execução: permite executar um algoritmo em um computador obtém solução para problemas rapidamente (?!) Algoritmo: centro do universo demais componentes são acessórios Ciências da Computação: estudo de algoritmos Inteligência de um computador: algoritmos programados28/2/2007 22:39 Algoritmos 30Algoritmos 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 Afaça B. 28/2/2007 22:39 Algoritmos 31Algoritmos 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 LP28/2/2007 22:39 Algoritmos 32Algoritmos e linguagens de programaçãoComo 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 tipo28/2/2007 22:39 Algoritmos 33Algoritmos e linguagens de programaçãoQue tipos de dados (em geral) estão presentes em uma LP? Tipos básicos: Valores inteiros, valores reais (ou quase.) valores binários (0 ou 1) Exemplos: X é uma variável de tipo inteiro (posição e memória onde se pode armazenar inteiros): X 1: carrega valor 1 na posição de memória correspondente a X X 2*X: recupera o valor armazenado na posição de memóriacorr­espondente a X, multiplica por 2 e (re)armazena o resultado na mesma posição de memória associada a X X é uma variável de tipo real: X 0.7856: carrega esse valor em X X cos(X): calcula coseno de X e recarrega o resultado em X28/2/2007 22:39 Algoritmos 34Algoritmos e linguagens de programaçãoQue tipos de dados (em geral) estão presentes em uma LP (cont): Vetores: seqüência indexada de valores de mesmo tipoExemplo: X é um vetor, indexado de 1 a 5, de tipo inteiro?????54321XX[2] 0 ???0?54321XX[5] X[2] + 3 3??0?54321XI é variável de tipo inteiro e seu valor é 4X[I-1] X[2] X[I+1] 3?-30?54321X28/2/2007 22:39 Algoritmos 35Algoritmos e linguagens de programaçãoProblema: 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 direitaExemplo:71218101554321X18151­210754321XentradasaídaIdéia: ?!?28/2/2007 22:39 Algoritmos 36Algoritmos e linguagens de programaçãoSe 3 primeiras celas ordenadas: 7121815105­4321Xatual=31. Próximo valor no vetor é X[atual+1] 122. Procura posição de 12 na parte já ordenada:deve entrar na posição 2712181510­54321atual=3procura=228/2/2007 22:39 Algoritmos 37Algoritmos e linguagens de programação4. Desloca bloco para direita:71218151054321atu­alprocura3. Salva valor de X[atual+1] na variável PROX:PROX X[atual+1] 12 71218151054321atualp­rocura71815151054321atualprocura28/2/2007 22:39 Algoritmos 38Algoritmos e linguagens de programação718151210­54321atualprocura5. Insere valor de PROX e avança atual:X[procura] PROX atual atual+1Ordenação avançou de uma posição para a direitaRepete o processo:71815121054321atu­alprocura4 primeiras celas estão ordenadas!18151210754321atua­lprocura28/2/2007 22:39 Algoritmos 39Algoritmos e linguagens de programaçãoComo começar ? Indicando que a parte ordenada é inicialmente vazia712181015543­21atualAté posição (atual-1) tudo já ordenado: trivialmente­Precisamos escrever essa idéia numa LP !28/2/2007 22:39 Algoritmos 40Algoritmos e linguagens de programação­Traduzindo numa LP: (assumindo tamanho do vetor é N 1)atual 1faça prox x[atual+1] procura 1enquanto (prox x[procura]) faça procura procura+1se (procura atual) então desloca atualenquanto (desloca procura) faça x[desloca+1] x[desloca] desloca desloca-1 x[procura] prox exatamente (N-1) vezes28/2/2007 22:39 Algoritmos 41Algoritmos 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 42Algoritmos correçãoO algoritmo corretamente soluciona o...

Descrição: Etiquetas: Endereço Permanente: