Algoritmos, "colocando no papel" parte I

Sei que prometi que mexeríamos no BrOffice Calc nessa aula, mas eu esqueci que algumas coisas poderiam ser ensinadas antes de iniciarmos a prática. Por isso, nessas próximas duas aulas vou ensinar a montar "algoritmos escritos" e "fluxogramas", que ajudam a planejar e analisar os algoritmos.

Os algoritmos escritos, que vamos abordar hoje, não passam de um conjunto de instruções, escritos com uma sintaxe própria mas "flexível", sem obedecer nenhuma linguagem de programação. Você não tem que se ater em importar bibliotecas ou descobrir se uma função existe ou não. Você vai simplesmente escrever as operações que pretendidas na ordem desejada e assim ter uma ideia de como o programa vai ficar.

Por exemplo, temos que fazer um programa que execute a soma de dois números e mostre o resultado. Podemos escreve-lo assim:

Receber número A;
Receber número B;
C = A+B;
Exibir número C;

Com esse "esqueleto", um programador conseguirá passar ele para a linguagem de programação de seu domínio. Como por exemplo em "C":

#include<stdio.h>

int main(){
  float a,b,c;
  scanf("%f",&a);
  scanf("%f",%b);
  c = a+b;
  printf("%f",c);
}

E poderia colocar ele em outras linguagens aqui. O caso é que o mais difícil não é passar um algoritmo para uma linguagem! O maior trabalho está em montar o algoritmo! E montar ele numa linguagem com a qual estamos mais acostumados (no nosso caso, português) é mais fácil do que tentar montar direto em uma linguagem estranha (qualquer linguagem de programação).

Regras de sintaxe:

Apesar do objetivo de um algoritmo "no papel" ser expressar a ideia do "programa" que desejamos montar, sem que precisemos nos preocupar com nomes de funções, limitações de hardware e sintaxe, ainda precisamos de algumas regras com relação à essa última, se não, em algoritmos mais complexos podemos acabar não entendendo nem o que nós mesmos escrevemos.

Vamos padronizar aqui algumas regras, entre a gente, para facilitar o entendimento dos algoritmos produzidos aqui e para já ir introduzindo um pouco da sintaxe da linguagem C.

Enumeração de ideias:

Como sabemos, um algoritmo é um conjunto de instruções claras e bem definidas em sequencia. Uma instrução é uma ação, uma operação, ou uma identificação, ela ocupará uma  linha e não dividirá essa com qualquer outra instrução. Além disso usaremos um ";" (ponto-e-vírgula) para sinalizar o fim daquela instrução. Exemplo:

Programa de comer:

Pegar comida com o talher;
Levar a comida até a boca;
Abrir a boca;
Colocar a comida na boca;
Fechar os lábios;
Retirar o talher;
Mastigar;
Engolir;

Note que a ordem é importante! Se colocássemos "Colocar a comida na boca" antes de "Abrir a boca", com certeza teríamos um triste resultado.

Condicionais, blocos e tabulação:

Vamos usar dois condicionais, o "SE ENTÃO" e o "ESCOLHA UM CASO".

O "SE ENTÃO" realiza um teste lógico, se o teste for verdadeiro ele executa um conjunto de instruções, "SE NÃO" ele executa outro conjunto.

Sua sintaxe será:

SE(teste lógico){bloco de instruções para resultado verdadeiro}
SE NÃO { bloco de instruções para resultado verdadeiro}

Veja só um exemplo:

Programa de "fazer o tipo 2"

Note que no exemplo não usamos o "SE NÃO", isso é porque não haviam instruções a serem executadas se  o teste lógico desse verdadeiro. Aqui vai um exemplo de algoritmo que usa o "SE NÃO":

Programa de ida ao banheiro

É importante assinalar que o SE NÃO depende do ultimo  teste "SE" realizado.

