%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[french]{amsbook}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{a4wide}
\setlength\parskip{\smallskipamount}
\setlength\parindent{0pt}
\usepackage{amssymb}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \numberwithin{section}{chapter}
 \theoremstyle{plain}    
 \newtheorem{thm}{Theorem}[section]
 \numberwithin{equation}{section} %% Comment out for sequentially-numbered
 \numberwithin{figure}{section} %% Comment out for sequentially-numbered
 \theoremstyle{definition}
  \newtheorem{problem}[thm]{Problem}
 \theoremstyle{definition}
  \newtheorem{example}[thm]{Exemple}
 \theoremstyle{definition}
 \newtheorem{defn}[thm]{Définition}
 \theoremstyle{remark}
 \newtheorem{rem}[thm]{Remarque}
 \theoremstyle{definition}
  \newtheorem{xca}{Exercice}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\usepackage{hyperref}
\makeatletter
% Yucky bugware to make hyperref and babel[francais] work together
\def\url#1{{\selectlanguage{english}\hyper@normalise\url@{#1}}}
\def\href#1#2{{\selectlanguage{english}\hyper@normalise\href@{#1}{#2}}}
\makeatother
\newcommand{\solution}{ \vspace{2cm}}

\usepackage[francais,american]{babel}
\makeatother
\begin{document}

