Resumos · Aplicações Informáticas BPT · Secundário

Algoritmia

Estuda-se o que é um algoritmo e as suas propriedades, como se representa (pseudocódigo e fluxogramas), como se manipulam dados (variáveis, tipos, operadores e expressões) e como se controla a execução (sequência, seleção e repetição), terminando na construção, teste (teste de mesa) e depuração de algoritmos. É a primeira unidade de Aplicações Informáticas B, disciplina de opção do 12.º ano sem Exame Nacional, avaliada internamente com forte componente prática.

5 secções~16 min de leitura5 competênciasNível Base 2 · Padrão 2 · Aprofundamento 1

T·0111 / 9

Perfil de exame

Definir algoritmo e reconhecer as suas propriedadesRepresentar algoritmos em pseudocódigo e fluxogramaUsar corretamente variáveis, tipos, operadores e expressõesAplicar as estruturas de controlo (sequência, seleção, repetição)Testar e depurar algoritmos com teste de mesa

Operadores:definedescreverepresentaidentificatraduzcalculaaplicatesta

nível básico

Conceber e representar algoritmos simples em pseudocódigo e fluxograma, usando as estruturas de controlo básicas.

nível avançado

Construir algoritmos com repetição e seleção encadeadas e validá-los sistematicamente por teste de mesa.

Profundidade

Texto

Conteúdo · 5 secções

Algoritmia

Conceito de algoritmo e suas propriedades#

BaseAE-aplicacoes-informaticas-b-12-algoritmia

Um algoritmo é uma sequência finita e ordenada de passos não ambíguos que, a partir de um conjunto de dados de entrada, resolve um problema e produz um resultado (dados de saída) num número finito de operações. A ideia é anterior aos computadores — uma receita culinária ou as instruções para fazer um origami são algoritmos —, mas em informática o algoritmo é o coração da resolução de qualquer problema: primeiro pensa-se o algoritmo, só depois se escreve o programa. A palavra homenageia o matemático persa al-Khwarizmi (séc. IX).

Para ser correto, um algoritmo deve respeitar um conjunto de propriedades. É finito: termina após um número finito de passos (não pode ficar preso para sempre). É não ambíguo (definido): cada passo tem um significado único e preciso, sem interpretações. Tem entrada: zero ou mais dados fornecidos no início. Tem saída: um ou mais resultados. É efetivo: cada operação é elementar e realizável em tempo finito. Um conjunto de instruções que nunca termina, ou cujo passo «pensa numa boa solução» não é executável mecanicamente, não é um algoritmo válido.

Convém distinguir três noções próximas. O problema é aquilo que se quer resolver (por exemplo, «ordenar uma lista de nomes»). O algoritmo é a estratégia de resolução, descrita de forma independente da máquina e da linguagem. O programa é a tradução do algoritmo para uma linguagem de programação concreta, que o computador executa. O mesmo algoritmo pode dar origem a muitos programas (em Python, em C, etc.), e o mesmo problema pode ser resolvido por vários algoritmos diferentes, uns mais eficientes do que outros.

Todo o processamento segue o modelo entrada → processamento → saída (Fig. 1): recebem-se dados, transformam-se segundo o algoritmo e devolve-se o resultado. Perante um problema complexo, a estratégia fundamental é a decomposição (abordagem top-down): partir o problema em subproblemas mais simples, resolver cada um, e compô-los. Esta decomposição, além de tornar o problema tratável, é a base da programação modular (funções) que se estuda mais à frente. Antes de escrever qualquer passo, o bom programador clarifica exatamente quais são os dados de entrada, qual é o resultado esperado e que relação os liga.

Modelo entrada – processamento – saída

Fig. 1Fig. 1 — Todo o algoritmo transforma dados de entrada em dados de saída através de um processamento.

Exemplo resolvido

Algoritmo para o maior de dois números

Descreve, em passos numerados, um algoritmo que leia dois números A e B e escreva o maior. Identifica entrada e saída.

Dados
Entrada: dois números, A e B. Saída: o maior dos dois.
Passo 1
Ler A e ler B.
Passo 2
Se A ≥ B, então o maior é A; senão, o maior é B.
Passo 3
Escrever o valor do maior. Fim.

Resultado: Algoritmo finito (3 passos), não ambíguo, com entrada (A, B) e saída (o maior) — respeita todas as propriedades de um algoritmo.

