Unidade 1: Fundamentos

Introdução a Algoritmos

1 - Noções de Lógica

A palavra lógica relaciona-se com a idéia de racionalidade e coerência.
Algumas definições:
- " a lógica é a arte de bem pensar"
- " a lógica é a ciência das formas do pensamento"
- " a lógica nos ensina a colocar ordem no pensamento"
Exemplo:
Todo mamífero e um animal.
Todo cavalo e um mamífero.
Portanto, todo cavalo e um animal.
A lógica no dia-a-dia
- Quando queremos escrever, falar ou agir corretamente precisamos colocar ordem no pensamento, isto é, utilizar lógica.
- Exemplo:
  A gaveta está fechada.
  A caneta está dentro da gaveta.
  Então, precisamos abrir a gaveta para depois pegar a caneta.
A lógica de programação
- Em que consiste?
  A lógica de programação consiste no uso correto das leis do pensamento, da "ordem da razão" e de processos de raciocínio e simbolização formais na programação de compudores.
- Qual o objetivo?
  Permitir a resolução de problemas específicos com soluções de boa qualidade.
- O raciocínio lógico pode ser expresso através de várias linguagens:
- Vamos utilizar uma forma de representação mais genérica (livre de detalhes computacionais) e que traduza mais fielmente o raciocínio da lógica de programação: ALGORITMOS
- Então ...
  O objetivo da lógica de programação é a construção de algoritmos corretos e válidos.

2 - Sobre Algoritmos

Definição: um algoritmo consiste numa seqüência de passos que visam atingir um objetivo bem definido.
- Para especificar uma seqüência de passos , precisamos utilizar ordem, ou seja "pensar com ordem", portanto, precisamos utilizar lógica.
Algoritmos são comuns no nosso cotidiano. Exemplo: uma receita de bolo - nela está escrita uma série de ingredientes necessários e uma seqüência de diversos passos (modo de preparar) que devem ser fielmente cumpridos para realizar a tarefa.
IMPORTANTE!!
Os algoritmos fixam um padrão de comportamento a ser seguido; uma norma de execução a ser trilhada, visando alcançar, como resultado final, a solução de um problema

Por que usar algoritmos?

abstração - todo o esforço é concentrado na resolução do problema e não em detalhes computacionais que podem ser acrescentados posteriormente
portabilidade - uma solução algorítmica pode ser traduzida para qualquer linguagem de programação

Vejamos um outro exemplo... Deseja-se escrever um algoritmo, usando português coloquial, para resolver um problema bastante simples, qual seja: trocar uma lâmpada queimada por uma lâmpada nova não queimada.

Algoritmo 1.1 - Trocar uma lâmpada queimada

pegar uma escada;
posicionar a escada debaixo da lâmpada;
buscar uma lâmpada nova;
subir na escada;
retirar a lâmpada queimada;
colocar lâmpada nova;

Reexaminando o algoritmo 1.1, notamos que ele tem um objetivo bem definido: trocar uma lâmpada queimada. Porém o algoritmo não atingirá seu objetivo se a lâmpada nova estiver queimada. Para tal, acrescentamos um teste condicional (estrutura seletiva).

Algoritmo 1.2 - Trocar uma lâmpada queimada (uso de teste condicional)

pegar uma escada;
posicionar a escada debaixo da lâmpada;
buscar uma lâmpada nova;
subir na escada;
retirar a lâmpada queimada;
colocar lâmpada nova;
se a lâmpada nova não acender, então:
- retirar a lâmpada queimada;
- colocar lâmpada nova;
- se a lâmpada nova não acender, então:
  - retirar a lâmpada queimada;
  - colocar a lâmpada nova;
- se a lâmpada nova não acender, então:
  - retirar a lâmpada queimada;
  - colocar a lâmpada nova;
  . . .
  
  até quando????

O Algoritmo 1.2 não está terminado. As ações cessarão quando conseguirmos colocar uma lâmpada que acenda (objetivo do algoritmo). Ao invés de reescrevermos várias vezes um conjunto de ações, podemos alterar o fluxo seqüencial de execução para permitir que ações sejam reexecutadas quantas vezes forem necessárias. Precisamos expressar essa repetição (estrutura de repetição) garantindo uma condição de parada.

Algoritmo 1.3 - Trocar uma lâmpada queimada (uso de estruturas de repetição)

pegar uma escada;
posicionar a escada debaixo da lâmpada;
buscar uma lâmpada nova;
subir na escada;
retirar a lâmpada queimada;
colocar lâmpada nova;
enquanto lâmpada nova não acender, faça
- retirar a lâmpada queimada;
- colocar lâmpada nova;

