\documentclass{article}
\textheight 23 cm 
\textwidth 15cm
\topmargin -1.5 cm
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage[francais]{babel}
\usepackage{times}
\usepackage{xspace}
\usepackage{makeidx}
\usepackage{ifpdf}
\ifpdf
 \usepackage[colorlinks,pdftex]{hyperref}
\else
 \usepackage[ps2pdf,breaklinks=true,colorlinks=true,linkcolor=red,citecolor=green]{hyperref}
\fi
\newcommand{\bs}{\symbol{92}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newtheorem{thm}{Th\'eor\`eme}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{defn}[thm]{D\'efinition}
\makeindex

% \renewcommand{\cuttingunit}{subsection} (add HEVEA after % for hacha)
%\input{giacfr.tex}
%HEVEA\htmlfoot{Retour \`a la page principale de \ahref{http://www-fourier.ujf-grenoble.fr/\~parisse/giac_fr.html}{Giac/Xcas}.}

\title{Programmation}
\author{Bernard.Parisse@ujf-grenoble.fr}
\date{2016}

\begin{document}

\noindent Licence 3 maths \hfill Programmation de méthodes numériques \hfill UGA

\section{Exercices types, flottants}
\begin{enumerate}
\item Afficher une table de multiplication demand\'ee \`a l'utilisateur.
\item D\'eterminer le plus petit entier $n$ tel que 
\verb|(1.0+2^(-n))-1.0==0| en utilisant le type
\verb|float| et \verb|double|. Attention \verb|^| n'est pas
la puissance en C, c'est le ou exclusif. Attention, utiliser \verb|1.0f| pour
coder 1.0 en flottants. En d\'eduire le nombre de bits de la mantisse
dans les 2 cas.
\item R\'esoudre par dichotomie $\cos(x)=x$ sur l'intervalle $[0,1]$.
Rappel: si $f$ continue change de signe sur $[a,b]$, on peut d\'eterminer
une valeur approch\'ee de $r$ tel que $f(r)=0$ en prenant $c$ le milieu
de $a$ et $b$, si $f(c)f(a)<0$ on remplace $b$ par $c$ sinon on remplace
$a$ par $c$.
Attention, $c$ peut \^etre \'egal \`a $a$ ou $b$ 
avec le type \verb|double|. Utiliser \verb|#include<cmath>| pour la fonction \verb|cos|.
\item Trouver une valeur de $h$ optimale pour d\'eterminer une valeur
approch\'ee de $f'(x)$ par les formules
$$\frac{f(x+h)-f(x)}{h}, \quad \frac{f(x+h)-f(x-h)}{2h}$$
On testera avec $f$ tel que $f(x)$ et $f'(x)$ soient de l'ordre de grandeur
de 1, par exemple $f(x)=e^x$ en $x=1.0$ et avec les types \verb|float| et \verb|double|.\\
Proposer et tester des formules pour $f'{'}(x)$.
\item Calculer des sommes partielles de s\'eries \`a terme positif d\'ecroissant
en commen\c{c}ant par le terme de plus grand ou de plus petit indice, comparer
les r\'esultats en \verb|float| ou \verb|double|, par exemple pour
$$ \sum_{k=1}^N \frac{1}{k^2}, \quad \sum_{k=1}^N \frac{1}{k}, ...$$
\end{enumerate}

\section{Exercices fonctions/vector}
On représentera un vecteur de réels par un \verb|vector<double>|, une matrice par un vecteur de vecteurs de même taille.
Pour lire un \verb|vector<double>| 
depuis un fichier \verb|data| du
disque dur contenant le nombre d'\'el\'ements suivi par la liste des valeurs,
(par exemple faire \verb|emacs data &| puis entrer
\verb|3 1.01 2.3 4.7| et sauvegarder), vous pouvez vous inspirer du
programme ci-dessous (à adapter avec des templates pour les matrices)~;
\begin{verbatim}
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

istream & operator >> (istream & is,vector<double> & v){
  int n; is >> n;
  v.resize(n);
  for (int i=0;i<n;i++)
    is >> v[i];
  return is;
}

ostream & operator << (ostream & os,const vector<double> & v){
  int n=v.size(); os << n << " ";
  for (int i=0;i<n;++i)
    os << v[i] << " ";
  return os;
}

int main(){
  ifstream fichier("data");
  vector<double> v; fichier >> v;
  cout << v << endl;
}
\end{verbatim}

\begin{enumerate}
\item \'Ecrire une fonction min qui calcule le minimum de 2 entiers,
puis l'utiliser pour cr\'eer une fonction min qui calcule le minimum
de 3 entiers.
\\ \'Ecrire une fonction qui calcule le min d'une liste de r\'eels.
\item \'Ecrire une fonction qui prend en argument deux nombres $a,b$
et remplace $a$ par le plus petit et $b$ par le plus grand.
\item \'Ecrire une fonction prenant en argument un \verb|vector<double>|
et calculant les \'el\'ements statistiques~: moyenne, \'ecart-type,
m\'ediane, quartiles. On pourra utiliser \verb|sort| pour trier le vecteur.
\item \'Ecrire une fonction calculant un rationnel proche
d'un r\'eel en utilisant la d\'ecomposition en fraction
continue.
\item \'Ecrire une fonction qui calcule la somme d'une liste de r\'eels.\\
  Pour améliorer la précision, on pourra tester l'algorithme suivant
  avec une (grande) liste ou en générant les éléments à sommer au fur et à
  mesure
\begin{verbatim}
Somme(l un vector<double>)
  variables locales x,s,c
  s:=0.0; c:=0.0; // la somme et la correction
  pour x élément de l faire
    c += (x-((s+x)-s));
    s += x;
  fin pour;
  renvoyer s+c;
\end{verbatim}
Explication~: $c$ devrait valoir 0 sans erreurs d'arrondis,
avec les erreurs d'arrondis, le premier calcul intervenant dans celui de $c$
est $s+x$ qui contribuera en
une erreur oppos\'ee \`a celui du calcul de $s += x$ \`a la ligne
suivante, le 2i\`eme calcul effectu\'e $(s+x)-s$ donne une erreur
absolue en $\varepsilon |x|$ au pire (car c'est une erreur relative
par rapport \`a $(s+x)-s$), 
et la 3i\`eme erreur d'arrondi est n\'egligeable
(puisque la somme vaut 0). On a donc une erreur absolue sur $s+c$
qui est au premier ordre au pire en $O(\varepsilon \sum|x_i|)$, 
bien meilleure que
la majoration $\varepsilon ((n-1)|x_1|+(n-2)|x_2|+...+|x_n||)$
calcul\'ee pr\'ec\'edemment.

\item \'Ecrire une fonction prenant en argument un \verb|vector<double>|
repr\'esentant les coefficients d'un polyn\^ome $P$ et un \verb|double|
repr\'esentant $a$ et calculant $P(a)$, en utilisant la méthode de Horner.\\
Bonus~: en itérant, déterminer la liste des coefficients de $P(x+a)$.
\item \'Ecrire une fonction calculant une valeur approch\'ee de $\cos(x)$
  sur $[-1,1]$ en utilisant le d\'eveloppement de Taylor en 0 \`a l'ordre 12.\\
  Prolonger cette fonction sur $\mathbb{R}$ en utilisant les propriétés
    de la fonction cosinus.
\item \'Ecrire une fonction r\'ecursive puis it\'erative pour calculer le
PGCD de 2 entiers (\verb|int|). Bonus~: renvoyer les 3 entiers de l'identité de Bézout.
\item \'Ecrire une fonction r\'ecursive calculant $a^n \pmod p$
(si $n=0$ on renvoie 1, si $n=1$ on renvoie $a$, si
  $n$ est pair on renvoie le carr\'e de $a^{n/2} \pmod p$ etc.). Bonus~:
  le faire en itératif.
\item \'Ecrire une fonction d\'eterminant la position d'un nombre 
dans une liste tri\'ee de nombres par dichotomie. On renverra -1 si
le nombre n'est pas trouv\'e.
\item \'Ecrire une fonction de dichotomie qui prend en argument
une fonction \verb|double| donne \verb|double| et les extremit\'es
de l'intervalle $a,b$. Tester.
\item Faire de même par la méthode du point fixe. Pour la méthode de Newton,
  il faut donner une deuxième fonction (la dérivée) ou en déterminer
  une estimation numérique, par exemple par la méthode de la sécante. Dans le
  cas d'un polynôme, on utilisera plutôt Horner deux fois.
\item Implémenter du calcul matriciel.
\end{enumerate}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
