Mini-corrigé du partiel

Exercice 1 : Jeu de la Vie.
  1. Voici les positions au temps 0 :
         
     X   
      X  
       X 
         
         
     XX  
     X   
         
         
         
      X  
     XXX 
      X  
         
         
      X  
      X  
      X  
         
    Voici les positions au temps 1 :
         
         
      X  
         
         
         
     XX  
     XX  
         
         
         
     XXX 
     X X 
     XXX 
         
         
         
     XXX 
         
         
    Voici les positions au temps 2 :
         
         
         
         
         
         
     XX  
     XX  
         
         
      X  
     X X 
    X   X
     X X 
      X  
         
      X  
      X  
      X  
         
    Voici les positions au temps 3 :
         
         
         
         
         
         
     XX  
     XX  
         
         
      X  
     XXX 
    XX XX
     XXX 
      X  
         
         
     XXX 
         
         
  2. Le choix de NUMROWS et NUMCOLS sert à avoir un tableau indexé de 0 à MAXROW+1 et de 0 à MAXCOL+1, qui représente l'univers, entouré d'une bande de cases toujours vides, afin de faciliter le calcul de l'évolution de la population sur les bords.
    Le fait que ces valeurs soient légèrement inférieures à la taille par défaut d'un terminal n'est pas un hasard, mais détermine le choix de MAXROW et MAXCOL et non pas celui de NUMROWS et NUMCOLS.
  3. Ne pas oublier qu'en l'absence de parenthésage l'ordre de priorité des opérateurs est : le test d'égalité == puis la conjonction && puis la disjonction ||.
    La formule supprimée est ((curr[r][c] == TRUE) && ((neighbors == 2) || (neighbors == 3))) || ((curr[r][c] == FALSE) && (neighbors == 3)) ce qui peut être simplifié en neighbors == 3 || (curr[r][c] && neighbors == 2)
  4. La variable m mesure le nombre de cases ayant changé de valeur, elle est retournée afin de tester sa nullité, qui permet de déterminer si la population est stable.
    • Une première technique consiste à remplacer l'univers rectangulaire de taille fixe par un univers rectangulaire de taille variable. Il faut détecter les cas où le rectangle doit être agrandi, par exemple en regardant le contenu de son bord. Éventuellement if faut diminuer sa taille. Pour ne pas avoir à recopier le rectangle en cas d'agrandissement, on peut utiliser une représentation spirale au lieu d'un tableau.
      Cette technique a pour inconvénient d'allouer un espace mémoire qui peut être très nettement supérieur aux nombre de cases occupées
    • Une seconde technique consiste à ne repérer que les cases remplies, par leurs coordonnées. Le problème est de détecter les cases voisines. Il n'y a pas tellement de façon efficace.
    • La meilleure technique utilise des rectangles de taille fixe, qui sont chaînés avec leurs quatre voisins. Seul les rectangles non vides sont alloués. Cette structure est suffisamment creuse pour permettre d'allouer un espace mémoire petit même si certaines cases occupées sont très éloignées, mais les rectangles sont suffisamment gros pour que le calcul des voisins reste efficace.
      Dans la variante la plus simple, il y a un rectangle central. Pour tout rectangle alloué, il existe un chemin vertical puis horizontal qui y mène. Le calcul de voisinage est facile.
      Dans la variante la plus creuse, le lien entre deux rectangles peut contenir une information de distance. En cas de création d'un rectangle, il faut parfois tester tout le bord de l'ensemble des rectangles pour savoir s'il a des voisins dans les quatre directions.
Exercice 2 : Calcul de racines carrées modulo n.
Éléments de preuve.
  1. Le carré d'un élément non nul est non-nul. Exactement deux éléments non nuls ont même carré car p est impair.
  2. x(p-1)/2 est une racine carrée de l'unité. Il y en a deux possibles, 1 et -1. Si x = y2 alors x(p-1)/2 = yp-1 = 1. Comme p-1 l'ordre du groupe multiplicatif Fp* il existe un x tel que x(p-1)/2 = -1. Puisque x |® x(p-1)/2 est un morphisme multiplicatif, il y a (p-1)/2 préimages de 1.
  3. x(p+1)/2 vaut ±x selon la valeur de x(p-1)/2.
    L'exponentiation se fait en temps linéaire en la taille de l'exposant : calcul de racine carrée en O(k).
  4. On calcule r2 qui vaut x(p+3)/4 = x.x(p-1)/4 ou 4x2(4x)(p-5)/4 = x.2(p-1)/2x(p-1)/4
    Deux exponentiations nous donnent un temps O(k).
  5. Au début de chaque exécution de 5, c2s-i=-1 et (r2u)2s-i=1. Donc à la fin de l'algorithme (r2u)2=1.
  6. L'étape 1 se fait en temps O(k). L'étape 2 se fait en temps O(k) car chaque essai réussit avec probabilité ½ donc le nombre moyen d'essais est 2. L'étape 3 se fait en temps O(k). L'étape 4 se fait en temps O(k). L'étape 5 s'exécute O(k) fois, chacune en temps O(k).
    Conclusion : l'algorithme s'exécute en temps O(k2).
  7. modulo p2 on calcule r2(1-wp)2u = r2u(1-2wp) =(1+vp)(1-vp)=1
  8. On calcule une racine de x modulo pl-1.
    On calcule u=x-1 mod pl, puis vp = (r2u mod pl)-1, puis 2w = v mod p, le résultat est r(1-wpl-1) mod pl.
  9. On utilise le théorème des restes chinois pour se ramener aux cas pl.
  10. On choisit un nombre x aléatoirement et on demande une racine carrée y de x2. Alors (x-y)(x+y)=0 mod n.
    Si n n'est pas premier, alors ceci donne un facteur non trivial de n avec probabilité ³½.