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]
Somme des $n$ nombres d'un tableau
Publié le January 29, 2023
| 3 minutes
| 452 mots
| David Latreyte
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
Publié le January 29, 2023
| 6 minutes
| 1157 mots
| David Latreyte
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
Publié le January 29, 2023
| 1 minutes
| 57 mots
| David Latreyte
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 ».