Catégorie : Algorithmie

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

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=x1x2xk et y=y1y2yk. Les bits x1 et y1 sont les bits de poids forts. 1. Donner […]

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 N2 dans N et est définie par : \[A(m,\:n) = \begin{cases} n+1& \text{ si }m=0\\ […]