Composition d'informatique de tronc commun n°1¶
1. Bases de données¶
Q.1.¶
Il s'agit ici d'une simple projection.
SELECT Idclient
FROM client
WHERE Pays='CH';
Q.2.¶
On utilise ici de l'utilisation simple d'une fonction d'agrégation.
SELECT Idproduit,COUNT(*)
FROM vente
GROUP BY Idproduit;
Q.3.¶
Une sélection en amont doit précéder l'application de la fonction d'agrégation. On trie ensuite les résultats obtenus pour n'en garder que les dix meilleurs.
SELECT Courriel,SUM(Prix) AS Montant
FROM client
JOIN vente
ON Idclient=Client
WHERE Annee=2023
GROUP BY Idclient
ORDER BY Montant DESC LIMIT 10;
Q.4.¶
On procède de même en ne changeant que la condition sur les résultats à conserver.
SELECT Courriel,SUM(Prix) AS Montant
FROM client
JOIN vente
ON Idclient=Client
WHERE Annee=2023
GROUP BY Idclient
ORDER BY Montant DESC LIMIT 40 OFFSET 10;
Q.5.¶
Ici c'est une sélection en aval qui doit être effectuée. Le renommage du prix total est impératif pour l'opération.
SELECT Courriel,SUM(Prix) AS Montant
FROM client
JOIN vente
ON Idclient=Client
WHERE Annee=2023
GROUP BY Idclient
HAVING Montant > 100;
Q.6.¶
Une solution simple est d'effectuer une sous-requête qui détermine les clients ayant effectué un achat en 2023.
SELECT Idclient
FROM client
WHERE Idclient NOT IN
(SELECT DISTINCT client
FROM vente
WHERE Annee=2023);
Si l'on estime que le mot-clef DISTINCT
est interdit, on peut également réaliser une jointure couplée à une sélection en aval pour ne garder que les clients n'ayant rien dépensé.
SELECT IdClient,SUM(Prix) AS Montant
FROM client
JOIN vente
ON Idclient=Client
WHERE Annee=2023
GROUP BY Idclient
HAVING Montant = 0;
Q.7.¶
On commence par réaliser une autojointure sur les adresses courriel communes. Les doublons sont les entrées pour lesquelles les identifiants diffèrent.
SELECT c1.Idclient,c2.Idclient
FROM client AS c1
JOIN client AS c2
ON c1.Courriel=c2.Courriel
WHERE c1.Idclient<c2.Idclient;
2. Conversion de données¶
Q.8.¶
Il suffit ici de calculer la somme en convertissant chaque caractère. On optimise le calcul des puissances en stockant la valeur du $128^j$.
def chaine_entier(s):
n=len(s)
som=0
puiss=1
for lettre in s:
som+=ord(lettre)*puiss
puiss*=128
return som
chaine_entier("mp")
14445
Q.9.¶
On se contente ici de réaliser une suite de divisions euclidiennes.
Donnons l'écriture de $N$ en base $b$ :
$$N=\sum\limits_{i=0}^{n-1} a_i b^i \quad {\rm avec \: } \forall i \: a_i<b$$
alors
$$a_0 = N {\rm mod\:} b
\quad {\rm avec} \quad
\frac{N-N {\rm mod\:} b}{b}=\sum\limits_{i=1}^{n-1} a_i b^i$$
ce qui ramène au cas précédent et permet de déterminer la suite des coefficients à calculer.
def entier_chaine(n):
s=''
x=n
while x>0:
s+=chr(x%128)
x=x//128
return s
entier_chaine(chaine_entier("Les MP aiment l'ITC."))
"Les MP aiment l'ITC."
Q.10.¶
Aucune difficulté dans cette question : il suffit de parcourir la liste l_b.
def code(l_b):
s=0
puiss=1
for coef in l_b:
s+=coef*puiss
puiss*=2
return s
code([0]),code([1]),code([1,0]),code([0,1]),code([0,0,1]),code([0,0,0,1]),code([0,0,0,0,1])
(0, 1, 1, 2, 4, 8, 16)
Q.11.&12¶
Les $r_k$ sont fabriqués à partir de regroupements de "paquets" de $N$ bits consécutifs de la suite $\ell_b$.
Plus précisément, on aura $r_0=\sum_{j=0}^{N-1}{b_j\,2^{(j)}},$ fabriqué à partir des bits $b_0,\ldots,b_{N-1}$,
$r_1=\sum_{j=0}^{N-1}{b_{N+j}\,2^{(j)}}$ fabriqué à partir des $N$ bits suivants $b_N,\ldots,b_{2N-1}$.
Il suffit de suivre les indications de l'énoncé : on calcule les $r_k$ à l'aide d'une boucle; chaque itération demandant le calcul du coefficient $r_k$ à l'aide d'une boucle.
def transforme(l_b,N):
n=len(l_b)
m=n//N
l_r=[]
for k in range(m):
s=0
for j in range(N):
s+=l_b[N*k+j]*2**j
l_r.append(s)
return l_r
transforme([1,1,1,1],2),transforme([1,1,1,1],3),transforme([1,1,1,1],4)
([3, 3], [7], [15])
Q.13.¶
Toutes les opérations effectuées sont de coût constant.
La boucle ligne 5 a une complexite en $\mathcal{O}(m)=\mathcal{O}\left(\frac{n}{N}\right)$, tandis que celle de la ligne 7 a une complexité en $\mathcal{O}(N)$.
La complexité globale est donc en $\mathcal{O}(n)$
Par définition de la décomposition en base 2 : $n=\mathcal{O}(\log_2(p))$.
Le programme est donc de complexité logarithmique en p.
3. Fonction de hachage cryptographique¶
Q.14.¶
Ceci pose le problème suivant : toute personne ayant accès (personnel de l'entreprise ou pirate informatique) à la base de données peut, comme il connaîtra l'identifiant et le mot de passe de chaque client, se faire passer pour lui et faire des achats "à sa place" sur le site.
Q.15.¶
La fonction $\psi$ doit être facilement calculable.
Idéalement, il faudrait que $\psi$ soit injective; mais comme son ensemble d'arrivée est fini, on ne pourra pas éviter des collisions.
Il faudra alors qu'elle soit le plus possible localement injective, c'est-à-dire que des mots de passe proches devront donner des entiers distincts.
Enfin, pour des questions de sécurité, il faudra qu'il soit difficile, connaissant une valeur de l'ensemble d'arrivée, de calculer le ou les antécédents de cet entier par la fonction $\psi$.
Q.16.¶
On suit ici les indications de l'énoncé :
- on convertit la chaîne de caractéres en entier
- on lui applique la fonction H en appliquant les définitions et en calculant la somme par une boucle.
La variable q
contient les valeurs de $f^{(j)}(z)$.
L'initialisation de q à la ligne 11 correspond à la convention sur l'identité.
x,y=lambda z:z%(2**64),lambda z:z//2**64
f=lambda z,x:((2*y(z)+3)*x//2)%(2**(128))
def H(z):
s=0
q=x(z)
for j in range(128):
s+=(q%2)*2**j
q=f(z,q)
return s
def encrypte(s):
chaine=chaine_entier(s)
return H(chaine)
encrypte("MP"),encrypte("Les MP aiment l'ITC"),encrypte("Les MP n'aiment pas l'ITC"),
(278133219136616628456523316312062432147, 245199880600320800185525570276585729844, 49945170395822905567561994812590424836)
4. Propriété d'équipartition de la dynamique issue d'une Conway-map¶
Q.17.¶
On commence par créer la liste c
. Pour cela, il suffit de lire la liste l
et d'incrémenter la case de c
correspondante.
On peut ensuite avec la seconde boucle tester pour chaque valeur de c
si la condition proposée par l'énoncé est bien vérifiée.
def equirepartie(l,N):
m=len(l)
c=[0]*2**N
for r in l:
c[r]+=1
for j in range(2**N):
test=(c[j]-m/2**N)/((m/2**N*(1-1/2**N))**0.5)
if test<-2.58 or test>2.58:
return False
return True
# Test
l_b=[1,1,2,1,2,3,1,2,3,2,2,1,1]
equirepartie(l_b,2)
True
Q.18.¶
La première boucle est exécutée quoi qu'il arrive et présente une complexité en $\mathcal{O}(m)$.
Quant à la seconde :
- dans le meilleur des cas, la condition n'est pas vérifiée et la complexité est en $\mathcal{O}(1)$.
- dans le pire des cas, la condition est toujours vérifiée et la complexité est en $\mathcal{O}\left(2^N\right)$.
Ainsi la complexité globale est au mieux en ${\mathcal{O}(m)}$ et au pire en $\mathcal{O}\left(m+2^N\right)$.
Q.19.¶
On peut commencer par montrer que si $z\geqslant 3,\quad \dfrac{cz}{2}-1\geqslant \dfrac{7}{6}z.$
Comme $c\geqslant 3$ et $z\geqslant 2$ on a : $$\dfrac{cz}{2}-1\geqslant \dfrac{3z}{2}-1 = \dfrac{9z-2}{6} > \dfrac{7z}{6}$$
De plus, si $z=2$, $\dfrac{cz}{2}$ est un entier valant $c$, qui est plus grand que $\dfrac{7z}{6}=\dfrac{7}{3}$.
Ainsi, pour tout $z\geqslant 2$, la partie entière de $\dfrac{cz}{2}$ est supérieure ou égale à $\dfrac{7z}{6}$. Ainsi par récurrence, pour tout entier naturel $n$, on aura $g^{(n)}(z)\geqslant\left(\dfrac{7}{6}\right)^n z$, qui tend vers l'infini. Par minoration, $g^{(n)}$ diverge donc.
Q.20.¶
On commence par créer la liste $\ell_b$ en appliquant la définition de l'énoncé.
On applique ensuite la fonction de transformation de la question 11 et on utilise enfin la fonction précédente.
def test(N,n,c,x):
y=x
l_b=[]
for j in range(n):
l_b.append(y%2)
y=(c*y//2)%(2**(128))
l_r=transforme(l_b,N)
return equirepartie(l_r,N)
test(3,1000,5,3)
2.216218832070947 1.8848216235369737 0.062136976600120006 -1.4291504618027602 -0.9320546490018001 0.062136976600120006 -0.10356162766686668 -1.7605476703367335
True
On remarque que test(N,n,c,x)
répond la plupart du temps True
quand $n$ est grand devant $2^N$, ce qui est cohérent avec le fait que la suite $(b_k)$ est très "imprévisible". On pourrait utiliser cette suite pour fabriquer un générateur pseudo-aléatoire...
5. Programmation dynamique au service d’une conjecture de Conway¶
Q.21.¶
On prend $E=\mathbb{N}$ et $f:n\mapsto n+1$.
Quel que soit le point de départ, on a pour tout i, $f^{(i)}(n)=n+i$, et les $f^{(i)}(n)$ sont deux à deux distincts.
Q.22.¶
Supposons la propriété $\pi$ fausse et notons $N=card(E)$. Les valeurs de $f(x)$,$f^{1}(x)$,\ldots,$f^{N+1}(x)$ sont toutes différentes, ce qui est supérieur au cardinal de l'ensemble $E$.
La propriété $\pi(x)$ est donc toujours vraie si $E$ est un ensemble fini.
Q.23.¶
$T_1(x)$ et $T_0(x)$ sont bien définies, comme minimum de parties non vides de N.
Montrons par récurrence sur $i$ que $\left(f^{(i)}(x)\right)_{i\geqslant T_0(x)}$ est $T_1-T_0$ périodique.
Initialisation :
l'identité est $1$-périodique, et l'on a $T_1(x)=1$ et $T_0(x)=0$
Héridité :
Supposons la propriété vraie au rang $i$ : $f^{(i+T_1(x)-T_0(x))}(x)=f^{(i)}(x)$
Alors :
$$
f^{(i+1+T_1(x)-T_0(x))}(x)
=f\left(f^{(i+T_1(x)-T_0(x))}(x)\right)
=f\left(f^{(i)}(x)\right)
=f^{(i+1)}(x)
$$
La suite $\left(f^{(i)}(x)\right)_{i\geqslant T_0(x)}$ est $T_1-T_0$ périodique.
Q.24.¶
Les valeurs atteintes à partir de 1 sont $\boxed{1,5,2,7,3,2,7,3,2,7,3,2... }$
Ainsi, $\boxed{T_0(1)=2, T_1(1)=5}$.
Q.25.¶
On choisit de créer et mettre à jour un dictionnaire dont les clefs seront les différentes valeurs atteintes au fur et à mesure du calcul des termes successifs de la suite $\left(f^{(n)}(x)\right)_{n\in\mathbb{N}}$, et les valeurs seront, pour chaque clef $c$, la plus petite valeur de $i$ pour laquelle $f^{(i)}(x)$ est égale à $c$.
Si $\pi(x)$ est fausse, alors on ne sortira jamais de la boucle, et le dictionnaire $d$ va grossir indéfiniment...
def redondance(f,x):
dico={}
i=0
clef=x
while clef not in dico:
dico[clef]=i
clef=f(clef)
i+=1
return (dico[clef],i)
#test de la fonction
def f0(x):
l=[0,5,7,2,5,2,3,3]
return l[x]
redondance(f0,1)==(2,5)
True
Q.26.¶
On a déjà vu que $T_1(x)-T_0(x)=3$ est la périodicité de la suite.
x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
$$T_1(x)$$ | 0 | 5 | 3 | 3 | 5 | 4 | 4 | 3 |
$$f^{(T_1(x))}(x)$$ | 0 | 2 | 2 | 3 | 2 | 2 | 3 | 7 |
Q.27.¶
On va suivre le même procédé que celui appliqué à la main pour répondre à la question précédente.
Pour cela, on boucle sur toutes les valeurs présentes dans $F$ qui seront les clefs du dictionnaire.
Pour chaque clef, on définit un dictionnaire orbite
qui contiendra l'orbite de la clef par la fonction.
Les trajectoires étant toujours les mêmes, on s'assure dans la boucle while de ne pas construire plusieurs fois les mêmes orbites.
Le test de la ligne 12 permet de distinguer 2 cas :
- si la valeur n'a pas encore été rencontrée comme point fixe, on passe tous les points de l'orbite construite pour trouver le premier point fixe;
- sinon, on se contente de rdonner le résultat déjà rencontré
def trouve_redondance(f,F):
D={}
for clef in F:
y=clef
i=0
orbite={}
while y not in D and y not in orbite:
orbite[y]=i
i+=1
y=f(y)
if y in orbite:
for z in orbite:
if orbite[z]<=orbite[y]:
D[z]=(y,i-orbite[y])
else:
D[z]=(z,i-orbite[y])
else:
for z in orbite:
D[z]=D[y]
return D
sorted(trouveRedondance(f0,[0,1,2,3,4,5,6,7]).items(), key=lambda x:x[0])
[(0, (0, 1)), (1, (2, 3)), (2, (2, 3)), (3, (3, 3)), (4, (2, 3)), (5, (2, 3)), (6, (3, 3)), (7, (7, 3))]
Q.28.¶
On commence par vérifier la première expression en calculer le produit $\Pi$ et la comparant à $b^b$.
Dans ce cas, on définit localement la fonction $f$ (puisqu'elle dépend de la valeur de $b$ qu'on ne peut passer en paramètre pour la compatibilité avec la fonction précédente) et l'on applique la définition.
On vérifie ensuite que la propriété est vraie pour toute les valeurs de $i$.
def conway(l_c,l_d,M):
b=len(l_c)
pi=1
for x in l_c:
pi=pi*x
if pi<b**b:
def f(p):
j=p%b
return l_c[j]*p//b+l_d[j]
l=[i for i in range(M)]
D=trouve_redondance(f,l)
return True
Q.29.¶
La fonction $S$ est une Conway-map avec $b=2$, $\ell_c=|1,3]$ et $\ell_d=[0,1]$ puisque $\left\lfloor\frac{3p}{2}\right\rfloor +1 =\frac{3p}{2}$ si $k$ est impair.
Utilisons alors la conjecture :
- on a bien $c_0 c_1=3<2^2=4$
- donc les points fixes existent.
On évalue alors $S(0)=0$,$S(1)=2$ et $S(2)=1$, ce qui permet de donner : $T_0(0)=T_0(1)=T_0(2)=0$ et $T_1(0)=1$,$T_1(1)=2$,$T_1(2)=2$.
soit $\boxed{D[0]=(0,1)}$, $\boxed{D[1]=(1,2)}$ et $\boxed{D[2]=(2,2)}$.
Pour tout k supérieur à 2, $\boxed{D[k]=D[2]}$ puisque la première valeur de redondance sera 2 et qu'à partir de ce rang, la suite sera 2-périodique.
On peut alors vérifier les différentes expressions le résultat d'exécution de la fonction précédente :
conway([1,3],[0,1],2)
True
et valider le résultat de la question
def S(p):
if p%2==0:
return p//2
else:
return (3*p+1)//2
trouve_redondance(S,[0,1])
{0: (0, 1), 1: (1, 2), 2: (2, 2)}