Prévia do material em texto
1 FACULDADE DE COMPUTAÇÃO E INFORMÁTICA BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO Introdução a Programação – Aula 1 – 2º SEMESTRE/2013 TEORIA: ALGORITMOS – PARTE (I): LÓGICA E ALGORITMOS Nossos objetivos nesta aula são: compreender a origem e o significado do termo algoritmo aplicar este conceito para resolver alguns problemas simples entender a relação de algoritmos com programas de computadores praticar com algoritmos em alguns ambientes de desenvolvimento A referência para esta aula é o Capítulo 1 (A Lógica e os Algoritmos) do nosso livro-texto: Piva Jr., D. et al. Algoritmos e Programação de Computadores. Rio de Janeiro: Elsevier, 2012. Não deixem de ler este capítulo após a aula de hoje! O termo algoritmo pode ser visto desde o século IX. Foi nesta época que o cientista, astrônomo e matemático persa Abū ‘Abd Allāh Muhammad ibn Mūsā al-Khwārizmī [ يمزراوخلا ىسوم نب دمحم الله دبع وبأ ] usou pela primeira vez o termo para indicar regras de operações aritméticas utilizando algarismos indoarábicos. Estas regras aparecem no Livro-Compêndio sobre Cálculo por Restauração e Balanceamento [página ao lado ]. ةلباقملاو ربجلا باسح يف رصتخملا باتكلا al-Kitāb al-mukhtaṣar fī ḥisāb al-jabr wa-l-muqābala 2 No século XII, Adelardo de Bath traduziu o termo para o latim Algorithmi . De lá para cá, o termo evoluiu bastante incluindo todos os procedimentos definidos para resolver problemas ou realizar tarefas. A formalização da noção de algoritmo ocorreu em 1936 com os trabalhos de Alan Turing e Alonzo Church, que desenvolveram independentemente os modelos de Máquinas de Turing e Cálculo Lambda. Do ponto de vista computacional, um algoritmo pode ser visto como um conjunto de regras e procedimentos lógicos perfeitamente definidos que levam à solução de um problema em um número finito de passos. EXERCÍCIO TUTORIADO Um dos algoritmos mais antigos conhecidos é o Algoritmo de Euclides (desenvolvido pelo próprio filósofo Euclides) para calcular o máximo divisor comum (mdc) entre dois números mdc(a,b): Dividir a por b, obtendo o resto r Substituir a por b Substituir b por r Continuar a divisão de a por b até que a não possa mais ser dividido por b. Neste caso, a é o mdc. Vamos simular este algoritmo para mdc(480,130) na tabela abaixo: a b r Por que a sequência de passos acima é realmente um algoritmo ? 3 EXERCÍCIO COM DISCUSSÃO EM DUPLAS Aplique o algoritmo anterior para calcular mdc (47,13): Dividir a por b, obtendo o resto r Substituir a por b Substituir b por r Continuar a divisão de a por b até que a não possa mais ser dividido por b. Neste caso, a é o mdc. a b r Donald Knuth, um dos pesquisadores mais respeitados em algoritmos, indica uma lista de cinco propriedades que são requisitos para algorimos: o Finitude: um algoritmo deve sempre terminar após um número finito de etapas (ou passos). o Definição: cada passo de um algoritmo deve ser definido com precisão. As ações a serem executadas deverão ser especificadas rigorosamente e sem ambiguidades. o Entrada: valores que são dados ao algoritmo antes que ele inicie. o Saída: os valores resultantes das ações do algoritmo a partir de uma determinada entrada. o Eficácia: todas as operações a serem realizadas pelo algoritmo devem ser suficientemente básicas para poderem, em princípio, ser feitas com precisão e em um período de tempo finito por um homem usando papel e lápis. Embora os requisitos de Knuth sejam intuitivos, falta-lhes rigor formal. A formalidade pode ser conseguida com o uso de lógica. Assim, vamos exigir que um algoritmo seja uma sequência lógica de passos com começo, meio e fim. ALGORITMO ENTRADA SAÍDA 4 Comumente, esta lógica é conhecida como lógica de programação e isto ocupará grande parte de nossa disciplina. De um ponto de vista mais geral, podemos dizer que Lógica é uma parte da Filosofia que trata das formas do pensamento em geral (dedução, indução, hipótese, inferência, dentre outros) e das operações intelectuais que visam à determinação do que é verdadeiro ou falso. Dentre outras coisas, a Lógica pode produzir algoritmos para estas formas e operações. EXERCÍCIO TUTORIADO Construa um algoritmo para fazer um sanduíche do tipo X-Salada. Será que conseguiríamos programar este algoritmo em um computador ? 5 algoritmos como o anterior são denominados de algoritmos não–computacionais. Agora, vamos considerar um outro problema. EXERCÍCIO TUTORIADO Construa um algoritmo para obter e somar dois números. Será que conseguiríamos programar este algoritmo em um computador ? algoritmos como o anterior são denominados de algoritmos computacionais, pois podem ser programados em um computador. 6 EXERCÍCIO COM DISCUSSÃO EM DUPLAS Construa um algoritmo para obter dois números e mostrar qual é o maior deles. Uma vez que o algoritmo tenha sido definido, podemos simulá-lo com ferramentas como Scratch, VisuAlg ou Raptor (que veremos mais tarde) ou implementá-lo diretamente em alguma linguagem de programação (C, C++, Java, Pascal, PHP, dentre outras). Nossa disciplina será mais focada em Java, uma das linguagens mais difundidas no mercado. Porém, veremos alguns exemplos em outras linguagens. Na realidade, vocês verão que a linguagem de programação (normalmente) é o que menos importa. Se a lógica do algoritmo for bem feita, poderemos implementá-lo na maioria das linguagens de programação conhecidas. Outro detalhe importante é que, ao se aprender bem uma linguagem dentro de um determinado conceito (ou paradigma), pode-se migrar sem muito esforço para outra linguagem do mesmo paradigma. Por exemplo, se você programa em C (linguagem imperativa), você conseguirá aprender (sem muito esforço) a linguagem Pascal, que também é imperativa. Se você programa em C++ (orientada a objetos), pode aprender Java, que também é orientada a objetos. Nas atividades de laboratório, teremos oportunidade de mostrar como alguns dos algoritmos vistos nesta aula podem ser simulados e programados. 7 ATIVIDADES DE LABORATÓRIO Na nossa atividade de laboratório, vamos inicialmente simular o algoritmo para decidir o maior de dois números, visto em aula, na ferramenta VisuAlg. Lembremos que o algoritmo era: LEIA (X) LEIA (Y) SE (X > Y) ENTÃO ESCREVA (X) SENÃO ESCREVA (Y) Seguindo as instruções de seu professor, digite e faça simulações deste algoritmo transformado para a notação do VisualAlg: ALGORITMO “MAIOR” VAR X,Y: INTEIRO INICIO LEIA (X) LEIA (Y) SE (X > Y) ENTAO ESCREVA (X) SENAO ESCREVA (Y) FIMSE FIMALGORITMO Modifique este algoritmo para ler dois números e mostrar qual o menor deles. Faça simulações do seu algoritmo no VisualAlg para verificar se a sua idéia está correta. 8 ATIVIDADES DE LABORATÓRIO Na atividade anterior, fizemos uma simulação do algoritmo (maior de dois números). Agora, vamos implementar este algoritmona linguagem Java, a linguagem-base da nossa disciplina. Seguindo as instruções do seu professor, digite, compile e execute o programa abaixo no ambiente Dr. Java: import java.util.*; public class Prog1{ public Prog1() { } public static void main(String[ ] args) { int x,y; Scanner entrada; entrada = new Scanner(System.in); x=entrada.nextInt(); entrada = new Scanner(System.in); y=entrada.nextInt(); if (x>y){ System.out.println(x); } else{ System.out.println(y); } } } Após compilar, executar e testar o seu programa, modifique-o para exibir o menor dos dois números. 9 EXERCÍCIOS EXTRA-CLASSE 1. Ler integralmente o Capítulo 1 do livro-texto, base desta aula. Não se preocupe ainda com as linguagens Pascal, C e PHP que aparecem no texto. Na próxima semana, teremos a oportunidade de estudar um pouco destas linguagens. 2. Proponha um algoritmo para trocar o pneu de um carro. O seu algoritmo é computacional ou não-computacional ? 3. Proponha um algoritmo que calcule a área de uma mesa de jantar. O seu algoritmo é computacional ou não-computacional ? 4. Uma agência de previsão de tempo armazena diariamente a temperatura média de uma determinada região. Cada uma dessas temperaturas fica arquivada em um cartão, com data e horário da coleta. Você deve desenvolver um algoritmo que irá descobrir qual é a menor temperatura registrada nos arquivos da agência. Lembre-se de que as temperaturas podem ser positivas e negativas. 5. Dois caçadores estão perdidos em uma floresta, sem munição e prestes a morrer de fome. Um deles, conhecedor da flora, conseguiu achar uma planta muito nutritiva. Entretanto, para comê-la, eles têm de esquentá-la por 30 segundos exatos, senão ela os matará. Porém, para marcar o tempo, eles só tem duas ampulhetas: uma que marca 22 segundos e outra que marca 14 segundos. Como eles conseguirão marcar o tempo ?