Baixe o app para aproveitar ainda mais
Prévia do material em texto
Universidade Federal da Grande Dourados Faculdade de Ciências Exatas e de Tecnologias Curso de Bacharelado em Sistemas de Informação Algoritmos Introdução à Lógica de Programação Profª Janne Oeiras Lachi 1 O estudo de algoritmos ` Fundamental para o desenvolvimento de sistemas computacionais ` Um programa de computador ou simplesmente software é representado pelas instruções e dados que algum ser humano definiu e que ao serem executados por alguma máquina cumprem algum objetivo. Um programa de computador é um produto resultante da atividade intelectual de um programador. Essa atividade, por sua vez, depende de um treinamento prévio em abstração e modelagem de problemas, bem como o uso da lógica na verificação das soluções. Souza, M. A. F. et al., 2004 2 O desenvolvimento de software ` Diferentes objetivos: ` Simular o funcionamento de um circuito digital; ` Comandar um robô em uma linha de montagem; ` Gerenciar informações em uma empresa; ` Controle de tráfego aéreo, metrô, trem... Figura 1: Simplificação do processo de construção de um software (Souza, M. A. F. et al., 2004) 3 Algoritmos e problemas ` Diferentes objetivos: ` Prover a interação social via Internet; ` Controlar empréstimo e devolução de livros em bibliotecas; ` Guardar nomes em uma agenda de celular; ` Apresentar uma rota traçada em um aparelho GPS. Figura 2: Resolução de problemas, algoritmo e programação (Siebra e da Silva, 2009) 4 Ação (Farrer et al., 2008) ` Ação é um acontecimento que, a partir de um estado inicial, após um período de tempo finito, produz um estado final previsível e bem definido. ` Exemplo: ` Escolher um número inteiro L, sendo L > 0 ` Escrever a seqüência de números pares inferiores a L ` Miriam: 15 Seqüência escrita: 2 4 6 8 10 12 14 ` Eduardo: 3 Seqüência escrita: 2 ` Harry: 1 Não escreveu nada. 5 Ação ` Parte do que as três pessoas executaram é uma ação. ` A escolha dos valores numéricos é imprevisível (não é ação). ` Escrever a seqüência de números pares é uma ação: ` A partir de um estado inicial (valor de L) ` Após um tempo limitado (alguns segundos) ` Produziu um estado final (o que foi escrito), previsível e bem definido ` Três pessoas diferentes, valores iniciais diferentes, resultados diferentes ` Mesmo padrão de comportamento e mesma norma de execução ` Comando: “Escreva a sequência de números pares inferiores a L.” Ação é um acontecimento que, a partir de um estado inicial, após um período de tempo finito, produz um estado final previsível e bem definido. 6 Algoritmo ` Definição (Farrer et al., 2008): ` Algoritmo é a descrição de um conjunto de comandos que, obedecidos, resultam numa sucessão finita de ações. ` Se destina a resolver um problema ` Fixa um padrão de comportamento a ser seguido, uma norma de execução a ser trilhada, para se atingir, como resultado final, a solução de um problema. 7 Programa que imprime “Hello world!” (1) int main() { printf(“Hello world!\n”); return 0; } ` Este programa imprime “Hello world!”? ` É fácil descobrir que esse programa imprime “Hello world!” e termina. Programa que imprime “Hello world!” (2) int exp(int i, n) /*calcula i elevado a potência n */ { int ans, j; ans = 1; for (j=1; j<=n; j++) ans*=i; return(ans); } int main() { int n, total, x, y, z; scanf(“%d”,&n); total = 3; while (1) { for (x=1; x <= total-2; x++) for(y=1;y <= total-x-1; y++) { z= total – x – y; if (exp(x,n) + exp(y,n)== exp(z,n)) printf(“hello, world\n”); } total++; } } ` E este? Programa que imprime “Hello world!” (2) ` O programa 2 recebe como entrada n e procura por soluções inteiras positivas para a equação xn+yn=zn ` Ao encontrar uma solução, ele imprime “hello, world” e termina; ` Se nunca encontrar inteiros x,y,z para satisfazer a equação, ele continuará a procurar para sempre e nunca imprimirá “Hello world!”; ` Não existem soluções inteiras para a equação quando n>2 (Último Teorema de Fermat). Algoritmo: exercício ` Um algoritmo não pode conter um comando como “Escreva todos os números pares”. Por quê? 11 Fases de construção de um algoritmo ` Entrada: são os dados de entrada do algoritmo. As informações necessárias para solucionar o problema. ` Processamento: são os procedimentos utilizados para chegar ao resultado final, tais como cálculos, conversões, operações, etc. ` Saída: são os dados já processados que, geralmente, serão apresentados aos usuários. 12 Fases de construção de um algoritmo Figura 3: Fases para a construção de um algoritmo (Siebra e da Silva, 2009) 13 Fases de construção de um algoritmo ` Problema: Receba duas notas, calcule e mostre a média ponderada dessas notas, considerando peso 2 para a primeira nota e peso 3 para a segunda nota. ` Entrada: duas notas (N1 e N2) ` Processamento: calcular a média ponderada (MP) (N1 * 2) + (N2 * 3) 5 ` Saída: mostrar a média ponderada (MP) MP = 14 Fases de construção de um algoritmo N1 e N2 (N1 * 2) + (N2 * 3) 5 MP MP= 15 Exercício 1 ` Problema: Receba o peso de uma pessoa em quilos, calcule e mostre esse peso em gramas. ` Entrada: peso (P) ` Processamento: calcular o peso em gramas (PG) PG = P * 1000 ` Saída: mostrar o peso em gramas (PG) 16 Exercício 2 ` Problema: Um funcionário recebe todo mês um salário fixo mais 4% de comissão sobre as suas vendas. Faça um algoritmo que receba o salário fixo de um funcionário e o valor de suas vendas, calcule e mostre a comissão e o salário final do funcionário. ` Entrada: salário fixo (S) e valor de suas vendas (V) ` Processamento: calcular a comissão (C) e o salário final do funcionário (SF) C = V * 0.04 SF = S + C ` Saída: mostrar a comissão (C) e o salário final do funcionário(SF) 17 Algoritmos e lógica de programação ` Consiste em aprender a pensar na mesma sequência de execução dos programas de computador. ` Como serão executadas as ações, partindo do estudo de um problema até chegar à construção de um algoritmo, que seria a solução deste mesmo problema ` Essencial no contexto do processo de criação de um software. 18 Lógica de programação ` É necessária para pessoas que desejam trabalhar com desenvolvimento de sistemas e programas; ` Estes pensamentos, podem ser descritos como uma seqüência de instruções, que devem ser seguidas para se cumprir uma determinada tarefa. ` Permite definir a seqüência lógica para o desenvolvimento. Lógica de programação é a técnica de encadear pensamentos para atingir determinado objetivo. Seqüência Lógica são passos executados até atingir um objetivo ou solução de um problema. 19 Seqüência Lógica: exemplo 20 Seqüência Lógica: exercício ` Escreva a sequência lógica para enviar uma mensagem de texto pelo seu celular. ` Selecionar o Menu; ` Escolher o ícone de Mensagens; ` Escolher a opção Nova mensagem; ` Digitar o texto da mensagem; ` Selecionar o menu Opções; ` Escolher a opção Salvar e enviar; ` Escolher a opção Abrir agenda; ` Selecionar destinatários (repetir esta operação quantas vezes for necessário); ` Selecionar o menu Enviar. 21 Formas de representação de algoritmos ` Português estruturado ` Diagrama de Blocos ` Diagrama de Chapin ou Nassi-Shneider 22 Português estruturado (PE) ` Baseada em PDL (Program Design Language) Æ Linguagem de Projeto de Programação ` Notação sintática semelhante às linguagens de programação PASCAL e STRUCTURE BASIC ` Criada para servir como documentação genérica de códigos a serem executados; ` Normalmente não é executável em um computador; ` Observação: os comandos variam entre os livrosda literatura. Usaremos a notação do MANZANO. J. A. N. G. Algoritmos. São Paulo: Érica, 2006. 23 Palavras reservadas ` Em Português estruturado temos palavras reservadas ` Cada palavra reservada tem um propósito dentro de um algoritmo e por isso deve ser usada de modo apropriado Programa, var, inteiro, real, caractere, lógico, início, leia, escreva, fim, se então, senão, fim_se, enquanto, faça, fim_enquanto, repita, até_que, para, de, até, passo, fim_para, conjunto, tipo, registro, fim_registro, procedimento, caso, seja, fim_caso e função 24 Corpo mínimo de um algoritmo em PE ` Em Português estruturado, todos os algoritmos começam com a palavra programa para denominar o algoritmo, tem a palavra início e terminam com a palavra fim. programa <nome> . . . início <comando 1> <comando 2> . . . <comando n> fim Português estruturado: exemplo ` Receba o peso de uma pessoa em quilos, calcule e mostre esse peso em gramas. programa PESO var P, PG: real início leia P PG Å P * 1000 escreva “O peso em gramas eh: ”, PG fim Observe aqui a indentação dos comandos no algoritmo, assim como fazemos com programas na Linguagem C. 26 Diagrama de blocos ` Figuras geométricas e dizeres são usados para representar as diversas operações do computador, sendo ligados por setas para indicar a seqüência da sua execução; ` Ampla liberdade que pode resultar em difícil compreensão, manutenção e modificação. 27 Diagrama de blocos: elementos básicos Fonte: Manzano, 200428 Diagrama de blocos: elementos básicos Fonte: Manzano, 200429 Diagrama de blocos: exemplo Receba o peso de uma pessoa em quilos, calcule e mostre esse peso em gramas. Início Fim PG Å P * 1000 P PG 30 Diagrama de Chapin ou Nassi-Shneider ` Desenvolvido por Nassi e Shneiderman e ampliado por Ned Chapin ` Apresenta uma visão hierárquica com um único ponto de entrada e um ponto de saída 31 Diagrama de Chapin: exemplo Receba o peso de uma pessoa em quilos, calcule e mostre esse peso em gramas. Início Leia P PG Å P * 1000 Escreva PG Fim 32 Referências ` ALGORITMOS. MANZANO – Lógica para desenvolvimento de programação de computadores. José Augusto N. G. Manzano, Jayr Figueiredo de Oliveira. São Paulo: Érica, 2006. ` ALGORITMOS E LÓGICA DE PROGRAMAÇÃO. Marco Antonio Furlan de Souza, Marcelo Marques Gomes, Marcio Vieira Soares e Ricardo Concilio. Editora Thonsom, 2004. ` REVISÃO E DISCUSSÃO DA NORMA ISO 5807 – 1985(E). José Augusto Navarro Garcia Manzano. THESIS, São Paulo, ano I, v. 1, p. 1-31, 1º Semestre. 2004. ` ALGORITMOS ESTRUTURADOS. Harry Farrer, Christiano Gonçalves Becker, Eduardo Chaves Faria et al. 3ª Edição. Rio de Janeiro: LTC, 2008. 33 Algoritmos O estudo de algoritmos O desenvolvimento de software Algoritmos e problemas Ação (Farrer et al., 2008) Ação Algoritmo Programa que imprime “Hello world!” (1) Programa que imprime “Hello world!” (2) Programa que imprime “Hello world!” (2) Algoritmo: exercício Fases de construção de um algoritmo Fases de construção de um algoritmo Fases de construção de um algoritmo Fases de construção de um algoritmo Exercício 1 Exercício 2 Algoritmos e lógica de programação Lógica de programação Seqüência Lógica: exemplo Seqüência Lógica: exercício Formas de representação de algoritmos Português estruturado (PE) Palavras reservadas Corpo mínimo de um algoritmo em PE Português estruturado: exemplo Diagrama de blocos: elementos básicos Diagrama de blocos: elementos básicos Diagrama de blocos: exemplo Diagrama de Chapin: exemplo Referências
Compartilhar