Algoritmia

O que é um algoritmo?

Um algoritmo é uma sequência finita e bem definida de passos que resolve um problema ou realiza uma tarefa.

Já usas algoritmos todos os dias, mesmo sem lhes chamar isso: a receita de um bolo, as instruções para montar um móvel, o percurso que segues para chegar à escola.

Todos têm algo em comum:

têm um início e um fim claros;
são feitos de passos pequenos e concretos;
seguidos pela mesma ordem, dão sempre o mesmo resultado.

Em informática, escrever um programa é basicamente isto: descrever, passo a passo e sem ambiguidades, como resolver um problema — de forma tão precisa que até um computador (que não interpreta nem adivinha nada) consiga seguir.

Pensamento computacional: dividir para resolver

Quando um problema parece grande ou complicado, a estratégia mais eficaz é decompô-lo em problemas mais pequenos, até chegar a passos tão simples que sejam fáceis de resolver (ou de programar) um a um.

A isto chama-se decomposição de problemas, e é uma das quatro ideias-chave do pensamento computacional:

• Decomposição — dividir um problema grande em partes mais pequenas e mais fáceis de gerir.

• Reconhecimento de padrões — notar semelhanças entre problemas ou situações já resolvidas.

• Abstração — focar no que é essencial e ignorar detalhes irrelevantes para o problema.

• Algoritmos — desenhar a sequência de passos que leva à solução.

Hoje vamos focar-nos sobretudo na primeira: a decomposição. É a competência que vamos usar constantemente ao longo do semestre, sempre que passarmos de "o que quero fazer" para "como o vou construir, passo a passo, em código".

O algoritmo mais importante: Fazer uma sandes de fiambre

O problema: Como fazer uma sandes de fiambre

Como descrever a tarefa a alguém que nunca tenha feito uma sandes?

Passos:

Pegar em duas fatias de pão.
Abrir o frigorífico e retirar a manteiga e o fiambre.
Barrar manteiga numa das fatias.
Colocar 2-3 fatias de fiambre sobre a manteiga.
Colocar a segunda fatia de pão por cima.
Cortar a sandes ao meio.

Dúvidas:

O que aconteceria se trocássemos a ordem dos passos 3 e 5?
E se o passo 2 dissesse só "vai buscar as coisas", sem dizer quais?
E se não houver manteiga?

Repara no que torna isto um algoritmo e não só uma explicação vaga tipo "fazes uma sandes de fiambre":

• Cada passo é concreto e sem ambiguidade (não diz "prepara o pão", diz exatamente o quê).

• A ordem importa — barrar a manteiga antes de fechar a sandes, não depois.

• Se seguires os passos à risca, chegas sempre ao mesmo resultado.

Atividade de aula: Decompor um problema em grupo

Analisem os seguintes problemas e escrevam o algoritmo em linguagem natural (como no exemplo da sandes): uma lista numerada de passos concretos, na ordem certa.

Problema 1:

O problema: Como encher um copo de leite e aquecê-lo no microondas

Problema 2:

O problema: Preparar-se de manhã para sair de casa a horas

Regras:

Mínimo de 6 passos: deve começar com "Início" e acabar com "Fim"
Nada de passos vagos ("organizar tudo", "tratar disso")
Reparem se algum passo depende de uma decisão ("se estiver a chover, leva casaco"). Partilha com o professor.

Linguagens naturais vs. linguagens formais

O português (ou qualquer língua que falamos) é uma linguagem natural: rica, flexível, cheia de subentendidos. As linguagens naturais não são desenhadas por pessoas: podem ter diversas interpretações e transformações naturais ao longo do tempo.

São ótimas para conversar — péssimas para dar instruções a um computador.

Repara na ambiguidade que passa despercebida quando falamos naturalmente:

"Quanto é 2 mais 2?

Se a resposta estiver errada, mostra uma mensagem, senão soma um ponto."

Um ser humano percebe isto sem esforço.

Um computador precisa de saber exatamente: o que é "a resposta", onde está guardada, o que significa "estar errada" (comparação com quê?), o que é "mostrar" e onde é que o ponto é somado.

Outros exemplos de frases ambíguas

"Leve o cão ao veterinário com a trela azul." - De quem é a trela?

"Ordena a lista." - Crescente ou decrescente?

"Aumenta o valor." - Quanto?

"Grava o ficheiro." — onde? Com que nome? Em que formato?

