TD 3

L’objectif de ce TP est d’approfondir les algorithmes en Diviser pour régner.

Algorithme de karatsuba

Nous allons étudier comment l’algorithme de multiplication de nombres entiers réalisé par Python. Pour ce faire, dans cette partie, il est n’est pas autorisé d’utiliser de nombres entiers, nous allons manipuler uniquement des chaînes de caractères qui représentent des nombres.

Pour que cela soit plus simple, nous allons faire l’ensemble des calculs en décimal.

1. Vérifier qu’une chaîne de caractère est un nombre.

Une chaîne de caractère représente un nombre correct s’il ne contient que des lettres qui représentent des chiffres décimaux (entre 0 et 9 donc). Écrire une fonction qui vérifie qu’une chaîne de caractères forme un nombre.

2. Le successeur.

Le successeur d’un nombre \(n\) est le résultat de l’opération \(n+1\). Écrire une fonction successeur qui prend en argument une chaîne de caractères qui représente un nombre et retourne une chaîne de caractères qui représente son successeur.

Pour vous aider, on vous autorise à utiliser la fonction suivante:

def successor_chiffre(u):
    if len(u) > 1:
        raise ValueError("Interdit d'utiliser cette fonction pour des chaines trop grandes")
    return str(int(u)+1)

3. L’addition.

Écrire une fonction addition qui prend en argument deux chaines de caractères qui représentent des nombres et qui retourne une chaîne de caractères qui réprésente leur somme.

4. La multiplication.

Écrire une fonction multiplication qui prend en argument deux chaines de caractères qui représentent des nombres et qui retourne leur produit.

6. Adapter la fonction d’addition de la question précédante pour faire des soustractions.

7. Proposez une fonction qui calcul la multiplication d’un nombre par une puissance de 10.

8. L’algorithme de Karatsuba.

L’algorithme de Karatsuba propose de réaliser la multiplication de deux nombre \(n\) et \(p\) de taille \(2k\) en les écrivant de la forme:

• \(n = a 10^k + b\)
• \(p = c 10^k + d\)

Il est alors possible d’utiliser l’égalité suivante pour réaliser un diviser pour régner:

\[(a10^k + b)(c10^k + d)=ac10^{2k} + (ad+bc)10^k+bd\]

On transforme une multiplication de taille \(2k\) en 4 multiplication de taille \(k\). On a donc une croissance asymptotique toujours quadratique. Pour faire mieux on peut remarquer que:

\[ad+bc= ac + bd - (a - b)(c - d)\]

Il est donc possible de calculer \(n*m\) uniquement en réalisant le cacul de \(ac\), \(bd\), et \((a - b)(c - d)\). Proposez une implémentation de cet algorithme.

6. Déterminer la complexité de cet algorithme

7. Tracer la fonction \(n\mapsto n^{\log_2(3)}\) et comparer à la courbe du cours 1.

Les Points les plus proches

Le problème PointProches retourne les deux éléments d’une liste les plus proches.

Par exemple, pour la liste [0, 4, 5, 9, 15], la fonction PointProches retourne me couple (4, 5).

1. Proposez une implémentation itératives naïve de ce problème.

2. Analyser la complexité de votre implémentation.

3. Proposez une implémentation en triant la liste et donner sa complexité.

4. Proposez une implémentation diviser pour régner de ce problème en utilisant median.

L’exercice suivant propose une implémentation de la médiane

Algorithme de séléction

1. Proposez une implémentation naïve impérative de cet algorithme. En faire l’analyse de complexité.

2. Proposez une amélioration en triant la liste dans un premier temps. Quelle est la complexité?

3. Comment faire mieux quand \(i\) est petit (par exemple pour \(i<10\)) ou quand \(i\) est grand \(n-10<i\) ?

4. Lire l’article wikipedia sur la médiane des médianes et faire une implémentation pour la médiane en complexité linéaire.

Conclusion

Quel est la complexité de PointProche ?

Difficile. Proposez une implémentation de PointProche pour une liste de vecteur de taille \(d\). En faire l’analyse de complexité. Comment généraliser l’approche par médiane?

Compiled the: lun. 31 mars 2025 10:06:56 CEST