\documentclass{article}

\textheight 23cm
%\textwidth 16.5cm \columnsep 10pt \columnseprule 0pt

%\usepackage[pdftex]{hyperref}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage{amsmath,amsfonts,amssymb}
\newcommand{\R}{{\mathbb{R}}}
\newcommand{\C}{{\mathbb{C}}}
\newcommand{\Z}{{\mathbb{Z}}}
\newcommand{\N}{{\mathbb{N}}}
\begin{document}
\noindent Universit\'e de Grenoble I \hfill 
Examen du 31 janvier 2003 \hfill Magistère info

{\em Durée 3h. 
Documents et instruments de calculs autoris\'es. Communication entre
candidats interdite (y compris par tous moyens \'electroniques).}

\vspace{0.5cm}

Une chaine d'ADN [respectivement d'ARN] peut être modélisée par une 
chaine de caractères dont les lettres sont choisies parmi A, C, G et T
[respectivement U, G, C et A], chaque lettre représente une 
des 4 bases possibles dans la chaine d'ADN ou d'ARN.
Une protéine est une chaine d'acides aminés, modélisée par une chaine 
de caractère, mais les lettres possibles sont au nombre de 20 
(il y a 20 acides aminés)
L'ADN sert à synthétiser des protéines. En simplifiant un peu, la traduction 
de l'ADN en protéine se fait en 3 étapes~: 
\begin{itemize}
\item traduction de l'ADN en ARN selon la table A $\rightarrow$ U, 
T $\rightarrow$ A, C $\rightarrow$ G et G$\rightarrow$ C, 
\item recherche d'un triplet AUG (codon start) 
\item traduction par triplets de bases de l'ARN en acides aminés du codon de 
start inclus jusqu'à ce qu'on rencontre un triplet de fin (codon stop FIXME).
La correspondance entre triplets de base ARN et acide aminé 
est une application (non injective), par exemple AUG donne la méthionine (M),
etc.
\end{itemize}
Le but de cet exercice est d'écrire quelques fonctions de base pour
des programmes de bioinformatique. On représente une chaine d'ADN ou d'ARN
ou une protéine par le type {\tt string}, une base d'une chaine d'ADN ou d'ARN
ou un acide aminé par le type {\tt char}.
\begin{enumerate}
\item \'Ecrire une fonction {\tt char traduction(char adn)} traduisant
un caractère d'ADN en ARN. De même pour traduire une chaine d'ADN en
ARN.
\item \'Ecrire une fonction \verb|bool is_adn(char c)| renvoyant
{\tt true} si {\tt c} est un caractère d'ADN (A, C, G ou T), et de même
pour l'ARN (A,C,G, U).
\item Créez un type structuré {\tt struct codon} représentant 3 bases d'ARN
avec un constructeur {\tt codon(char a,char b,char c,bool adn)} qui teste
que les 3 caractères sont bien des caractères d'ADN ou d'ARN en fonction
de la valeur de la variable {\tt adn} et traduit l'ADN en ARN si {\tt adn}
est vrai.
\item Créez une variable globale {\tt start} de type {\tt codon}
correspondant au codon de start AUG.
Créez une variable globale {\tt stop} de type {\tt vector<codon>}
contenant les 3 codons ...
\item \'Ecrire une fonction qui détermine la position d'un
codon de start (ADN traduit en AUG) dans une chaine d'ADN à partir 
d'une position donnée.
\item \'Ecrire une fonction qui détermine la position du premier codon
de stop dans une chaine d'ADN à partir d'une position donnée
(donc la position du premier triplet de bases d'ADN qui traduit en ARN
se trouve dans les codons du vecteur {\tt stop}).
\item Testez les fonctions précédentes dans un programme demandant
à l'utilisateur d'entrer une chaine d'ADN et affichant le premier
codon de start rencontré puis le codon de stop suivant.
\item Surchargez l'opérateur {\tt <} pour le type {\tt codon} afin
de permettre le tri alphabétique entre 2 codons.
\item Pour établir la correspondance entre les codons et les acides
aminés on utilise un dictionnaire représenté par le type~:\\
{\tt map<codon,char>}\\
Ajoutez au type {\tt codon} un constructeur {\tt codon(string s)} qui
construit un codon à partir des 3 premiers caractères de {\tt s}
supposés être des caractères d'ARN.
\'Ecrivez une fonction \verb|map<codon,char> init_dico()| qui renvoie
un dictionnaire dans lequel on a établi la correspondance FIXME
\item En utilisant les fonctions précédentes écrire une fonction
de traduction d'une chaine d'ADN renvoyant dans un vecteur les protéines
qu'on peut synthétiser à partir de cette chaine (on crée une protéine par
couple codon start/codon stop consécutifs dans la chaine d'ADN donc
un vecteur de protéines pour une chaine d'ADN)
\item Utilisez les fonctions précédentes pour écrire un programme
qui sauvegarde dans un fichier nommé {\tt "proteine"} 
la liste des protéines qu'on peut synthétiser à partir du code ADN 
lu dans un fichier {\tt "adn"}
\item L'ADN se présente sous forme
d'une double-hélice composé de 2 brins dits complémentaires~: à la lettre
A sur une chaine correspond la lettre T sur le 2ème brin, à la lettre C
correspond la lettre G, et réciproquement. Les 2 brins sont lus
en sens inverse l'un de l'autre. \'Ecrire une fonction renvoyant
la liste des protéines synthétisable à partir d'une chaine d'ADN
ou de sa chaine complémentaire.
\item Créez une fonction renvoyant un {\tt map< char,vector<codon> >}
à partir d'un dictionnaire de type {\tt map<codon,char>} permettant
de connaitre les codons correspondant à un acide aminé donné.
\end{enumerate}
Bonus: 
\begin{itemize}
\item Créez un fichie en-tête contenant les déclarations de vos
fonctions avec des commentaires.
\item Des biochimistes ont réussi à ajouter deux bases artificielles
S et Y au code naturel de l'ADN. Créez une copie de votre programme
pour en tenir compte de la manière qui vous parait le plus adaptable
pour un usage ultérieur, rajoutez des commentaires expliquant
à un programmeur comment il devra modifier le code de votre programme
pour l'adapter à de futures recherches.
\end{itemize}

\end{document}
\section{Les 8 reines}
Il s'agit de trouver toutes les solutions du problème des 8 reines:
placer sur un échiquier 8x8 huit reines sans qu'elles soient
en position de se prendre~: chaque reine ne doit pas avoir une reine
dans la même ligne, ni dans la même colonne.

%\vspace{1cm}

\section{Championnat}
Il s'agit d'écrire un programme gérant un classement de type championnat
ou les matches se jouent à deux, donnent lieu à un score pour
chaque joueur (ou équipe). A l'issue d'un matche, chaque joueur marque un
nombre de points au classement pouvant prendre 3 valeurs selon
le résultat du matche (score supérieur, score égal, score inférieur).
Par exemple, si on gère un championnat de football, le score représente
le nombre de buts marqués, les 3 valeurs sont 3, 1 et 0. Au cours
d'une période donnée (par exemple une année), tous les joueurs sont
amenés à se rencontrer, on additionne les points obtenu par chaque
joueur pour établir un classement.
\begin{enumerate}
\item Créez un type structuré {\tt joueur} pour contenir le nom du joueur
(ou de l'équipe), le nombre de points, le total des scores réalisés pendant
les matches et le total des scores réalisés par les équipes rencontrées
pendant ces matches.
\item On utilise une variable de type  {\tt vector<joueur>} 
pour représenter un championnat.
Créez une fonction renvoyant un championnat dans un état initial (tous les
scores nuls) à partir de la liste des joueurs lue au clavier. Faites
de même pour lire la liste des joueurs lue dans un fichier {\tt "liste"}.
\item Créez une fonction remettant à zéro les nombre de points et scores
d'un championnat.
\item Créez une fonction qui affiche un championnat sur un flux
en surchargeant
\verb|ostream & operator <<| pour le type {\tt joueur} et le type
{\tt vector<joueur>}
\item Testez les fonctions précédentes en créant un championnat contenant les
équipes de Grenoble, Lyon, Saint Etienne, Valence et Voiron.
\end{enumerate}
On va maintenant gérer le tableau des rencontres. On suppose que le
championnat comporte $n$ joueurs (ou équipes) numérotées de 0 à $n-1$. 
Au cours de la $i$-ième journée de matches, on fait se rencontrer
les joueurs dont les numéros $j$ et $k$ vérifient $j+k=i \mod n$ (si $j=k$
alors le joueur $j$ est au repos).
Ceci assure qu'on fait se rencontrer chaque paire de joueur une fois
et une seule (Pourquoi?)
\begin{enumerate}
\item \'Ecrivez une fonction prenant en argument l'entier $i$ et un flux
de sortie de type {\tt ostream} qui affiche
la liste des matches de la $i$-ième journée sur le flux. Testez cette
fonction en sauvegardant la $0$-ième journée dans le fichier
{\tt "matches"};
\item \'Ecrivez une fonction qui génère toutes les journées
de championnat dans des fichiers {\tt "journee.$i$"} où $i$
désigne le numéro de la journée.
\item Les scores sont supposés être entrés manuellement, mais
pour tester le programme et faire des simulations, on va utiliser
la fonction aléatoire {\tt rand} pour déterminer le score d'un matche.
Créez une fonction comme la précédente mais qui affiche aussi les
scores obtenus de manière aléatoire.
\item \'Ecrivez une fonction qui lit une liste de matches et les scores
correspondants dans un fichier et met à jour le championnat: on utilisera
trois variables globales pour le nombre de points marqué pour un
score supérieur, un score égal ou un score inférieur.
\item Créez un {\tt bool operator >} pour le type {\tt joueur}
qui classe par ordre décroissant de nombre de points, en cas
d'égalité par ordre décroissant entre la différence entre score marqué 
et score des adversaires et en cas d'égalité par ordre décroissant
de score marqué.
\item \'Ecrire une fonction qui affiche le classement actuel du
championnat (on pourra utiliser la fonction {\tt sort}, faites attention
à ce que les matches des journées suivantes restent corrects)
\item Simulez un championnat avec les 5 équipes proposées.
\item Créez un programme de gestion
de championnat permettant d'ajouter, enlever des joueurs, remettre
à zéro les scores, générer une journée de matches, mettre à jour
le championnat (à partir d'un fichier contenant les résultats), 
afficher le classement actuel à l'écran ou dans un fichier
\end{enumerate}

\section{ADN et protéines}