Matière

Informatique

Nombre de pages

nombre d’heures

2 h

Classes

2ième Cycle préparatoire

Examen Numéro 2

Année universitaire 2021

NB : Si un candidat est amené à repérer ce qui peut lui sembler être une erreur d’énoncé, il le signalera sur sa

copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu’il a été amené à prendre.

Problème 1- Décomposition de Choleskey (10 points)

L’objectif de ce probleme est de résoudre un systeme d’équations linéaire déterminé de la forme :

Ax = b

(1)

1 point

ou A ∈ Mn(C) est une matrice Hermitienne définie positive et b ∈ Cn un vecteur a composantes complexes

pour n ∈ N∗.

(1)

Donner les instructions Python permettant d’importer le module numpy ainsi que les fonctions de l’algèbre

linéaire.

Une matrice A ∈ Mn(C) est dite Hermitienne (ou auto adjointe) si et seulement si elle vérifie la relation décrite

par l’équation suivante :

(2)

où A

est la matrice transconjugée de A (matrice transposée de la matrice conjuguée).

Solution:

import numpy as np

from numpy import linalg

FILALI

Houcemeddine

Par exemple, la matrice A = A

⇔ aij = aji ∀i, j ∈ {1 . . . n}

 est Hermitienne.

1 + 2i

1 − i

1 − 2i

−3i

1 + i

A = A

return np.all(a == a.T.conjugate())







Solution:

def is_hermitian(a):

1 point

(2)

Écrire une fonction is_hermitian qui prend en entrée une matrice a (instance de la classe ndarray) et

qui retourne un bool (True si a est Hermitienne et False sinon).

Une matrice est dite définie positive si et seulement si toutes ses valeurs propres sont strictement positives.

1 point

(3)

Écrire une fonction is_positive_definite qui prend en entrée une matrice a (instance de la classe

ndarray) et qui retourne un bool (True si a est définie positive et False sinon).

Solution:

def is_positive_definite(a):

return np.all(linalg.eigvals(a) > 0)

Université de Monastir\IPEIM\Houcemeddine FILALI

page 1 sur 9

La décomposition de Choleskey permet de décomposer une matrice A ∈ Mn(C) hermitienne définie positive

en un produit faisant intervenir une autre matrice L ∈ Mn(C) triangulaire inférieure (cid:28) Lower triangular (cid:29) tel

que :

A = L L

(3)

Où L

suivantes :

est la matrice transconjuguée de L. Les coefficients lij de la matrice L sont décrits par les équations

Le calcul des éléments de l doit s’effectuer dans l’ordre ligne par ligne ou bien colonne par colonne en utilisant

les équations 4, 6 et 5.

2 points

(4)

Écrire une fonction choleskey qui prend en entrée une matrice a (instance de la classe ndarray) supposée

hermitienne et définie positive et qui retourne en sortie la matrice l (instance de la classe ndarray) qui

vérifie la relation décrite par l’équation 3.

(4)

(5)

(6)

aij −

lij =

j−1

(cid:88)

k=1

ljj

lik ljk

∀i, j tel que n ≥ i > j ≥ 1

Solution:

def choleskey(a):

k=1

i−1

(cid:88)

lii =

(cid:118)

(cid:117)

(cid:116)aii −

lik lik ∀i ∈ {1 . . . n}.

lij = 0 ∀i, j tel que n ≥ j > i ≥ 1

FILALI

Houcemeddine

l = np.zeros(a.shape, np.float)

h, w = a.shape

for i in range(h):

l[i,j] = (a[i,j] - l[i,:j].dot(l[j,:j].conjugate()))/l[j,j]

l[i,i] = np.sqrt(a[i,i]- l[i,:i].dot(l[i,:i].conjugate()))

for j in range(i):

return l

page 2 sur 9

(7)

(8)

(9)

Un système d’équation linaires est dit triangulaire supérieur s’il a la forme suivante :







u11x1 + u12x2 + . . . + u1nxn = b1