Vamos ver agora o "ESCOLHA UM CASO". Ele não é nada mais que um "SE ENTÃO" metido a besta. Ele é tipo aqueles atendimentos automáticos por telefone que nos infernizam quando temos que reclamar de algo. Ele basicamente lê o valor de uma variável (no caso do atendimento automático, a tecla que você pressionou) e compara com os "casos" que ele conhece, direcionando o programa para o rumo devido.

Sua sintaxe é:

ESCOLHA UM CASO

Onde a variável a ser lida é uma coisa qualquer que pode ter vários valores possíveis, como "tecla do telefone pressionada", "cor da ficha médica" e etc. A, B, C... são valores que a variável pode assumir (1,2,3, vermelho, verde e etc). RESTANTE é o caso em que a variável não assumiu nenhum dos outros caso. SAIR é o comando dado para, depois de ter executado as instruções do caso, sair do "ESCOLHA UM CASO" e continuar o programa. Se não tiver o SAIR ele vai, após executar as operações em um caso, saltar para o caso seguinte e assim por diante, até encontrar um "SAIR", ou executar as instruções do caso "RESTANTE".

Vamos a um exemplo:

Atendimento automático

Um exemplo de um atendimento automático. O programa lê o número teclado pelo usuário e envia o mesmo para o serviço requisitado. Se o usuário digitar uma tecla diferente de 1,2,3,4,ou 5 ele vai ser mandado para o atendimento geral. Depois de atendido (qualquer atendimento) o programa sai do "ESCOLHA UM CASO", passa o número do protocolo para o usuário e encerra a ligação.

Vejamos agora esse outro exemplo:

Atendimento hospitalar

É um algoritmo de atendimento médico. Conforme o sujeito chega no hospital ele é tratado de uma forma. Note que o "SAIR" foi suprimido. Qual o resultado disso? Se um sujeito chega com o estado grave, ele vai sofrer um cirurgia, realizar um tratamento com remédios, ficar de repouso, realizar uma consulta médica e receber uma conta. Ou seja, o "algoritmo" vai encaminhar o paciente para o seu "caso" e após realizar as instruções deste, ele vai realizar todas as instruções dos casos abaixo até sair do "ESCOLHA UM CASO".

Podemos colocar testes "SE ENTÃO" dentro das instruções de outro "SE ENTÃO", dentro de um "SE NÃO" dentro de um caso... podemos colocar um teste "ESCOLHA UM CASO" dentro das instruções de um "SE ENTÃO", dentro de um caso de outro "ESCOLHA UM CASO"... para fazer isso no entanto, sem gerar ambiguidade e sem nos confundimos, precisamos entender o conceito de bloco.de instruções.

Blocos de instruções são conjuntos de instruções "separadas", digamos assim, da linha do principal do algoritmo e elas só serão executadas se forem chamadas (em geral por um condicional, ou então por um loop). O bloco é iniciado e fechado por chaves "{}" e suas instruções recebem uma tabulação, ou seja, recebem um "espaço" à esquerda (apertando a tecla tab) antes de serem escritas.

Veja a figura:

Blocos de instruções

O nosso programa segue sua linha normal até que encontra esse SE ENTÃO de teste lógico A. Se este teste der verdadeiro ele executa o bloco AZUL, ou seja, a instrução1, depois a 2 e depois o teste lógico B. Se B for verdadeiro ele vai executar o bloco vermelho, se não, vai executar o bloco verde, que tem um teste lógico C dentro, podendo executar o bloco amarelo dentro do verde.

Nesse caso, o bloco azul é o mais externo e o amarelo é o mais interno, pois está dentro do verde, que está dentro do azul. O bloco vermelho e verde estão no mesmo nível.

Notem que as instruções de mesma cor recebem o mesmo "espaço" à esquerda. As instruções em azul receberam uma tabulação (tecla tab apertada uma vez), as em vermelho e em verde receberam duas tabulações e as em amarelo receberam três tabulações. a quantidade de tabulações indicam o nível dos blocos, quanto mais tabulações, mais interno está um bloco.