Um exemplo mais envolvendo processamento de dados (tipo de problema que realmente nos interessa!): Deseja-se elaborar um algoritmo que escreva os termos da série de Fibonacci inferiores a L.
A série de Fibonacci: 1 1 2 3 5 8 13 ...

Algoritmo 2 - Calcular a série de Fibonacci

pegar o valor L;
atribuir o valor 1 ao primeiro termo;
se o primeiro termo for menor do que L, então
- escreva-o;
atribuir o valor 1 ao segundo termo;
se o segundo termo for menor do que L, então
- escreva-o;
calcular novo termo somando os dois anteriores;
enquanto novo termo for menor do que L, faça:
- escreva-o;
- atualiza os termos anteriores;
- calcule novo termo somando os dois anteriores;

Quando o nosso algoritmo estará completo?
- Um algoritmo é considerado completo quando seus comandos (ações/instruções) forem do entendimento do destinatário.
- Se um comando não estiver claro, este deve ser desdobrado em novos comandos, que constituirão um refinamento do comando inicial. Em alguns casos, devem ser feitos refinamentos sucessivos do algoritmo.
- No algoritmo 2, dependendo do tipo de destinatário, poderia ser necessário detalhar algumas ações, como por exemplo, a ação atualiza os termos anteriores. Nesse caso, teríamos:
  ...
  - primeiro termo passa a ter o valor do segundo termo;
  - segundo termo passa a ter o valor do novo termo;
  ...
Como representar nossos algoritmos?
- No sentido de evitar problemas de ambigüidades no uso do português para representar algoritmos, vamos utilizar um conjunto de regras que visam restringir e estruturar o uso do português.
- É interessante ressaltar que, a idéia de restringir o uso do português para facilitar a descrição dos algoritmos muito se aproxima da maneira pela qual as linguagens de programação reais (como C e Pascal) representam os algoritmos que serão executados pelo computador.

2.1 Itens Fundamentais dos Algoritmos

Tipos de Dados:
- Numérico: valores numéricos
- Literal: dado composto por um conjunto de caracteres (letras, dígitos ou caracteres especiais)
- Lógico (booleano): dado que pode assumir apenas os valores Verdadeiro ou Falso.
Constantes:
- São os dados que não sofrem modificação durante a execução do algoritmo.
- Exemplos: 123, 12.34, "Campina Grande", VERDADE.
Variáveis:
- São os dados que sofrem modificação durante a execução do algoritmo. É um contêiner que pode armazenar um tipo determinado de dado e cuja identificação e dada através de um nome.
- A área de uma círculo é processada pela fórmula descrita abaixo:
  área = pi * raio ²
  área = 3,14 * raio * raio
  
  área e raio representam variáveis, uma vez que seus valores dependem de qual círculo estamos considerando; 3,14 é um valor constante utilizado para calcular a área de qualquer círculo.
- No ambiente computacional cada variável corresponde a uma porção (parte ou pedaço) de memória (memoria principal), cujo conteúdo pode variar durante a execução de um programa.
- Embora uma variável possa assumir vários valores, ela só pode armazenar um valor de cada vez.
- Os identificadores das variáveis representam as posições de memória (endereços de memória) que armazenam os dados.
Identificadores de Variáveis
- No exemplo anterior, área e raio são os identificadores (nomes) das variáveis que armazenam respectivamente a área e o raio do círculo.
- Os identificadores podem conter caracteres letras e dígitos, mas sempre iniciam por um caracter letra.
Declaração de variáveis
- Como especificar o tipo de uma variável? Através da declaração de variáveis.
- Na declaração associamos a variável ao tipo de dado a ser armazenado nela.
- Forma geral da declaração de uma variável:
  <nome_do_tipo> : lista de identificadores
- Exemplos:
  numérico: área, raio;
  literal: nome;

Expressões aritméticas

São expressões cujos resultados de suas avaliações são valores numéricos. As expressões aritméticas são compostas de:
- operadores: são os operadores aritméticos: +, -, * e /
- operandos: constantes ou variáveis.
além das operações basicas, tem-se:
- potenciação - pot(x,y)
- radiciação - rad(x)
- módulo (resto da divisão de um número por outro) - mod

exemplo: 2 * A mod 3 + rad(9)

atentar para a ordem de precedência entre os operadores:

(maior precedência)	parênteses mais internos
	pot rad
	* /
(menor precedência)	+ -

Expressões lógicas

São expressões cujo resultado é sempre um valor lógico (VERDADE - V ou FALSO - F). As expressões aritméticas são compostas de:
- operadores: são os operadores relacionais (= ,> , <, >=, <=, <>) e os operadores lógicos (Não, E, Ou - NOT, AND, OR, respectivamente).
- operandos: relações, variáveis ou constantes do tipo lógico.
Exemplo: A + B = 0 AND C <> 1
Cada operação lógica tem a sua tabela lógica que contém o conjunto de todas as possibilidades combinatórias entre os valores de diversas variáveis lógicas envolvidades numa operação lógica.