Erros frequentes

Confundir algoritmo com programa: o algoritmo é a estratégia (independente da linguagem); o programa é a sua tradução para uma linguagem concreta.
Aceitar como algoritmo um conjunto de passos que não termina (viola a finitude) ou que contém uma instrução ambígua/não executável.

Revisão ativa

Escreve, por palavras tuas e em passos numerados, um algoritmo que receba dois números e determine (e escreva) o maior deles. Indica os dados de entrada e de saída.

Evocação ativa

Recorda os pontos-chave — depois revela.

Fontes: Aprendizagens Essenciais de Aplicações Informáticas B — 12.º ano (DGE) (Direção-Geral da Educação (DGE))

Representação de algoritmos: pseudocódigo e fluxogramas#

BaseAE-aplicacoes-informaticas-b-12-algoritmia

Um algoritmo tem de ser escrito de forma clara, rigorosa e independente de qualquer linguagem de programação. Usam-se sobretudo duas representações: o pseudocódigo (descrição textual estruturada) e o fluxograma (representação gráfica). Ambas exprimem exatamente a mesma lógica; a escolha é uma questão de conveniência e de comunicação. O pseudocódigo aproxima-se do código e é fácil de traduzir; o fluxograma dá uma visão global do fluxo de execução.

O pseudocódigo usa palavras-chave em linguagem quase natural para exprimir instruções e estruturas: «Início/Fim», «Ler»/«Escrever» (entrada/saída), a atribuição «←» (por exemplo «soma ← 0»), e as estruturas «Se … Então … Senão», «Enquanto … Fazer», «Para … De … Até … Fazer». A indentação (avanço) mostra o que está dentro de cada estrutura. Não há uma norma única de pseudocódigo — o essencial é ser coerente e não ambíguo.

O fluxograma representa o algoritmo com símbolos normalizados ligados por setas que indicam o sentido do fluxo (Fig. 2): a elipse (oval) marca o Início e o Fim; o paralelogramo representa a entrada/saída de dados (Ler/Escrever); o retângulo representa um processamento (um cálculo ou uma atribuição); e o losango representa uma decisão (uma condição), do qual saem dois caminhos rotulados «Verdadeiro» (V/Sim) e «Falso» (F/Não). Um fluxograma bem construído tem um único início, e todos os caminhos conduzem a um fim.

Fluxograma: o maior de dois números

Fig. 2Fig. 2 — Fluxograma do algoritmo «maior de dois números»: a decisão (losango) encaminha para escrever A ou B.

As duas representações são intertraduzíveis: a cada símbolo do fluxograma corresponde uma instrução de pseudocódigo e vice-versa. Por isso, na prática, esboça-se o algoritmo na representação que for mais cómoda e traduz-se depois. Saber ler e produzir ambas é uma competência central da disciplina, porque garante que o raciocínio está correto antes de se enfrentar a sintaxe de uma linguagem de programação.

Exemplo resolvido

Do pseudocódigo ao fluxograma

Escreve em pseudocódigo o algoritmo «maior de dois números» e indica a que símbolo do fluxograma corresponde cada linha.

Pseudocódigo
«Início» → «Ler A, B» → «Se A ≥ B Então Escrever A Senão Escrever B» → «Fim».
Correspondência
«Início»/«Fim» → elipses; «Ler A, B» → paralelogramo; «Se A ≥ B» → losango; «Escrever A»/«Escrever B» → paralelogramos.
Fluxo
O ramo Verdadeiro do losango conduz a «Escrever A»; o ramo Falso conduz a «Escrever B»; ambos terminam em «Fim» (ver Fig. 2).

Resultado: As duas representações descrevem o mesmo algoritmo: uma decisão binária que seleciona qual dos valores escrever.

Erros frequentes

Usar o símbolo errado no fluxograma — por exemplo, um retângulo (processo) onde devia estar um losango (decisão) ou um paralelogramo (entrada/saída).
Deixar um ramo da decisão sem saída ou o fluxograma sem um fim alcançável a partir de todos os caminhos.

Revisão ativa

Representa em pseudocódigo E em fluxograma um algoritmo que leia a idade de uma pessoa e escreva «Maior de idade» se for ≥ 18 e «Menor de idade» caso contrário.

Evocação ativa

Recorda os pontos-chave — depois revela.

