Coloration d'un graphe

 Publié le April 14, 2024  |  10 minutes  |  2115 mots  |  

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]
Graphe  Structure de données 

Représentation d'un graphe en informatique

 Publié le March 19, 2024  |  10 minutes  |  1951 mots  |  

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

  1. É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.
    """

    Remarque : La classe Sommet possède deux attributs :

    [Lire]
Graphe  Structure de données 

Tri par insertion

 Publié le November 24, 2023  |  4 minutes  |  827 mots  |  

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.
  • Pour savoir où placer une carte dans son jeu, le joueur la compare avec chacune des cartes déjà présentes dans sa main gauche, en examinant les cartes de la droite vers la gauche.
  • À tout moment, les cartes tenues par la main gauche sont triées ; ces cartes étaient, à l’origine, les cartes situées au sommet de la pile sur la table.
  1. Choisir sept cartes à jouer. Les placer en ligne au hasard sur une table et mettre en œuvre la technique décrite ci-dessus.
    Se filmer pendant toute l’opération en commentant chacune des étapes !

Tri par insertion

Introduction

La méthode du tri par insertion est ilustré à cette adresse, ou, de façon plus folklorique, à cette adresse.

[Lire]
Tri  Invariant de boucle  Variant de boucle  Complexité 

Tri par sélection

 Publié le November 24, 2023  |  8 minutes  |  1610 mots  |  

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]
Tri  Invariant de boucle  Variant de boucle  Complexité 

Algorithmes de tri

 Publié le November 24, 2023  |  1 minutes  |  68 mots  |  

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  |  

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.
    """

    def __init__(self: Maillon, valeur: int, suivant: Maillon = None) -> None:
        self.valeur = valeur
        self.suivant = suivant


class Liste:
    """
    Implémentation de la classe liste.
    """

    def __init__(self: Liste, valeur: int = None) -> None:
        """
        Initialisation de l'objet. Il est possible de créer une liste
        vide ou une liste contenant un élément.

        Il est possible de créer directemnt une liste contenant plusieurs
        éléments il faut utiliser une fonctionnalité de Python que vous
        ne connaissez pas forcément et qui n'est pas au programme.
        """
        if valeur is None:
            self.maillons = None
        else:
            self.maillons = Maillon(valeur)

    def est_vide(self: Liste) -> bool:
        """ Détermine si la liste est vide. """
        return self.maillons is None

    def __len__(self: Liste) -> int:
        """ Retourne le nombre d'éléments dans la liste. """
        if self.est_vide():
            return 0
        else:
            nbre = 0
            maillon = self.maillons
            while maillon is not None:
                nbre += 1
                maillon = maillon.suivant
            return nbre

    def append(self: Liste, valeur: int) -> None:
        """
        Ajoute valeur à la fin de la liste.
        """
        if self.est_vide():
            self.maillons = Maillon(valeur)
        else:
            maillon = self.maillons
            while maillon.suivant is not None:
                maillon = maillon.suivant

            maillon.suivant = Maillon(valeur)

    def append_first(self: Liste, valeur: int) -> None:
        """
        Ajoute valeur au début de la liste.
        """
        maillon = Maillon(valeur)
        maillon.suivant = self.maillons
        self.maillons = maillon

    def pop(self: Liste) -> int:
        """
        Retire le dernier élément de la liste et le retourne.

        Lève une erreur si la liste est vide.
        """
        if self.est_vide():  # Liste vide
            raise Exception("La liste est vide !")

        maillon = self.maillons
        if maillon.suivant is None:  # Cas d'une liste à un élément
            valeur = maillon.valeur
            self.maillons = None
            return valeur
        else:
            while maillon.suivant.suivant is not None:  # Cas général
                maillon = maillon.suivant
            valeur = maillon.suivant.valeur
            maillon.suivant = None
            return valeur

    def pop_first(self: Liste) -> int:
        """
        Retire le premier élément de la liste et le retourne.

        Lève une erreur si la liste est vide.
        """
        if self.est_vide():  # Liste vide
            raise Exception("La liste est vide !")

        valeur = self.maillons.valeur
        self.maillons = self.maillons.suivant
        return valeur

    def __getitem__(self: Liste, i: int) -> int:
        """
        Redéfinition de la fonction d'accès à l'élément d'indice i.
        """
        if self.est_vide():
            raise Exception("La liste est vide !")

        maillon = self.maillons
        j = 0
        while j < i:
            if maillon is None:
                raise IndexError("Indice hors des limites !")
            maillon = maillon.suivant
            j += 1
        return maillon.valeur

    def __str__(self: Liste) -> str:
        """
        Représentation de la liste sous-forme d'une chaîne de caractères.
        """
        rep = "["

        maillon = self.maillons
        while maillon is not None:
            rep += str(maillon.valeur)
            if maillon.suivant is not None:
                rep += ", "
            maillon = maillon.suivant

        rep += "]"
        return rep
