Fiche de révision : Algorithmique et bases de Python

📋 Plan du Cours

1. Définition et écriture des algorithmes
2. Implémentation et qualité algorithmique
3. Valeurs et types Python
4. Chaînes, booléens et tuples
5. Variables et entrées-sorties
6. Fonctions, listes et contrôle
7. Branchements conditionnels en Python
8. Boucles for et accumulateurs
9. Boucles while et imbrications
10. Fonctions et valeurs de retour
11. Portée et composition des fonctions
12. Programmation récursive
13. Récursion et tours de Hanoï
14. Flocon récursif de Von Koch
15. Listes et parcours Python
16. Évaluation et recherche dans les listes
17. Création, tri et mutation des listes
18. Structures séquentielles et graphes

📖 1. Définition et écriture des algorithmes

🔑 Notions clés & Définitions

• Algorithme : Procédé automatique qui transforme une information symbolique d’entrée en une information symbolique de sortie au moyen d’un nombre fini d’opérations élémentaires, chacune réalisable en temps fini.

★ À maîtriser

📌 Un algorithme exécutable doit comporter un nombre fini d’opérations élémentaires, tandis qu’un procédé comportant une quantité infinie d’opérations ne peut pas être exécuté comme tel par un ordinateur.

• La description effective précise: le nom et les spécifications, les entrées et les sorties, les préconditions éventuelles, les opérations élémentaires indentées et commentées

Compléments

• Dans l’algorithme d’addition de deux entiers, on initialise p à m, puis on ajoute 1 à p n fois si n est positif et on retranche 1 à p -n fois si n est négatif.

💡 Astuce mémo

Entrées → opérations élémentaires → sorties

📖 2. Implémentation et qualité algorithmique

🔑 Notions clés & Définitions

• Implémentation : Traduction d’un algorithme écrit en pseudo-code dans un langage compris effectivement par une machine.
• Complexité : Étude du temps nécessaire à l’exécution complète d’un algorithme et de la mémoire nécessaire à cette exécution.

★ À maîtriser

📌 La programmation impérative exécute des opérations successives qui modifient l’état des données, tandis que la programmation fonctionnelle emboîte des fonctions et utilise des données immuables.

• Les quatre critères essentiels sont:

  • la spécification
  • la terminaison
  • la correction
  • la complexité

• Les tests doivent être prévus avant l’écriture du programme, couvrir suffisamment de cas et être réalisés progressivement pendant l’implémentation, et pas seulement à la fin.

Compléments

• Python peut être utilisé en programmation impérative et en programmation orientée objet, tandis qu’Ocaml est utilisé dans ce cours pour la programmation fonctionnelle.

💡 Astuce mémo

STCC : spécification, terminaison, correction, complexité

📖 3. Valeurs et types Python

★ À maîtriser

📌 Le type int représente les entiers, tandis que le type float représente les nombres flottants utilisés pour approcher les réels.

📐 Formule — La division euclidienne de a par b, avec b strictement positif, vérifie $a=qb+r$ et $0\leqslant r<b$.

📌 En Python, l’opérateur // donne le quotient de la division euclidienne, l’opérateur % donne le reste et l’opérateur / produit un flottant.

• Les flottants sont représentés en base 2 avec une précision limitée, ce qui peut produire des arrondis à chaque opération et des résultats comme 0.1 + 0.2 - 0.3 égal à 5.551115123125783e-17.

Compléments

• En Python, -7 // 3 vaut -3 et -7 % 3 vaut 2.

• La conversion explicite int d’un flottant se fait vers l’entier rencontré en se rapprochant de 0, ainsi int(2.718) vaut 2 et int(-2.718) vaut -2.

💡 Astuce mémo

Entier exact, flottant approximatif

📖 4. Chaînes, booléens et tuples

🔑 Notions clés & Définitions

• Chaîne de caractères : Valeur textuelle de type str, délimitée par des guillemets simples ou doubles.
• Booléen : Type possédant exactement deux valeurs distinctes, True et False.
• Tuple : Regroupement ordonné de plusieurs valeurs, éventuellement de types différents.

★ À maîtriser

• L’opérateur + concatène deux chaînes de caractères et la multiplication d’une chaîne par un entier la répète.

Compléments

• Les fonctions int et float convertissent une chaîne interprétable en entier ou en flottant, tandis que str convertit une valeur en chaîne.

• Le standard ASCII associe aux caractères courants des valeurs comprises entre 0 et 127, et ord('A') vaut 65.

📖 5. Variables et entrées-sorties

🔑 Notions clés & Définitions

• Affectation : Évalue d’abord l’expression située à droite, puis stocke sa valeur dans la variable située à gauche.

📝 Points essentiels

• Python est un langage à typage dynamique dans lequel une même variable peut stocker successivement des valeurs de types différents.