Observem como o programa irá proceder de acordo com o resultado dos testes lógicos:

Tabular seu algoritmo de acordo com a estrutura dos blocos é importante, principalmente para o entendimento do programa por parte de programador-revisor. Ainda que a tabulação seja supérflua para muitas linguagens (como por exemplo o C, que se você quiser escrever tudo numa linha, colocando os "; e {}" necessários, o compilador entende e executa sem problemas) ela evita que um colga de equipe mais sensível tenha um troço ao ver o seu programa, ou que um mais estressado lhe meta um murro na cara para lhe ensinar a ser mais caprichoso com o seu trabalho;

Eis como é visto o programador que não tabula corretamente o seu algoritmo:

Esse programador, não seja esse programador.

Ciclos:

Apesar de eu ter citado que existem dois tipos de ciclos (loops) anteriormente, aqui, no algoritmo escrito, nós só vamos ter um tipo genérico. Ele vai se chamar, hum... bem... "CICLO" e sua sintaxe será "CICLO{bloco de instruções}".  As instruções no bloco do ciclo serão executadas normalmente e, quando chegarmos na última, voltaremos automaticamente para a primeira.

O programa só sairá do "CICLO" quando a instrução "QUEBRAR CICLO" for executada. É obvio que essa instrução deverá estar dentro do ciclo a ser quebrado, não menos obvio, a quebra de ciclo deverá estar dentro de um condicional, se não o ciclo não funcionará de nada.

Veja o modelo:

um "CICLO"

Percebam que, ao entrar no ciclo, o programa vai executar 1-2-3-4-testeA, se A for falso ele vai executar 1-2-3-4-testeA de novo e de novo, até A ser verdadeiro e o ciclo ser quebrado.

Se houve um "CICLO" dentro de outro "CICLO" a "QUEBRA DE CICLO" só vai agir sobre o que ela (ou o condicional dela) estiver dentro. 

Veja o exemplo:

Um "relógio"

O nosso "programa" entra no primeiro ciclo (azul) e logo entra no segundo e no terceiro. Ele vai ficar executando o terceiro (verde) até completar 60 segundos. Feito isso, ele vai zerar o contador de segundos e vai executar uma "QUEBRA DE CICLO". Ele então vai ver qual ciclo ele está executando no momento, o mais interno e nesse caso é o ciclo verde, portanto ele vai sair SOMENTE do verde. Ai então ele vai adicionar um minuto e voltar para o topo do ciclo vermelho, entrar novamente no ciclo verde, contar 60 segundos e fazer isso repetidamente até completar 60 minutos. Nessa ocasião ele já vai estar fora do ciclo verde, mas ainda dentro do azul e do vermelho. Ele vai cumprir o teste "minutos == 60", vai zerar os minutos, vai encontrar uma "QUEBRA DE CICLO", vai ver que o ciclo mais externo que ele está executando no momento é o vermelho, vai sair do ciclo vermelho, vai cair no azul e etc, etc, etc.

Variáveis, entradas, saídas e operações matemáticas: 

Variáveis, como eu já disse, é qualquer coisa que possa assumir valores diversos. Os valores não precisam ser necessariamente numéricos (1, 1,5 , -10,), podem ser lógicos (verdadeiro, falso, sim, não, ligado, desligado, levantado, abaixado...), textuais ("Frederico", "nome", "rio", " "), ou qualitativos (vermelho, verde, azul, bom, muito bom, ruim). Por enquanto não vamos nos preocupar em "declarar" as variáveis, mas já saibam em um algoritmo, antes de qualquer coisa é declarado as variáveis que vão ser usadas no mesmo, ou seja é dito os nomes das variáveis e os tipos a qual elas pertencem.

