Représentation d'un graphe en informatique

Plusieurs modes de représentation peuvent être implémentés pour stocker des graphes : matrices d’adjacence (ou sommet-sommet), listes des voisins, des successeurs ou des prédécesseurs. Lors de cette séance nous allons écrire les classes réalisant ces implémentations. Structure de graphe basée sur une liste d’adjacence Écrire le code de la méthode __init__ de la classe Sommet dont la spécification est : 1 2 3 4 def __init__(self: Sommet, val: str) -> None: """ Initialisation d'un sommet. [Lire]

Tri par insertion

Tri du joueur de cartes Le tri par insertion est un tri « naturel » souvent qualifié de « tri du joueur de carte ». Comment un joueur de carte trie-t-il ses cartes ? Au début, la main gauche du joueur est vide et ses cartes sont posées sur la table. Le joueur prend alors sur la table les cartes, une par une avec sa main droite, pour les placer dans sa main gauche. [Lire]

Tri par sélection

La recherche d’un élément dans un tableau est beaucoup plus efficace si ce tableau est ordonné. À vrai dire, ce n’est pas en cours d’informatique que vous avez découvert ceci : dans toutes les bibliothèques les livres sont classés de façon à rendre leur recherche plus rapide ! Le tri des tableaux/listes permet de trouver rapidement les objets recherchés et facilite la recherche des valeurs extrêmes. La question que se propose d’aborder ce document est donc : « comment classer les éléments d’un tableau selon une relation d’ordre donnée ? [Lire]

Algorithmes de tri

Au programme de la classe de première

Contenus Capacités attendues Commentaires
Tris par insertion, par sélection - Écrire un algorithme de tri.
- Décrire un invariant de boucle qui prouve la correction des tris par insertion, par sélection.
- La terminaison de ces algorithmes est à justifier.
- On montre que leur coût est quadratique dans le pire cas.

Documents

Réalisation d'une classe Liste Chainee

Par transformation des fonctions du document 1 dans ce chapitre en méthodes, écrire le code de la classe Liste qui définit le type abstrait « Liste chaînée ». Réponse 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 from __future__ import annotations class Maillon: """ Un maillon de la liste. [Lire]

Implémentation du type abstrait Liste Chaînée à l'aide de listes Python

Reprendre toutes les fonctions des sections 2 et 3 du document 1 de ce chapitre, en implémentant cette fois le type abstrait « Liste chaînée » à l’aide de tuples (à la place de la classe). Réponse 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 def est_dans(tab: list[int], val: int) -> bool: """ Recherche la présence de val dans tab. [Lire]

Somme des $n$ nombres d'un tableau

L’objectif de ce document est d’écrire et d’implémenter un algorithme s’appuyant sur le raisonnement « Diviser pour régner » qui permet de déterminer la somme des $n$ nombres (entiers) d’un tableau. Écrire le code de fonction somme1 dont la spécification est : 1 2 3 4 5 6 7 def somme1(tab: List[float]) -> float: """ Calcul de la somme des nombres éléments de tab. Algorithme : Récursivité enveloppée """ Penser à écrire un jeu de tests. [Lire]

Diviser pour régner

Dans quel cas ? On parvient à découper un problème en sous-problèmes indépendants les uns des autres. On poursuit cette démarche jusqu’à aboutir à une situation simple : cas de base. La solution du cas de base est généralement simple à obtenir et permet la construction de la solution du problème. Remarque C’est l’indépendance des sous-problèmes qui permet la construction de la solution globale directe par recombinaison des solutions intermédiaires. [Lire]

Décomposition d'un problème en sous-problèmes

Principe

  • On décompose le problème en sous-problèmes plus simples.
  • On résout les sous-problèmes.
  • On combine les sous-problèmes de façon à construire la solution du problème initial.

Indépendance des sous-problèmes

  • Si les sous-problèmes sont indépendants les uns des autres : « Diviser pour règner ».
  • Si les sous-problèmes dépendent les uns des autres : « Programmation dynamique ».

Recherche numérique de zéros de fonctions

Dans ce document on introduit une méthode permettant d’évaluer numériquement une solution de l’équation $f (x) = 0$, avec $f$ une fonction de $\mathbb{R}$ dans $\mathbb{R}$ (lorsque la solution existe, bien sur) : la méthode de dichotomie. La méthode de dichotomie est efficace et converge relativement vite. De plus, les conditions de son utilisation sont assez simples : la fonction $f$ doit seulement être continue et changer de signe sur l’intervalle choisi ; La méthode de Newton converge étonnement vite ! [Lire]