• Pour échanger deux variables avec une variable temporaire, on sauvegarde la première valeur dans c, on affecte la deuxième à la première, puis on affecte c à la deuxième.

• L’affectation simultanée a, b = b, a permet d’échanger les valeurs de a et b, car l’expression de droite est évaluée avant l’affectation.

📌 L’expression 210 produit la valeur 1024, tandis que print(210) affiche 1024 et renvoie None.

📌 La fonction input renvoie toujours une chaîne de caractères, même lorsque l’utilisateur saisit un nombre, qui doit donc être converti explicitement avec int ou float.

💡 Astuce mémo

Une variable est une boîte dont l’affectation remplace le contenu

📖 6. Fonctions, listes et contrôle

🔑 Notions clés & Définitions

• Fonction : Prend une ou plusieurs valeurs en entrée et peut renvoyer une valeur en sortie.
• Liste : Succession ordonnée de valeurs de type list, définie entre crochets et indexée de 0 à sa longueur moins 1.

★ À maîtriser

• Si t est une liste de longueur n, l’accès t[k] est valide pour 0 ≤ k < n et un indice hors de ces bornes lève l’exception list index out of range.

• L’opérateur and évalue d’abord sa première opérande et n’évalue la seconde que si la première est vraie, tandis que or n’évalue la seconde que si la première est fausse.

📌 L’instruction if exécute un bloc seulement si sa condition est vraie, elif permet de tester d’autres conditions et else exécute le bloc correspondant si aucune condition précédente n’est vraie.

• Dans une structure if-elif-else, seul le bloc correspondant à la première condition vraie est exécuté.

Compléments

• Une matrice peut être représentée par une liste de listes, et l’élément d’indices i et j s’obtient avec m[i][j].

💡 Astuce mémo

Condition vraie → bloc exécuté ; condition fausse → bloc alternatif

📖 7. Branchements conditionnels en Python

🔑 Notions clés & Définitions

• Instruction if : Soumet l’exécution d’une instruction ou d’un bloc d’instructions à une condition.

📝 Points essentiels

📌 En Python, le bloc soumis à une instruction conditionnelle est délimité par une indentation uniforme, généralement de quatre espaces, et l’instruction suivant le bloc reprend le niveau d’indentation de l’instruction if.

• Avec if, elif et else, Python évalue les conditions dans l’ordre et n’exécute que le bloc correspondant à la première condition vraie; si aucune condition n’est vraie, le bloc else est exécuté.

💡 Astuce mémo

if → elif → else

📖 8. Boucles for et accumulateurs

🔑 Notions clés & Définitions

• Boucle for : Répète un bloc d’instructions un nombre de fois connu avant l’entrée dans la boucle, ce qui en fait une boucle inconditionnelle et bornée.

★ À maîtriser

📌 La boucle for k in range(a, b) affecte successivement à k les valeurs entières a, a + 1 jusqu’à b - 1.

• Pour calculer une somme par une boucle for, on initialise un accumulateur à l’élément neutre de l’addition, puis on lui ajoute successivement chaque terme avant de le renvoyer.

Compléments

📌 La fonction range(a, b, p) parcourt les entiers a, a + p, a + 2p jusqu’au plus grand entier de cette forme strictement inférieur à b si p est positif et strictement supérieur à b si p est négatif.

💡 Astuce mémo

Itérations connues → boucle bornée

📖 9. Boucles while et imbrications

🔑 Notions clés & Définitions

• Variant : Une grandeur entière positive qui diminue strictement à chaque itération et permet de prouver qu’une boucle while termine.

📝 Points essentiels

📌 Une boucle for convient lorsque le nombre d’itérations est connu avant l’entrée dans la boucle, tandis qu’une boucle while convient lorsque le bloc doit être répété tant qu’une condition est vérifiée et que ce nombre n’est pas connu a priori.

• La fonction int_sqrt(n) initialise a à 0, augmente a de 1 tant que a² ≤ n, puis renvoie a - 1, qui est le plus grand entier dont le carré est inférieur ou égal à n.

📌 Une boucle while peut ne jamais terminer si sa condition reste vraie, ce qui produit une boucle infinie.

• L’algorithme d’Euclide calcule le pgcd de a et b en remplaçant successivement le couple (a, b) par (b, a mod b) tant que b est positif, puis en renvoyant a.

💡 Astuce mémo

for : nombre connu ; while : condition

📖 10. Fonctions et valeurs de retour

🔑 Notions clés & Définitions

• Fonction Python : Définie par def, reçoit éventuellement des arguments formels, exécute un bloc d’instructions et peut renvoyer une valeur avec return.
• Signature de fonction : Une indication documentaire des types attendus et du type renvoyé, comme est_pair(n: int) -> bool.