Entradas são os dados recebidos de fora do programa. Quando o programa de auto-atendimento pede para o usuário apertar uma tecla e este assim o faz, este está mandando um dado para o programa, ou seja, o programa está recebendo uma entrada. Quando o médico do nosso algoritmo de atendimento olha o estado de um paciente, ele está recebendo uma "entrada", um dado externo. Vamos usar a instrução "LER variável" para obter uma entrada.

Saídas são o que o algoritmo retorna ao usuário. A imagem que você está vendo agora, não é nada mais que uma saída que o sistema operacional do seu computador está retornando para você. Vamos usar a instrução "IMPRIMA variável" ou "IMPRIMA "frase" " para expressar saídas.

As operações aritméticas simples podem ser executadas normalmente. Vale lembrar no entanto que {}, [] e () não tem mais valor matemático e não podem ser mais usados. Se tivermos uma expressão do tipo: 

E = A +{C*[D+C] - [D*(A-B) }

O melhor a fazermos é decompô-la:

G =A-B;

H=D*G;

I=D+C;

J=C*I-H;

E=A+J;

Funções matemáticas como "seno", "cosseno" e até operações como "raizquadrada", "potenciade2", serão expressadas como "FUNÇÃO(variável)", por exemplo: SENO(30), "RAIZQUADRADA(B+C)" e etc.

Exercícios: 

1) Escreva o algoritmo para que, dado os catetos b e c de um triângulo retângulo, se encontre o valor da hipotenusa.

2) Escreva o algoritmo para que, dado o valor da hipotenusa e de um ângulo não reto de um triângulo retângulo, se determine o valor dos catetos do mesmo.

3) Escreva o algoritmo para que, dado os coeficientes a, b e c de uma equação de segundo grau se determine as raízes dessa equação.

4) Escreva o algoritmo para um robô encher um balde de água.

5) Escreva o algoritmo para um frentista abastecer um carro.

6) Escreva o algoritmo para um frentista abastecer um carro de acordo com "l" litros que o cliente pedir.

7) Escreva o algoritmo para um frentista abastecer um carro de acordo com "l" litros de acordo com "r" reais que o cliente pedir em combustível, sabendo que esse combustível está a R$ 2,50 o litro.

8) Identifique as variáveis, os blocos, os condicionais, as entradas, as saídas e os ciclos dos problemas anteriores.

Bom pessoal, vamos ficando por aqui. Nossa próxima postagem está prevista para 04/10 e será sobre organogramas. Nesse dia também eu vou postar as respostas dos exercícios que eu postei hoje. Já vou avisando que se a greve tiver acabado (eu ainda não sei, estou escrevendo isso 10/09), vou parar de publicar quinzenalmente e passar a postar mensalmente. Eu não espero diminuir o ritmo da minha produção, mas eu tenho que armazenar postagens para, caso a coisa fique preta e eu fique sem tempo de escrever, vocês não fiquem sem postagens para ler.

Isso é tudo e até mais ver.

Respostas dos exercícios de 04/09

1) Se uma proposição tem "n" átomos e cada átomo só pode assumir um de dois valores (ou verdadeiro, ou falso), então existem 2n combinações possíveis de valores, ou seja, teremos 2n linhas.

2) Temos 4 átomos: (a,b,c,d), portanto teremos 24  linhas, ou seja 16 linhas. Agora, vamos às colunas: temos que ter uma coluna para cada átomo: 4, mais uma coluna para cada molécula "menor" ((a||b),(a&&b),(c||d)): 3, mais uma para cada molécula maior  ((a&&b)||(c||d)): 1 e uma para a proposição em si: 1. Com isso temos 4 + 3 + 1 +1 = 9 colunas.

3)

P

Q

R

S

T

U

V

X

Z

A

B

4)

P) Átomos:  a=ela,  b=eu. Moléculas: a^b= "ou ela, ou eu". Proposição: P = a^b. Tabela verdade:

