close

Se connecter

Se connecter avec OpenID

5LXOTOL

IntégréTéléchargement
Interrogation d’informatique no 8. Corrigé.
Exercice A
1) SELECT taupin FROM Candidats
JOIN Ecoles
ON Candidats.concours = Ecoles.nom
WHERE dep = 75
2) SELECT classe, AVERAGE(age) AS moy
FROM ( Candidats
JOIN Ecoles
ON Candidats.taupin = Etudiants.taupin
WHERE concours = "Centrale"
GROUP BY classe
ORDER BY moy
3) SELECT MAX(nombre) FROM
( SELECT concours , COUNT(candidats) AS nombre
FROM ( Candidats
JOIN Etudiants
ON Candidats.taupin = Etudiants.taupin
WHERE age = 21 )
GROUP BY concours )
Exercice B
1 Pd
Mi :
d i=1
!
2Mi ) = 0 , donc le mouvement de G est uniforme.
1) Les coordonnées du barycentre G sont dé…nies par G =
d2 G
1 Pd
k(M(i+1) mod d + M(i
=
2
dt
d i=1
2) def dessin(M) :
Donc
1) mod d
L = M + [M[0]]
X = [P[0] for P in L] ; Y = [P[1] for P in L]
# P représente les sommets
plot(X,Y,"o")
3) def suivant(M,V,r,h) :
d = len(M) ; N = [] , W = []
for i in range(d) :
A = r*(M[(i+1)%d]+M[(i-1)%d]-2*M[i])
# A représente l’accélaration
N.append( M[i] + h*V[i] )
W.append( W[i] + h*A )
return N,W
def calcul(M0,V0,r,n,T) :
M = M0 ; V = V0 ; h = T/n
for i in range(n) :
# Il est plus clair d’introduire des variables locales explicites
M,V = suivant(M,V,r,h)
return M
4) def suivant(M,N,r,h) :
P = []
# M et N représentent respectivement M (t
# On souhaite calculer P qui représente M (t + h)
for i in range(d) :
A = r*(N[(i+1)%d]+N[(i-1)%d]-2*N[i])
P.append( 2*N[i] - M[i] + h**2*A )
h) et M (t)
# On renvoie le couple (M (t); M (t + h)), cf schéma de récurrence d’ordre 2
return N,P
def calcul(M0,V0,r,n,T) :
M = M0 ; N = M + h*V0 ; h = T/n
for i in range(n-1) :
M,N = suivant(M,N,r,h)
return N
Exercice C
lnm
jnk
n+1
, donc toujours < n:
2
2
2
On en déduit que f (n) est bien dé…ni par récurrence forte (cf principe de Fermat sur les suites décroissantes d’entiers).
1) a) Pour tout n
2,
et
sont des entiers compris entre 1 et
On montre par récurrence forte sur n la propriété P(n) : f (n)
La propriété est vraie pour n = 1, car f (2) = 2 + 2f (1) = 4
f (n + 1):
f (1):
Supposons la propriété vraie jusqu’au rang n 1: On a donc f (1) f (2) ::: f (n):
n+1
n+1
Alors f (n + 1) = (n + 1) + f
+f
:
2
2
lnm
lnm
n+1
n+1
Comme
n, alors par hypothèse de récurrence f
f
:
2
2
2
2
jnk
n+1
f
. Donc a fortiori f (n) f (n + 1).
De même f
2
2
n
n
n
b) Pour n = 2p , on a f (n) = n + 2f
= n + 2 + 4f
= ::: = np + 2p f (1) = n log n + n, donc f (n)
2
2
4
c) Dans le cas général, avec p = blog nc, on a : 2p n 2p+1 , donc f (2p ) f (n) f (2p+1 ):
n
Or, f (2p ) (2p ) log(2p ) (2p ) log(n)
log(n):
2
Et f (2p+1 ) (2p+1 ) log(2p+1 ) (2p+1 ) log(n) 2n log(n):
1
f (n)
est compris entre deux fonctions convergeant respectivement vers et 2: D’où le résultat.
Donc
n log n
2
2) Comme précédemment, f est bien dé…nie (par récurrence forte) et est croissante.
n
n
n
n n n
n
- Pour n = 2p , On a f (2p ) = n + f
=n+ +f
= ::: = n + + + + ::: + p + f (1):
2
2
4
2
4
8
2
1
1
1 1 1
! 2, alors f (n) 2n:
Comme 1 + + + + ::: + p = 2 1
2 4 8
2
2p+1
n log n:
- On en déduit comme au 1) c) que f (n) est de l’ordre de grandeur de n.
Exercice D
On considère l’algorithme suivant :
- On trie en temps O(n log n) les segments [a; b] selon la valeur de a
- Une fois obtenue la liste triée des segments [ai ; bi ], avec 0
0
i
n
i < n, on teste en temps O(n) si bi < ai+1 pour tout
2: D’où le code Python :
def f(S,T) :
# On dé…nit la relation d’ordre : S = [a; b]
return S[0] <= T[0]
def disjoints(L)
M = sorted(L,f) ; n = len(M)
for i in range(n-1) :
if M[i][1] >= M[i+1][0] :
return True
return False
[a0 ; b0 ] = T ssi a
a0 :
Auteur
Document
Catégorie
Uncategorized
Affichages
0
Taille du fichier
65 KB
Étiquettes
1/--Pages
signaler