Scheda di revisione: Introduction à l'Algorithmique et Structures de Données

📋 Plan du Cours

1. Algorithmes et rigueur
2. Algorithme d’Euclide et PGCD
3. Entrées-sorties et séquences
4. Variables et types de données
5. Opérateurs sur les entiers
6. Opérateurs sur les réels
7. Caractères et chaînes
8. Opérateurs booléens
9. Échange de variables sans intermédiaire

📖 1. Algorithmes et rigueur

🔑 Notions clés & Définitions

• Algorithme : Un algorithme est une suite finie d’instructions appliquées dans un ordre déterminé pour obtenir un résultat à partir de données, en un nombre fini d’étapes.
• Algorithmique : L’algorithmique désigne la démarche de conception qui transmet des moyens efficaces de calcul, avec une méthode systématique pour traiter des entrées et produire des sorties.
• Pseudo-code : Le pseudo-code est une écriture intermédiaire d’un algorithme, présentée de façon indépendante des syntaxes des langages de programmation.
• Cahier des charges : Le cahier des charges est la demande formulée par le client qui précise ce que le projet doit réaliser.
• Cahier fonctionnel : Le cahier fonctionnel regroupe l’ensemble des algorithmes du projet décrivant comment atteindre les objectifs.

📝 Points essentiels

• Le mot algorithme vient d’Al-Khwarizmi au 9e siècle, puis a été latinisé en « algoritmi » au Moyen Âge.
• Un algorithme est structuré pour être exécutable par une machine, avec une écriture stricte et conventionnée.
• L’écriture algorithmique sert de langage commun d’équipe et permet de relire une solution sans dépendre d’un langage de programmation précis.
• La validation de structures algorithmiques est plus aisée que la validation directe de langages de programmation évolués.
• Les spécifications d’un algorithme indiquent au minimum BUT, ENTREE, SORTIE, COMMENTAIRE entre DEBUT et FIN ALGORITHME.

💡 Astuce mémo

Algorithme = ENTRÉES → suite d’OPÉRATIONS finies → SORTIE, avec une écriture stricte de pseudo-code.

📖 2. Algorithme d’Euclide et PGCD

🔑 Notions clés & Définitions

• PGCD : Le PGCD est le plus grand entier qui divise exactement deux entiers donnés.
• Algorithme d’Euclide : L’algorithme d’Euclide est une méthode de calcul pour obtenir le PGCD à partir de deux entiers.

📝 Points essentiels

• Le premier algorithme d’Euclide connu sert au calcul du PGCD et date du IIIe siècle av. J.-C.

📖 3. Entrées-sorties et séquences

🔑 Notions clés & Définitions

• ENTREE : Champ des spécifications qui décrit les données fournies à l’algorithme avant son exécution.
• SORTIE : Champ des spécifications qui décrit ce que l’algorithme produit en résultat une fois exécuté.
• Séquence algorithmique : Enchaînement d’actions élémentaires exécutées dans un ordre imposé, sans saut entre étapes non prévues.
• LIRE() : Primitve d’entrée qui lit une valeur saisie par l’utilisateur au clavier dans un algorithme.
• ECRIRE() : Primitive de sortie qui affiche à l’écran une valeur calculée ou manipulée par l’algorithme.

📝 Points essentiels

• Les spécifications d’un algorithme reprennent un bloc avec BUT, ENTREE, SORTIE et COMMENTAIRE pour décrire le problème et ses données.
• En algorithmique, l’exécution suit une logique séquentielle et se lit du haut vers le bas de DEBUT jusqu’à FIN.
• LIRE() sert à récupérer une valeur saisie par l’utilisateur avant de lancer les calculs.
• ECRIRE(produit) permet d’afficher à l’écran le résultat calculé (par exemple un entier correspondant à un carré).
• Dans un organigramme associé, les actions sont aussi présentées comme une suite d’étapes correspondant à des opérations exécutées séquentiellement.

💡 Astuce mémo

Séquence = flèche du haut vers le bas : LIRE() au début, calcul au milieu, ECRIRE() à la fin.

📖 4. Variables et types de données

🔑 Notions clés & Définitions

• Variable : Une variable désigne une donnée dont la valeur peut changer pendant l’algorithme, tandis que son type reste le même.
• Constante : Une constante est une donnée dont la valeur ne change pas après son initialisation au début de l’algorithme.
• Type de données : Un type de données décrit l’ensemble des valeurs possibles et la manière d’écrire ces valeurs en algorithmique.
• CARACTERE : Un type CARACTERE correspond à un symbole unique écrit entre quotes simples.
• CHAINE : Un type CHAINE correspond à une suite de caractères écrite entre guillemets.

📝 Points essentiels

• Les variables doivent être déclarées en début de section, avec un nom et un type, par exemple VARIABLES : a, b : ENTIER.
• Une constante doit être initialisée lors de sa déclaration, puis sa valeur reste identique tout au long du programme.
• En algorithmique, le type REEL utilise la virgule pour écrire les nombres décimaux.
• En écriture algorithmique, les booléens sont VRAI ou FAUX et les caractères sont écrits avec ' ' (quotes simples).
• Les chaînes de caractères sont écrites avec des guillemets " " et peuvent contenir chiffres, symboles et espaces.
• L’opérateur d’affectation d’une valeur est <— (et se lit comme une “mise en mémoire” de la valeur dans la variable).