★ À maîtriser

📌 Une fonction Python renvoie une unique valeur avec return; si elle atteint la fin sans return, Python renvoie automatiquement None.

• Un test unitaire exécute une fonction avec des arguments dont le résultat attendu est connu et utilise assert pour vérifier que le résultat obtenu lui est égal.

Compléments

• Python utilise le typage dynamique et le duck typing: une fonction peut recevoir un argument si les opérations utilisées dans son corps sont définies pour son type, sans déclaration obligatoire du type par Python.

💡 Astuce mémo

return renvoie ; print affiche

📖 11. Portée et composition des fonctions

🔑 Notions clés & Définitions

• Variable locale : Créée dans une fonction, appartient à son appel et est supprimée lorsque l’exécution de cet appel se termine.
• Pile d’appels : Empile un nouvel état local lors de chaque appel de fonction et supprime cet état lorsque l’appel se termine.

★ À maîtriser

📌 Une variable globale est accessible en lecture depuis une fonction si elle n’est pas masquée, mais sa modification dans la fonction nécessite le mot-clé global.

📌 Une fonction pure renvoie une valeur sans effet de bord, tandis qu’une procédure Python produit un effet de bord et renvoie généralement None.

Compléments

• La fonction binome(k, n) compose la fonction factorielle pour calculer le coefficient binomial par la relation $\binom{n}{k}=\frac{n!}{k!(n-k)!}$.

💡 Astuce mémo

La pile d’appels empile puis dépile les états locaux

📖 12. Programmation récursive

🔑 Notions clés & Définitions

• Fonction récursive : Une fonction qui s’appelle elle-même en réduisant le problème à un problème similaire de taille strictement inférieure.

★ À maîtriser

📌 Toute fonction récursive doit définir un ou plusieurs cas de base et garantir que les réductions successives atteignent un cas de base en un nombre fini d’appels.

📐 Formule — La factorielle vérifie $n! = n(n-1)!$ pour n ≥ 1 et $0! = 1$.

📐 Formule — Pour l’exponentiation rapide, si n = 2p + r avec r dans {0, 1}, alors $x^n=(x^p)^2$ si r = 0 et $x^n=x(x^p)^2$ si r = 1, avec $x^0=1$.

• Pour n = 2^p, l’exponentiation rapide calcule x^n en 2 + p multiplications, tandis que l’algorithme naïf en utilise n - 1; pour x^1024, cela représente 12 multiplications contre 1023.

• La résolution récursive des tours de Hanoï déplace d’abord n - 1 disques de la tige de départ vers la tige pivot, déplace le dernier disque vers la tige d’arrivée, puis déplace les n - 1 disques vers la tige d’arrivée.

Compléments

• En Python, la pile des appels récursifs ne peut normalement pas dépasser 1000 niveaux, et un dépassement provoque une erreur de type RecursionError.

💡 Astuce mémo

Cas de base → réduction → retour

📖 13. Récursion et tours de Hanoï

🔑 Notions clés & Définitions

• Jeu des tours de Hanoï : Edouard Lucas — Le jeu utilise trois tiges et n disques de diamètres différents, initialement empilés sur la première tige du plus grand au plus petit, et consiste à les déplacer sur la troisième tige sans déplacer plusieurs disques à la fois ni poser un disque sur un disque plus petit.

📝 Points essentiels

• Pour déplacer n disques de la tige i vers la tige k en utilisant la tige j comme pivot, il faut déplacer récursivement n−1 disques de i vers j, déplacer le disque restant de i vers k, puis déplacer récursivement les n−1 disques de j vers k.

💡 Astuce mémo

n−1 à gauche → disque restant → n−1 à droite

📖 14. Flocon récursif de Von Koch

📝 Points essentiels

• Pour une génération n≥1 du flocon de Von Koch, le programme dessine quatre flocons de génération n−1 et de longueur a/3, en effectuant successivement des rotations à gauche de 60 degrés, à droite de 120 degrés, puis à gauche de 60 degrés entre les tracés.

📌 Pour la génération 0 du flocon de Von Koch, le programme trace un segment de longueur a.

💡 Astuce mémo

segmenter, tourner à gauche, tourner à droite, tourner à gauche

📖 15. Listes et parcours Python

🔑 Notions clés & Définitions

• Liste Python : Une succession ordonnée de n valeurs, écrite entre crochets et séparée par des virgules, dont les éléments sont indexés de 0 à n−1.

📝 Points essentiels

• La longueur d’une liste t est obtenue avec len(t), et un accès t[k] avec k≥n lève une exception.

• La recherche séquentielle d’un élément x dans une liste t consiste à parcourir les indices admissibles, comparer t[i] à x et renvoyer True dès qu’une égalité est trouvée, puis False si le parcours s’achève sans égalité.

