Aula 1 - Lógica e Algoritmos

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 ?