Q) Átomos a = "aceite eu", b = "aceite o cachorro", c = "durma fora de casa". Moléculas: a&&b= "aceite eu e o cachorro", a&&b||c = "aceite eu e o cachorro ou vá dormir fora de casa". Proposição: Q = a&&b||c. Tabela verdade (Vide "T" do exercício anterior).

R) Átomos a = "dar um jeito no ninho metralhadoras", b = "dar um jeito naquele cara com lança foguetes", c= "dar a volta no morro", d = "atacar o inimigo por trás". Moléculas: a&&b = "dar um jeito no ninho de metralhadoras e no cara com lança foguetes", c&&d = "dar a volta no morro e atacar o inimigo por trás", (a&&b)||(c&&d) = "Dê a um jeito no ninho de metralhadoras e naquele cara com o lança foguetes, ou dê a volta no morro e ataque o inimigo por trás". Proposição: R =  (a&&b)||(c&&d). Tabela verdade:

S) Átomos a="bocejarás", b="arrotarás". Moléculas ~a = "não bocejarás", ~b="não arrotarás", (~a)&&(~b) = "não bocejarás e nem arrotarás". Proposição S =  (~a)&&(~b). Tabela verdade:

Algoritmos, introdução à lógica II

Dois mais três é igual a cinco. Poderíamos descrever muitas operações matemáticas textualmente, de fato por muito tempo elas foram feitas dessa maneira. No entanto é inegável que o uso de símbolos torna mais simples as operações. Da mesma forma a lógica tem seus símbolos e convenções, que visam facilitar o trabalho de quem a usa.

As proposições:

Os átomos, na lógica, são representado como letras minusculas do alfabeto. Já a proposição total a ser analisada  pode ser representada por uma letra maiúscula. Veja o exemplo:

A água do chuveiro está fria: Acabou o gás, ou aquecedor está no mínimo.

A proposição a ser analisada é:  "Acabou o gás, ou aquecedor está no mínimo". Temos dois átomos: 

a = "Acabou o gás" 

b = "aquecedor está no minimo"

A proposição então pode ser representada como:

A = a OU b

Conectores:

O  conector "E" é escrito na lógica matemática como "Λ". Porém, como estamos focados na área informática, usaremos "&" e "&&". O primeiro está ao nível de bits o segundo de conjunção lógica. Explicarei a diferença quando for conveniente, até lá vamos ignorar essa diferença.

Já o conector "OU" é escrito como um "V" na lógica matemática. Da mesma forma, vamos preferir a notação informática que é "|" e "||". O ou exclusivo, ou "XOR" é representado como um "V" na lógica matemática e como um "^" na informática, ao nível de bits.

O sinal de negação é, tanto na lógica matemática, quanto na informática, ao nível de bits, representado por um "~" e no nível lógico por um "!".

Exemplos:

A = a || b (a OU b)

B = a && b (a E b)

C = !a (não a)

Hierarquia das operações:

Assim como na aritmética as operações obedecem uma ordem de resolução a lógica e suas operações tem sua hierarquia.

Primeiramente são resolvidas as operações entre parênteses () , depois as entre colchetes [], as entre chaves  {} e por fim as externas. No entanto, em algoritmos computacionais, os colchetes e as chaves, em geral tem outras funções e por motivos de sintaxe só usamos os parênteses. Por isso a regra é resolver primeiro as operações nos parênteses mais internos e depois os mais externos. Ou seja, a operação:

!{a & [(b | c) | (a &d)]}

Ficaria:

!(a & ((b | c) | (a&d)))

E a ordem de operação seria:

1º) b | c

2º) a & d

3º) (b | c) | (a & d)

4º) a & ((b | c) | (a&d))

5º) !(a & ((b | c) | (a&d)))

Dentre as operações, as de negação são executadas em primeiro lugar as negações (! ou ~) e em seguida as conexões E, OU e OU exclusivo (&, | e ^). Sempre da esquerda para a direita.