Liste  Liste chaînée 

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

 Publié le November 20, 2023  |  3 minutes  |  555 mots  |  

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.
    """
    trouve = False

    i = 0
    while i < len(tab) and not trouve:
        if val == tab[i]:
            trouve = True
        i += 1

    return trouve


def est_dans_rec(tab: list[int], n: int, i: int = 0) -> bool:
    """
    Recherche si la valeur n est présente au moins une fois
    dans le tableau tab.
    Algorithme récursif, i est l'indice de recherche.
    """
    if i == len(tab):
        return False
    elif tab[i] == n:
        return True
    else:
        return est_dans_rec(tab, n, i + 1)


def insere(tab: list[int], n: int, i: int) -> None:
    """
    Insère la valeur n à l'indice i du tableau tab.
    Algorithm itératif et en place.
    
    Lève une exception si le tableau est déjà plein.
    
    HYPOTHÈSE : la gestion des "trous" n'est pas assurée,
    l'algorithme se contente de décaler les valeurs vers 
    la droite.
    """
    dernier_indice = len(tab) - 1

    if tab[dernier_indice] != None:
        raise Exception("Tableau plein !")

    k = dernier_indice
    while k > i:
        tab[k] = tab[k - 1]
        k -= 1

    #for k in range(dernier_indice, i, -1):
    #    tab[k] = tab[k - 1]

    tab[i] = n


def insere_rec(tab: list[int], n: int, i: int, k: int) -> None:
    """
    Insère la valeur n à l'indice i du tableau tab.
    Algorithm récursif et en place. k est l'indice de
    recherche. 
    Sa première valeur doit être len(tab) - 1.
    
    Lève une exception si le tableau est déjà plein.
    
    HYPOTHÈSE : la gestion des "trous" n'est pas 
    assurée, l'algorithme se contente de décaler 
    les valeurs vers la droite.
    """
    dernier_indice = len(tab) - 1

    if tab[dernier_indice] != None and k == dernier_indice:
        raise Exception("Tableau plein !")
    elif k == i:
        tab[i] = n
        return None
    else:
        tab[k] = tab[k - 1]
        return insere_rec(tab, n, i, k - 1)


if __name__ == "__main__":
    tab = [i for i in range(20)]

    assert est_dans(tab, 12) == True
    assert est_dans(tab, 0) == True
    assert est_dans(tab, 20) == False

    assert est_dans_rec(tab, 12) == True
    assert est_dans_rec(tab, 0) == True
    assert est_dans_rec(tab, 20) == False

    print("Insertion itérative")
    tab = [1, 1, 2, 3, 4, 5, None, None, None]
    print(tab)
    insere(tab, 7, 0)
    print(tab)
    insere(tab, 7, 0)
    print(tab)
    insere(tab, 7, 0)
    print(tab)
    #insere(tab, 7, 0)
    #print(tab)
    print()
    print("Insertion récursive")
    tab = [1, 1, 2, 3, 4, 5, None, None, None]
    print(tab)
    insere_rec(tab, 7, 0, len(tab) - 1)
    print(tab)
    insere_rec(tab, 7, 0, len(tab) - 1)
    print(tab)
    insere_rec(tab, 7, 0, len(tab))
    print(tab)
Liste  Liste chaînée 

Somme des $n$ nombres d'un tableau

 Publié le January 29, 2023  |  3 minutes  |  452 mots  |  

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.

  1. É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  Récursivité 

Diviser pour régner

 Publié le January 29, 2023  |  6 minutes  |  1157 mots  |  

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]
Diviser pour régner 

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

 Publié le January 29, 2023  |  1 minutes  |  57 mots  |  

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 ».
Diviser pour régner  Programmation dynamique