💡 Astuce mémo

tableau : accès direct ; pile : ajout facile mais accès limité

📖 16. Évaluation et recherche dans les listes

★ À maîtriser

📐 Formule — L’algorithme de Hörner évalue le polynôme avec $C_3(n)=n+1$ multiplications.

• La recherche dichotomique dans une liste triée maintient une tranche g≤k<d, compare l’élément recherché à l’élément d’indice m=⌊(g+d)/2⌋, puis conserve la moitié gauche, la moitié droite ou termine selon le résultat.

• Pour une liste triée de n=2^p−1 éléments, la recherche dichotomique nécessite au plus p=log_2(n+1) comparaisons.

Compléments

📐 Formule — Pour un polynôme de degré n évalué par la méthode naïve, le nombre de multiplications est $C_1(n)=\sum_{k=0}^{n}(k+1)=\frac{(n+1)(n+2)}{2}$.

📐 Formule — L’évaluation progressive d’un polynôme, qui accumule les puissances successives, nécessite $C_2(n)=2(n+1)$ multiplications.

💡 Astuce mémo

recherche linéaire : jusqu’à n comparaisons ; dichotomie : intervalle divisé par deux

📖 17. Création, tri et mutation des listes

🔑 Notions clés & Définitions

• Slicing : L’opération qui crée une nouvelle liste contenant les éléments d’indices i+kp compris entre i et j, avec un pas p positif.

📝 Points essentiels

• Une compréhension de liste construit une nouvelle liste en appliquant une expression à chaque valeur d’une itération, avec la possibilité de conserver seulement les valeurs satisfaisant une condition.

📐 Formule — Le tri par sélection effectue exactement $C_s(n)=\frac{n(n-1)}{2}$ comparaisons et exactement n−1 échanges.

📐 Formule — Le tri par insertion effectue au plus $C_i(n)\leqslant\frac{n(n-1)}{2}$ comparaisons, exactement n−1 sur une liste déjà triée et exactement n(n−1)/2 sur une liste décroissante.

💡 Astuce mémo

sélection : comparaisons fixes ; insertion : dépend de l’ordre initial

📖 18. Structures séquentielles et graphes

🔑 Notions clés & Définitions

• Dictionnaire : Une structure qui associe des clés deux à deux distinctes à des valeurs et permet d’accéder aux valeurs par leurs clés plutôt que par des indices.
• Graphe non orienté : Un couple G={S,A}, où S est un ensemble fini non vide de sommets et A un ensemble de paires de sommets distincts appelées arêtes.
• Chemin : Une suite de n+1 sommets z₀,z₁,…,zₙ telle que chaque paire successive zₖ−zₖ₊₁ est une arête du graphe.
• Degré d'un sommet : le nombre d'arêtes de la forme x - y, c'est-à-dire son nombre de voisins.
• Chemin : Un chemin de longueur n est une suite de n + 1 sommets z₀, z₁, ..., zₙ telle que chaque paire consécutive zₖ - zₖ₊₁ est une arête.
• Arbre : un graphe connexe et acyclique.
• Graphe orienté : un couple G = (S, A) où S est un ensemble fini non vide de sommets et A un ensemble de couples (x, y) de sommets distincts appelés arcs.
• Degrés orientés : Le degré entrant d'un sommet x compte les arcs y→x, le degré sortant compte les arcs x→y et le degré total est la somme des deux.
• Graphe pondéré : la donnée d'un graphe G = (S, A) et d'une application ρ : A → ℝ₊ appelée poids.
• Matrice d'adjacence : La matrice d'adjacence M indique par mᵢ,ⱼ = 1 qu'un sommet j est successeur de i et par mᵢ,ⱼ = 0 dans le cas contraire.
• Liste d'adjacence : un tableau g dans lequel gᵢ contient la liste des successeurs du sommet i.

📝 Points essentiels

📌 Une pile suit le principe LIFO, car le dernier élément empilé est le premier dépilé, tandis qu’une file suit le principe FIFO, car le premier élément enfilé est le premier défilé.

📌 Un chemin élémentaire ne passe jamais deux fois par le même sommet, tandis qu'un chemin simple ne passe jamais deux fois par la même arête.

📐 Formule — Le poids d'un chemin c = z₀, z₁, ..., zₙ est $\rho(c) = \sum_{k=0}^{n-1} \rho(z_k z_{k+1})$.

📌 La distance d(x,y) est le nombre minimal d'arêtes entre x et y, tandis que δ(x,y) est le poids minimal d'un chemin entre ces sommets.

📌 Un graphe est non orienté si et seulement si sa matrice d'adjacence est symétrique.

💡 Astuce mémo

pile : LIFO ; file : FIFO

📊 Tableaux de synthèse

Critères de qualité d’un algorithme

Types numériques Python