Notations, stepwise refinement and logic · Notações, refinamento passo a passo e lógica
| English | Português |
|---|---|
| notation/nəʊˈteɪʃn/ | notação |
| structured English/ˈstrʌktʃəd ˈɪŋɡlɪʃ/ | inglês estruturado |
| pseudocode/ˈsuːdəʊkəʊd/ | pseudocódigo |
| flowchart/ˈfləʊtʃɑːt/ | fluxograma |
| stepwise refinement/ˈstepwaɪz rɪˈfaɪnmənt/ | refinamento passo a passo |
| logic statement/ˈlɒdʒɪk ˈsteɪtmənt/ | declarativa lógica |
| Boolean/ˈbuːlɪən/ | Boolean |
| precedence/ˈpresɪdəns/ | precedência |
| De Morgan's law/də ˈmɔːɡənz lɔː/ | lei de De Morgan |
The first algorithm had no language to be written in
- In 1843 Ada Lovelace published the steps for computing Bernoulli numbers on Babbage's Analytical Engine, a machine that was never built.
- There was no programming language, so she wrote the algorithm as a numbered table of operations: a notation 记法 of her own.
- Every algorithm still starts that way. You write it down in some notation, check it, and only then turn it into code.
- This lesson is about the three notations the exam uses, how to move between them, and how to write the conditions inside them.
O primeiro algoritmo não tinha linguagem para ser escrito
- Em 1843, Ada Lovelace publicou os passos para calcular números de Bernoulli na Máquina Analítica de Babbage, uma máquina que nunca foi construída.
- Não havia linguagem de programação, então ela escreveu o algoritmo como uma tabela numerada de operações: uma notação 记法 de sua própria criação.
- Todo algoritmo ainda começa assim. Você o escreve em alguma notação, verifica-o, e só então o transforma em código.
- Esta lição trata das três notações que a prova usa, como transitar entre elas, e como escrever as condições dentro delas.
Three notations
- Structured English 结构化英语: ordinary sentences, indented, with a few fixed words such as
IF,FOR EACH,REPEAT. Good for a first outline. - Pseudocode 伪代码: the keyword notation (
IF … ENDIF,WHILE … ENDWHILE,FOR … NEXT), closest to real code and marked against Cambridge's guide. - Flowchart 流程图: a diagram of standard shapes. Rounded rectangle for
START/STOP, parallelogram for input and output, rectangle for a process, diamond for a decision, arrows for the flow.
A flowchart for averaging a list of numbers, drawn with the standard shapes
Três notações
- Inglês estruturado 结构化英语: frases comuns, indentadas, com algumas palavras fixas como
IF,FOR EACH,REPEAT. Bom para um primeiro esboço. - Pseudocódigo 伪代码: a notação de palavras-chave (
IF … ENDIF,WHILE … ENDWHILE,FOR … NEXT), mais próxima do código real e avaliada contra o guia do Cambridge. - Fluxograma 流程图: um diagrama de formas padrão. Retângulo arredondado para
START/STOP, paralelograma para entrada e saída, retângulo para processo, losango para decisão, setas para o fluxo.
Um fluxograma para calcular a média de uma lista de números, desenhado com as formas padrão
In a flowchart, which shape represents a decision? · Em um fluxograma, qual forma representa uma decisão?
A diamond is a decision; rounded rectangle = start/stop, parallelogram = input/output, rectangle = process. · Um losango é uma decisão; retângulo arredondado = início/parada, paralelogramo = entrada/saída, retângulo = processo.
Match each flowchart shape to its meaning. · Combine cada forma de fluxograma com seu significado.
Parallelogram = I/O, rectangle = process, rounded rectangle = start/stop, diamond = decision. · Paralelogramo = E/S, retângulo = processo, retângulo arredondado = início/parada, losango = decisão.
Match each notation to its description. · Combine cada notação com sua descrição.
All three describe the same algorithm at different distances from the code. · As três descrevem o mesmo algoritmo em diferentes distâncias do código.
Worked example: structured English to pseudocode
- Structured English: Set the total to zero. For each of the N numbers, add it to the total. Divide the total by N and output the result.
- Each sentence becomes one construct: an assignment, a
FORloop with an assignment inside it, then an assignment and an output.
- The order of the sentences is the order of the statements. Nothing is added and nothing is left out.
Exemplo resolvido: inglês estruturado para pseudocódigo
- Inglês estruturado: Defina o total como zero. Para cada um dos N números, adicione-o ao total. Divida o total por N e exiba o resultado.
- Cada frase se torna um constructo: uma atribuição, um laço
FORcom uma atribuição dentro dele, depois uma atribuição e uma saída.
Total <- 0
FOR Index <- 1 TO N
Total <- Total + Number[Index]
NEXT Index
Average <- Total / N
OUTPUT Average
- A ordem das frases é a ordem das instruções. Nada é adicionado e nada é deixado de fora.
In the averaging algorithm, the FOR loop that adds each number to the total is an example of the ____ construct. · No algoritmo de média, o loop FOR que adiciona cada número ao total é um exemplo da construção de ____.
Repeating a block for each number is iteration. The assignment inside it stores the running total. · Repetir um bloco para cada número é iteração. A atribuição dentro dele armazena o total acumulado.
Worked example: pseudocode to flowchart
- Take the same algorithm.
STARTgoes in a rounded rectangle,Total ← 0andIndex ← 1in rectangles. - The
FORloop becomes a diamond askingIndex <= N?. The Yes exit leads to the rectangleTotal ← Total + Number[Index], thenIndex ← Index + 1, and an arrow back up to the diamond. - The No exit continues to
Average ← Total / N, an output parallelogram, andSTOP. - Label both exits of every diamond. A diamond with one unlabelled exit is not a decision.
Exemplo resolvido: pseudocódigo para fluxograma
- Pegue o mesmo algoritmo.
STARTvai em um retângulo arredondado,Total ← 0eIndex ← 1em retângulos. - O laço
FORtorna-se um losango perguntandoIndex <= N?. A saída Sim leva ao retânguloTotal ← Total + Number[Index], depoisIndex ← Index + 1, e uma seta de volta para cima até o losango. - A saída Não continua para
Average ← Total / N, um paralelograma de saída, eSTOP. - Rotule ambas as saídas de todo losango. Um losango com uma saída não rotulada não é uma decisão.
Stepwise refinement
- Stepwise refinement 逐步求精 means writing an algorithm as a short outline, then expanding each step into more detailed sub-steps, and repeating until every step can be coded directly.
- Each level keeps the structure of the level above and adds detail. The outline is not thrown away: it becomes the structure of the program.
- The design stops when a step is one line of pseudocode or one module you already have.
Stepwise refinement expands each step until it can be coded
Refinamento passo a passo
- Refinamento passo a passo 逐步求精 significa escrever um algoritmo como um esboço curto, depois expandir cada passo em sub-passos mais detalhados, e repetir até que cada passo possa ser codificado diretamente.
- Cada nível mantém a estrutura do nível acima e adiciona detalhes. O esboço não é descartado: ele se torna a estrutura do programa.
- O projeto para quando um passo é uma linha de pseudocódigo ou um módulo que você já tem.
Refinamento passo a passo expande cada passo até que possa ser codificado
Stepwise refinement is the technique of: · Refinamento passo a passo é a técnica de:
You refine a high-level outline level by level, adding detail while keeping the structure. · Você refina um esboço de alto nível nível por nível, adicionando detalhes mantendo a estrutura.
Worked example: three levels
- Level 1: Process the exam results.
- Level 2: Input each mark. Calculate the mean. Count how many passed. Output the report.
- Level 3, refining "count how many passed":
Passes ← 0, thenFOReach mark,IF Mark >= 40 THEN Passes ← Passes + 1. - Asked to "describe stepwise refinement", give the three ideas: start from an outline, expand each step into smaller steps, stop when each step can be programmed.
Exemplo resolvido: três níveis
- Nível 1: Processar os resultados do exame.
- Nível 2: Entrar cada nota. Calcular a média. Contar quantos passaram. Exibir o relatório.
- Nível 3, refinando "contar quantos passaram":
Passes ← 0, entãoFORpara cada nota,IF Mark >= 40 THEN Passes ← Passes + 1. - Perguntado para "descrever refinamento passo a passo", dê as três ideias: começar de um esboço, expandir cada passo em passos menores, parar quando cada passo puder ser programado.
Stepwise refinement: outline to code · Refinamento passo a passo: esboço para código
Step down the levels. You start with the whole task in one line and keep expanding each step into smaller ones — until every step is simple enough to code directly. · Desça pelos níveis. Você começa com a tarefa inteira em uma linha e continua expandindo cada passo em partes menores — até que todos os passos sejam simples o suficiente para serem codificados diretamente.
In stepwise refinement, each new level replaces the level above it, so the original outline is thrown away. · No refinamento passo a passo, cada novo nível substitui o nível acima, então o esboço original é descartado.
Each level keeps the structure of the one above and adds detail. The outline becomes the shape of the finished program. · Cada nível mantém a estrutura do nível acima e adiciona detalhes. O esboço torna-se a forma do programa final.
Logic statements
- A logic statement 逻辑语句 is a Boolean 布尔 condition: it is either
TRUEorFALSE, and it controls anIF, aWHILEor anUNTIL. - It is built from comparisons (
=,<>,<,>,<=,>=) joined byAND,ORandNOT. Mark >= 0 AND Mark <= 100is true only for marks in range.Age < 12 OR Age >= 65is true for children and pensioners.
Comparisons joined by AND, OR and NOT make one condition
Declarações lógicas
- Uma declaração lógica 逻辑语句 é uma condição Booleana 布尔: ela é ou
TRUEouFALSE, e controla umIF, umWHILEou umUNTIL. - Ela é construída a partir de comparações (
=,<>,<,>,<=,>=) unidas porAND,OReNOT. Mark >= 0 AND Mark <= 100é verdadeiro apenas para notas em faixa.Age < 12 OR Age >= 65é verdadeiro para crianças e pensionistas.
Comparações unidas por AND, OR e NOT fazem uma condição
Precedence and brackets
- Operators are applied in a fixed order of precedence 优先级:
NOTfirst, thenAND, thenOR. - So
A OR B AND CmeansA OR (B AND C), not(A OR B) AND C. WithA = TRUE,B = FALSE,C = FALSEthe first isTRUEand the second isFALSE. - Use brackets whenever a condition mixes
ANDandOR. They cost nothing and remove the ambiguity.
Precedência e parênteses
- Operadores são aplicados em uma ordem fixa de precedência 优先级:
NOTprimeiro, depoisAND, depoisOR. - Então
A OR B AND CsignificaA OR (B AND C), não(A OR B) AND C. ComA = TRUE,B = FALSE,C = FALSEo primeiro éTRUEe o segundo éFALSE. - Use parênteses sempre que uma condição misturar
ANDeOR. Eles não custam nada e removem a ambiguidade.
Put the logic operators in order of precedence, highest (evaluated first) to lowest. · Coloque os operadores lógicos em ordem de precedência, do mais alto (avaliado primeiro) ao mais baixo.
NOT binds tightest, then AND, then OR — use brackets when in doubt. · NOT liga-se mais fortemente, depois AND, depois OR — use parênteses quando tiver dúvidas.
With no brackets, what does A OR B AND C mean? · Sem parênteses, o que significa A OR B AND C?
AND has higher precedence than OR, so it is evaluated first. Bracket the condition anyway, so nobody has to remember. · AND tem maior precedência que OR, então é avaliado primeiro. Envolva a condição em parênteses de qualquer forma, para ninguém precisar lembrar.
De Morgan's laws
- De Morgan's law 德摩根定律:
NOT (A AND B)is the same as(NOT A) OR (NOT B), andNOT (A OR B)is the same as(NOT A) AND (NOT B). - In words: "not (registered and paid)" means "not registered, or not paid".
- Use it to simplify a condition, or to check one: pick values for
AandB, work out both sides, and they must agree in every case.
Leis de De Morgan
- Lei de De Morgan 德摩根定律:
NOT (A AND B)é o mesmo que(NOT A) OR (NOT B), eNOT (A OR B)é o mesmo que(NOT A) AND (NOT B). - Em palavras: "não (registrado e pago)" significa "não registrado, ou não pago".
- Use para simplificar uma condição, ou para verificar uma: escolha valores para
AeB, calcule ambos os lados, e eles devem concordar em todos os casos.
By De Morgan's law, NOT (A AND B) is the same as (NOT A) OR (NOT B). · Pela lei de De Morgan, NOT (A AND B) é o mesmo que (NOT A) OR (NOT B).
NOT distributes over the bracket and flips AND↔OR; likewise NOT (A OR B) = (NOT A) AND (NOT B). · NOT se distribui sobre o parêntese e inverte AND↔OR; da mesma forma NOT (A OU B) = (NOT A) E (NOT B).
Worked example: a condition from words
- Rule: a student may sit the exam if they are registered and have either paid or hold a bursary, but not if they are suspended.
- Name the Boolean variables:
Registered,Paid,Bursary,Suspended. - Statement:
Registered AND (Paid OR Bursary) AND NOT Suspended. - The brackets around
Paid OR Bursaryare essential. Without them,ANDbinds first and a student with a bursary but no registration would get in.
Exemplo resolvido: uma condição a partir de palavras
- Regra: um aluno pode fazer o exame se estiver registrado e tiverEither pago ou ter uma bolsa, mas não se estiver suspenso.
- Nomeie as variáveis Booleanas:
Registered,Paid,Bursary,Suspended. - Declaração:
Registered AND (Paid OR Bursary) AND NOT Suspended. - Os parênteses em torno de
Paid OR Bursarysão essenciais. Sem eles,ANDassocia primeiro e um aluno com bolsa mas sem registro entraria.
Which conditions are equivalent to NOT (Registered AND Paid)? Select all · todos that apply. · Quais condições são equivalentes a NOT (Registered AND Paid)? Selecione todos os que se aplicam.
De Morgan turns NOT of an AND into an OR of the NOTs. The AND version is too strict: a student who is registered but has not paid should make the original condition TRUE, and it makes the AND version FALSE. · De Morgan transforma NÃO de um E em UM OU dos NÃOs. A versão E é muito estrita: um aluno que está matriculado mas não pagou deve tornar a condição original VERDADEIRA, e torna a versão E FALSA.
Marks that slip away
a = 1 OR 2is not a condition. Writea = 1 OR a = 2: each side ofORmust be a complete comparison.NOTapplies only to what follows it.NOT A AND Bmeans(NOT A) AND B.- A diamond needs two labelled exits, and a loop needs an arrow that goes back up. A flowchart with no arrow returning is not a loop.
- Structured English is still precise. "Deal with the marks" is not a step; "add the mark to the total" is.
Marcas que escapam
a = 1 OR 2não é uma condição. Escrevaa = 1 OR a = 2: cada lado deORdeve ser uma comparação completa.NOTse aplica apenas ao que vem depois.NOT A AND Bsignifica(NOT A) AND B.- Um losango precisa de duas saídas rotuladas, e um laço precisa de uma seta que volte para cima. Um fluxograma sem seta retornando não é um laço.
- Inglês estruturado ainda é preciso. "Lidar com as notas" não é um passo; "somar a nota ao total" é.
To test whether a is 1 or 2, the correct condition is: · Para testar se a é 1 ou 2, a condição correta é:
Each side of OR must be a full comparison: a = 1 OR a = 2. Writing a = 1 OR 2 is a common error. · Cada lado de OU deve ser uma comparação completa: a = 1 OR a = 2. Escrever a = 1 OR 2 é um erro comum.
You've got it
- three notations for one algorithm: structured English, pseudocode, flowchart (diamond = decision, back-arrow = loop)
- stepwise refinement: outline → expand each step → stop when a step can be coded
- a logic statement is a Boolean condition; precedence NOT → AND → OR, so bracket anything that mixes them
- De Morgan:
NOT (A AND B)=NOT A OR NOT B;NOT (A OR B)=NOT A AND NOT B
Entendeu?
- três notações para um algoritmo: inglês estruturado, pseudocódigo, fluxograma (losango = decisão, seta de retorno = laço)
- refinamento passo a passo: esboço → expandir cada passo → parar quando um passo puder ser codificado
- uma declaração lógica é uma condição Booleana; precedência NOT → AND → OR, então parenteze tudo que os mistura
- De Morgan:
NOT (A AND B)=NOT A OR NOT B;NOT (A OR B)=NOT A AND NOT B