Processing math: 100%

$\newcommand{\eps}{\varepsilon} \newcommand{\RR}{\mathbb{R}} \newcommand{\rd}{\operatorname{d}} \newcommand{\set}[1]{\left\{#1\right\}}$

Catégorie : Algorithmie

Distance d’édition

Auteur de la publication Par Xavier BADIN de MONTJOYE
Date de publication 20 novembre 2021
Catégories Dans Algorithmie, Exercices
Aucun commentaire sur Distance d’édition

Étant donné deux textes, il est parfois utile de savoir à quel point ils sont semblables ou différents. Un des outils utilisé pour répondre à ce problème est la distance de Levenshtein ou distance d’édition. Elle est notamment utilisé dans les correcteurs orthographiques. Exercice À partir d’un mot donné, on définit les opérations élémentaires comme […]

Produit efficace en binaire

Auteur de la publication Par Xavier BADIN de MONTJOYE
Date de publication 14 novembre 2021
Catégories Dans Algorithmie, Exercices
Aucun commentaire sur Produit efficace en binaire

Exercice Nous cherchons ici à effectuer le produit de deux entiers $x$ et $y$ écrits en binaire sur $k$ bits, avec $k$ une puissance de $2$ . On peut noter $x = x_1 x_2 \ldots x_k$ et $y = y_1 y_2 \ldots y_k$ . Les bits $x_1$ et $y_1$ sont les bits de poids forts. $1.$ Donner […]

La fonction d’Ackermann

Auteur de la publication Par Xavier BADIN de MONTJOYE
Date de publication 12 septembre 2021
Catégories Dans Algorithmie, Correction et Terminaison, Exercices
Un commentaire sur 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\\ […]