Étiquette : exercice

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 […]

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 […]