Não estamos tratando delas aqui agora, mas só por curiosidade, as implicações SE  e SE E SOMENTE SE, são tratadas por último.

Tabela verdade:

A tabela verdade é uma poderosa ferramenta para analisar o valor lógico de uma proposição. Ela é simplesmente uma tabela (ou matriz) onde as colunas são constituídas pelos átomos, moléculas e finalmente a proposição inteira e as linhas são preenchidas pelos valores lógicos que os mesmos podem assumir. 

Vejamos este exemplo:

A = (a||b)&&(a&&c)

A tabela deverá ter nas 3 primeiras colunas os valores dos átomos a,b,c.  Na 4ª e na 5ª coluna as moléculas (a||b) e (a&&c) e por fim a proposição em si.

Como temos 3 átomos e cada um pode assumir apenas dois valores (verdadeiro ou falso), então para cobrir todas as combinação possíveis teremos 2x2x2, ou 2³, ou seja, 8 linhas. Com isso, podemos construir a seguinte tabela:

Tabela verdade

 Vamos preencher a primeira linha, supondo que todos os átomos são verdadeiros: 

Agora percebam: como "a" é verdadeiro e "b" é verdadeiro, "a || b" só poderá ser verdadeiro. Da mesma forma, como "a" e "c" são verdadeiros "a && c" será verdadeiro:

Como as duas moléculas são verdadeiras, a conexão das duas pelo conector "E" será verdadeira e a proposição por fim será verdadeira. 

A próxima linha será "a" e "b" verdadeiros e "c" falso, a terceira "a" e "c" verdadeiros e "b" falso e assim por diante, até cobrir todas as possibilidades. A análise das moléculas e da proposição vai variar, obviamente de acordo com o valor lógico dos átomos.

Ao final, nossa tabela ficará assim:

E com ela podemos analisar todos os resultados possíveis da proposição e a probabilidade de conseguirmos um valor verdadeiro.

Algumas tabelas verdade analisando conectores:

a E b

a OU b

a OU exclusivo b

não a

Exercícios:

"Muito que bem", vou a partir de agora passar alguns exercícios por postagem, para ajudar a fixar o conteúdo passado. As respostas aos exercícios serão postados juntos com o próximo item da série e eu estarei atento aos comentários para tirar eventuais dúvidas.

1) Se uma proposição tem "n" átomos, quantas linhas sua tabela verdade deverá ter?

2) A proposição P = (a || b) && ((a&&b)||(c||d)) gerará uma tabela verdade com quantas linhas? E quantas colunas ela deverá ter?

3) Monte as tabelas verdade das seguintes proposições:

P = (a||b) && c

Q = a || (~a)

R = a || b || c

S = a || b && c

T =  a && b || c

U  = a && b && c

V = (a||b) && ( b||c)

X = ((a&&b)||c)&&((a||d)&&(b||d))

Z = !(a||b)

A= !(a&&b)

B=!(a^b)

4) Identifique os átomos e moléculas, monte a expressão lógica usando a simbologia adequada e faça a tabela verdade das seguintes proposições:

P = Ou ela, ou eu!

Q = Aceite eu e o cachorro, ou vá dormir fora de casa.

R = Dê um jeito naquele ninho de metralhadoras e naquele cara com o lança foguetes, ou dê a volta no morro e ataque o inimigo por trás.

S = Não bocejarás e nem arrotarás!

Considerações finais:

Mais uma vez ressalto que o conteúdo aqui é adaptado. Posso ter omitido e até distorcido alguns conceitos da lógica matemática para facilitar o entendimento do leitor. Por isso se você tiver interesse em se aprofundar no assunto de fato, sugiro que procure apostilas na internet.

Na nossa próxima "aula" (prevista para 19/09), exploraremos as funções lógicas do BrOffice Calc/ MS Office Excel para construir pequenos programas.

Até mais ver.