Fontes: Aprendizagens Essenciais de Aplicações Informáticas B — 12.º ano (DGE) (Direção-Geral da Educação (DGE))

Variáveis, tipos de dados, operadores e expressões#

PadrãoAE-aplicacoes-informaticas-b-12-algoritmia

Uma variável é uma posição de memória com um nome (identificador) que guarda um valor que pode mudar ao longo da execução. Uma constante guarda um valor que não muda (por exemplo «PI ← 3,14159»). O identificador deve ser significativo (por exemplo «total», «numAlunos»), começar por letra e não coincidir com palavras reservadas. A operação de atribuição «variável ← expressão» calcula a expressão à direita e guarda o resultado na variável à esquerda; «x ← x + 1» lê-se «o novo x é o antigo x mais um».

Cada valor tem um tipo de dados, que determina os valores possíveis e as operações permitidas (Fig. 3). Os tipos básicos são: inteiro (números sem parte decimal: …, −1, 0, 1, 2, …), real (números com parte decimal: 3,14; −0,5), booleano (lógico: apenas Verdadeiro ou Falso) e caráter/cadeia (um caráter ou uma sequência de carateres — texto, escrito entre aspas: «"Olá"»). Usar o tipo certo é importante: dividir dois inteiros pode dar um real, e não se somam diretamente números com texto.

Tipos de dados básicos

Fig. 3Fig. 3 — Os tipos de dados básicos, com exemplos de valores e de operações.

Os operadores combinam valores em expressões. Os aritméticos operam sobre números: «+», «−», «*» (multiplicação), «/» (divisão real), «div» (quociente inteiro) e «mod» (resto da divisão inteira) — por exemplo «17 div 5 = 3» e «17 mod 5 = 2». Os relacionais comparam valores e produzem um booleano: «<» (menor), «>» (maior), «≤» (menor ou igual), «≥» (maior ou igual), «=» (igual) e «≠» (diferente). Os lógicos combinam booleanos: «E» (conjunção — só é verdadeiro se ambos o forem), «ou» (disjunção — verdadeiro se pelo menos um o for) e «não» (negação).

Numa expressão, os operadores são avaliados por ordem de precedência (prioridade), tal como na matemática: primeiro «não»; depois «*», «/», «div», «mod»; depois «+» e «−»; depois os relacionais; e por fim «E» e «ou». Em caso de igualdade de prioridade, avalia-se da esquerda para a direita. Os parênteses forçam a ordem e devem usar-se sempre que houver dúvida — tornam a expressão inequívoca e legível. Perceber a precedência é essencial para prever corretamente o valor de uma expressão.

Exemplo resolvido

Avaliação de uma expressão com precedência

Calcula, passo a passo, o valor da expressão «2 + 3 * 4 − 10 div 3».

Operadores de maior prioridade
Primeiro «» e «div» (da esquerda para a direita): 3 4 = 12 e 10 div 3 = 3 (quociente inteiro; sobra resto 1).
Substituir
A expressão reduz-se a «2 + 12 − 3».
Adição e subtração
2 + 12 = 14; 14 − 3 = 11.

Resultado: A expressão vale 11. (Nota: 10/3 ≈ 3,33 seria a divisão real; «div» dá apenas o quociente inteiro 3.)

Erros frequentes

Confundir a divisão real «/» com o quociente inteiro «div» e o resto «mod» (por exemplo, escrever 17/5 = 3 quando 17/5 = 3,4 e 17 div 5 = 3).
Trocar a atribuição «←» (ou «=» em muitas linguagens) pela igualdade de comparação; «x ← 5» guarda 5 em x, não afirma que x é igual a 5.

Revisão ativa

Indica o tipo de dados adequado para: (a) o número de alunos de uma turma; (b) a altura em metros; (c) a resposta a «é maior de idade?»; (d) o nome de uma pessoa. Depois calcula o valor de «10 + 6 div 2 * 3».

Evocação ativa

Recorda os pontos-chave — depois revela.

Fontes: Aprendizagens Essenciais de Aplicações Informáticas B — 12.º ano (DGE) (Direção-Geral da Educação (DGE))

Estruturas de controlo: sequência, seleção e repetição#

PadrãoAE-aplicacoes-informaticas-b-12-algoritmia