💡 Astuce mémo

Quotes : CARACTERE = ' ' (1 symbole) ; CHAINE = " " (une phrase de symboles).

📖 5. Opérateurs sur les entiers

🔑 Notions clés & Définitions

• Opérateur modulo MOD() : Opérateur de calcul sur entiers qui donne le reste de la division euclidienne du premier argument par le second.
• Reste de division euclidienne : Résultat entier $r$ utilisé pour remplacer les valeurs dans l’algorithme d’Euclide jusqu’à ce que la seconde valeur atteigne 0.
• Réaffectation sur entiers : Opération qui réécrit une variable entière avec une expression arithmétique compatible sur entiers.

📝 Points essentiels

• Dans l’algorithme d’Euclide, tant que (b > 0) on calcule r <-- MOD(a, b), puis on remplace a par b et b par r.
• Le PGCD est obtenu comme la dernière valeur non nulle de r lors de l’exécution de l’algorithme d’Euclide.
• Pour une variable entière, la réaffectation peut utiliser une addition du type nom_de_la_donnée <-- nom_de_la_donnée + 1.
• Pour une variable entière, la réaffectation peut aussi utiliser une multiplication du type nom_de_la_donnée <-- nom_de_la_donnée * 0,3.

💡 Astuce mémo

Euclide = boucle sur b, et MOD(a,b) sert à garder le reste qui remplace ensuite b.

📖 6. Opérateurs sur les réels

🔑 Notions clés & Définitions

• Type REEL : Le type REEL désigne une variable contenant un nombre à virgule et sert à exprimer des valeurs fractionnées en algorithmique.
• Valeurs réelles : Les valeurs réelles regroupent les nombres négatifs, positifs, fractionnés et les zéros sous la même catégorie mathématique en programmation.
• Réaffectation sur REEL : La réaffectation sur une variable de type REEL remplace sa valeur courante par une nouvelle expression numérique compatible avec le type.

📝 Points essentiels

• En écriture algorithmique française, la virgule sert de séparateur décimal pour écrire un REEL comme -5,3 ou 11,0/5,0.
• Un REEL peut prendre des valeurs négatives, positives, fractionnées et nulles, par exemple 3,0, -12,3, 7,23 et 0,0.
• Lors d’une réaffectation, l’expression de droite doit produire une valeur compatible avec REEL, comme $a \leftarrow a * 0,3$.

📖 7. Caractères et chaînes

🔑 Notions clés & Définitions

• EXTRACTION : Opérateur qui permet de récupérer un caractère ou une sous-chaîne à partir d’une chaîne et de positions.
• CONCATENATION : Opérateur binaire qui assemble deux chaînes pour produire une nouvelle chaîne.

📝 Points essentiels

• Un caractère se note avec des quotes simples, par exemple 'a', tandis qu’une chaîne se note avec des quotes doubles, par exemple "abc".
• Une comparaison de caractères ($<, >, =, \neq$...) se fait à partir des codes ASCII des caractères.
• EXTRACTION(prenom, 1) renvoie le caractère de rang 1 de la chaîne, comme 'L' dans "Lina".
• EXTRACTION(chaine, debut, longueur) extrait une sous-chaîne, par exemple EXTRACTION("LA CHAINE", 1, 2) donne "LA".
• LONGUEUR(chaine) renvoie le nombre de caractères, comme 9 pour "LA CHAINE" et 7 pour "HELLO!!".
• CONCATENATION(chaine1, chaine2) produit la chaîne obtenue en collant les deux textes, par exemple "LA " + "CHAISE" donne "LA CHAISE".

💡 Astuce mémo

EXTRACTION: 1er rang = 1, et LONGUEUR te dit combien de caractères tu coupes.

📖 8. Opérateurs booléens

🔑 Notions clés & Définitions

• OU : Opérateur booléen binaire qui combine deux valeurs booléennes et renvoie un booléen selon “au moins l’un est vrai”.
• ET : Opérateur booléen binaire qui combine deux valeurs booléennes et renvoie un booléen selon “les deux sont vrais”.
• NON : Opérateur booléen unaire qui inverse une valeur booléenne et renvoie l’opposé logique.

📝 Points essentiels

• Les opérateurs ET et OU sont binaires, s’appliquent à deux booléens et produisent un booléen.
• NON est unaire, s’applique à un seul booléen et produit un booléen inversé.
• En pseudo-algorithme, NON s’écrit NON ou !, ET s’écrit ET ou &&, OU s’écrit OU ou ||.

💡 Astuce mémo

ET = “AND” (tous vrais), OU = “OR” (au moins un vrai), NON = “NOT” (inverse).

📖 9. Échange de variables sans intermédiaire

🔑 Notions clés & Définitions

