TD - Séance 0

Exercise 0 - Échauffement

Problème 0:

Implémenter en Racket une fonction poly-0 qui permet de calculer les valeurs du polynôme \(x^2-5\) appliquées : nombres entiers, rationnels, flottants ou complexes, exacts ou inexacts.

Exemples de résultats attendus :

> (poly-0 0)
-5
> (poly-0 10)
95
> (poly-0 0.03)
-4.9991
> (poly-0 1/2+2i)
-35/4+2i

Problème 1:
Faites de même pour \(x^2+x-2\) (utilisez poly-1 comme nom de la fonction que vous écrirez). Exemples de résultats attendus :

> (poly-1 0)
-2
> (poly-1 1/2)
-5/4
> (poly-1 0.3+1/2i)
-1.86+0.8i

Exercice 1 - Itération et points fixes

Étant donné une fonction \(f(x) : \mathbb{R} \rightarrow \mathbb{R}\), un point fixe \(p\) de \(f\) est défini comme une solution de l'équation \(f(p) = p\).
Sous diverses conditions qui ne nous concernent pas, de tels points fixes peuvent être approchés par l'itération suivante :

\(x_{n+1} = f(x_n)\) pour \(0 \leq n \leq N\),

où \(x_0\) est une supposition initiale et \(N\) est le nombre d'itérations que nous sommes prêts à calculer.

Ces itérations sont fréquemment utilisées en informatique, dans divers contextes allant de l'analyse numérique à l'optimisation et l'apprentissage automatique. Dans cet exercice, nous verrons quelques applications élémentaires de cette technique.

Problème 0:

Implémenter une fonction point fixe telle que point fixe f x iter calcule le résultat de iter pas de l'itération du point fixe à partir d'une estimation initiale de x. Utilisez ensuite cette fonction pour estimer le point fixe de la fonction cosinus:

> (fixed-point cos 0.5 100)
0.7390851332151607

Problème 1:

Le mathématicien grec du premier siècle, Héron d'Alexandrie, a décrit dans son ouvrage Metrica (AD 60), une méthode itérative d'approximation de la racine carrée \(\sqrt{s}\) d'un nombre réel non négatif \(s\):

\(x_{n+1} = \frac{1}{2} \left(\frac{s}{x_n} + x_n\right)\).

Implémenter une fonction heron telle que heron s x iter estime la racine carrée de s en calculant le résultat de iter itérations de cette procédure avec l'estimation initiale x. Exemple de résultats attendus :

> (heron 2 0.1 10)
1.414213562373095
> (heron 3 2.0 10)
1.7320508075688772

Problème 1:

La méthode Newton-Raphson, nommée d'après Isaac Newton et Joseph Raphson, est un algorithme d'approximation des racines d'une fonction différentiable à valeur réelle. Elle est décrite par l'itération :

\(x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\).

Implémenter une fonction newton telle que newton f f-prime x iter estime les résultats d'une fonction calculée par f, dont la dérivée est calculée par f-prime, en effectuant iter itérations de l'algorithme de Newton-Raphson. Utilisez-le pour estimer les racines de poly-0 et poly-1 :

> (newton poly-0 poly-0-prime -1.0 100)
-2.23606797749979
> (newton poly-0 poly-0-prime 1.0 10)
2.23606797749979
> (newton poly-1 poly-1-prime 0.5 10)
1.0
> (newton poly-1 poly-1-prime -1.0 10)
-2.0

Où poly-0-prime et poly-1-prime sont des fonctions que vous implémentez et qui évaluent les dérivées de \(x^2-5\) et \(x^2+x-2\) respectivement.

Problème 1: Souvent, au lieu de préciser le nombre d'itérations, on préfère préciser la précision du résultat attendu. Par exemple, supposons que nous cherchions une approximation \(z\) d'une racine d'une fonction \(f(x)\) telle que \(f(z) < acc\) où \(acc\) est un nombre proche de zéro. Comment modifier newton pour obtenir une fonction réalisant une telle procédure ?

TP - Séance 0

Exercice 0 - Nombres triangulaires et factoriels

Problème 0: Implementez une fonction triangular-number telle que triangular-number n pour n un nombre donné calcule (de manière récursive) la somme \(T_n = \sum\limits_{i=0}^{n} i\). Exemple de résultat attendu :
```
> (triangular-numbers 5)
15
> (triangular-numbers 10)
55
```
Problème 1: Implementez une fonction factorial telle que factorial n calcule le produit \(n! = \prod\limits_{i=1}^{n} i\).
```
> (factorial 5)
120
> (factorial 10)
3628800
```

Hint

Remarquez que \(T_0 = 0, T_n = n + T_{n-1}\) et \(1! = 1, n! = n (n-1)!\).

Exercice 1 - Calculer avec des listes

Problème 0 : Ecrivez une fonction prod qui, étant donné une liste de nombres, calcule leur produit. Exemple de résultat attendu :
```
> (define example-list '(1 2 3 4 5 6 7 8 9 10))
> (prod example-list)
3628800
```
Problème 1 : Ecrivez une fonction succ qui, étant donné une liste de nombres, produit une nouvelle liste dont les éléments sont les successeurs des éléments respectifs de la liste initiale. Rappelons que le successeur d'un nombre \(n\) est \(n+1\). Exemple de résultat attendu :
```
> (succ example-list)
'(2 3 4 5 6 7 8 9 10 11)
```