Coloration d'un graphe
Publié le April 14, 2024
| 10 minutes
| 2115 mots
| David Latreyte
L’objectif de cette séance est de découvrir comment colorier chaque sommet d’un graphe à l’aide d’un algorithme glouton.
Colorier un graphe signifie associer une couleur à chacun de ses sommets de façon à ce que deux sommets liés par une arête n’aient pas la même couleur (deux sommets non adjacents peuvent avoir la même couleur).
Colorier un graphe avec un nombre minimal de couleurs est un problème difficile mais l’utilisation d’un algorithme glouton permet de résoudre le problème, au prix d’un nombre de couleurs qui n’est pas toujours minimal.
[Lire]
Représentation d'un graphe en informatique
Publié le March 19, 2024
| 10 minutes
| 1951 mots
| David Latreyte
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
Publié le November 24, 2023
| 4 minutes
| 827 mots
| David Latreyte
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
Publié le November 24, 2023
| 8 minutes
| 1610 mots
| David Latreyte
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
Publié le November 24, 2023
| 1 minutes
| 68 mots
| David Latreyte
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
Publié le November 20, 2023
| 3 minutes
| 611 mots
| David Latreyte
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
Publié le November 20, 2023
| 3 minutes
| 555 mots
| David Latreyte
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
Publié le November 20, 2023
| 1 minutes
| 60 mots
| David Latreyte
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
Publié le September 5, 2021
| 4 minutes
| 842 mots
| David Latreyte
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]
Parcours en profondeur : écriture du code en Python
Publié le May 6, 2021
| 6 minutes
| 1168 mots
| David Latreyte
Écriture d’une classe Graphe L’objectif de cette partie est l’écriture du code modélisant un graphe orienté. La représentation choisie est celle d’un dictionnaire de successeurs (en cours et dans le document 15,2 on a étudié les représentations par des matrice et liste de successeurs).
La représentation par un dictionnaire de successeurs présente de nombreux avantages. Par exemple,
les sommets peuvent être des entiers ou des chaînes de caractères quelconques ; La complexité de la liste des successeurs est directement proportionnelle au nombre de successeurs pour un sommet donné.
[Lire]