u22x2 + . . . + u2nxn = b2

...

unnxn = bn

. . .

Ce système peut s’écrire sous la forme matricielle suivante :



u11



u1n

est une matrice triangulaire supérieure et b ∈ Cn. La résolution d’un système d’équations de forme triangulaire

supérieure, peut s’effectuer itérativement du bas vers le haut, en remontant et en remplaçant les xi pour i allant

de n vers 1 par les solutions trouvées dans l’étape précédente.

U x = b où U =





∈ Mn(C)





unn

bi −

(cid:88)

xi =

uikxk

k=i+1

uii

∀i allant de n → 1

FILALI

Houcemeddine

x[i] = (b[i]-u[i,i+1:].dot(x[i+1:]))/u[i,i]

x = np.ndarray(b.shape)

for i in reversed(range(b.size)):

return x

l11





Solution:

def solve_upper(u,b):

Écrire une fonction solve_upper qui prend en entrée :

— Une matrice u de forme triangulaire supérieure.

— un vecteur b.

La fonction doit résoudre le système puis renvoyer le vecteur solution x en appliquant le procédé de remonté

expliquée ci-haut.

Un système triangulaire inférieur est décrit par la forme matricielle suivante :

L x = b où L =

∈ Mn(C)

(10)





ln1

lnn





2 points

(5)

1 point

une matrice triangulaire inférieure et b ∈ Cn.

(6)

Écrire une fonction python solve_lower qui prend en entrée :

— Une matrice l de forme triangulaire inférieure.

— Un vecteur b.

La fonction doit renvoyer x la solution du système l x = b en appliquant l’équation suivante :

likxk

bi −

i−1

(cid:88)

k=1

lii

xi =

∀i allant de 1 → n.

page 3 sur 9

Solution:

def solve_lower(l,b):

x = np.ndarray(b.shape)

for i in range(b.size):

x[i] = (b[i]-l[i,:i].dot(x[:i]))/l[i,i]

return x

La fonction doit renvoyer x la solution du système linéaire a x = b en appliquant démarche décrite ci-haut.

Étant donnée une matrice A ∈ Mn(C) supposée hermitienne et définie positive soit L ∈ Mn(C) la matrice

triangulaire inférieure résultante de sa décomposition de Choleskey A = LL

. Il est possible de transformer

la résolution du systeme Ax = b en une résolution de deux systemes linéaires (un système inférieur puis un

système supérieur)

1 point

(7)

1 point

(8)

Solution:

Écrire une fonction solve_choleskey qui prend en entrée :

— b un vecteur (instance de la classe ndarray)

— a une matrice (instance de la classe ndarray) supposée hermitienne définie positive.

(cid:40)

x = y

L y = b

A x = b ⇔

FILALI

Houcemeddine

O(a.size

2 )

def solve_choleskey(a,b):

l = choleskey(a)

lt = l.T.conjugate()

y = solve_lower(l,b)

return solve_upper(lt,y)

Analyser la complexité asymptotique de la fonction solve_choleskey.

Solution:

Problème 2- Base de Données Relationnelle (10 points)

Soit le schéma relationnel d’une base 'theoremes.db' contenant les deux tables suivantes :

(cid:4) Mathematicien (Id , Nom , Nationalite , Siecle )

La relation Mathematicien contient un ensemble de mathématiciens actuellement existant dans la table.

— Id : identifiant du mathématicien (entier), clé primaire.

— Nom : nom du mathématicien (chaˆıne de caractères).

— Nationalite : nationalité du mathématicien (chaˆıne de caractères).

— Siecle : siècle auquel il a vécu (entier).