Vejamos as tabelas lógicas para as operações NOT, AND, OR (considere A e B com sendo uma expressão, constante ou variável lógica).

Operação de Negação

A	NOT A
V	F
F	V

Operação de Conjunção

A	B	A AND B
F	F	F
F	V	F
V	F	F
V	V	F

Operação de Disjunção

A	B	A OR B
F	F	F
F	V	V
V	F	V
V	V	V

mais exemplos:

	2 < 5 AND 15/3 = 5
	V AND V
resultado da expressão:	V

ordem de precedência entre todos os operadores:

(maior precedência)	parênteses mais internos
	operadores aritméticos
	operadores relacionais
(menor precedência)	operadores lógicos

Comando de Atribuição
- Permite-nos fornecer um valor para uma variável (conteúdo para armazenamento na memória principal).
- Forma geral de um comando de atribuição:
  
  <identificador> ¬ valor
- Exemplos:
  
  lógico: A;
  numérico: X;
  
  A ¬ VERDADE;
  X ¬ 8 + 12/3;
  A ¬ X = 3;
Comandos de Entrada e Saída
- permite-nos fornecer um os dados que "alimentam" os algoritmos e mostram os resultados processados pelos mesmos.
- O comando leia, permite atribuir o dado lido (externo ao algoritmo) à variável identificada.
  
  Exemplo: leia(raio); {atribui o valor lido à variável raio}
- O comando escreva, permite exibir o valor de constantes ou o conteúdo armazenado nas variáveis identificadas.
  
  Exemplo: escreva("o valor do raio é", raio); - escreve a constante "o valor do raio é" seguido do valor armazenado na variável raio.
Blocos
- Caracteriza um conjunto finito de ações com uma função definida, então, um algoritmo é um bloco.
- Todo bloco tem início e fim, o que é delimitado pelas palavras início e fim, respectivamente.
Comentários
- Texto explicativo que aparece entre {} ou /* */ ao longo do algoritmo.
- Os comentários não fazem parte das ações (comandos) do algoritmo e têm como finalidade aumentar a clareza na leitura do algoritmo, ou seja, facilitar o entendimento das pessoas acerca do que sendo descrito no algoritmo.

2.2 Estruturas de Controle

As estruturas de controle determinam a sequência de execução (fluxo de execução) das ações dos algoritmos.
Existem três tipos de estruturas de controle: estrutura seqüencial, estrutura de seleção, estrutura de repetição. Vejamos um pouco mais sobre cada uma delas...

Estrutura Seqüencial:
- por via de regra, as ações descritas num algoritmo serão executadas numa sequência linear, isto é, da primeira à última, na ordem em que aparecem.
- o delimitador ' ; ' indicará o fim de cada ação.
- modelo geral de um algoritmo:
  
  início
  
      /* Declaração de variáveis
  
      ...
  
      /* Corpo do algoritmo */
  
      ação1;
  
      ação2;
  
      ...
  
      açãoN;
  
  fim /* do algoritmo */
- Para exercitar em sala: escreva um algoritmo para calcular a média aritmética entre quatro notas de disciplina, fornecidas por um aluno.

Algoritmo 4 - Cálculo da média aritmética de quatro valores

início

/* Declaração de variáveis */

numérico: nota1, nota2, nota2, média;

/* Obtenção da notas */

escreva("Informe as notas do aluno: ");

leia(nota1, nota2, nota3, nota4);

/* Cálculo da média */

média = (nota1 + nota2 + nota3 + nota4) / 4;

escreva("Média calculada: " média);

fim

Estruturas de seleção

permite a escolha de um conjunto de ações (bloco) a ser executado quando determinadas condições, representadas por expressões lógicas ou relacionais, forem ou não satisfeitas.
seleção simples - forma geral:
se <condição>
    então /* Bloco verdade */
       início
            sequência de comandos;
       fim
fim-se
seleção composta - forma geral:
se <condição>
   então /* Bloco verdade */
       início
            sequência de comandos;
       fim
   senão /* Bloco falso*/
        início
            sequência de comandos;
       fim
fim-se
para exercitar em sala: modifique o algoritmo 4 de modo que seja avaliado se o aluno obteve nota maior do que 7.0; deve-se informar sobre a aprovação ou não do aluno.
é possível agruparmos várias seleções numa única estrutura denominada: seleção encadeada.
forma geral de uma seleção encadeada:
se <condição1>
   então
        se <condição2>
            então
               início
                    sequência de comandos;
               fim
        fim-se
   senão
        se <condição3>
            então
                início
                    sequência de comandos;
               fim
            senão
                início
                    sequência de comandos;
               fim
