%% 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]{amsart}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\IfFileExists{url.sty}{\usepackage{url}}
                      {\newcommand{\url}{\texttt}}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \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{plain}    
 \newtheorem*{thm*}{Théorème} 
 \theoremstyle{plain}    
 \newtheorem{algorithm}[thm]{Algorithme} %%Delete [thm] to re-start numbering
 \theoremstyle{definition}
  \newtheorem*{xca*}{Exercice}
 \theoremstyle{definition}
  \newtheorem*{problem*}{Problème}
 \theoremstyle{definition}
  \newtheorem*{example*}{Exemple}
 \newenvironment{lyxcode}
   {\begin{list}{}{
     \setlength{\rightmargin}{\leftmargin}
     \setlength{\listparindent}{0pt}% needed for AMS classes
     \raggedright
     \setlength{\itemsep}{0pt}
     \setlength{\parsep}{0pt}
     \normalfont\ttfamily}%
    \item[]}
   {\end{list}}
 \theoremstyle{remark}    
 \newtheorem*{correction}{Correction} 
 \theoremstyle{definition}
  \newtheorem{problem}[thm]{Problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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{\foreignlanguage{american}{\hyper@normalise\url@{#1}}}
\def\href#1#2{\foreignlanguage{american}{\hyper@normalise\href@{#1}{#2}}}
\makeatother
\newcommand{\solution}{ \vspace{2cm}}
% Bug fix: without forcing the switch to francais after \begin{document}, chapter, table of contents and others are not translated properly.
\AtBeginDocument{
\selectlanguage{francais}
}

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

\title{Système \& Réseaux}

\maketitle

\section{Rudiments de cryptographie }

L'objectif de ce cours est de vous donner un aperçu des techniques
de cryptographie qui sont utilisées dans des protocoles comme PGP,
ssh ou ssl: chiffrage et déchiffrage, signature, authentification.


\subsection{Problèmes}

\begin{itemize}
\item Chiffrement / déchiffrement (protocoles symétriques / non symétriques)
\item Signature
\item Authentification
\item Tatouage (watermark)
\item Dissimulation
\end{itemize}

\subsection{Un exemple d'algorithme de cryptographie: RSA}

La méthode de cryptographie RSA, codage à clef publique, a été inventée
en 1977 par R.-L.~Rivest, A.~Shamir et L.~Adleman \emph{A method
for obtaining digital signatures and Public-Key cryptosystems}, communications
of the A.C.M., février 1978. 

Quelques rappels sur les nombres premiers et les entiers modulos $p$
($Z/pZ$).

\begin{xca}
Trouver les nombres inversibles dans $Z/5Z$ et $Z/6Z$.
\end{xca}
\begin{thm*}
Petit théorème de Fermat:

Si $p$ est un nombre premier, alors pour tout entier $m$, alors
\[
m^{p}=m\mod p.\]

\end{thm*}
Variations: 

\begin{itemize}
\item Si $p$ est un nombre premier, et si $m$ n'est pas divisible par
$p$, alors \[
m^{p-1}=1\mod p.\]

\item Si $p$ et $q$ sont deux nombres premiers, et si $m$ est premier
avec $p$ et $q$, alors \[
m^{(p-1)(q-1)}=1\mod pq.\]

\end{itemize}
La méthode RSA est basée sur cette dernière variation. On prend deux
grands nombres premiers $p$ et $q$, et on note $n$ le produit $pq$.
On choisit ensuite un nombre $e$ premier avec $(p-1)(q-1)$. Alors
$e$ est inversible modulo $(p-1)(q-1)$. On note $d$ son inverse.
On appelle alors:

\begin{itemize}
\item clef publique le couple $(n,e)$. 
\item clef privée le couple $(n,d)$; 
\end{itemize}
L'algorithme fonctionne alors comme suit:

\begin{algorithm}
{[}Rivest, Shamir et Adleman{]}

Soit $M<n$ un nombre appelé message. Le message chiffré est alors
le nombre codé à l'aide de la clef publique

\[
C:=M^{e}\mod n.\]
 On retrouve alors $M$ à l'aide de la clef privée par \[
M':=C^{d}\mod n.\]

\end{algorithm}
\begin{xca*}
Vérifier que l'on retrouve bien le message d'origine $M$.

Vérifier que les deux clef jouent des rôles symétriques: si on chiffre
avec la clef privée puis l'on déchiffre avec la clef publique, alors
on reobtient encore le message d'origine. On dit que le chiffrement
est \emph{commutatif}.
\end{xca*}
%

\begin{xca*}
Connaissant $p$, $q$, et $e$, comment peut-on calculer $d$ ?
\end{xca*}
%

%

%

%

%

La sécurité de ce chiffrement repose sur le fait qu'il est très difficile
d'obtenir $d$ sans connaître la factorisation $pq$ de $n$.


\subsubsection{Implantation (mercredi 3 novembre)}

Nous allons maintenant implanter cet algorithme en java (on utilisera
un système de calcul formel comme Maple ou MuPAD pour la génération
de nombres premiers et la factorisation). Le TP du mercredi 10 décembre
sera basé sur cette implantation et sera noté. Il est donc indispensable
que vous ayez d'ici là une version fonctionnelle.

\begin{xca*}
Nombres premiers en Maple, MuPAD, ...

Avec les commandes Maple ou MuPAD \texttt{nextprime}, \texttt{prevprime}
et \texttt{ithprime}, afficher des nombres premiers à 10 et 20 chiffres.
Effectuer le produit de deux nombres premiers, puis tenter de  factoriser
ce résultat avec la commande \texttt{ifactor}/\texttt{factor}. Que
pouvez-vous conclure ? Écrire une fonction qui renvoie un nombre premier
\char`\"{}aléatoire\char`\"{} entre $10^{n}$ et $10^{n+1}$.
\end{xca*}
%

\begin{xca*}
Implantation en java: complétez le squelette fourni: \url{http://lapcs.univ-lyon1.fr/~nthiery/DESS/Notes/Exemples/OI-TP1-Nicolas.Thiery-1.0.tar.gz}.

Note: on demande d'implanter des fonctions pour calculer puissances
et inverses modulo m, même si elles sont en fait déjà disponibles
dans BigInteger.
\end{xca*}

\subsubsection{Utilisation de RSA (mercredi 10 novembre)}

\begin{xca}
On va expérimenter en taille réelle pour voir comment on peut arriver
à échanger des données confidentielles par dessus un media non sûr.
\begin{enumerate}
\item Le répertoire /home/Media sera le média non sûr par dessus lequel
vous allez communiquer (tout le monde peut y lire et écrire librement).
Pour entrer dans le répertoire, taper \\
\texttt{cd /home/Media}
\item Créez une paire clef publique/clef privée, et mettez la clef publique
(c'est-à-dire $n$ et $e$) dans un fichier \texttt{Prenom.Nom.clef-publique},
par exemple en utilisant \texttt{emacs.}
\item Pour écrire un message à quelqu'un, écrire le message chiffré dans
un fichier avec un nom dans le genre \texttt{Prenom1.Nom1-pour-Prenom2.Nom2-numero},
ou 1 est l'expéditeur, 2 est le destinataire, et \texttt{numero} est
le numéro du message. Typiquement: \texttt{Nicolas.Thiery-pour-Florent.Hivert-4.}
\item Pour visualiser un message, vous pourrez par exemple utiliser\\
\texttt{cat Nicolas.Thiery-pour-Florent.Hivert-4}
\item Le copier-coller sera très utile pour toutes ces manoeuvres! De même
que l'utilisation de la touche TAB pour la complétion automatique
des noms de fichiers.
\item Évidement, vous êtes plus qu'encouragés à essayer d'intercepter les
messages de vos petits camarades :-)
\end{enumerate}
Pour mettre un peu de piment, on va faire un petit championnat:
\begin{itemize}
\item Chaque message envoyé de manière sûre donne un point à l'expéditeur
et au destinataire;
\item Chaque message intercepté et déchiffré par une tierce personne lui
donne trois points;
\item Celui qui marque le plus grand nombre de points a gagné.
\end{itemize}
Dans le répertoire, il y a déjà ma clef publique, un message que j'ai
chiffré avec ma clef privée à l'intention de tout le monde, la clef
publique de Toto et un message chiffré à l'intention de Toto. Toto
a une clef privée que vous ne connaissez pas, votre objectif est de
déchiffrer ce message.
\end{xca}
Le TP sera noté sur 10. Il sera à rendre comme d'habitude sous la
forme d'une archive contenant le code java, vos clefs publiques et
privées, le message chiffré à mon intention, et le contenu déchiffré
du message pour tout le monde et du message pour Toto.


\subsection{Applications}

\begin{xca*}
Applications de RSA

Décrivez comment on peut utiliser RSA pour résoudre les problèmes
suivants:
\begin{enumerate}
\item Chiffrement
\item Signature
\item Authentification
\end{enumerate}
À votre avis, quelles sont les difficultés qui peuvent être rencontrées
dans la mise en oeuvre de RSA ?

%

%

%

%

%

%

\solution
\begin{enumerate}
\item Garantie de qualité du générateur aléatoire de nombres premiers
\item Garantie que $n$ ne soit pas factorisable
\item Compromis vitesse de calcul / niveau de sécurité
\item Gestion du risque inhérent de tomber sur un message non premier avec
$(p-1)(q-1)$
\item Gestion des clefs publiques
\item Protection des clefs privées
\item Standardisation
\item Difficultés légales
\item Difficultés avec les brevets
\end{enumerate}
\end{xca*}
%

\begin{xca*}
Vous devez envoyer à un correspondant une petite mallette pouvant
être fermée par un ou plusieurs cadenas, et contenant des documents
ultra-confidentiels mais non urgents. Les seuls moyens à votre disposition
pour communiquer avec votre correspondant sont la poste et le téléphone,
qui sont notoirement non sûrs. Comment procéder ?
\end{xca*}

\subsection{Principe de fonctionnement de PGP / GNU PG}

\begin{enumerate}
\item Certification de clefs, réseau de confiance, serveurs de clefs, \ldots{}
\end{enumerate}

\subsection{Principe de fonctionnement de ssh}

\begin{enumerate}
\item Authentification avec ou sans échange de mot de passe
\item Échange de clef de session + chiffrement symétrique
\end{enumerate}

\subsection{Références}

\begin{enumerate}
\item Site web de GNU PG \url{http://www.gnupg.org/}
\item GNU Privacy Handbook \url{http://www.gnupg.org/gph/en/manual.html}
Ce manuel (en anglais) contient une excellente introduction à l'utilisation
d'outils de cryptographie pour protéger sa vie privée.
\item Documentation de GNU PG \url{http://www.gnupg.org/howtos/fr/} Version
abrégée et traduite du précédent.
\item Site web d'openssh \url{http://www.openssh.org}
\item Une introduction a la cryptographie \url{http://www.di.ens.fr/~wwwgrecc/Recherche/Crypto/intro/intro.html}
\item Une discussion sur la taille des cles de chiffrement \url{http://www.di.ens.fr/~pornin/faq-cle.html}
\end{enumerate}

\section{Introduction au fonctionnement des réseaux}

Je vous conseille de lire le document suivant \url{http://www.eleves.ens.fr:8080/tuteurs/hublot/rezo.ps.gz}.
De manière générale, je recommande chaleureusement le site des tuteurs \url{http://www.eleves.ens.fr/tuteurs/},
qui contient de très bons documents d'introduction.

\begin{xca}
Utilisez la commande \texttt{traceroute machine} depuis votre connexion
ssh sur lapcs.univ-lyon1.fr pour explorer la topologie du réseau aux
alentours de la fac. Vous pourrez par exemple commencer par \texttt{traceroute
www.google.fr}, ou toute autre machine de votre choix. Au fur et à
mesure, dessinez le réseau sur le tableau noir. Préciser au fur et
à mesure les noms, adresse IP, et si possible adresses de sous-réseaux.

Expérimentez aussi avec les commandes ping, host, route.
\end{xca}
%

\begin{xca}
Quelques ordres de grandeurs:

Évaluer le nombre d'octets nécessaires pour stocker:
\begin{enumerate}
\item Un nombre entier sur 5 chiffres;
\item Un nombre flottant;
\item Un caractère;
\item Une page de texte;
\item La bible;
\item Une photo;
\item Une heure de son;
\item Une heure de vidéo;
\end{enumerate}
En déduire, à la louche, la capacité d'un CDROM et d'un DVD.

Évaluer la quantité d'images que l'on pourrait stocker dans une camionnette.

Évaluer le débit nécessaire pour transmettre:
\begin{enumerate}
\item Du texte tapé à la main (talk, IRC, et autres messageries instantanées);
\item Du son;
\item De la vidéo.
\end{enumerate}
Évaluer le temps de latence maximal pour transmettre:
\begin{enumerate}
\item Du texte tapé à la main;
\item Du son;
\item De la vidéo.
\end{enumerate}
Votre machine chez vous est connectée à internet par le téléphone
soit par une connexion normale (\textasciitilde{}50 kb/s) ou par ADSL
(\textasciitilde{}512 kb/s). Évaluer dans les deux cas quel est le
moyen le plus rapide de rapatrier le contenu d'un DVD disponible sur
internet.
\end{xca}

\section{Calculs scientifiques et réseaux}

Objectif: Comprendre comment on peut utiliser le réseau pour faire
des calculs scientifiques

\begin{problem*}
Vous avez un super nouvel algorithme pour, mettons, faire une certaine
analyse statistique d'un jeu de données et vous voulez que le plus
grand nombre de personnes puissent l'utiliser. 

Jusqu'à la fin de ce cours, vous allez découvrir différentes possibilités
pour faire cela, en implantant des petits jeux en réseaux.
\end{problem*}

\subsection{Communications entre processus par tuyaux et prises (pipes \& sockets,
\ldots{})}

Un réseau c'est a priori compliqué. Le but est de fournir une interface
qui permette à des programmes (processus) de communiquer simplement
entre eux, en faisant abstraction de la complexité du réseau en dessous.

Rien de sorcier, c'est comme le téléphone:

\begin{itemize}
\item Le numéro de téléphone est remplacé par un nom de machine
\item Comme il peut y avoir plusieurs programmes sur une machine (plusieurs
personnes pour un même numéro de téléphone) on rajoute un numéro de
port (numéro de poste).
\end{itemize}
Voilà comment ça se passe:

\begin{enumerate}
\item Le programme A sur la machine alpha demande au système d'attendre
les connections sur le port 6083.
\item Le programme B sur la machine beta demande au système de se connecter
sur la machine alpha sur le port 6083.
\item Le programme A accepte la connexion et décroche; la connexion est
établie.
\item Les programmes A et B ont à leur disposition deux tuyaux leur permettant
de communiquer.
\item Quand ils ont terminé ils coupent la communication.
\end{enumerate}

\subsection{Exemples de protocoles réseaux: http (web), smtp (mail), nntp (Usenet),
...}

Ce sont des protocoles client-serveur typiques:

\begin{enumerate}
\item A est un serveur web (apache, \ldots{}) qui tourne sur le port www
(80) de alpha
\item B est un navigateur web (netscape, \ldots{}) qui se connecte sur
alpha
\item A accepte la connexion, et démarre un nouveau processus A' en redirigeant
les entrées et sorties standard de celui-ci vers le tuyau.
\item A reprends l'attente de nouvelles connections
\item A' envoie (éventuellement) un message d'accueil
\item B demande une page web
\item A' renvoie la page web puis raccroche
\end{enumerate}
\begin{example*}
Récupérer un fichier à la main sur un serveur web:
\begin{lyxcode}
icare>~telnet~lapcs.univ-lyon1.fr~www

GET~/index.html
\end{lyxcode}
Version un peu plus avancée:
\begin{lyxcode}
icare>~telnet~lapcs.univ-lyon1.fr~www

GET~/index.html~HTTP/1.0
\end{lyxcode}
\end{example*}
%

\begin{example*}
Envoyer un mail à la main:
\begin{lyxcode}
icare>~telnet~localhost~smtp

HELO~univ-lyon1.fr

MAIL~FROM:~le.pere.noel@antartique.fr

RCPT~TO:~nthiery@localhost

DATA

Voilà~plein~de~cadeaux!

~~~~~~~~~~~~~~~~~~~~~~~~~~~~Le~père~noël

.

QUIT
\end{lyxcode}
Cette méthode permet d'envoyer des faux mails.

Elle ne marche pas toujours, car il y a des protections.

De toutes les façons, IL NE FAUT PAS EN ABUSER !

Si un faux mail porte préjudice à quelqu'un, celui-ci peut engager
des poursuites judiciaires, comme pour tout usage de faux documents.
\end{example*}
%

\begin{xca*}
Lire les news à la main:

Essayez les commandes suivantes:
\end{xca*}
\begin{lyxcode}
lapcs>~telnet~news.univ-lyon1.fr~nntp

HELP

LIST

GROUP~fr.comp.lang.php

BODY~15090

HEAD~15090

ARTICLE~15090

NEXT

HEAD

BODY

ARTICLE
\end{lyxcode}
\begin{xca*}
Utiliser l'exercice précédent et les commandes UNIX que vous avez
vues pour récupérer la liste de tous les groupes de discussion francais
(fr.quelquechose).

Indication: telnet est une application UNIX comme les autres; vous
pouvez donc rediriger à volonté son entrée et sa sortie standard.
\end{xca*}
Ne regardez pas la correction ci-dessous avant d'avoir vraiment essayé
par vous-même!

%

%

%

%

%

%

\solution

\begin{correction}
Version minimale:

\texttt{echo list | telnet news.univ-lyon1.fr nntp | grep fr}

Version avancée plus polie avec le serveur et garantissant que le
fr est en début de ligne:

\texttt{(echo list; echo quit) | telnet news.univ-lyon1.fr nntp |
grep '\textasciicircum{}fr\textbackslash{}.'}

Expliquez ce qu'il ce passe lorsque l'on exécute ces commande!
\end{correction}

\subsection{Comment cela marche les tuyaux ?}

On utilise des niveaux d'abstraction successifs, chaque couche apportant
une amélioration à la {}``qualité de service''. Dans l'implantation
de chaque couche, on a pas besoin de se préoccuper des détails d'implantation
des couches inférieures.

\begin{enumerate}
\item Envoi d'un signal entre deux machines: couche physique (câble Ethernet,
ligne de téléphone (normal/ADSL), fibre optique, faisceau lumineux,
radio (faisceaux herziens, téléphone portable, réseau local sans fil),
télégraphe, pigeon voyageur\ldots{})
\item Envoi d'un paquet entre deux machines directement connectées: Ethernet,
PPP, PLIP, \ldots{}
\item Envoi d'un paquet avec routage entre machines sur des réseaux différents:
IP
\item Envoi de suites de paquets avec garantie de qualité: TCP
\item Tuyaux et prises (socket)
\item Tuyaux sécurisés (authentification, chiffrement): ssl/ssh 
\item Protocoles réseaux (http, smtp, nntp, nfs, samba, netware, ntp, \ldots{})
\item Interfaces utilisateur (navigateur web, logiciel de mail, lecteur
de news, \ldots{})
\end{enumerate}
Toutes ces couches font l'objet de spécifications précises dans des
standards. La plupart du temps sous forme de documents RFC (Request
For Comments). Le développement d'Internet a été essentiellement permis
par le fait que ces standards soient \emph{ouverts}.


\subsection{TP: les prises et tuyaux en java}

La bibliothèque standard de java contient toutes les fonctions nécessaires
pour utiliser des prises et tuyaux. Vous trouverez deux exemples d'utilisation
dans l'archive suivante:\url{http://lapcs.univ-lyon1.fr/~nthiery/DESS/Notes/Exemples/SR-TP3-Nicolas.Thiery-1.0.tar.gz}

Ce TP ne sera pas noté. Il est à faire pour le mercredi 29 janvier.

\begin{xca}
Écrivez une application java \texttt{Aspirateur} qui prends comme
argument sur la ligne de commande l'URL d'un document sur le web,
se connecte sur le serveur web correspondant et rappatrie le document
dans un fichier. Par exemple, si on tape\\
\texttt{java Aspirateur http://lapcs.univ-lyon1.fr/\textasciitilde{}nthiery/DESS/index.html}~\\
l'application doit récupérer le fichier \texttt{index.html} et le
sauvegarder dans le répertoire courant.
\end{xca}
%

\begin{xca}
Écrivez un serveur qui calcule $n!$. 

Description du protocole:
\begin{enumerate}
\item Le serveur attends la connection d'un client.
\item Le client se connecte.
\item Le client envoie au serveur une ligne contenant un nombre $n$.
\item Le serveur lui renvoie une line contenant $n!$.
\item Boucle en 3.
\end{enumerate}
De plus:
\end{xca}
\begin{itemize}
\item Pour se déconnecter, le client envoie une ligne contennant la commande
\texttt{quit}.
\item Si le client envoie n'importe quoi (nombre négatif, commande inconnue,
...), le serveur lui renvoie une ligne avec un message d'erreur.
\end{itemize}
%

\begin{xca}
Écrivez deux applications (un client et un serveur) qui permettent
à deux personnes sur des machines différentes de dialoguer en s'envoyant
des lignes de texte à tour de rôle. Mettez-vous d'accord entre groupes
pour que tous vos programmes soient compatibles entre eux!
\end{xca}

\subsection{Calculs scientifiques et réseaux}

\begin{problem*}
En quoi les réseaux peuvent-ils être utiles pour les calculs scientifiques
?

%

%

%

%

%

%

\solution
\end{problem*}
\begin{itemize}
\item Distribution rapide de logiciels
\item Distribution simplifiée de logiciels complexes à installer\\
Versions de démonstration
\item Lancement de calculs sur plusieurs machines
\item Calcul parallèle (PVM, MPI, clusters, machines spécialisées)
\item Calcul massivement parallèle (seti@home)
\item Mise à disposition de puissance de calcul et de logiciels\\
(centre de calcul medicis.polytechnique.fr)
\item Bases de données (encyclopédie des séquences d'entiers)
\item Documents scientifiques interactifs, éducation en ligne
\end{itemize}
\begin{problem*}
Quelles solutions techniques? 

%

%

%

%

%

%

\solution
\end{problem*}
\begin{itemize}
\item Côté client (on fournit le logiciel qui est exécuté sur le client):

\begin{enumerate}
\item Programme autonome
\item Bibliothèque pour un système existant
\item Bibliothèque précompilée (C, C++, fortran, java, ...) à lier avec
un autre programme
\item Code exécuté dans le navigateur web: HTML+Javascript / Applet java
\item Distribution: source / binaire ? licence ?
\end{enumerate}
\item Côté serveur (le logiciel est exécuté sur le serveur):

\begin{enumerate}
\item Connexion par ssh sur le serveur, et travail à distance avec les logiciels
qui y sont installés (medicis.polytechnique.fr)
\item Interface web (linbox, encyclopédie des séquences d'entiers):

\begin{enumerate}
\item {}``scripts'' CGI (programme appelé par le serveur web), souvent
en perl
\item PHP/ASP + bases de données (code exécuté directement par le serveur
web)
\end{enumerate}
\item Interface avec protocole dédié (serveurs de calcul FGb+RS)
\end{enumerate}
\end{itemize}
Problèmes principaux: sécurité, simplicité d'emploi, fiabilité, efficacité,
pérennité

\begin{problem}
Quels sont les avantages et inconvénients de chacune d'entre elles? 

Pour chacune des applications ci-dessus, quelles sont les solutions
raisonnables ?
\end{problem}

\subsection{Projet: jeu de Hex en réseau}

L'objectif du projet est d'améliorer le jeu de Hex que vous avez programmé
en utilisant le réseau.

\begin{xca}
On suppose que deux programmes de jeu de dame sont connectés l'un
à l'autre par un tuyau. Il va falloir décider comment ces deux programmes
vont utiliser ce tuyau pour transmettre les informations nécessaires
pour jouer l'un contre l'autre. Commencons par un exemple: voilà un
dialogue typique entre deux humains jouant aux dames:
\begin{enumerate}
\item Joueur 1: Bonjour, tu joues aux dames avec moi ?
\item Joueur 2: Ok. je joue C3-D2
\item Joueur 1: je joue F4-E5
\item Joueur 2: je joue C5-E5
\item Joueur 1: nan, tu n'as pas le droit; essaye encore.
\item Joueur 2: je joue C5-E5
\item ...
\item Joueur 2: je joue F4-H6, t'as perdu!
\item Joueur 1: zut. Je joue plus.
\item Joueur 2: mauvais joueur; tant pis, à bientôt
\end{enumerate}
Un programme ne serait probablement pas capable de suivre un tel dialogue.
Il y a des ambiguités, des bouts inutiles, des bouts sous-entendus.
Le but de l'exercice est de formaliser ce type de dialogue pour qu'il
puisse avoir lieu entre deux programmes; c'est-à-dire de mettre au
point un protocole permettant à ces programmes d'échanger leurs coups
pour mener à bien leur partie.
\end{xca}
%

\begin{xca}
Joueur humain contre machine distante.
\begin{enumerate}
\item Écrire une application java qui implante ce protocole via son entrée
et sa sortie standard. Ainsi, un joueur connaissant le protocole peut
jouer directement avec lui en le lançant à la main. Vous pouvez écrire
plusieurs variantes, avec des stratégies de jeu différentes.
\item Modifier le programme précédent pour en faire un serveur qui attends
sur un port donné d'une machine distante.
\item Améliorer ce serveur pour qu'il gère plusieurs coups en même temps.
\item Modifier l'interface utilisateur pour qu'elle se connecte sur le serveur
précédent pour permette à l'utilisateur de jouer contre la machine.
Pour cela, vous pouvez créer une nouvelle classe {}``RemotePlayer'';
lorsqu'un objet \texttt{o} de cette classe est créé, il ouvre une
connexion avec le serveur distant. Ensuite, lorsque l'on appelle la
méthode nextMove de cet objet, celle-ci envoie les informations au
serveur, et récupère le mouvement suivant.
\end{enumerate}
\end{xca}
%

\begin{xca}
Joueurs humains à distance.

Écrire un serveur {}``arbitre'' qui attends que les interfaces des
deux joueurs (ou plus) se connectent dessus, et gère leur dialogue.

Optionnel: étendre ce serveur pour qu'il gère plusieurs parties en
même temps. 

TODO: faire utiliser les threads
\end{xca}

\subsection{Les Threads, ou processus légers}

Références:

\begin{itemize}
\item Tutorial java de SUN sur les processus légers \url{http://java.sun.com/docs/books/tutorial/essential/threads/}
\item Des notes de cours en français sur les processus légers \url{[http://javahttp://cedric.cnam.fr/~farinone/CCAM/threads.pdf}
\end{itemize}
\begin{xca}
Écrire une version du programme joueur humain contre joueur automatique
sur la machine locale pour que le calcul du prochain coup ait lieu
dans un autre processus léger. Pour cela, vous pouvez créer une nouvelle
classe {}``ThreadPlayer'' dont la méthode nextMove créé un nouveau
processus léger; ce processus léger à son tour créé un objet de la
classe GreedyPlayer (ou de n'importe quel joueur automatique), et
appelle la méthode nextMove de cet objet.
\end{xca}
%

\begin{xca}
Parallélisme: Écrire un joueur automatique qui recherche le meilleur
coup en explorant récursivement l'arbre des possibilités, en parallélisant
le calcul sur plusieurs machines.

Une architecture possible:
\begin{enumerate}
\item On a une liste de machines disponibles.
\item Sur chaque machine tourne un serveur qui attends des connexions. Lorsqu'il
en reçoit une, il lance un sous-processus (\emph{thread}) qui traite
la connexion (recevoir une requête, calculer une réponse, la renvoyer
et se déconnecter). Pour limiter les dégats, le serveur peut tenir
à jour le nombre de sous-processus lancés, et se déclarer «indisponible»
s'il y en a trop.
\item Une requête consiste en la description d'un échiquier, d'une couleur
(est-ce aux noirs ou aux blancs de jouer) et d'une profondeur $p$.
Le programme fait une recherche dans l'arbre des possibilités et calcule
le meilleur coup pour le joueur considéré, c'est-à-dire le coup qui
maximise l'évaluation $e$ à profondeur $p$. La réponse est composée
du meilleur coup et de l'évaluation $e$. Bien entendu ce problème
est à traiter récursivement: on parcoure la liste des coups possibles;
pour chacun d'entre eux, on calcule la meilleure contre-attaque pour
le joueur adverse, et l'évaluation correspondante; enfin on choisi
le coup qui minimise la contre-attaque.
\item Chaque programme connaît la liste des machines. S'il le souhaite,
il peut décider en cours de calcul de déléguer une partie du travail
sur une autre machine. Pour cela, il peut rechercher un autre serveur
disponible (s'il y en a un), et lui donner à résoudre une des sous-branches.
\end{enumerate}
\end{xca}

\subsection{Références}

Exemples de serveurs de calcul sur le web:

\begin{itemize}
\item L'encyclopedie electronique des suites d'entiers (Sloane) \url{http://www.research.att.com/~njas/sequences/}
\item Serveur de calcul d'algebre lineaire exacte \url{linalg.org}
\end{itemize}
Documents:

\begin{itemize}
\item Usenet (protocole nntp) \url{http://ecole.eu.org/doc/usenet/index.html}
\item Les services de base d'internet (ftp http mail, nntp) \url{http://ecole.eu.org/doc/cours4/internet2/}
\item Supports de cours de l'Ecole Ouverte de l'Internet \url{http://ecole.eu.org/doc/supports.html}
\item Documents sur l'utilisation d'UNIX sur Linux-France \url{http://www.linux-france.org/}
\item Documents sur l'utilisation d'UNIX, sur le site des tuteurs \url{http://www.eleves.ens.fr:/tuteurs/}
\item Un tutorial pour javascript \url{http://www.pageresource.com/jscript/}
\item Un tutorial java \url{http://javaboutique.internet.com/tutorials/Step/Chapter1/index.html}
\item Tutorial sur les tuyaux (sockets) et java \url{http://www.javaworld.com/jw-12-1996/jw-12-sockets.html}
\item Les exemples présentés en cours \url{http://www.lapcs.univ-lyon1.fr/~nthiery/DESS/Notes/Exemples/}
\end{itemize}

\end{document}
