Baixe o app para aproveitar ainda mais
Prévia do material em texto
PROGRAMA DE INFORMÁTICA BÁSICA Algoritmos Prof. João Dallyson Aula passada... • Introdução • Evolução do Software • Classificação do Software • Sistema Operacional (SO) • Evolução do SO • Funções do SO • Componentes do SO 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 2 Sumário • Introdução à Lógica de Programação • Conceito de Algoritmo • Representação de Algoritmos • Descoberta de Algoritmos • Exemplos 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 3 Noções de Lógica • Lógica: Ciência que estuda as formas do pensamento; • Sempre que pensamos a lógica nos acompanha: – Um bebê sabe que precisa chorar para receber atenção; – A gaveta está fechada. A caneta está dentro da gaveta. Precisamos primeiro abrir a gaveta para depois pegar a caneta. • O pensamento (e a lógica) pode ser expresso através da palavra falada ou da palavra escrita; • Um mesmo pensamento pode ser expresso em inúmeros idiomas, tanto oralmente quanto por escrito; 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 4 Algoritmo • Qual sua importância na programação? – Representar o raciocínio, independentemente de detalhes computacionais, que podem ser acrescentados mais tarde – Focalizar primeiro na resolução algorítmica do problema, possibilitando depois codificá-la em qualquer linguagem 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 5 Conceito de Algoritmo • Definição Informal: – É o pensamento descrito como uma sequência de passos que visam atingir um objetivo; – Conjunto de passos que definem como uma tarefa é realizada. (BROOKSHEAR, 2013); • Ex: ciclo de máquina realizado pela CPU: Enquanto a instrução parar não for executada Continue a executar os seguintes passos: a) Obtenha uma instrução. b) Decodifique a instrução. c) Execute a instrução. • Exemplos de Algoritmos no cotidiano? 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 6 Conceito de Algoritmo • Definição Formal: – É um conjunto ordenado de passos executáveis, não ambíguos, que define um processo finalizável. (BROOKSHEAR, 2013) • Ex: algoritmo infinito – Crie uma lista de todos os inteiros positivos. • Obs: – Existem aplicações importantes para processos que não terminam: • Monitoramento de sinais vitais de um paciente 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 7 Natureza abstrata dos algoritmos • Diferença: algoritmo x representação – Analogia: Uma história X um livro – Uma história: abstrata, conceitual, em sua natureza – Um livro: representação física de uma história • Livro em vários idiomas, a história continua imutável – Um algoritmo é abstrato e distinto de sua representação. • Ex: F = (9/5)C + 32, ou, Multiplique o valor da temperatura em Celsius por 9/5 e adicione 32 ao produto. 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 8 Natureza abstrata dos algoritmos • Programas X Processos X Algoritmos ? – Entidades distintas, porém relacionadas. – Programa: Representação de um algoritmo – Processo: Atividade de executar um algoritmo • Importância dos algoritmos na programação? – Representar o raciocínio, independentemente de detalhes computacionais, que podem ser acrescentados mais tarde – Focalizar primeiro na resolução algorítmica do problema, possibilitando depois codificá-la em qualquer linguagem 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 9 Exercício • Em que sentido os passos descritos pela seguinte lista de instruções falham em constituir um algoritmo? – Passo 1: Pegue um moeda de seu bolso e coloque sobre a mesa. – Passo 2: Retorne ao Passo 1. 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 10 Dois pontos: 1º) As instruções definem um processo que não termina. 2º) Ambiguidade: O processo alcançara um estado no qual não haverá mais moedas em seu bolso. O algoritmo não descreve o que deve ser feito nesta situação Representação de Algoritmos • Humanos: linguagem natural tradicional, linguagem de figuras. – Problemas da linguagem natural: • Mal entendimento: algumas vezes possui mais de um significado. • Ex: “Visitar os netos pode ser irritante” – Ou os netos causam problemas quando você os visita – Ou ir visitá-los é problemático • Problemas de comunicação surgem quando a linguagem usada para a representação de um algoritmo não é precisamente definida ou quando a informação não é dada com o detalhamento adequado. 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 11 Representação de Algoritmos • Requer primitivas bem definidas (evita ambiguidade) – Primitivas: conjunto bem definidos de blocos de construção a partir dos quais representações de algoritmos podem ser construídas. • Sintaxe: representação simbólica da primitiva • Semântica: significado da primitiva • Ex: água (sintaxe: 5 símbolos, semântica: líquido natural, transparente, incolor, indispensável para a sobrevivência da maioria dos seres vivos) • linguagem de programação: – Coleção de primitivas + – Coleção de regras • definem como as primitivas podem ser combinadas para representar ideias mais complexas 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 12 Pássaro de origami - primitivas 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 13 Primitivas de origamis Algoritmo Primitivas - Pseudocódigo • Pseudocódigo: – É um sistema notacional no qual ideias podem ser expressas informalmente durante o processo de desenvolvimento do algoritmo (BROOKSHEAR, 2013); – Objetivo de fornecer meios para representar algoritmos de uma maneira legível e informal. • Exemplos: – Sentença de Atribuição: • Nome expressão • Atribua a nome o valor de expressão. • Saldo SaldoContaCorrente + SaldoPoupanca – Sentença de Condição se (condição) então (atividade) senão 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 14 Primitivas - pseudocódigo – Sentença de repetição: enquanto (condição) faça (atividade) repita (atividade) até (condição) Ex: enquanto (existem ingressos a serem vendidos) faça (venda um ingresso) • Indentação: 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 15 Descoberta de Algoritmos • Matemático G. Polya (1945) apresentou fases para guiar o processo de resolução de problemas: Fase 1. Entender o problema. Fase 2. Bolar um plano para resolver o problema. Fase 3. Executar o plano. Fase 4. Avaliar a solução em termos de precisão e de seu potencial como uma ferramenta para solucionar outros problemas. 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 16 Exemplos • Problemas das Torres de Hanói – Mover os discos de uma haste para outra sem que o disco maior fique sobre o disco menor 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 17 Solução? Dando o primeiro passo • Tentar trabalhar o problema de trás para frente – Se um problema for encontrar uma maneira de produzir uma saída a partir de uma dada entrada, poderíamos iniciar com a saída e voltar até a entrada. – Ex: Pássaro origami, tentar desdobrar para descobrir como foi feito. • Resolver um problema relacionado mais fácil – Relaxar algumas das restrições do problema – Resolver partes do problema primeiro (metodologia bottomup) • Refinamento passo a passo: – Divide o problema em problemas menores (metodologia top- down) – Ex: Componentes pré-fabricados de grandes sistemas coorporativos 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 18 Resolução de Problemas • Partimos do problema geral para atingir níveis específicos. • Ex: Considere uma escola cujo cálculo da média é realizado com utilização de quatro notas bimestrais que determinam a aprovação ou reprovação dos alunos. Considere que o valor da média dever ser maior ou igual a 7 para que haja aprovação. 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 19 Resolução de Problemas 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 20 Resolução de Problemas Programa média 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 21 Exemplos • Trocar uma lâmpada (v1.1) – sequencial 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 22 pegar uma escada; posicionar a escada embaixo da lâmpada; buscar uma lâmpada nova; subir na escada; retirar lâmpada velha; colocar lâmpada nova. Exemplos • Trocar uma lâmpada SE estiver queimada (v1.2) – Seleção (Decisão) 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 23 pegar uma escada; posicionar a escada embaixo da lâmpada; buscar uma lâmpada nova; acionar o interruptor; se a lâmpada não acender, então subir na escada; retirar lâmpada queimada; colocar lâmpada nova. Exemplos • Trocar uma lâmpada SE estiver queimada (v1.3) – Seleção (Decisão) – Evita buscar a escada e lâmpada 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 24 acionar o interruptor; se a lâmpada não acender, então pegar uma escada; posicionar a escada embaixo da lâmpada; buscar uma lâmpada nova; acionar o interruptor; subir na escada; retirar lâmpada queimada; colocar lâmpada nova. Exemplos • Trocar uma lâmpada SE estiver queimada (v1.4) – Seleção (Decisão) – Re-teste depois da troca 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 25 acionar o interruptor; se a lâmpada não acender, então pegar uma escada; posicionar a escada embaixo da lâmpada; buscar uma lâmpada nova; acionar o interruptor; subir na escada; retirar lâmpada queimada; colocar lâmpada nova; se a lâmpada não acender, então retirar lâmpada queimada; colocar lâmpada nova; se a lâmpada não acender, então . . . Exemplos • Trocar uma lâmpada SE estiver queimada (v1.5) – Repetição – Re-teste depois da troca (por repetição) 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 26 acionar o interruptor; se a lâmpada não acender, então pegar uma escada; posicionar a escada embaixo da lâmpada; buscar uma lâmpada nova; acionar o interruptor; subir na escada; retirar lâmpada queimada; colocar lâmpada nova; enquanto a lâmpada não acender, faça retirar lâmpada queimada; colocar lâmpada nova; Problemas e Soluções • Não existe, em geral, uma única solução para o mesmo problema; • Algumas soluções são melhores do que outras, sob algum critério; • Alguns problemas são casos particulares de outros similares; • As vezes, é melhor resolver o problema mais genérico, assim, resolve-se uma classe de problemas, e não apenas um. 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 27 Formas de Representação • Gráficas (Fluxograma) – Vantagens • Maior clareza no fluxo de execução • Linguagem visual – Desvantagens • Requer conhecimento de convenções gráficas • Mais trabalhoso em decorrência de seus desenhos • Dificuldade para fazer correções • Textuais (Linguagem Natural e Pseudo-código ) – Apresenta mais vantagens, desde que se tomem alguns cuidados: • Riqueza gramatical de nossa língua pode levar a ambiguidades • Para resolver, utilizaremos um conjunto restrito de regras, conhecido como Português Estruturado 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 28 Calcular raiz de uma equação do 1º grau? • Linguagem natural 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 29 Calcular raiz de uma equação do 1º grau? • Fluxograma 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 30 Calcular raiz de uma equação do 1º grau? • Pseudo-código 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 31 Exercícios 1) Descreva a diferenças entre um processo, um algoritmo e um programa. 2) Cite exemplos de algoritmos com os quais você esteja familiarizado. Eles são realmente algoritmos segundo a definição formal? 3) Escreva um algoritmo para realizar a troca de um pneu de uma bicicleta. 4) Escreva um algoritmo para realizar a troca de um único pneu de um carro. 5) Construa um algoritmo que, dado o valor de um compra, sejam aplicados 10% de desconto na venda à vista e exiba o valor a ser pago. 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 32 Links Metropole Digital – Lógica e Algorimos http://www.metropoledigital.ufrn.br/aulas/disciplinas/logic a/ Web Portugol http://siaiacad17.univali.br/webportugol login: bctfc senha:bctfc Jogo Light Bot http://www.jogosjogos.com/jogar-jogo/Light-Bot.html Scratch http://scratch.mit.edu/ 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 33 Agradecimentos • Ao Prof. Dr. Bruno Feres, do BCT/UFMA • Ao Prof. Dr. Sergio Souza Costa, do BCT/UFMA • Ao Prof. Me. Geraldo Braz, DEINF/UFMA • Ao Prof. Me. Osvaldo Silva Sousa Junior, NTI/UFMA 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 34 Referências • BROOKSHEAR, J. G. Ciência da Computação: Uma visão abrangente. 11ª Ed. Porto Alegre, 2013. • MANZANO, J. A. N. G; OLIVEIRA, J. F. Algoritmos: Lógica para Desenvolvimento de Programação de Computadores. 26ª Ed. São Paulo: Érica, 2013; • MANZANO, J. A. N. G; OLIVEIRA, J. F. Algoritmos: Estudo Dirigido. 15ª Ed. São Paulo: Érica, 2013; 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 35 Perguntas.... 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 36
Compartilhar