• Inter-échange sans variable temporaire : Technique de calcul qui échange deux valeurs en ne conservant pas une troisième variable de sauvegarde.
• Variable intermédiaire : Variable temporaire utilisée pour mémoriser une valeur pendant l’échange de deux autres variables.

📝 Points essentiels

• Le schéma de calcul sans variable temporaire est a <- a - b, puis b <- a + b, puis a <- b - a en supposant que a et b sont des entiers.
• Avec a=10 et b=-5, on obtient successivement a=15 puis b=10 puis a=-5, donc les valeurs sont bien échangées.
• Chaque affectation modifie immédiatement une des deux variables, et l’échange se fait uniquement via les résultats de ces trois formules successives.

💡 Astuce mémo

a=a-b; b=a+b; a=b-a : 3 lignes pour inverser a et b sans tmp.

📅 Repères chronologiques

Date	Événement
9ième siècle après Jésus Christ	Origine du mot « algorithme » (al-Khwarizmi)
Moyen Âge	Latinisation du mot en « algoritmi »
IIIe siècle av. J.-C	Premier algorithme d’Euclide : calcul du PGCD

📊 Tableaux de synthèse

Opérateurs selon le type

Type	Opérations/uses	Symboles/mots clés
ENTIER	Addition, soustraction, multiplication, division entière, exposant, modulo, comparaisons	+ - * DIV() ^ MOD() ; < <= > >= = <> !=
REEL	Addition, soustraction, multiplication, division, exposant, comparaisons	+ - * / ^ ; < <= > >= = <> !=
CARACTERE	Comparaison, extraction	< <= > >= = <> != ; EXTRACTION(chaîne, position)
CHAINE	Concaténation, longueur, extraction	CONCATENATION(chaine1,chaine2) ; LONGUEUR(chaine) ; EXTRACTION(chaine,début,longueur)
BOOLEEN	Comparaison (égalité/ineq), négation, conjonction/disjonction	= <> != ; NON ou ! ; ET ou && ; OU ou ||

⚠️ Pièges & confusions fréquents

1. Confondre déclaration et initialisation : en pseudo-code, l’initialisation (avec <-- valeur) n’est pas la même chose que la réservation en début d’algorithme.
2. Mettre le mauvais format pour les chaînes/caractères : CARACTERE doit être entre quotes simples 'a' et CHAINE entre guillemets "abc".
3. Écrire un REEL avec un mauvais séparateur décimal : en écriture algorithmique française, le REEL se note avec la virgule (ex. 3,0).
4. Confondre affectation et réaffectation : après coup, la réaffectation réutilise la variable dans l’expression (nom <-- nom + ...).
5. Se tromper sur l’opération d’affectation : le symbole est <-- et le cours indique que cela correspond à « PREND POUR VALEUR ».
6. Penser que MOD() rend le quotient : MOD(a,b) donne le reste de la division euclidienne (utilisé dans la boucle de l’Euclide).
7. Mélanger accès direct et indirect avec les pointeurs : '*' sert à accéder à la valeur pointée, tandis que '&' sert à obtenir l’adresse.

✅ Checklist Examen

1. Écrire un algorithme avec la structure : BUT, ENTREE, SORTIE, COMMENTAIRE puis DEBUT … FIN ALGORITHME, et rappeler la convention // pour les commentaires.
2. Présenter les spécifications de l’algorithme dans le corps : déterminer ce qui est ENTREE (données) et ce qui est SORTIE (résultat).
3. Montrer une séquence séquentielle (lecture puis calcul puis affichage) et utiliser LIRE() et ECRIRE().
4. Déclarer des VARIABLES correctement en début de bloc, avec nom et type (ENTIER, REEL, CARACTERE, CHAINE, BOOLEEN).
5. Distinguer variable vs constante : une constante doit être initialisée lors de sa déclaration et sa valeur reste invariante.
6. Choisir les écritures correctes : CARACTERE = '...' et CHAINE = "..." (et reconnaître l’inclusion de chiffres/espaces dans une CHAINE).
7. Appliquer correctement l’affectation nom <-- valeur en respectant la compatibilité des types.
8. Faire une réaffectation en utilisant la variable dans l’expression de droite (ex. a <-- a + 1 ou a <-- a * 0,3) selon le type.
9. Utiliser et interpréter les opérateurs par type : ENTIER (DIV(), MOD(), comparaisons), REEL (/ et virgule décimale), CHAINE (CONCATENATION, LONGUEUR, EXTRACTION).
10. Écrire une extraction correcte : EXTRACTION(chaine, position) pour CARACTERE et EXTRACTION(chaine,début,longueur) pour CHAINE, avec les bons paramètres.
11. Résoudre/écrire l’algorithme d’Euclide en pseudo-code : TANT QUE (b > 0) FAIRE r <-- MOD(a,b) puis mises à jour a <-- b, b <-- r, et identifier le PGCD comme la dernière valeur non nulle de r.
12. Expliquer et appliquer : (1) échange sans variable temporaire pour deux entiers, (2) POINTEUR avec * et & (valeur pointée vs adresse), (3) portée GLOBALE/LOCALE délimitée par les blocs de base.