(cid:4) Theoreme ( Nom , themes,# Id)

La relation Theoreme contient tous les théorèmes des différents mathématiciens.

— Nom : nom du théoreme (chaˆıne de caracteres), clé primaire.

— Theme : theme du théoreme (chaˆıne de caractères).

— Id : clé étrangère qui référence l’identifiant du mathématicien (entier).

page 4 sur 9

1 point

(1)

En utilisant le module sqlite3 donner le script PYTHON permettant de :

— Créer les deux tables dans la base 'theoremes.db' en exprimant toutes les contraintes d’intégrité déjà

mentionnées ci-dessus ;

— Ajouter le mathématicien ayant les informations suivantes : (1121 , 'Hilbert' , 'allemand' , 20).

Solution:

import sqlite3

cnx = sqlite3.connect('theoremes.db')

cur = cnx.cursor()

req1 = """

CREATE TABLE Mathematicien

(

Id INTEGER PRIMARY KEY,

Nom TEXT,

Nationalite TEXT,

Siecle INTEGER

);

"""

cur.execute(req1)

req2 = """

CREATE TABLE Theoreme

(

Nom TEXT PRIMARY KEY,

Theme TEXT,

Id INTEGER REFERENCES Mathematicien

);

"""

cur.execute(req2)

req3 = """

INSERT INTO Mathematicien VALUES(?,?,?,?);

"""

FILALI

Houcemeddine

cur.execute(req3, (1121, 'Hilbert', 'allemand', 20))

cnx.commit()

cnx.close()

Solution:

Dans la suite, on suppose que les deux tables sont remplies. Donner les requêtes SQL permettant de :

1 point

(2)

Déterminer les noms des mathématiciens français du 20eme siecle, classés par ordre alphabétique croissant.

SELECT Nom

FROM Mathematicien

WHERE Nationalite = 'français' AND Siecle = 20

ORDER BY Nom;

1 point

(3)

Déterminer le nombre de mathématiciens français qui ont vécu entre le 17eme siecle et le 19eme siecle.

Solution:

SELECT COUNT(*) AS Nbr_mathematiciens

FROM Mathematicien

WHERE Nationalite = 'français' AND Siecle BETWEEN 18 AND 19;

page 5 sur 9

1 point

(4)

Déterminer le nombre de mathématiciens par nationalité.

Solution:

SELECT Nationalite, COUNT(*) AS Nbr_mathematiciens

FROM Mathematicien

GROUP BY Nationalite;

1 point

(5)

Déterminer les noms de tous les thèmes.

Solution:

1 point

(6)

1 point

(7)

Déterminer les themes des théoremes démontrés par ’Lagrange’.

ou bien

Solution:

SELECT DISTINCT Theme

FROM Theoreme;

SELECT DISTINCT Theme

FROM Theoreme

WHERE Id IN (

SELECT Id

FROM Mathematicien

WHERE Nom LIKE 'Lagrange'

);

FILALI

Houcemeddine

SELECT DISTINCT Theme

FROM Theoreme AS T

JOIN Mathematicien AS M

ON M.Id = T.Id

WHERE M.Nom LIKE 'Lagrange';

SELECT DISTINCT Theme

FROM Theoreme AS T, Mathematicien AS M

WHERE M.Id = T.Id AND M.Nom LIKE 'Lagrange';

ou bien

Déterminer les noms des mathématiciens ayant démontré au moins un théorème.

Solution:

SELECT Nom

FROM Mathematicien

WHERE Id IN

(

SELECT Id

FROM Theoreme

);

ou bien

SELECT Nom

FROM Mathematicien AS M

page 6 sur 9

WHERE EXISTS

(

SELECT *

FROM Theoreme AS T

WHERE T.id = M.id

);

ou bien

1 point

(8)

Déterminer les noms des mathématiciens n’apparaissant pas comme auteurs de théorèmes dans la table

théorème.

SELECT M.NOM

FROM Mathematicien AS M

JOIN Theoreme AS T

ON M.Id = T.Id;

ou bien

Solution:

SELECT Nom

FROM Mathematicien

WHERE Id NOT IN

SELECT M.NOM

FROM Mathematicien AS M, Theoreme AS T

WHERE M.Id = T.Id;

FILALI

Houcemeddine

SELECT Id

FROM Theoreme

);

