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


Mardi 25 novembre 2014 - 16:00 → 18:20 (durée 2H20)  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 Python sous forme de commentaires en début de programme.

Le barème est approximativement de 5 points par exercice.

NB. Si vous n'avez pas réussi à suivre les instructions ci-dessus et que je dois intervenir pour faire ce travail à votre place (20% des étudiants de la promotion 2013-2014), je retirerai 4 points à votre note.

Écrivez une fonction Python IdxMin(L) qui renvoie la liste des indices de la valeur minimale de la liste, la fonction renvoit donc la liste (0,3,4) pour la liste L = (2,5,7,2,2,3,5). La fonction devra se contenter d'une seule passe sur la liste L.

def IdxMin(L):
   ivm = 0
   LMIN = [ivm]
   i = 1
   while i < len(L):
      if L[i] < L[ivm]:
         ivm = i
         LMIN = [ivm]
      elif L[i] == L[ivm]:
         LMIN = LMIN + [i]
      i = i + 1
   return LMIN
Écrivez une fonction Python MaxMax(L) qui renvoie les deux valeurs les plus grandes d'une liste L en une seule passe sur la liste L (on supposera que la liste contient au moins deux éléments).
def MaxMax(L):
   if L[0] > L[1]:
      maxor = L[0]
      maxargent = L[1]
   else:
      maxor = L[0]
      maxargent = L[1]
   i = 2
   while i < len(L):
      if L[i] >= maxor:
         maxargent = maxor
         maxor = L[i]
      elif L[i] > maxargent:
         maxargent = L[i]
      i = i + 1
   return maxor,maxargent	    

Ecrivez une fonction TriBulles(L) qui effectue le tri in situ (sur place, on ne crée par d'autre liste) de la liste L à l'aide de l'algorithme du tri à bulles étudié en cours.

def TriBulles(L):
   fin = len(L)
   transposition = True
   while (fin > 1) and (transposition):
      i = 0
      transposition = False
      while (i < fin - 1):
         if (L[i] > L[i + 1]):
            aux = L[i]
            L[i] = L[i + 1]
            L[i + 1] = aux
            transposition = True
         i = i + 1
      fin = fin - 1
   return L # facultatif

Écrivez une fonction EstSS(u,v) qui renvoie vrai si u est une sous-séquence de v et faux sinon (u et v sont des chaînes de caractères). NB. Cette question ne demande aucune connaissance de l'algorithme des plus longues sous-séquences communes, seule la définition d'une sous-séquence est utile.

def EstSS(u,v):
    i = 0
    j = 0
    while (i < len(u)) and (j < len(v)):
        if (u[i] == v[j]):
            i = i + 1
        j = j + 1
    return (i >= len(u))

Écrivez une fonction python AMP(P,Q,b) qui réalise l'addition multiprécision de deux entiers p et q représentés par deux listes P et Q contenant respectivement les chiffres de p et de q exprimés en base b. Par exemple, si b = 10, p = 35 et q = 2038, on aurait P = (5,3) et Q = (8,3,0,2) et la liste renvoyée par la fonction serait la liste (3,7,0,2).

def AMP(P,Q,b):
    if len(P) > len(Q):     # on permute P et Q si #P > #Q
        aux = P
        P = Q
        Q = aux
    R = [0] * len(Q)
    retenue = 0
    i = 0 
    while i < len(Q):
        R[i] = Q[i] + retenue
        retenue = 0
        if i < len(P):
            R[i] = R[i] + P[i]
        if (R[i] >= b - 1):
            retenue = 1
            R[i] = R[i] - b
        i = i + 1
    if retenue > 0:
        R = R + [retenue]
    return R