fim-se
Para exercitar em sala: escreva um algoritmo que determine se um conjunto de 3 valores (fornecidos pelo usuário) - lado1, lado2, lado3 - formam um triângulo e, se forem, verificar se compôem um triângulo equilátero, isósceles ou escaleno. Informar se não compuserem um triângulo

Algoritmo 5 - Verificar se três lados formam um triângulo e que tipo de triângulo

início

/* Declaração de variáveis */

numérico: lado1, lado2, lado3;

/* Obtenção dos dados */

leia(lado1, lado2, lado3);

    se (lado1 < lado2+lado3) AND (lado2 < lado1+lado3) AND (lado3 < lado2+lado1) /* Testa se é triângulo */
        então
            se (lado1=lado2) AND (lado2=lado3) /* Testa se é equilátero */
                então
                    escreva ("Os valores fornecidos formam um triângulo equilátero.");
                senão /* Testa se é isósceles */
                    se (lado1 = lado2) OR (lado2 = lado3) OR (lado1 = lado3)
                        então
                            escreva ("Os valores fornecidos formam um triângulo isósceles");
                        senão /* É escaleno */
                            escreva ("Os valores fornecidos formam um triângulo escaleno");
                    fim-se
            fim-se
    fim-se

fim /* do algoritmo */

Seleções encadeadas podem seguir um mesmo padrão lógico:
1 - Padrão se-então-se:
- Suponha um comando qualquer que deva ser executado apenas quando as condições, condição1 e condição2, forem verdadeiras. Então teremos a seguinte situação:
  se <condição1>
      então se <condição2>
                  então comando;
              fim-se
  fim-se
2 - Padrão se-senão-se
- Suponha que uma variável var só possa assumir os valores valor1 e valor2; e que existam comandos diferentes para cada valor armazenado em var. Então teremos a seguinte situação:
  se var = valor1
      então
          comando1;
  fim-se
  
  se var = valor2
      então
          comando2;
  fim-se
  
  melhorando o desempenho dessa estrutura (diminuindo a quantidade média de testes):
  
  se var = valor1
      então
          comando1;
      senão se var = valor2
                  então
                      comando2;
              fim-se
  fim-se
  
  outra forma de representar a situação descrita acima é através do uso de uma estrutura de seleção de múltipla escolha:
  
  escolha (var)
      caso valor1: comando1;
      caso valor2: comando2;
      caso contrário: comandoErro;
  fim-escolha

Estruturas de repetição

Quando um trecho de programa deve ser repetido ao longo do algoritmo, ao invés de reescrevê-lo várias vezes utilizam-se laços de repetição.
O número de execuções de um laço de repetição pode ser indeterminado, mas sempre será finito.
Tipos de laços:
Laço indeterminado

enquanto <condição> faça
início
comandos;
fim
fim-enquanto

Exemplo: calcular a média aritmética de quatro notas para um conjunto de alunos.

Algoritmo 6 - Calcular a média aritmética de 4 notas para vários alunos

início
/* Declaração de variáveis */

numérico: nota1, nota2, nota3, nota4, média;

literal: resposta;

resposta ¬ "S";

    enquanto (resposta = "S") faça
    início
        /* Obtenção da notas */
        escreva("Informe as notas do aluno: ");
        leia(nota1, nota2, nota3, nota4);
        /* Cálculo da média */
        média = (nota1 + nota2 + nota3 + nota4) / 4;
       escreva("Média calculada: " média);
        escreva("Deseja calcular outras médias de alunos (S/N)?");
        leia(resposta);
    fim
    fim-enquanto

fim /* do algoritmo */

Tipos de laços

Laço determinado

para <variável> de <valorInicial> até <valorFinal> passo <incremento> faça
início
comandos;
fim
fim-para

Exemplo: modificar o algoritmo 6, considerando a quantidade de alunos igual a 50.

Algoritmo 7 - Calcular a média aritmética de 4 notas para 50 alunos

início
/* Declaração de variáveis */

numérico: nota1, nota2, nota2, média, numAlunos;

    para numAlunos de 1 até 50 passo 1 faça
    início
        /* Obtenção da notas */
        escreva("Informe as notas do aluno: ");
        leia(nota1, nota2, nota3, nota4);
        /* Cálculo da média */
        média = (nota1 + nota2 + nota3 + nota4) / 4;
       escreva("Média calculada: " média);
    fim
    fim-enquanto

fim /* do algoritmo */

Versão ".doc" do material apresentado acima (aqui)