Ctrl+K

Applications

Applications#

Composantes connexes#

Définition

Soit \(G\) un graphe non orienté. La composante connexe d’un sommet \(s\) de \(G\) est l’ensemble des sommets atteignables depuis \(s\) en suivant un chemin dans \(G\).

Exercice (pour aller plus loin)

  1. Décrire un algorithme pour calculer toutes les composantes connexes d’un graphe non orienté

    VOTRE RÉPONSE ICI

  2. Implanter cet algorithme et visualiser son exécution

Généralisation#

Exercice:

  1. Généraliser la fonction parcours de la fiche 01-ParcoursDeGraphe.md pour qu’elle prenne en argument la fonction de voisinage du graphe plutôt que le graphe lui-même.

from typing import Callable, Iterable, Set
from graph import Node

def parcours_fonction(voisins: Callable[[Node], Iterable[Node]], u: Node) -> Set[Node]:
    """
    INPUT:
    - `voisins`: une fonction telle que `voisins(v)` renvoie les voisins sortants de `v`
    - 'u' - un sommet du graphe
    
    OUTPUT: l'ensemble des sommets `v` de `G`
            tels qu'il existe un chemin de `u` à `v`
    """
    # VOTRE CODE ICI
    raise NotImplementedError()

  1. Testez votre fonction sur l’exemple suivant.
    Indication: étant donné un graphe G tel que implanté précédément, la fonction voisins requise par distance peut être construite comme suit:

from graph import examples
G = examples.parcours_directed()
voisins = G.neighbors

assert parcours_fonction(voisins, 'D') == {'D', 'F', 'G', 'H'}

  1. Reprenez de même tous les tests de la fiche 01 avec votre nouvelle fonction.

Application: ensembles définis récursivement#

De nombreux ensembles mathématiques sont définis en donnant quelques éléments initiaux, puis en applicant récursivement un processus permettant de produire de nouveaux éléments à partir d’éléments déjà présents. Par exemple, l’ensemble des entiers naturels est construit à partir de \(0\) et de la fonction successeur \(x \mapsto x+1\).

Définition

Soit \(E\) un ensemble, \(R\subset E\) un sous ensemble fini, et \(f\) une fonction associant à chaque élément de \(E\) un sous-ensemble fini de \(E\). L’ensemble \(f\) défini récursivement par \(R\) et \(f\) est le plus petit sous-ensemble de \(E\) contenant \(R\) et stable par \(f\): si \(e\in F\) alors \(f(e)\subset F\).

Exercice (pour aller plus loin)

Décrire les ensembles définis récursivement obtenus dans chacun des cas suivants:

  • \(E=\mathbb N\), \(R=\{1\}\), \(f(e) = \{ e + 2 \}\) VOTRE RÉPONSE ICI

  • \(E=\mathbb N\), \(R=\{1\}\), \(f(e) = \{ 2e, e+3 \}\) VOTRE RÉPONSE ICI

  • \(E\): listes, \(R=\{()\}\), \(f(u)\): rajouter \(0\) ou \(1\) à la fin du \(u\) VOTRE RÉPONSE ICI

  • \(E\): listes, \(R=\{(1,2,3,2,1)\}\), \(f(u)\): supprimer la première ou dernière lettre de \(u\) VOTRE RÉPONSE ICI

Exercice (pour aller plus loin)

Soit \(C_n\) l’ensemble récursivement défini par:

  • \(R=\{ (\underbrace{1,1,\cdots,1}_n)\}\)

  • \(f\) qui a une liste associe toute les listes obtenues en regroupant et sommant deux entrées consécutives
    Par exemple, \(f((2,3,1,1)) = \{(5,1,1), (2,4,1), (2,3,2)\}\)

  • Calculer à la main les quatres éléments de \(C_3\), sans oublier \((3)\)!

  • Calculer avec la machine tous les éléments de \(C_6\).

  • Combien y en a t’il?

  • Même chose pour \(C_1,C_2,C_3,C_4,C_5\).

  • Que conjecturez vous?

  • Pouvez vous le prouver?

VOTRE RÉPONSE ICI

Exercice (pour aller plus loin)

Une permutation est une liste d’entiers telle que, si \(n\) est sa longueur, alors tous les entiers de \(1\) à \(n\) apparaissent exactement une fois. Décrire l’ensemble des permutations comme un ensemble énuméré. Utiliser cela pour lister toutes les permutations de longueur \(n\leq 6\).

VOTRE RÉPONSE ICI

Contenu