\chapter{Rappels de complexité (et d'algèbre linéaire)}

\begin{problem}
Quel est le meilleur méthode pour calculer le déterminant d'une matrice
?

Comment prédire le temps que va mettre un programme pour s'exécuter
?

Quelle est le meilleur algorithme pour trouver un nom dans un annuaire
?

Comment savoir, entre deux algorithmes, lequel est le plus rapide
?

Comment savoir si un algorithme est optimal ?
\end{problem}
\begin{example}
Je recherche le nom «Zorro» dans un annuaire en utilisant l'algorithme
suivant:
\end{example}
\begin{enumerate}
\item Je pars du début de l'annuaire;
\item Je compare le nom avec «Zorro»;
\item Si oui, j'ai terminé;
\item Si non, je recommence en 2 avec le nom suivant;
\end{enumerate}
%

%

%

%

%

%

%

\solution

Analyse de ce que l'on a fait:

On s'est donné un problème (rechercher un mot dans un dictionnaire),
un algorithme pour le résoudre (recherche exhaustive). Puis on a introduit
un \emph{modèle de calcul}:

\begin{enumerate}
\item Choix de la mesure de \emph{la taille d'une instance problème} (le
nombre de mots d'un dictionnaire donné)
\item Choix des \emph{opérations élémentaires} (comparer deux mots)
\end{enumerate}
Dans ce modèle, on a cherché le nombre d'opérations élémentaires effectuées
par l'algorithme pour un problème de taille $n$. C'est ce que l'on
appelle la \emph{complexité de l'algorithme}. En fait, on a vu deux
variations:

\begin{enumerate}
\item Complexité au pire ($n$ opérations)
\item Complexité en moyenne ($\frac{n}{2}$ opérations)
\end{enumerate}
À partir de cette information, et en connaissant le temps nécessaire
pour de petites instances du problème on peut évaluer le temps nécessaire
pour résoudre n'importe quelle instance du problème.

\begin{example}
Évaluons la complexité de la recherche dichotomique.
\end{example}
%

%

%

%

%

%

%

\solution

Analyse: 

La plupart du temps, il suffit d'avoir un ordre de grandeur du nombre
d'opérations: les constantes sont sans grande importance. Un algorithme
en $1000\log_{2}n+50$ sera meilleur qu'un algorithme en $\frac{n}{1000}$
dès que l'on s'intéressera à des instances suffisament grandes.

\begin{defn}
Soient $f$ et $g$ deux fonctions de $\N$ dans $\N$ (par exemple
les complexités de deux algorithmes).

On note $f=O(g)$ si, asymptotiquement, $f$ est au plus du même ordre
de grandeur que $g$, i.e. s'il existe une constante $a$ et un entier
$N$ tels que $f(n)\leq ag(n)$ pour $n\geq N$.

On note $f=o(g)$ si, assymptotiquement, $f$ est négligeable devant
$g$, i.e. si pour toute constante $a$ il existe $N$ tel que $f(n)\leq ag(n)$
pour $n\geq N$.

En gros: $f$
\end{defn}
\begin{rem}
Quelques règles de calculs sur les $O()$:
\begin{enumerate}
\item $O(4n+3)=O(n)$
\item $O(\log n)+O(\log n)=O(\log n)$
\item $O(n^{2})+O(n)=O(n^{2})$
\item $O(n^{3})O(n^{2}\log n)=O(n^{5}\log n)$
\end{enumerate}
Et de même pour les $o()$.
\end{rem}
\begin{xca}
Donner un algorithme pour chercher le plus grand élément d'une liste
de nombres. Évaluer la complexité de cet algorithme. Existe-t'il un
meilleur algorithme ?
\end{xca}
%

%

%

%

%

%

%

\solution

\begin{defn}
La \emph{complexité d'un problème} est la complexité du meilleur algorithme
pour le résoudre. 

On dit qu'un algorithme est \emph{optimal} si sa complexité coïncide
avec celle du problème.
\end{defn}
\begin{xca}
Donner un algorithme pour calculer la somme de deux matrices carrées,
et évaluer sa complexité. Est-il optimal ?

Donner un algorithme pour calculer le produit de deux matrices carrées,
et évaluer sa complexité. Est-il optimal ?

Rappeller l'algorithme du pivot de Gauss, et donner l'ordre de grandeur
de sa complexité.
\end{xca}
%

%

%

%

%

%

%

\solution

\begin{xca}
On dispose d'un ordinateur pouvant exécuter $10^{9}$ opérations élémentaires
par seconde (1GHz). On a un problème (par exemple, chercher un mot
dans une liste, calculer le déterminant d'une matrice), et des instances
de taille $1,10,100,1000$ de ce problème. Enfin, on a plusieurs algorithmes
pour résoudre ce problème, dont on connaît les complexités respectives:
$O(\log n)$, $O(n)$, $O(n\log n)$, $O(n^{2})$, $O(n^{3})$, $O(n^{10})$,
$O(2^{n})$, $O(n!)$, $O(n^{n})$. Évaluer dans chacun des cas le
temps nécessaire.
\end{xca}
%

%

%

%

%

%

%

\solution

\begin{xca}
Comparaison de la complexité de deux méthodes de tri.

On a une liste que l'on veut trier, mettons $7,8,4,2,5,9,3,5$.
\begin{itemize}
\item Méthode $1$ (tri sélection)

\begin{enumerate}
\item On échange le premier élément avec le plus petit des éléments $2,8,4,7,5,9,3,5$
\item On échange le deuxième élément avec le plus petit des éléments restants
$2,3,4,7,5,9,8,5$
\item \ldots{}
\item Au bout de $k$ étapes, les $k$ premiers éléments sont triés; on
échange alors le $k+1$ème élément avec le plus petit des éléments
restants.
\item À la fin, la liste est triée: $2,3,4,5,5,7,8,9$.
\end{enumerate}
\item Méthode 2 (tri fusion)

\begin{enumerate}
\item On groupe les éléments par paquets de deux, et on trie chacun de ces
paquets: $7,8,2,4,5,9,3,5$.
\item On groupe les éléments par paquets de quatres, et on trie chacun de
ces paquets: $2,4,7,8,3,5,5,9$.
\item \ldots{}
\item Au bout de $k$ étapes, les paquets de $2^{k}$ éléments sont triés;
on les regroupe par paquets de $2^{k+1}$ que l'on trie.
\item À la fin, tous les éléments sont dans le même paquet et sont triés:
$2,4,7,8,3,5,5,9$.
\end{enumerate}
\end{itemize}
Quelle est la meilleure méthode ?
\end{xca}
%

\begin{xca}
Évaluer au mieux la complexité des problèmes suivants:
\end{xca}
\begin{enumerate}
\item Calcul du $n$-ième nombre de Fibonacci;
\item Calcul du déterminant d'une matrice;
\item Calcul du rang d'une matrice;
\item Calcul de l'inverse d'une matrice;
\item Calcul d'un vecteur $x$ solution de $Ax=b$, où $A$ est une matrice
et $b$ un vecteur;
\item Calcul du pgcd de deux nombres;
\item Test de primalité de $n$;
\item Recherche du plus court chemin entre deux stations de métro à Paris;
\item Calcul de la $n$-ième décimale de $\sqrt{2}$;
\item Calcul de l'inverse d'un nombre modulo $3$;
\item Recherche d'un échec et mat en $4$ coups à partir d'une position
donnée aux échecs.
\item Problème du sac à dos: étant donné un ensemble d'objets d'épaisseur
variable, et un sac à dos de hauteur donnée, peut-on remplir le sac
à dos à bloc, sans déborder ?
\end{enumerate}

\end{document}
