Catégorie : Exercices

Stabilité des langages rationnels

Le but de cet exercice est de présenter plusieurs opérations stables sur les langages rationnels. On suppose connu l’équivalence entre les langages rationnels et les langages reconnaissables par automate fini. Exercice Soit $\mathcal{L}_1$ et $\mathcal{L}_2$ deux langages rationnels sur l’alphabet $\Sigma$. Montrer que les langages suivants sont rationnels. $1)$ $\overline{\mathcal{L}_1} = {\;w \in \Sigma^{*}\;|\;w \notin […]

La fonction d’Ackermann

Ici on s’attaque à un des exercices les plus classiques en matière de terminaison d’algorithme. On présente une fonction récursive et le but est de montrer qu’un algorithme calculant cette fonction termine. Exercice La fonction d’Ackermann est une fonction de $\mathbb{N}^{2}$ dans $\mathbb{N}$ et est définie par : \[A(m,\:n) = \begin{cases} n+1& \text{ si }m=0\\ […]

La fonction 91 de McCarthy

Exercice On définit la fonction récursive suivante due à McCarthy. Elle prend en entrée un entier $n$ et est définie par : \[f(n) = \begin{cases} n – 10 & \text{ si } n \gt 100 \\ f(f(n+11)) & \text{ sinon} \end{cases}\] On considère l’algorithme qui calcule $f(n)$ en partant de la formule de récurrence. Montrer […]

Coloration de Wigderson

Exercice Le but de cet exercice est de colorer un graphe que l’on sait $3$-coloriable en utilisant le moins de couleurs possible. $1)$ Soit un graphe $G$ quelconque de degré maximal $\Delta$. Donner une borne sur le nombre chromatique de $G$. Soit $G$ un graphe $3$-coloriable. Pour $u$ un sommet de $G$, on note $N(u)$ […]

Formule de Cayley

Exercice La formule de Cayley affirme que pour $n \gt 1$, le nombre $C_n$ d’arbres qu’on peut construire sur $n$ sommets est $n^{n-2}$. Le matrix tree theorem ou théorème de Kirchhoff, déjà présenté en exercice, nous permet de calculer directement cette valeur. $1)$ Prouver la formule de Cayley à l’aide du Matrix Tree Theorem. Une […]

Théorème de Kirchhoff

On présente ici un résultat important de la théorie des graphes pourtant méconnus des étudiants. Le but de cet exercice est de démontrer le théorème de Kirchhoff, aussi appelé matrix tree theorem. Ce théorème donne une formule pour compter le nombre d’arbres couvrants d’un graphe. Cet exercice nécessite une bon maîtrise mathématique de la notion […]

Codage de Gray

Exercice Le but du codage de Gray est de représenter les entiers de telle sorte qu’un seul bit soit modifié à chaque incrémentation. Pour $n$ un entier strictement positif, on définit la fonction $\Gamma_n$ de $\{\;0,\;\ldots,\;2^{n}-1\;\}$ dans $\{\;0,\;1\;\}^{n}$, qui à un entier associe son codage de Gray sur $n$ bits. On définit de même la […]