Notations, stepwise refinement and logic · Notations, raffinement progressif et logique
| English | Français |
|---|---|
| notation/nəʊˈteɪʃn/ | notation |
| structured English/ˈstrʌktʃəd ˈɪŋɡlɪʃ/ | anglais structuré |
| pseudocode/ˈsuːdəʊkəʊd/ | pseudocode |
| flowchart/ˈfləʊtʃɑːt/ | diagramme de flux |
| stepwise refinement/ˈstepwaɪz rɪˈfaɪnmənt/ | affinement successif |
| logic statement/ˈlɒdʒɪk ˈsteɪtmənt/ | énoncé logique |
| Boolean/ˈbuːlɪən/ | Boolean |
| precedence/ˈpresɪdəns/ | prévalence |
| De Morgan's law/də ˈmɔːɡənz lɔː/ | loi 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.
Le premier algorithme n'avait pas de langage dans lequel il pouvait être écrit
- En 1843, Ada Lovelace publia les étapes pour calculer les nombres de Bernoulli sur la Machine analytique de Babbage, une machine qui ne fut jamais construite.
- Il n'y avait pas de langage de programmation, elle écrivit donc l'algorithme sous forme de tableau numéroté d'opérations : une notation 记法 de son cru.
- Tout algorithme commence ainsi. Vous l'écrivez dans une certaine notation, le vérifiez, et seulement ensuite le transformez en code.
- Cette leçon porte sur les trois notations utilisées par l'examen, comment passer de l'une à l'autre, et comment écrire les conditions à l'intérieur.
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
Trois notations
- Anglais structuré 结构化英语 : phrases ordinaires, indentées, avec quelques mots fixes comme
IF,FOR EACH,REPEAT. Bon pour un premier plan. - Pseudocode 伪代码 : la notation par mots-clés (
IF … ENDIF,WHILE … ENDWHILE,FOR … NEXT), la plus proche du vrai code et évaluée selon le guide de Cambridge. - Diagramme de flux 流程图 : un schéma de formes standards. Rectangle arrondi pour
START/STOP, parallélograme pour l'entrée et la sortie, rectangle pour un processus, losange pour une décision, flèches pour le flux.
Un diagramme de flux pour la moyenne d'une liste de nombres, dessiné avec les formes standards
In a flowchart, which shape represents a decision? · Dans un organigramme, quelle forme représente une décision ?
A diamond is a decision; rounded rectangle = start/stop, parallelogram = input/output, rectangle = process. · Un losange est une décision ; rectangle arrondi = début/arrêt, parallélogramme = entrée/sortie, rectangle = processus.
Match each flowchart shape to its meaning. · Reliez chaque forme d'organigramme à sa signification.
Parallelogram = I/O, rectangle = process, rounded rectangle = start/stop, diamond = decision. · Parallélogramme = E/S, rectangle = processus, rectangle arrondi = début/arrêt, losange = décision.
Match each notation to its description. · Reliez chaque notation à sa description.
All three describe the same algorithm at different distances from the code. · Les trois décrivent le même algorithme à différentes distances du code.
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.
Exemple résolu : anglais structuré vers pseudocode
- Anglais structuré : Mettre le total à zéro. Pour chacun des N nombres, l'ajouter au total. Diviser le total par N et afficher le résultat.
- Chaque phrase devient une construction : une affectation, une boucle
FORavec une affectation à l'intérieur, puis une affectation et une sortie.
Total <- 0
FOR Index <- 1 TO N
Total <- Total + Number[Index]
NEXT Index
Average <- Total / N
OUTPUT Average
- L'ordre des phrases est l'ordre des déclarations. Rien n'est ajouté et rien n'est omis.
In the averaging algorithm, the FOR loop that adds each number to the total is an example of the ____ construct. · Dans l'algorithme de moyennage, la boucle FOR qui ajoute chaque nombre au total est un exemple du constructeur ____.
Repeating a block for each number is iteration. The assignment inside it stores the running total. · Répéter un bloc pour chaque nombre est une itération. L'affectation à l'intérieur stocke le total cumulé.
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.
Exemple résolu : pseudocode vers diagramme de flux
- Prenez le même algorithme.
STARTva dans un rectangle arrondi,Total ← 0etIndex ← 1dans des rectangles. - La boucle
FORdevient un losange demandantIndex <= N?. La sortie Oui mène au rectangleTotal ← Total + Number[Index], puisIndex ← Index + 1, et une flèche retourne vers le haut au losange. - La sortie Non continue vers
Average ← Total / N, un parallélograme de sortie, etSTOP. - Étiquetez les deux sorties de chaque losange. Un losange avec une sortie non étiquetée n'est pas une décision.
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
Affinement progressif
- Affinement progressif 逐步求精 signifie écrire un algorithme sous forme de court plan, puis développer chaque étape en sous-étapes plus détaillées, et répéter jusqu'à ce que chaque étape puisse être codée directement.
- Chaque niveau conserve la structure du niveau supérieur et ajoute des détails. Le plan n'est pas jeté : il devient la structure du programme.
- La conception s'arrête lorsqu'une étape correspond à une ligne de pseudocode ou à un module que vous avez déjà.
L'affinement progressif développe chaque étape jusqu'à ce qu'elle puisse être codée
Stepwise refinement is the technique of: · Le raffinement progressif est la technique consistant à :
You refine a high-level outline level by level, adding detail while keeping the structure. · Vous raffinez un plan de haut niveau niveau par niveau, ajoutant des détails tout en conservant la structure.
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.
Exemple résolu : trois niveaux
- Niveau 1 : Traiter les résultats de l'examen.
- Niveau 2 : Saisir chaque note. Calculer la moyenne. Compter combien ont réussi. Afficher le rapport.
- Niveau 3, affinant "compter combien ont réussi" :
Passes ← 0, puisFORpour chaque note,IF Mark >= 40 THEN Passes ← Passes + 1. - On vous demande de "décrire l'affinement progressif" : donnez les trois idées : commencer par un plan, développer chaque étape en petites étapes, s'arrêter lorsque chaque étape peut être programmée.
Stepwise refinement: outline to code · Raffinement progressif : plan vers code
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. · Descendez les niveaux. Vous commencez avec toute la tâche en une seule ligne et continuez à développer chaque étape en parties plus petites — jusqu'à ce que chaque étape soit suffisamment simple pour être codée directement.
In stepwise refinement, each new level replaces the level above it, so the original outline is thrown away. · Dans le raffinement progressif, chaque nouveau niveau remplace le niveau précédent, donc le plan original est jeté.
Each level keeps the structure of the one above and adds detail. The outline becomes the shape of the finished program. · Chaque niveau conserve la structure de celui qui le précède et ajoute des détails. Le plan devient la forme du programme fini.
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
Déclarations logiques
- Une déclaration logique 逻辑语句 est une condition Booléenne 布尔 : elle est soit
TRUEsoitFALSE, et elle contrôle uneIF, uneWHILEou uneUNTIL. - Elle est construite à partir de comparaisons (
=,<>,<,>,<=,>=) jointes parAND,ORetNOT. Mark >= 0 AND Mark <= 100est vraie uniquement pour les notes dans la plage.Age < 12 OR Age >= 65est vraie pour les enfants et les retraités.
Les comparaisons jointes par AND, OR et NOT forment une seule condition
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.
Priorité et parenthèses
- Les opérateurs sont appliqués dans un ordre fixe de priorité 优先级 :
NOTd'abord, puisAND, puisOR. A OR B AND CsignifieA OR (B AND C), pas(A OR B) AND C. AvecA = TRUE,B = FALSE,C = FALSEle premier estTRUEet le second estFALSE.- Utilisez des parenthèses chaque fois qu'une condition mélange
ANDetOR. Elles ne coûtent rien et suppriment l'ambiguïté.
Put the logic operators in order of precedence, highest (evaluated first) to lowest. · Placez les opérateurs logiques dans l'ordre de priorité, du plus élevé (évalué en premier) au plus bas.
NOT binds tightest, then AND, then OR — use brackets when in doubt. · NOT lie le plus étroitement, puis AND, puis OR — utilisez des parenthèses en cas de doute.
With no brackets, what does A OR B AND C mean? · Sans parenthèses, que signifie 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 a une priorité supérieure à OR, donc il est évalué en premier. Mettez la condition entre parenthèses de toute façon, pour que personne n'ait à se souvenir.
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.
Lois de De Morgan
- Loi de De Morgan 德摩根定律 :
NOT (A AND B)est la même chose que(NOT A) OR (NOT B), etNOT (A OR B)est la même chose que(NOT A) AND (NOT B). - En mots : "pas (enregistré ET payé)" signifie "pas enregistré, OU pas payé".
- Utilisez-la pour simplifier une condition, ou pour la vérifier : choisissez des valeurs pour
AetB, calculez les deux côtés, et ils doivent coïncider dans tous les cas.
By De Morgan's law, NOT (A AND B) is the same as (NOT A) OR (NOT B). · Selon la loi de De Morgan, NOT (A AND B) est la même chose 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 distribue sur les parenthèses et inverse AND↔OR ; de même NOT (A OR B) = (NOT A) AND (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.
Exemple résolu : une condition issue de mots
- Règle : un étudiant peut passer l'examen s'il est enregistré ET a soit payé, soit bénéficie d'une bourse, mais PAS s'il est suspendu.
- Nommez les variables Booléennes :
Registered,Paid,Bursary,Suspended. - Déclaration :
Registered AND (Paid OR Bursary) AND NOT Suspended. - Les parenthèses autour de
Paid OR Bursarysont essentielles. Sans elles,ANDs'associe d'abord et un étudiant avec une bourse mais sans inscription serait accepté.
Which conditions are equivalent to NOT (Registered AND Paid)? Select all · tout that apply. · Quelles conditions sont équivalentes à NOT (Registered AND Paid) ? Sélectionnez tous ceux qui s'appliquent.
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 transforme la négation d'un AND en un OR des négations. La version AND est trop stricte : un étudiant qui est inscrit mais n'a pas payé devrait rendre la condition originale VRAIE, et cela rend la version AND FAUSSE.
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.
Pièges qui font perdre des points
a = 1 OR 2n'est pas une condition. Écriveza = 1 OR a = 2: chaque côté deORdoit être une comparaison complète.NOTne s'applique qu'à ce qui suit.NOT A AND Bsignifie(NOT A) AND B.- Un losange nécessite deux sorties étiquetées, et une boucle nécessite une flèche qui revient vers le haut. Un diagramme de flux sans flèche de retour n'est pas une boucle.
- L'anglais structuré reste précis. "Gérer les notes" n'est pas une étape ; "ajouter la note au total" l'est.
To test whether a is 1 or 2, the correct condition is: · Pour tester si a vaut 1 ou 2, la condition correcte est :
Each side of OR must be a full comparison: a = 1 OR a = 2. Writing a = 1 OR 2 is a common error. · Chaque côté de OR doit être une comparaison complète : a = 1 OR a = 2. Écrire a = 1 OR 2 est une erreur courante.
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
Vous avez compris
- trois notations pour un algorithme : anglais structuré, pseudocode, diagramme de flux (losange = décision, flèche de retour = boucle)
- affinement progressif : plan → développer chaque étape → s'arrêter lorsque chaque étape peut être codée
- une déclaration logique est une condition Booléenne ; priorité NOT → AND → OR, donc mettre entre parenthèses tout ce qui les mélange
- De Morgan :
NOT (A AND B)=NOT A OR NOT B;NOT (A OR B)=NOT A AND NOT B