"Repete até terminar." — até terminar o quê, exatamente? Qual é a condição que marca o fim?

Por esta razão usamos linguagens formais: têm regras fixas, vocabulário limitado e não toleram ambiguidade.

Ao contrário das linguagens naturais, as linguagens formais são desenhadas para determinados fins. São delineadas de modo a evitar equívocos na utilização dos termos, como por exemplo na Matemática ou na programação.

Linguagens de baixo nível e de alto nível

Dentro das linguagens formais, as linguagens de programação dividem-se, grosso modo, consoante a distância a que estão do que o processador realmente entende:

• Baixo nível — muito perto do hardware. Exemplos: linguagem máquina (sequências de 0s e 1s) e assembly. Rápidas e eficientes, mas difíceis de ler e escrever para humanos.

• Alto nível — muito mais perto da linguagem humana (normalmente inglês). Exemplos: Python, JavaScript, Java. Mais fáceis de aprender e ler, mas precisam de ser traduzidas (por um compilador ou interpretador) antes de o processador as conseguir executar.

O Python, que vamos usar, é uma linguagem de alto nível.

Exercício: Sintaxe e Semântica

1 - Investiga qual é a diferença entre a sintaxe e a semântica de uma linguagem.

2 - Dá dois exemplos de erros de sintaxe e de erros de semântica

Ferramentas de apoio à Algoritmia: Fluxogramas

Um fluxograma é uma maneira visual de explicar um raciocínio, usando formas com significados fixos:

Exemplo: Soma de dois números inteiros

No exemplo abaixo poderás ver o mesmo algoritmo descrito de várias maneiras, tal como o resultado final (output):

Atividade: Utilizar o Flowgorithm para escrever o nosso primeiro fluxograma

O Flowgorithm é uma ferramenta gráfica que permite criar fluxogramas, transformá-los e executá-los em forma de um programa.

Clica aqui para instalar

Abre o programa Flowgorithm
Cria o fluxograma acima no Flowgorithm
Executa e verifica que está correto

Exercício 1: Nome e idade de um utilizador

Crie um algoritmo no Flowgorithm com as etapas necessárias para a criação de um programa que efetue a leitura do seu primeiro nome e idade, mostrando estes dados de acordo com o apresentado no seguinte exemplo: “O João tem 17 anos.”

Exercício 2: Calcular o dobro

Crie um algoritmo no Flowgorithm que efetue a leitura de um número real e apresente o dobro deste.

Exercício 3: Conversor de medidas

Crie um algoritmo no Flowgorithm que efetue a leitura de uma medida em metros e apresente em decímetros, centímetros e milímetros.

Exercício 4.1: Linguagem natural para Fluxograma

Apresente sob a forma de fluxograma o algoritmo seguinte, desenvolvido em linguagem natural.

1. Início

2. Ler valor real (num1)

3. Ler valor real (num2)

4. Calcular o produto dos dois valores reais (produto = num1 X num2)

5. Calcular a divisão por 2 do produto (divisao = produto/ 2)

6. Escrever o resultado do produto: (produto)

7. Escrever o resultado da divisão: (divisao)

8. Fim

Teste e controlo de erros em algoritmia

O teste e o controlo de erros num algoritmo permitem verificar se este resolve o problema pretendido.

Para isso, utiliza-se a técnica do tracing (traçagem), que permite acompanhar passo a passo a execução de um algoritmo, eliminando, desta forma, a possibilidade de ocorrência de erros.

Ver exemplo abaixo:

Exercício 4.2: Linguagem natural para Fluxograma

Cria uma tabela de tracing do passo-a-passo do algoritmo do exercício 4.1.

Podes utilizar o caderno, Excel, Word ou qualquer ferramenta a teu gosto para desenhar a tabela.

Exercício 5: Troca valores e tracing

Considere o algoritmo seguinte:

Algoritmo troca_valores;

Variáveis a, b, c: lógico;

Início

a<-true;

b<-false;

c<-a;

a<-b;

b<-c;

Escrever (a, b);

Fim.

a) Apresente o algoritmo anterior, sob a forma de fluxograma.

b) Efetue o tracing deste algoritmo.

Ficha de Exercícios Nº1 - Algoritmia

Clica aqui para acederes -> https://forms.gle/LLaKUiiTLdhXp2Ap8

Page updated

Google Sites

Report abuse