Mini-corrigé du partiel
- Exercice 1 : Jeu de la Vie.
-
Voici les positions au temps 0 :
Voici les positions au temps 1 :
Voici les positions au temps 2 :
Voici les positions au temps 3 :
-
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.
-
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)
-
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.
-
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.
-
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.
-
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).
-
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).
-
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.
-
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).
-
modulo p2 on calcule
r2(1-wp)2u = r2u(1-2wp)
=(1+vp)(1-vp)=1
-
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.
-
On utilise le théorème des restes chinois pour se ramener
aux cas pl.
-
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é ³½.