O fluxo de execução de um algoritmo é organizado por três estruturas de controlo, e demonstra-se (Teorema da Programação Estruturada) que qualquer algoritmo se pode escrever apenas com elas: sequência, seleção e repetição. A sequência é a mais simples — as instruções executam-se uma após a outra, pela ordem em que aparecem. As outras duas permitem que o fluxo se ramifique ou se repita conforme os dados.

A seleção (decisão) escolhe entre caminhos conforme uma condição. Na forma simples, «Se condição Então instruções» só executa quando a condição é verdadeira. Na forma completa, «Se condição Então A Senão B» executa A quando é verdadeira e B quando é falsa. Encadeando várias («Se … Senão Se … Senão …») escolhe-se entre vários casos; quando há muitos valores possíveis de uma mesma variável, usa-se a estrutura de seleção múltipla «Caso» (o «switch» das linguagens). A condição é sempre uma expressão booleana.

A repetição (ciclo/iteração) repete um bloco de instruções (o corpo do ciclo) enquanto se justificar. Há dois grandes tipos. Os ciclos controlados por condição: «Enquanto condição Fazer …» testa a condição antes de cada iteração (pode não executar nenhuma vez); «Repetir … Até condição» testa depois (executa sempre pelo menos uma vez). O ciclo controlado por contador: «Para i De 1 Até N Fazer …» repete um número de vezes conhecido, atualizando automaticamente a variável de controlo. A Fig. 4 mostra um ciclo «Enquanto» que soma os inteiros de 1 a N.

Fluxograma de um ciclo «Enquanto» (soma de 1 a N)

Fig. 4Fig. 4 — Ciclo «Enquanto i ≤ N»: acumula a soma e incrementa i; quando a condição é falsa, escreve o resultado.

Todo o ciclo controlado por condição precisa de uma condição de paragem que acabe por tornar-se falsa: dentro do corpo, alguma variável tem de evoluir em direção a essa condição (por exemplo, um contador que aumenta). Se isso não acontecer, obtém-se um ciclo infinito — o programa nunca termina, violando a propriedade da finitude. Escolher a estrutura certa (contador quando o número de repetições é conhecido; condição quando depende dos dados) e garantir a paragem são competências decisivas.

\sum_{i=1}^{N} i = 1 + 2 + \cdots + N = \dfrac{N\,(N+1)}{2}

Soma dos primeiros N inteiros

O ciclo da Fig. 4 acumula esta soma; para N = 5 dá 5×6/2 = 15, útil para verificar o resultado do algoritmo.

Exemplo resolvido

Somar os inteiros de 1 a 5 com um ciclo

Executa mentalmente o ciclo «Enquanto i ≤ N» da Fig. 4 para N = 5 e indica o valor final de «soma».

Inicialização
soma ← 0; i ← 1. A condição é «i ≤ 5».
Iterações
i=1: soma=1; i=2: soma=3; i=3: soma=6; i=4: soma=10; i=5: soma=15. Depois i passa a 6.
Paragem
Com i = 6, «6 ≤ 5» é falso: o ciclo termina e escreve-se soma.
$\dfrac{N(N+1)}{2} = \dfrac{5\cdot 6}{2} = 15$

Resultado: soma = 15, em concordância com a fórmula N(N+1)/2 — o ciclo está correto e termina (i cresce até falhar a condição).

Erros frequentes

Escrever um ciclo sem atualizar a variável da condição de paragem, gerando um ciclo infinito.
Confundir «Enquanto» (testa antes, pode não executar) com «Repetir … Até» (testa depois, executa sempre ao menos uma vez).

Revisão ativa

Escreve em pseudocódigo um algoritmo que leia números até ser lido o valor 0 e, no fim, escreva quantos números positivos foram lidos. Indica qual a estrutura de repetição mais adequada.

Evocação ativa

Recorda os pontos-chave — depois revela.

Fontes: Aprendizagens Essenciais de Aplicações Informáticas B — 12.º ano (DGE) (Direção-Geral da Educação (DGE))

Construção, teste e depuração de algoritmos#

AprofundamentoAE-aplicacoes-informaticas-b-12-algoritmia

Construir um algoritmo é um processo disciplinado, não um lance de sorte. Começa-se por compreender bem o problema (dados de entrada, saída esperada, restrições), decompõe-se em subproblemas (top-down), escolhem-se as estruturas de controlo adequadas e escreve-se o algoritmo em pseudocódigo ou fluxograma. Só depois de o algoritmo estar pensado e verificado se passa ao código. Um algoritmo pode estar sintaticamente «bem escrito» e mesmo assim estar errado — daí a necessidade de o testar.

