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]

Algorithmes gloutons

Au programme de la classe de première

Contenus Capacités attendues Commentaires
Algorithmes gloutons Résoudre un problème grâce à un algorithme glouton. Exemples : problèmes du sac à dos ou du rendu de monnaie. Les algorithmes gloutons constituent une méthode algorithmique parmi d’autres qui seront vues en terminale.

Documents

Héron d'Alexandrie

Héron d’Alexandrie est un ingénieur, un mécanicien et un mathématicien grec du premier siècle après J.-C. On ne sait pas grand chose de la vie d’Héron, si ce n’est qu’il était originaire d’Alexandrie ; les historiens se sont même longtemps divisés sur l’époque où il a vécu. Leurs estimations allaient du 1er siècle avant J.-C. au 3ème siècle de notre ère. Aujourd’hui, la querelle est éteinte : il est clairement établi que Héron est postérieur à Vitruve mort en $- 20$, et contemporain de Pline l’Ancien (23 – 79), en étant actif autour de l’an 62. [Lire]

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. Matrice sommet-sommet Écrire le code de la classe GrapheM qui implémente une matrice sommet-sommet. La spécification du constructeur de la classe est : 1 2 3 4 def __init__(self: GrapheM, mat: List[List[int]]) -> None: """ Constructeur de la classe. [Lire]

Le modèle Entités/Associations

Le modèle Entités/Associations en tant que tel n’est pas au programme. Par contre il me semble utile afin de vous faire comprendre comment on modèle le réel et on parvient au final à un schéma relationnel. L’objectif de ce chapitre n’est donc pas la conception de schémas E/A mais plutôt leur compréhension et leur interprétation. Ce chapitre présente la première étape du processus de modélisation du monde réel. On commence par recueillir les informations à intégrer dans la base de donnée puis on les transcrit sous une forme qui nous permettra, dans le prochain chapitre, à passer au modèle relationnel (choix de la structure de la base, clés, . [Lire]