TD 3

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

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. Proposez une implémentation diviser pour régner de ce problème.

3. Facultatif. (*) Proposez une implémentation diviser pour régner de la variante de ce problème ou la liste contient des nombres complexes.

4. Facultatif. (**) Proposez une implémentation diviser pour régner de la variante de ce problème ou la liste contient des vecteurs de dimension \(d\).

L’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.

5. L’algorithme de Karatsuba.

En utilisant l’égalité suivante:

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

Proposez un algorithme en diviser pour régner pour la multiplication.

6. Lire la complexité de cet algorithme sur la page wikipédia.

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

Compiled the: dim. 07 janv. 2024 23:19:17 CET