A técnica central de verificação manual é o teste de mesa (ou traçado): simula-se a execução do algoritmo passo a passo, registando numa tabela o valor de cada variável em cada iteração (Fig. 5). O teste de mesa revela erros de lógica que a leitura distraída não apanha — um contador mal inicializado, uma condição trocada, um ciclo que executa uma vez a mais ou a menos (o erro «off-by-one»). É a forma mais eficaz de ganhar confiança de que o algoritmo faz o que se pretende antes de o programar.

Teste de mesa: maior de uma lista

Fig. 5Fig. 5 — Teste de mesa do algoritmo «maior da lista [3, 9, 2, 7]»: a variável «maior» só muda quando surge um elemento maior.

Um bom conjunto de testes cobre casos representativos: casos normais (dados típicos), casos limite (fronteira — uma lista vazia, o valor zero, o primeiro e o último elemento) e casos inválidos (dados que não deviam ocorrer, para ver como o algoritmo reage). Escolher os casos de teste com intenção — em especial os limites — é o que distingue uma verificação séria de uma verificação superficial.

Quando um teste revela um comportamento errado, entra a depuração (debugging): localizar a causa e corrigir. Distinguem-se três tipos de erro. Os erros de sintaxe violam as regras da linguagem (uma palavra-chave mal escrita) e impedem a tradução/execução. Os erros de execução (run-time) surgem durante a execução (uma divisão por zero, um índice fora dos limites). Os erros de lógica são os mais perigosos: o programa corre sem se queixar, mas produz um resultado errado — só o teste os deteta. A par da correção, considera-se ainda a eficiência: entre dois algoritmos corretos, prefere-se o que resolve o problema com menos passos.

Exemplo resolvido

Teste de mesa do maior de uma lista

Faz o teste de mesa do algoritmo que determina o maior valor da lista [3, 9, 2, 7]: inicia «maior» com o primeiro elemento e percorre os restantes, atualizando «maior» sempre que encontra um valor superior.

Inicialização
maior ← 3 (o primeiro elemento da lista).
Elemento 9
9 > 3 é Verdadeiro → maior ← 9.
Elemento 2
2 > 9 é Falso → maior mantém-se 9.
Elemento 7
7 > 9 é Falso → maior mantém-se 9. Fim da lista.

Resultado: maior = 9. O teste de mesa (Fig. 5) confirma que o algoritmo está correto, incluindo o caso limite do primeiro elemento (usado como valor inicial).

Erros frequentes

Confiar num algoritmo só porque «parece certo», sem o testar — os erros de lógica não se manifestam na tradução, só nos resultados.
Testar apenas casos típicos e esquecer os casos limite (lista vazia, primeiro/último elemento), onde o erro «off-by-one» costuma esconder-se.

Revisão ativa

Faz o teste de mesa de um algoritmo que percorre a lista [4, 1, 7, 3] e determina o menor valor. Constrói a tabela com as colunas «elemento» e «menor» e indica o resultado.

Evocação ativa

Recorda os pontos-chave — depois revela.

Fontes: Aprendizagens Essenciais de Aplicações Informáticas B — 12.º ano (DGE) (Direção-Geral da Educação (DGE))

Referências e fontes

Fontes

Direção-Geral da Educação (DGE)

Aprendizagens Essenciais de Aplicações Informáticas B — 12.º ano (DGE)

Algoritmia

5 secções~16 min de leitura5 competênciasNível Base 2 · Padrão 2 · Aprofundamento 1

Algoritmia

Pontos-chave

Algoritmo para o maior de dois números

Pontos-chave

Do pseudocódigo ao fluxograma

Pontos-chave

Avaliação de uma expressão com precedência

Pontos-chave

Somar os inteiros de 1 a 5 com um ciclo

Pontos-chave

Teste de mesa do maior de uma lista

Fontes

Algoritmia

Pontos-chave

Algoritmo para o maior de dois números

Pontos-chave

Do pseudocódigo ao fluxograma

Pontos-chave

Avaliação de uma expressão com precedência

Pontos-chave

Somar os inteiros de 1 a 5 com um ciclo

Pontos-chave

Teste de mesa do maior de uma lista

Fontes