L2 - I31. Examen de travaux pratiques d'algorithmique.


Vendredi 08 novembre 2013 - 13:00 → 15:30 / 16:15 → 18:45 (durée 2H30)  DOCUMENTS INTERDITS

Avant de commencer, lisez attentivement les énoncés et suivez scrupuleusement les instructions (en bleu) en respectant à la lettre les noms des fichiers proposés, majuscules/minuscules comprises (vous devriez les copier à la souris afin d'éviter de confondre la quote et l'antiquote...). Les réponses aux questions posées doivent être incorporées aux fichiers sources C sous forme de commentaires en début de programme.

  1. Au début de l'examen: créez un répertoire EXAM-I31 à la racine de votre répertoire de travail avec la commande cd ~; mkdir EXAM-I31 puis placez vous dans ce répertoire pour y écrire tous vos programmes à l'aide de la commande cd EXAM-I31
  2. A la fin de l'examen:
    1. Placez-vous à la racine de votre répertoire de travail avec la commande cd ~
    2. Créez une archive à l'aide de la commande tar zcvf `whoami`.tgz EXAM-I31
      Un fichier  monlogin.tgz doit apparaître dans votre répertoire de travail
      (où monlogin désigne bien entendu votre propre login. J'espère ne trouver aucun fichier réellement intitulé monlogin.tgz, utilisez la commande ls pour vous en assurer).
    3. Copiez le fichier monlogin.tgz dans le répertoire /home/partage/exam.I31/ en utilisant la commande cp `whoami`.tgz /home/partage/exam.I31/
Le barème est de 6 points par exercice (oui, il y a 4 points supplémentaires...)

Écrivez une fonction Python MinMax(T) qui renvoie le minimum et le maximum du tableau T en une seule passe sur la liste T. Ecrivez une fonction TriDenombrement(T) qui effectue le tri de la liste T à l'aide de l'algorithme du tri par dénombrement.

On rappelle le triangle de Pascal pour les 5 premières valeurs non-nulles:

n\p012345
01
111
2121
31331
414641
515101051

On rappelle que la ligne numéro n contient les n + 1 coefficients binomiaux C(n,p) pour p allant de 0 à n et que C(n,p) = C(n - 1,p - 1) + C(n - 1,p). Écrivez une fonction Python TrianglePascal(n) qui renvoie la liste des n + 1 coefficients binomiaux, par exemple TrianglePascal(6) renverra la liste [1,6,15,20,15,6,1].

Soient deux listes L1 et L2 supposées triées. Écrivez une fonction Python Fusion(L1,L2) qui fusionne les deux listes et renvoie une liste triée contenant les éléments des deux listes. Bien entendu, vous n'utiliserez pas de fonctions de tri. Exemple: L1 = [1,3,3,6,8] et L2 = [2,4,7,8,9,10] donneront la liste [1,2,3,3,4,6,7,8,8,9,10].

Soit P une liste fournissant les coefficients d'un polynôme dans l'ordre croissant des puissances. Ecrivez une fonction Python Horner(P,a) qui calcule la valeur de la fonction polynomiale P en a à l'aide de la méthode de Hörner.