SELECT *

FROM Theoreme AS T

WHERE T.id = M.id

);

(

ou bien

SELECT Nom

FROM Mathematicien AS M

WHERE NOT EXISTS

1 point

(9)

Déterminer les noms des mathématiciens ayant démontré le plus grand nombre de théorèmes.

Solution:

SELECT M.Nom

FROM Mathematicien AS M

JOIN Theoreme AS T

ON T.Id = M.Id

GROUP BY M.Id

HAVING COUNT(*) = (

SELECT MAX(Nbr_Theoremes)

page 7 sur 9

FROM (

SELECT Id, COUNT(*) AS Nbr_Theoremes

FROM Theoreme AS T

GROUP BY T.Id

)

);

ou bien

1 point

(10)

Déterminer le nombre moyen de théorèmes démontrés par les mathématiciens ayant démontré au moins

un théorème.

SELECT M.Nom

FROM Mathematicien AS M

JOIN Theoreme AS T

ON T.Id = M.Id

GROUP BY M.Id

HAVING COUNT(*) = (

SELECT COUNT(*) AS Nbr_Theoremes

FROM Theoreme AS T

GROUP BY T.Id

ORDER BY Nbr_Theoremes DESC

LIMIT 1

);

FILALI

Houcemeddine

SELECT COUNT(*) AS Nbr_Theoremes

FROM Theoreme AS T

GROUP BY T.Id

);

Solution:

SELECT AVG(Nbr_Theoremes)

FROM (

page 8 sur 9

Annexe

Le tableau suivant contient quelques commandes utiles que l’étudiant peut éventuellement utiliser pour la

composition de ses réponses.

Commande Python

import numpy as np

z = np.array([[1, 1+2j, 3j],

[1-2j, 2, 1+1j],

[-3j, 1-1j,5]])

Description

Importation du module numpy.

Création d’une matrice z contenant des coefficients

complexes.

np.identity(n)

a[dep :fin :pas]

a.dot(b) ou bien a@b

np.all(a)

np.any(a)

z.T ou bien z.transpose()

z.conjugate()

FILALI

Houcemeddine

Renvoie la matrice identité d’ordre n sous forme

d’un ndarray à deux dimensions.

Donne la matrice transposée de z.

Produit une matrice formée par les conjugués des

éléments de z (terme à terme).

Donne True si tous les éléments du ndarray a

valent True, sinon renvoie False.

Renvoie True si le ndaray a contient au moins une

valeur True, sinon False.

Permet d’extraire une partie du vecteur a (ndar-

ray) formé par les éléments d’indices compris entre

dep (inclue) et fin (exclue) et séparés par la valeur

pas.

Renvoie le produit scalaire de a et b (pour a et b

naddays à une seule dimension). Sinon elle renvoie

le résultat du produit matriciel entre a et b.

Renvoie la somme de tous les éléments du ndarray

Renvoie un ndarray qui résulte de la somme des

sous vecteurs projetés sur l’axe numéro i.

Renvoie la valeur maximale du ndarray a.

Renvoie l’indice de la valeur maximale du ndarray

Renvoie les indices où les éléments du nadday a

sont plus grand que c.

Importation du module linalg contenant les fonc-

tionnalités de l’algèbre linéaire.

Renvoie un tuple formé par deux vecteurs vp et p,

tel que : vp contient les valeurs propres de a et p

contient les vecteurs propres de a.

Renvoie un vecteur à une seule dimension (ndar-

ray) contenant les valeurs propres de a.

Renvoie le déterminant de a.

a.sum()

a.sum(axis = i)

a.max()

a.argmax()

np.where(a > c)

linalg.eigvals(a)

linalg.det(a)

from numpy import linalg

linalg.eig(a)

page 9 sur 9

(cid:7)♠♥♣ Bonne chance (cid:7)♠♥♣

Examen numéro 2 en Informatique