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


Mardi 04 décembre 2012 - 2 heures. (durée 2H00)  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 8 points par exercice (oui, il y a 4 points supplémentaires...)

Complétez le programme pgcd.c qui calcule le pgcd (a,b) de deux entiers a et b saisis sur la ligne de commande. On rappelle que si on note respectivement q et r le quotient et le reste de la division euclidienne de a par b, en supposant que ab, i.e. a = b.q + r, alors
   (a,b) = (b,r) si r > 0
      et
   (a,b) = b sinon.

Complétez le programme triinsertion.c qui réalise le tri par insertion des valeurs placées sur la ligne de commande en écrivant la fonction tri.  Indiquez la (les) complexité(s) de votre fonction.

On se propose d'écrire un programme motif qui recherche un motif dans une chaîne de caractères et qui affiche sur la sortie standard, la/les position(s) de ce motif dans la chaîne (l'indexation commence à 0). Par exemple,

    >> ./motif abc ababbbdsabcaabbabcdbcb
    >> 8 15
ou -1 si le motif n'est pas présent dans la chaîne. Complétez le programme motif.c qui récupère les deux chaînes de caractères saisies sur la ligne de commande (rangées dans le tableau argv de la fonction main) et réalise ce travail.