%% 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}
\IfFileExists{url.sty}{\usepackage{url}}
                      {\newcommand{\url}{\texttt}}

\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{xca}{Exercice}
 \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{american}\hyper@normalise\url@{#1}}}
\def\href#1#2{{\selectlanguage{american}\hyper@normalise\href@{#1}{#2}}}
\makeatother
\newcommand{\solution}{ \vspace{2cm}}

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

\title{Remise à niveau en informatique}

\maketitle
\tableofcontents{}


\chapter{Organisation}

Ce module sera composé d'un cours d'introduction aux concepts fondamentaux
d'informatique (structures de données, complexité, calculabilité,
\ldots{}) et de TP d'applications. Vous serez évalués sur les TPs
et sur un examen théorique final.


\chapter{Jeudi 07/10/2003: TP1, structures de données}

À rendre pour le 16/10/2003.

Sujet: \url{http://lapcs.univ-lyon1.fr/~nthiery/DESS/Notes/Exemples/RN-TP1-Nicolas.Thiery-1.0.tar.gz}

Correction: \url{http://lapcs.univ-lyon1.fr/~nthiery/DESS/Notes/Exemples/RN-TP1-Nicolas.Thiery-1.0-Correction.tar.gz}


\chapter{Jeudi 16/10/2003: TP2, Tris et complexité}

À rendre pour le 23/10/2003.

\begin{xca}
Dans le cadre de l'utilisation de l'outil informatique, vous avez
déjà implanté le tri à bulle. Complétez la class \texttt{Sort} avec
des fonctions pour le tri rapide, le tri fusion et le tri par arbre
binaire de recherche. Pour ce dernier tri, on suggère de définir une
nouvelle classe \texttt{BinarySearchTree} qui hérite de \texttt{BinaryTree},
avec une méthode \texttt{add} pour insérer un nouvel élément. 

Ceux qui voudront aller plus loin pourront implanter une classe \texttt{BalancedBinarySearchTree},
héritant de \texttt{BinaryTree}, dans laquelle les arbres ont des
branches dont les longueurs diffèrent d'au plus $1$. On pourra par
exemple utiliser l'astuce des noeuds rouge/noir (red-black tree).
\end{xca}
%

\begin{xca*}
Pour chacun de ces tris, estimez le nombre d'opérations élémentaires
à l'aide d'un compteur, et faites quelques statistiques sur des échantillons
aléatoires. Déduisez-en une évaluation de leur complexité en moyenne,
au mieux et au pire.
\end{xca*}

\section{\textsf{Quelques références}}

\begin{itemize}
\item \textsf{Un support de cours sur les tris \url{http://dept-info.labri.u-bordeaux.fr/~lachaud/IUT/ASD-Prog-E1-2000/planning-prof.html}}
\item Un support de cours sur les tris séquentiels \url{http://deptinfo.unice.fr/~fedou/ENSEIGNEMENT/ASD/TRIS/index.html}
\item Une fiche de TP sur les tris \url{http://www.lri.fr/~denise/M2Spec/97-98.1/TDSpec6.ps}
\item Démonstration de bubble sort et quicksort \url{http://jade.lim.univ-mrs.fr/~vancan/mait/demo/SortDemo/example1.html}
\end{itemize}

\chapter{Mardi 23/10/2003: TP3, Polynômes et complexité}

À rendre pour le 30/10/2003. Non noté.

\begin{xca*}
Compléter les méthodes \texttt{add}, \texttt{multiply} et \texttt{multiplyKaratsuba}
dans la classe \texttt{Polynom} fournie \url{http://lapcs.univ-lyon1.fr/~nthiery/DESS/Notes/Exemples/RN-TP3-Nicolas.Thiery-1.0.tar.gz}.
Pour ceux qui veulent aller plus loin: compléter aussi la méthode
\texttt{multiplyFFT}. Tracer, pour des polynômes aléatoires de degré
croissant, la courbe du temps nécessaire pour les différentes opérations
de multiplication en fonction du degré des polynômes en entrée.

Correction: \url{http://lapcs.univ-lyon1.fr/~nthiery/DESS/Notes/Exemples/RN-TP3-Nicolas.Thiery-1.0-Correction.tar.gz}
\end{xca*}

\chapter{Jeudi 30/10/2003, TP 4: Automates et langages rationnels}

À rendre pour le 6 novembre.

\begin{xca}
Écrire des programmes (par exemple en perl ou en java) utilisant des
expressions régulières appropriées pour:
\begin{itemize}
\item Extraire la liste des utilisateurs depuis le fichier \texttt{/etc/passwd}
contenant la base de donnée des utilisateurs des machines.
\item Prendre un fichier de données contenant dans chaque ligne 3 nombres
séparés par des tabulations, et inverser les deux premières colones.
\item Étant donné un mot sur la ligne de commande, renvoyer tous les mots
anglais le contenant comme sous-mot (on considère que \texttt{car}
est un sous-mot de \texttt{spe}\texttt{\underbar{c}}\texttt{t}\texttt{\underbar{a}}\texttt{to}\texttt{\underbar{r}}).
On pourra utiliser le fichier \texttt{/usr/share/dict/words.}
\item Étant donnés deux mots sur la ligne de commande, chercher le nombre
d'occurences de ces mots proches l'un de l'autre dans un texte. On
pourra se contenter, pour simplifier, de ne rechercher de tels mots
proches que lorsqu'ils sont sur la même ligne.
\end{itemize}
Si vous optez pour java, vous pouvez utiliser la bibliothèque \texttt{gnu.regexp}.
Un mini d'exemple d'utilisation est fourni:

\url{http://lapcs.univ-lyon1.fr/~nthiery/DESS/Notes/Exemples/RN-TP4-Nicolas.Thiery-1.0.tar.gz}

Pour la documentation complète de cette bibliothèque, voir:

\url{file:/usr/java/docs/gnu.regexp/}
\end{xca}
\emph{Le reste des exercices est facultatif.}

\begin{xca*}
Soit $\Sigma=\{ a,b,c\}$ un alphabet. Les langages suivants sur $\Sigma$
sont-ils rationnels?
\begin{enumerate}
\item $L_{1}=\{ aba,bba,acab\}$
\item $L_{2}=a^{*}$
\item $L_{3}=a^{*}b^{*}$
\item $L_{4}=\{ a^{n}b^{n},n\in\N\}$ 
\item $L_{5}=\{(ab)^{n},n\in\N\}$.
\end{enumerate}
\end{xca*}
%

\begin{xca*}
Soit $\Sigma=\{ a,b\}$ un alphabet. Construire les automates d\'{e}terministe
finis qui reconnaissent respectivement:
\begin{enumerate}
\item Le langage $L_{1}:=\{ aa,ab,bbaab\}$;
\item Le langage $L_{2}:=a^{*}$;
\item Le langage $L_{3}:=a^{+}$;
\item Le langage $L_{4}:=a^{*}b^{*}$;
\item L'ensemble des mots se terminant par $b$;
\item L'ensemble des mots contenant au moins un $b$;
\item L'ensemble des mots contenant une sequence de 4 $b$ cons\'{e}cutifs;
\item L'ensemble des mots dont le nombre d'occurrence de $b$ est divisible
par 3;
\item $L_{9}:=\{ a,b\}^{*}\{ a\}\{ a,b\}^{2}$;
\item $L_{10}:=(aab+aa+aabb)^{*}$.
\end{enumerate}
\end{xca*}
%

\begin{xca*}
Implantation des automates sur machine.
\begin{enumerate}
\item Concevoir une structure de donnée appropriée pour stocker un automate
déterministe fini.
\item Implanter, dans le langage de votre choix, une fonction prenant en
entrée un automate et un mot, et vérifiant que le mot est bien reconnu
par l'automate. 
\item Utiliser cette fonction pour écrire des programmes reconnaissant les
langages de l'exercice précédent.
\end{enumerate}
\end{xca*}
%

\begin{xca*}
Implanter une fonction qui étant donné un entier $n$ construit un
automate reconnaissant le langage $L:={ab,aabb,aaabbb,\ldots,a^{n}b^{n}}$.
\end{xca*}
%

\begin{xca*}
Pour ceux qui n'ont peur de rien!
\end{xca*}
\begin{enumerate}
\item Implantez une fonction prenant un automate non déterministe, et renvoyant
un automate déterministe reconnaissant le même langage.
\item Implantez une fonction prenant en entrée un automate fini déterministe
pour $L_{1}$, et retournant un automate fini déterministe pour $L_{1}^{*}$.
\item Implantez une fonction prenant en entrée des automates finis déterministes
pour $L_{1}$ et $L_{2}$, et retournant un automate fini déterministe
pour $L_{1}.L_{2}$.
\item Implantez une fonction prenant en entrée des automates finis déterministes
pour $L_{1}$ et $L_{2}$, et retournant un automate fini déterministe
pour $L_{1}\cup L_{2}$.
\end{enumerate}

\subsection{Quelques références}

\begin{itemize}
\item TD: Dragons, trolls et automates finis \url{http://pauillac.inria.fr/ups/tp/tp6.ps}
\item Le Dragon Book \url{http://www.science.uva.nl/~mes/jargon/d/dragonbook.html}
\item Langages et compilation, resume de cours \url{http://pauillac.inria.fr/algo/banderier/P13/html/}
\end{itemize}
%


\chapter{Jeudi 30/10/2003, TP 4: Grammaires}

À rendre pour le 13 novembre. Non noté.

L'objectif de ce TP est d'apprendre à utiliser les grammaires en pratique,
par exemple avec javacc. Un mini exemple d'utilisation de javacc est
fourni:

\url{http://lapcs.univ-lyon1.fr/~nthiery/DESS/Notes/Exemples/RN-TP5-Nicolas.Thiery-1.0.tar.gz}

Pour la doc et des exemples plus complets d'utilisation de javacc,
voir:

\url{file:/usr/java/javacc/}

\begin{xca}
Modifier l'exemple fourni pour qu'il reconnaisse n'importe quel jeu
de parenthèses, accolades, comme par exemple: {[}{[}\{\}{[}({[}{]}){]}{]}\{()\}{]}).

Écrire une application Calc qui calcule la valeur d'une expression
comme '(3 + 4) {*} (3 + 4{*}(1+2))'.

En réutilisant les classes ExpressionTree \& autres du premier TP,
écrire une application InfixToPolish qui transforme en notation infixe
une expression comme '(3 + 4) {*} (3 + 4{*}(1+2))'.
\end{xca}
%

\begin{xca}
Écrire une classe qui permet de lire des fichiers au format Hexier.
\end{xca}

\end{document}
