%% 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[frenchb]{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{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}
\usepackage[english,francais]{babel}
\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[english,francais]{babel}
\makeatother
\begin{document}

\chapter{Notions de complexité}

\begin{problem}
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{problem}
%

\begin{xca}
Évaluer au mieux la complexité des problèmes suivants:
\end{xca}
\begin{enumerate}
\item Calcul de $n!$;
\item Calcul du $n$-ième nombre de Fibonacci;
\item Recherche d'un mot dans un dictionnaire;
\item Calcul du pgcd de deux nombres;
\item Calcul du produit de deux matrices;
\item Calcul du déterminant d'une matrice;
\item Calcul du rang d'une matrice;
\item Inversion d'une matrice;
\item Calcul d'un vecteur $x$ solution de $Ax=b$, où $A$ est une matrice
et $b$ un vecteur;
\item Recherche du plus court chemin entre deux stations de métro à Paris;
\item Test de primalité de $n$.
\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}
