M I N I S T E R E D E L ' E N S E I G N E M E N T SUPERIEUR E T DE L E R E C H E R C H E S C I E N T I F I Q U E

U N I V E R S I T E D E S S C I E N C E S E T D E L A T E C H N O L O G I E D'ORAN « Mohamed BOUDIAF »

F A C U L T E DES SCIENCES - DEPARTEMNT D'INFORMATIQUE

Concours d'Accès en 1 Année Doctorat 3

er Cycle L M D en Informatique

(Options : I S I , I V A , R F I A , S I R )

Epreuve Générale
Date : 10/11/2012
Durée : 01h30

Répondre à 4 exercices.

Exercice n°l : Bases de Données Avancées

1/ (0.75pt) Dans quel cas le protocole à deux phases est i l bloquant ? Pourquoi ? Comment peut-
on le rendre non bloquant ?

21 (Olpt) Soient 4 sous transactions participant à une validation à 2 phases :

T l : coordinateur ; T 2 , T 3 , T4 : participants
Pour chacun des cas suivants, préciser les conséquences sur la transaction globale (validée ou
non) en justifiant vos réponses.
1er cas : Toutes les transactions envoient un message O K au coordinateur T l qui envoie le
message C O M M I T à tous les sites mais T2 tombe en panne m o m e n t a n é m e n t avant d'avoir reçu
ce message.
2e m ecas : foutes les transactions participantes envoient un message O K sur T l mais T l tombe en
panne après avoir envoyé le message C O M M I T au site T2 uniquement
3e m c cas : T2 tombe en panne après avoir reçu le massage C O M M I T .
4 c a s ; T2 tombe en panne après avoir envoyé un message A B O R T .
emc

3/ (2.25pts) Soit le s c h é m a conceptuel global d'une B D répartie (les clés sont en gras) :
R (A, B, C) avec 0 < B < 100, où B est de type entier.
S (D,E. F)
T (A, D, G) avec A clé étrangère de R et D clé étrangère de S.
On considère un système réparti ayant 3 serveurs (chacun ayant son propre SGBD et sa B D ) . Ces
serveurs peuvent communiquer entre eux par le réseau. Les clients se connectent à l'un des
serveurs pour poser des requêtes.
Le placement des tables est le suivant :
• La table R est fragmentée horizontalement sur les trois sites selon l'attribut B: Sitel
contient les tuples de R tels que B < 25. Site2 ceux tels que B e ] 2 5 . 70], et Site3 les
autres.
•
La table S est fragmentée verticalement en SI (D, E), p'iacé sur le site S i t e l , et S2 (D, F),
placé sur Site2.
• La fragmentation de T est dérivée de celle de R.
a) Donner les s c h é m a s de placement (fragmentation et allocation des fragments aux sites)
maintenus sur les sites. Utiliser la notation nomFragment@nomSite pour indiquer que le fragment
nomFragment est alloué au site nomSite.
b) Exprimer en algèbre relationnelle les (3) requêtes de reconstruction des tables R, S et T

1
4/ (lpt) En quoi consiste la réplication ? A quel type de granule s'applique la réplication ? A
quel type de réplication correspond un snapshot ?

Exercice n ° 2 : Génie Logiciel

Question 1
On procède au d é v e l o p p e m e n t d'un logiciel avec la méthode X P ( e X t r ê m e Programming).
Comment s'effectue la refactorisation ? (2pts)
Question 2
Expliquez la notion de « logiciel critique » utilisée en GL. (1 pts)
Question 3
Le projet A L P H A a été estimé à 67 points de fonctions. Calculez la quantité de travail, le temps
de développement T D E V , l'effectif moyen, et la productivité pour le projet alpha sachant que des
estimations en interne ont permis d'établir qu'un point de fonction correspond à 580 L O C . (2pts)

Exercice n° 3 : Fondements de l'Apprentissage Machine

1. Dans un P M C , comment interpréter le passage couche d'entrée -couche cachée et le passage

couche c a c h é e - c o u c h e de sortie ? (lpt)

2. Comment doit-être la fonction d'activation dans un PMC ? justifier (lpt)

3. Quels sont les paramètres à optimiser dans un PMC à 3 neurones en couche d'entrée, 2
neurones en couches cachée et 3 neurones en couche de sortie ? (lpt)

4. Définissez les termes suivants : a) un problème d'optimisation, c) une règle d'apprentissage,

d) minima locaux (lpt)

5. La figure ci-jointe schématise l'évolution de l'erreur d'apprentissage et de test dans un réseau

de neurones. Pourquoi l'erreur de test ne décroît pas après l'itération / ? Comment appelle t-
on ce p h é n o m è n e ? Quel critère faut-il rajouter à l'algorithme d'apprentissage pour décider
de l'arrêt à l'itération / ? (lpt)

test

apprentissage

Figure

2
 Exercice n°4 : Systèmes Répartis

La classe Net suivante permet de simplifier l'écriture d'applications client/serveur en java.

public class Net {
static public ServerSocket createServer(int server_port) { }
static public Socket acceptConnection(ServerSocket s) { }
static public Socket establishConnection(String ip, int port) { }
static public PrintStream connectionOut(Socket s){ }
static public BufferedReader connectionIn(Socket s){ }
}
Ainsi, pour créer une socket serveur, on pourra par exemple écrire :
ServerSocket sockel écoute -• Net.createServer(5000);

1- Ecrire le corps de chacune des méthodes de la classe NET

2- En utilisant les m é t h o d e s statiques de la classe NET, écrire un serveur d'écho itératif en mode
TCP. Le service d'écho doit être réalisé par une méthode statique n o m m é e echo.

Exercice n°5 Répondre à l'une des questions suivantes :

Question 1 : Sécurité des Réseaux et des Systèmes d'Information

Partie 1 : 2pts

En quoi consiste la cryptographie irréversible ?

a- L ' é m e t t e u r et le récepteur chiffrent leurs échanges

b- Obligation de chiffrement de l'échange chiffré
c- L ' é m e t t e u r chiffre ses émissions et le récepteur déchiffre ses réceptions
d- Obligation de chiffrement de signatures
e- Le récepteur déchiffre les émissions chiffrées par les émetteurs
f- Non nécessité de chiffrement ni de chiffrement mais calcul de signature.

Partie 2 : 3 pts
Par définition une politique de sécurité est un ensemble de règles fixant les actions permises et
non permises dans le domaine de sécurité. Quelles sont les étapes types d'une politique de
sécurité ?

>

3
Question 2 : Sémantique Formelle

1. Quel est le principe de la sémantique interprétative ? (Olpt)

Soit la partie du programme P suivante :
début jonc f (x) retourner x*x ;
début var w ; w := fonc(5) ;

M
Mil
2. Proposer une règle d'interprétation pour la déclaration d'une fonction suivant le schéma
suivant (Olpt):
<début fonc f(x) u. ; retourner resfonc ; Pi j\n ] e> —* ?
Où : / est une fonction qui retourne une valeur (l'évaluation de l'expression resfonc) à
l'aide de l'instruction retourner,
3. Proposer une règle d'interprétation pour l'appel d'une fonction suivant le schéma
suivant (Olpt):
< res := i\exp) ; Pi | e> —»• ?
4. En utilisant les deux règles proposées, définir la sémantique interprétative du programme P
(02pt).

Question 3 : Traitement d'images

1. La numérisation d'une image se décompose en deux éjapes. Expliquer le principe de

chacune d'elle (lpt)
2. Expliquer le fonctionnement et le rôle du filtre médian (lpt)
3. Expliquez comment, à partir d'une image en niveaux de gris, on obtient une image binaire
dans laquelle les contours (fins) sont blancs et le reste de l'image est noir (lpt)
4. Quel est le principe d'égalisation d'histogramme, donner alors l'algorithme correspondant
( 2pts)

Question 4 : Télédétection

1. La télédétection exploite deux catégories de capteurs. Citer ces catégories, sur quels
systèmes peut on les trouver. Y a l ' i l une différence entre eux. (justifier votre réponse)
2. Expliquer le principe du processus de la télédétection.
3. Quelles sont les perturbations liées à la traversée de l'atmosphère. Donner la relation qui
relie la vitesse de la lumière à la longueur d'onde.
4. Donner la définition ainsi que les caractéristiques d'un rayonnement électromagnétique.
5. Donner les aspects sur lequel repose la télédétection.

4
 Université desSciences et de la Technologie Houari Boumediene
Faculté d'Electronique et d'Informatique
usrHs Dé par t e me nt d' I nf ormat ique

Concours d'accès au Doctorat LMD Informatique, 2012/2013

Epreuve d'Analyse et complexité des algorithmes
USTHBle 26/ 11/ 2012

Exercice 1 : structure de donnéeset algorithme de tri (10 pts)

La structure de d on n ées tas ouheap est une structure d'optimisation de l'espace m ém oire et est utiliséepar exemple
pour trier un tableau d'entiers. Rappelons qu'un tas est unarbre binaire équilibrédans lequel chaque valeur associéeà
un nœud est supérieure aux valeurs asso ciées respectivement à ses fils s'ils existent. Deplus, untas est représenté à
l'aide d'un vecteur Aen supposant les hypothèses suivantes : .
les fils de l'élément A[i] setrouvent respectivement auniveau des positions 2*i et 2*i+l, s'ils existent bien
entendu.
A[i] est par conséquent une feuille si 2*i >n
1. Quelle première co n séquen cepeut-on tirer d'un tas ?
2. Pour trier un vecteur, cedernier est d'abord transform éenun tas dans le but d'extraire le plus grand élém ent.
Cette opérationest renouveléepour le reste du tableau, L'idéeprincipale pour obtenir un tas est de permuter
l'élém entse trouvant àun nœud par le fils qui a la plus grande valeur.
a. Ecrire l'algorithme de construction d'un tas àpartir d'un vecteur quelconque.
b. Calculer sa com plexité.
. c. Illustrer l'algorithme sur le tableau contenant les élém entssuivants: 11,73,29,45,6,31,52,89,93,9
3. Ecrire un algorithme pour rechercher un élém ent dans un tas. Calculer sa com plexité.
4. Ecrire un algorithme pour insérer,un élém ent dans un tas. Calculer sa com plexité. Illustrer votre algorithme en
insérant l'entier 90 dans le tas construit en 2)
Exercice 2 : N P-com piétude(10 pts)
Une proposition atomique est une variable booléenne, c'est-à-dire prenant ses valeurs dans l'ensemble
BOOL={VRAI,FAUX}. Un littéral est une proposition atomique ou la négationd'une proposition atomique. Une proposition
atomique est aussi appelée littéral positif; et la négation d'une proposition atomique littéral négatif. Uneclause est une
disjonction de littéraux.
Etant d onnéesm propositions atomiques pi, pm, une instanciation du m-uplet (p1; ...,pm) est un élém ent de
{VRAI,FAUX}m. Une instanciation (eh em) de(pI; -....Pm) satisfait une clause c (noté (eh ej f=c) si et seulement si
l'une des conditions suivantes est satisfaite :
1. il existe iC{1,... ,rn} tel que (e;=VRAI) et (p; occurre dans c)
2. il existe iC{1,... ,m} tel que (ei=FAUX) et (-] pi occurre dans c)
Une instanciation satisfait une conjonction de clauses si et seulement si elle satisfait chacune de ses clauses. Une conjonction
de clauses est satisfiable si et seulement si il existe une instanciation la satisfaisant. Une instanciation satisfaisant une
conjonction est dite solution ou modèle de la conjonction.
Le problème SATest maintenant défini comme suit :
Description : une conjonction Cde n clauses construites à l'aide de mpropositions atomiques pi,...,pm
Question : la conjonction Cest-elle satisfiable ?
Le but de l'exercice est de montrer quele Problème'SAT appartient à la classe de com plexité NP, la classe des
problèmes dedécisionnon déterm inistes polynôm iaux. Il faut pour cefaire trouver" un algorithme polynôm ial de validation
pour le problème, que vous appellerez validation_s. Il vous est d em and éde procédercomme suit :
1. Donner une structure de d o n néespermettant de représenterune instance du problème SAT. Expliquer
2. Donner l'algorithme validation_s sous forme d'une fonction booléenne dont il est important que vous expliquiez
les paramètres.
3. Calculer le nombre d'opérationsélém entairesdans le pire des cas de l'algorithme.
4. Montrer que l'algorithme est polynôm ial.

BONCOURAGE !
 Université des Sciences et de la Technologie Houari Boumediene
Faculté d'Electronique et d'Informatique
D ép ar t em ent d' I nf ormat ique

Concours d'accès au Doctorat LMD Informatique, 2012/ 2013

Epreuve : Architecture et Administration des Bases de Données
*

Exercice N° 1
Soient deux t ables JO U EU R e t EQ UI PE crées par USER1 et définis co m m e suit
JO U EU R(Co d eJ, N O M , Pr é n o m , D at e _N aissance , Co d e j Eq u i p e * )
EQU I PE(Code Eq uip e, N o m , D at e _Cré at i o n) .

• Les clés primaires sont soulignées et * signifie l'existence d'une clé étrangère.
• Nous supposons que l'équipe « EL SAOURA » possède le code 'ESR' et est composée de30 joueurs
Soit un ut ilisat eur USER 2 . Ce d e rnie r lance la req uêt e RI suivant e :
Select * Fr om U SER1 JO U EU R
1. Quelles sont les vérif icat io ns ef f ect uées par le SGBD p our rép o nd re à cet t e req uêt e ?
Supposons q u' ap rès vé rif icat io n, le SGBD envoi la réponse suivant e :
Table ou Vue JOUEUR inexistante
2. Quelles seraient les cause s g énérant ce message ?
Pour régler ce p r o b l è m e , U SER2 ve ut ret ro uver t o ut es les t ab les qu'il a cr é é e s, les t ab les sur lesquelles il a
des droit s ainsi que le co m p t e d' ut ilisat eur utilisé pour se co nne ct e r.
3. Dans quelle part ie du SGBD il peut t ro uver ces inf ormat ions ?
4. D o nner les re q uê t e s SQL Oracle ut ilisées pour les ret ro uver
Supposons m aint e nant que U SER 1 ve ut sup p rim er l'équipe « El SAO U RA ».«
5. Quelle serait la r é p o nse du SGBD ?
6. Quelles sont les solut ions possibles à ce p ro b lèm e ?
7. D o nner les re q uê t e s SQ L Oracle ut ilisées d ans chaq ue solut ion ?
8. D o nne r la re q uê t e p e rm e t t an t à USER 1 de ret ro uver t o ut e s les co nt raint es qu'il a créées.

Exercice N°02
So i e n t d e u x t r a n sa ct i o n s T l , T 2 d é f i n i e s c o m m e sui t :
Tl T2
Rl ( A ) :A - » a l R2(B) : B- »b 2
R1(B) : B- > b l R2(A) : A- » a 2
al+ bl - »al W 2 ( B) :a 2 - » B
W 1 ( A) : a l - » A W 2 ( A) : b 2 - » A
1. Si A= 2 0 et B= 10 alo rs d o nne r t o us les résu t at s co rrect s.
Soit l' o rd o nnance m e nt suivant :
R1 ( A) R1 ( B) R2 ( B) R2 ( A) W 2 ( B) W 2 ( A) W 1 ( A)
2. D o n n e r le scé n a r i o d ' e xé cu t i o n d e ce t o r d o n n a n c e m e n t e n a p p l i q u a n t l' algorit hme
d ' e st a m p i l l a g e à d e u x e st a m p i l l e s.
So i e n t les e xé cu t i o n s p a r a l l è l e s su i va n t e s : •
Tl T2 T3 T4
R1(A) : A - » a l R2 ( B) : B- »b 2 R3 (B) : B- > b3 R4(C) : C- > c4
R1(B) : B- » b l R2 ( A ) : A- > a2 W 3 ( C) :b 3 x3 - » C R4 (B) : B- »b 4
al+ bl - »al W 2 ( B) :a 2 - » B W 3 ( D ) : b 3 + 1 0 - »D W 4 ( B) : b 4 xc4 - > B
W l ( A) :a l - » A W 2 ( A) : b 2 - » A

Soit l' o rd o nnance m e nt suivant :

 R1 ( A ) R1 ( B) W 1 ( A ) R3 ( B) R2 ( B) R2 ( A ) W 2 ( B) R4 ( C) W 3 ( C) R4 ( B) W 4 ( B) W 3 ( D ) W 2 ( A )
3. A p p l i q u e r le p r o t o co l e d e ve r r o u i l l a g e à d e u x p h a se s à ce t o r d o n n a n c e m e n t .
4. Exist e- t - il u n d e a d l o ck ? Just i f i e z.
5. Si o u i , p r o p o se r u n e so l u t i o n à ce p r o b l è m e .

Exercice N° 03
Soit l'exécut ion de dix t ransact i o ns, T l , T 2 , T 1 0 rep résent ée d ans le g rap he suivant :
L'axe horizont al re p ré se nt e le t e m p s où sont rep résent és t rois é vé n e m e n t s import ant s : Checkpoint 1,
Checkpoint 2 et l' arrivée d' une p anne.
1. D o n n e r le s d i f f é r e n t s é t a t s q u ' u n e t r a n sa ct i o n q u e l co n q u e t r a v e r se et les é v é n e m e n t s
p r o vo q uant le p a ssa g e d ' u n é t a t ve r s u n a u t r e .
2. D o nne r les d if f é re nt e s act ions que le gest ionnaire de t ransact ion ef f ect ue à l'arrivée des
é vé n e m e n t s Checkp o int 1 et Checkpoint 2.
3. D o nner l'ét at d e chaq ue t ransact io n just e avant l'arrivée de la panne
4. Ap rè s la rep rise, q uelles sont les t ransact ions t e r m i né e s, annulées et refait es.

il

Tl

T2 -

T3 - -

T4 - -
Abort
T5
Abort
T6 - -

T7
Abort
T8 - -

T9 • -

T10- -

Checkpolnt 1 Checkpoint 2 à Temps

 Concours d’accès au Doctorat LMD Informatique 15/10/2014

Directives

Cher(e) candidat(e),

Prière de lire attentivement les règles suivantes dont la responsabilité du respect total
vous incombe:

Assurez-vous que votre nom et prénom sont écrits sur chaque feuille
d’examen que vous remettrez, et ce exclusivement dans l’emplacement réservé
pour cela.
NE PAS ECRIRE SUR LE VERSO DE LA ZONE (CADRAN)
RESERVE(E) POUR LE NOM. Cette partie sera découpée pour des raisons
d’anonymat.
Utiliser des feuilles d’examens séparées pour les différentes parties/exercices
de l’épreuve.
Bien écrire le nom de l’épreuve sur chaque feuille d’examen.
NE PAS UTILISER LES COULEURS ROUGE ET VERT ET EVITER
TOUTE MARQUE DISTINCTIVE SUR VOTRE FEUILLE.
AUCUNE FEUILLE DE BROUILLON NE SERA CORRIGEE !!! Ne pas
répondre non plus sur les feuilles des sujets.
Les feuilles anonymes ne seront pas corrigées.
Vous êtes tenu(e) de passer toutes les épreuves du concours, faute de quoi
vous serez exclu(e) du concours.
Si, pour une épreuve donnée, vous n’avez pas de réponse, vous êtes tenu(e) de
remettre une feuille blanche comportant votre nom et prénom et le nom de
l’épreuve, faute de quoi vous serez exclu(e) du concours.
A la fin de chaque épreuve, vous êtes tenu(e) de signer la feuille de remise des
réponses en indiquant le nombre de feuilles doubles et de feuilles volantes
(non-doubles).
Vous ne pourrez pas quitter la salle d’examen pendant le dernier quart d’heure
de l’épreuve. Vous devrez attendre la fin de l’épreuve et rester à votre place
jusqu’à ce qu’un(e) enseignant(e) passe réceptionner votre feuille de réponse.
A la fin de l’épreuve, si vous continuez à écrire alors que le responsable vous a
demandé de cesser de le faire, vous êtes seul(e) responsable de la mesure
disciplinaire qui sera prise à votre encontre.

Prière de coopérer avec nous pour gérer les épreuves de ce concours de la façon la
plus agréable, et pour vous et pour nous.
 \^_jsmi j ^J* n ^jj- L - û j j <SJ^J& ^x-^—
! Jk U n i v e r s i t é d e s S c i e n c e s et de la T e c h n o l o g i e Houari B o u m e d i e n e
£B§ Faculté d'Electronique et d'Informatique
tf*î Département d'Informatique

Concours d'accès au Doctorat LMD Informatique, 2012/2013

Epreuve de Systèmes distribués
(Option : Systèmes Informatiques)
USTHB le 26/ 11/ 2012

Exercice 1 : (9 pts=l + l.5*2+1 + 1.5+2)

AJ Répondre aux questions suivantes :
- Pourquoi sont structurés les algorithmes distribués de manière non déterministe ?
- Quel est l'handicap des horloges logiques de Lamport? Qu'apportent de nouveau les horloges vectorielles "
de Mattern?

B/ Soit la structure d ' é v é n e m e n t s §=* (E, <) définie par le diagramme de temps suivant :
1- Dater les événements de la structure en utilisant les horloges vectorielles de Mattern.
2- Donner la relation entre les couples d'événements suivants en utilisant les horloges vectorielles :
(c3,b4);(al,c3).
4- Vérifier la nature de chacune des coupures C l et C2 à l'aide du théorème connu dans ce
contexte.
5- Pour les coupures consistantes, donc l'état global correspondant est consistant, donner les
messages en transit pour chacune et pour chaque canal.

Cl ' C2
Exercice 2 : (11 pts= 2.5 + 1 + 4.5 + 1 + 2)
On considère un système distribué composé de N processus P(i), i - 1, N où i est l'identité du
processus P(i) connectés selon une topologie physique connexe. Ces processus sont organisés selon
une arborescence logique (i.e. chaque nœud ne peut communiquer dans les deux sens qu'avec son
père et ses fils, s'il y a lieu, dans l'arborescence) supposée optimale (i.e. chaque voisin dans
l'arborescence est aussi un voisin dans le réseau).
On désire implémenter un service d'exclusion mutuelle pour deux ressources différentes sur cette
structure en supposant que le processus racine de l'arborescence est le serveur de tous les autres
processus. Chaque processus désirant utiliser une ressource donnée, la demande au serveur en
envoyant sa requête, qui contient le numéro de la ressource et une estampille locale (selon les
horloges de Lamport), à travers la structure. Tous les autres messages liés au service d'exclusion
mutuelle doivent circuler à travers la structure logique établie.

a- Donner le principe de fonctionnement de l'algorithme

b- Lister les différents messages à utiliser,
c- Ecrire l'algorithme.
d- Donner la complexité moyenne en nombre de messages pour réaliser une section critique.
e- Que faut-il modifier pour inclure le serveur comme client ?

Bon courage
 Université des Sciences et de la Technologie Houari Boumediene
' Faculté d'Electronique et d'Informatique
a S T H B Département d'Informatique

Concours d'accès au Doctorat LMD Informatique, 2012/2013

(Option : Systèmes Informatiques)
Epreuve Génie Logiciel

Remarque : l'exercice II est notésur 7,5 pts

EXERCICEI (12,5 pts)

1.1- 2- Expliquer comment on peut utiliser dans un même projet logiciel un modèle hybride du
cycle de vie. (1,5 pts)

1.2 S
pécificationopérationnelle(3 pts)
- On considère qu'une séq uenceest une suite de caractères alphanumériques.
Donner la spécificationopérationnelle de la fonction qui vérifie que le miroir d'une séq
uen
ce
donnéeSi est un sous mot d'une autre séq
uenced o nnéeS2.

1.3 Modélisationlogicielle (8 pts)

Une société souhaite réaliserun système d'information de suivi de commande ainsi que de fret de
marchandises de tous genres
Chaque commande ém isepar un client est transmise à une sociétéde transport. Pour le fret, chaque société
detransport assure le bon acheminement de la commande en utilisant tous les types de transports dont elle
dispose (par exemple : camion, bateau. :.) ainsi qu'enmobilisant le personnel conducteur ad éq u at.
Les clients peuvent passer une ou plusieurs commandes à une société de transport. Une commande est
définiepar unn u m érode commande, sonprix, sa villede départ et d'arrivée. Chaque n um érode commande
est attribuépar lasociétéde transport. DeuXso ciétésdetransport différentespeuvent donc attribuer unmême
n um érodecommande.
Une commande est c om po
séed'au moins une marchandise. Pour chaque marchandise connue, on note le
transport qui lui est associé.
Chaque sociétéde transport dispose desonpropreensemble de personnel conducteur.
•
1) Etablir undiagramme declasses UMLCOMPLETcorrespondant
2) Faire le diagrammeUMLdecomposants correspondant
3) Donnez le m étamodèle associéà votre diagramme de classes et de composants
 Université des Sciences et de ia Technologie Houari Boumediene
Faculté d'Electronique et d'Informatique
U ST H B
Département d'Informatique
(Option : Systèmes Informatiques)
Partie 2 : GP . USTHBle Z6/II/2OI2- A
nnée2012/2013

Exercice 2 :

Tout projet est b asé sur un équilibre parfait entre les trois paramètres de base définis par
«Qualité, Coût et délai » ; comme décritpar le graphe suivant:

Qualité
100%

Coût 100°/A Délai

y* ^W0%

1. proposer et justifier les représentations graphiques relatives au 03 cas de figure que peut atteindre
un projet, à savoir la situation optimal, pessimiste et vraisemblable. P réciserà chaque fois
l'étatet l'étatréel du projet.
 •

Université des Sciences et de la Technologie Houari Boumediene

ï^^ZS; Faculté d'Electronique et d'Informatique
u s 7 H 3 Département d'Informatique

(Option : Systèmes Informatiques)

Partie 2 : GP USTHBle 26/II/2012-Année2012/2013

2. Pour tout projet de développem ent, il existe toujours un écart entre un état prévisionnel et un état
réel. Voici plusieurs situations d'évolutionde projet, analyser et préciser clairement l'état de chaque
situation. {Optimiste, Pessimiste, Vraisemblable).
Il est à savoir que : L'état réel du projet est représentéen trait GRAS et l'état prévisionnel du projet
en trait normal.

3/%
 Université des Sciences et de la Technologie Houari Boumediene
Faculté d'Electronique et d'Informatique
Département d'Informatique

Concours d'accès au Doctorat LMD Informatique, 2012/2013

Epreuve : Modélisation et Evaluation

des Performances des Systèmes

(Commune aux deux options)

USTHB le 26/11/2012

Une entreprise de production met sur le marché un nouvel article à grande consommation. Les
statistiques indiquent que le niveau des ventes de la semaine dépend uniquement des ventes lors de
la dernière semaine écoulée. Ces statistiques fournissent également les indications suivantes :

• Si dans une semaine donnée le niveau des ventes est élevé, alors il y a 50% de chance qu'il
reste élevé la semaine suivante et 40% de chance d'être moyen.
• Si le niveau des ventes est moyen lors de la dernière semaine, alors il y a toujours 50% de
chance que le niveau des ventes soit élevé là semaine d'après, mais seulement 20% de
chances de rester moyen.
• Si dans une semaine donnée le niveau des ventes est bas, i l y a 80 % de chances qu'il reste
bas la semaine d'après et seulement 10% de chances d'être moyennement vendu.
»

1. Quel est le modèle adapté à ce problème ? Justifier.

2. Calculer la probabilité que le produit se vende bien la 3 ième semaine si i l a été mal vendu la
première semaine. Même question si i l a été bien vendu la première semaine.
3. L'entreprise est elle « stable » ? Expliquer.
:

4. Quelle est la proportion de temps où le niveau de vente du produit est élevé ?

5. Si on considère que les profits moyens enregistrés lors d'une semaine de niveau de vente
élevé, moyen et bas sont respectivement de 50, 20 et 0 unités de monnaie, déterminer les
gains moyens de l'entreprise ?

4/4
 Universit é des Sciences et de la Technologie Houari Boumediene
Faculté d'Electronique et d'Informatique
Département d'Informatique

Concours d'accès au Doctorat LM D Inf ormat ique, 2012/ 2013

Epreuve de Réseaux & Prot ocoles

(Option : Systèmes Informatiques) USTHB le 26/ 11/ 2012

Sélect ionner la ou les bonnes réponses

*
1. Un message de 30 octets est transmis de la couche application d'un syst ème A vers la
couche application d'un syst ème B. Chacune des couches de la hiérarchie OSI ajoute 5
octets d'information de contrôle. Quelle est la taille du message reçu par la couche 7 du
syst ème B ?
A. 55 octets C. 60 octets
B. 30 octets D. 80 octets

2. Que se passe-t-il après une collision sur un réseau Et hernet , lorsque le signal de bourrage a
été envoyé ?
A. Le routeur libère la voie et avise la source qu'elle peut émettre de nouveau.
B. Toutes les stations cessent d'envoyer des trames pendant une période aléatoire.
C. Un signal de message de veille est généré pour retenir le message jusqu'à ce que la voie
soit libre.
3. Si un ordinat eur est déplacé du réseau 192.168.25.0 vers le réseau 192.168.223.0, quels
énoncés parmi les suivants sont vrais au sujet de la configuration manuelle de la carte
réseau de cet ordinat eur ?

A. Inutile de changer la configuration de la carte réseau car son adresse M AC est immuable
B. Il faudra modifier l'adresse IP de la passerelle car elle est forcément différente
C. Il faudra modifier l'adresse M AC de la passerelle car il 'faut pouvoir s'adresser à la
passerelle en couche 2
D. Il faudra penser à modifier la table ARP pour éviter tout conflit d'adresse

4. Parmi les crit ères suivant s, lesquels sont susceptibles de ralentir une navigation sur
Internet ?
A. Le serveur web.saturé
B. La surcharge due aux en- têtes de protocoles
C. Une connexion anonyme

5. Quelle est la t echnique permet t ant de contrôler à t out instant la quantité de données en
transit dont la récept ion n'a pas été confirmée, et d'assurer la fiabilité de TCP ?
A. Le fenêtrage C. La reprise sur incident
B. La prévention de collision D. Le broadcast

6. Quelles sont les postes qui sont sur le même réseau 192.168.196.195/ 26 ?
A. 192.168.197.10/ 26 C. 172.16.0.2/ 26
B. 192.168.196.246/ 26 D. 192.168.10.150/ 26

7. Quelle couche de protocole permet à de multiples ent it és de partager le média de

transmission ?
A. Physique C. LLC
B. M AC D. Réseau
 8. Qu'est ce qui caract érise les algorithmes de routage à état de lien ?
A. les routeurs maintiennent une carte complète du réseau
B. les routeurs communiquent la liste de toutes les destinations connues
C. les métriques ne sont pas limitées à la distance
D. les calculs de route sur chaque routeur peuvent être longs

II. Exercice:

Soit la topologie suivante :

Nous disposons de l'adresse 192.168.10.0/ 24 pour le réseau ci- dessus. Le réseau est constitué des
segments suivants :
'• • Le réseau LAN1 a besoin d'adresses IP en nombre suffisant pour prendre en charge 60 hôtes..
• Le réseau LAN2 a besoin d'adresses IP en nombre suffisant pour prendre en charge 30 hôtes.
• Le réseau LAN3 a besoin d'adresses IP en nombre suffisant pour prendre en charge 15 hôtes.

1. Remplissez le tableau suivant :.

Adresse Réseau M asque de sous- Première adresse Dernière adresse Adresse de

réseau décimal utilisable utilisable diffusion
• LAN1

LAN2
LAN3
LAN R1-R2
LAN R1-R3
LAN R2-R3

2. On considère que les routeurs (RI , R2 et R3) ont été configurés avec le protocole de routage RIP.
a. Déterminer les tables de routage des routeurs RI et R2.
b. On suppose que la liaison entre RI et R2 tombe en panne. Déterminer les tables de routage
des routeurs RI , R2.
3. M aintenant on décide de reconfigurer les routeurs avec comme protocole de routage OSPF. Le
coût (associé au débit) de la liaison est représenté sur la topologie.
a. Donner la base de données topologique du réseau.
b. Quelles sont les tables de routage des routeurs RI et R2 si la métrique 'débit' est utilisé.
Remarque : Le coût de la liaison entre les routeurs et les réseaux LAN est de 15.

•
 Université des Sciences et de la Technologie Houari Boumediene
SîSS Faculté d'Electronique et d'Informatique
0 s THB Département d'Informatique
Concours d'accès au Doctorat LMD Informatique, 2012/2013
Epreuve Système d'Exploitation (Durée 1h)
Exercice 1 :
Les périphériques de stockage d'information constituent la partie visible d'un système d'exploitation à travers le
concept de fichier. Pour toute opératio n d'entrée/sortie disque, on doit désigner l'unité disque et le fichier concernés par
l'entrée/sortie.
1- Quel est l'effet d'un double clic sur un nom de fichier exécutable ?
2- Comment le système d'exploitation identifie l'emplacement exact de l'information sur disque et crée et e x é c u te le
processus correspondant ?
Chaque disque est c o m p o s é de N pistes numérotées de 0 à N - l .
3- Proposer une structure de d o n n é e s qui permet de gérer les requêtes d'E/S.
4- Ecrire l'algorithme de l'ascenseur avec regard.
En pratique les entrées/sorties peuvent être des ordres de lecture ou d'écriture .
5- Comment peut-on satisfaire ces requêtes de manièr e efficace et sans conflit entre les processus ?
Par ailleurs, le disque est un espace de stockage des fichiers organisé en répertoire. On suppose qu'on utilise une
stratégie d'allocation d'espace contigu sur disque.
6- Comment peut-on organiser (stocker) un répertoire et ses fichiers sur disque afin de minimiser le déplacement la
tête de lecture ?

Exercice 2:
On s'intéresse à la gestion des fichiers pour un disque dur de taille 64 G O de blocs ( l b l o c - 256K) avec une
m é t h o d e d'allocation chainée a m é l i o r é e .
1/ Soit deux fichiers F l et F2 ayant les blocs physiques suivants :
F l : 5, 100,40, 1,80, 3 0 , 9 0 , 60, 15
F 2 : 2 0 , 50, 10
Représenter les structures de d o n n é e s dans les deux cas de m é t h o d e s d'allocation : chainée simple et chainée amélioré e
21 Dresser un tableau comparatif regroupant les avantages et inconvénients de chacune des deux m é t h o d e s chainées.
3/ Sachant la politique d^allocation est chainée améliorée et la politique de la gestion de l'espace libre est Bitmap
(vecteur Bits). Ecrire les primitives systèmes suivantes :
a. Supprimer_bloc (F, REP, i ) permettant de supprimer le bloc n u m é r o i du fichier F du répertoire REP.
b. Supprimer_phy(F,REP) permettant la suppression physique du fichier F du répertoire REP.
c. Supprimer_log(F,REP) permettant la suppression logique du fichier F du répertoire REP.

Exercice 3:
Nous considérons un pont de circulation à une seule voie sur lequel, i l n'est pas possible d'autoriser le passage £•
deux véhicules circulant dans des direction différentes.

Direction 1

Direction 2
' xPortel Porte2
<
Nous représentons les véhicules qui doivent empreinter ce pont par les processus suivants:
Processus Direction 1 -Processus Direction2

AccèsPont.Portel() AccèsPont.Porte2( )
. <circuler sur le pont> <circuler sur le pont>
SortiePont.porte2 SortiePont.portel()

1/ Nous supposons que le pont peut comporter un nombre infini de véhicules qui le traversent dans un m ê m e sens à
un moment d o n n é .
Ecrire les procédur e A c c è s P o n t et SortiePont() en utilisant des s é m a p h o r e s pour la synchronisation.
2/ Nous supposons maintenant, que le pont ne peut comporter qu'un nombre N de véhicules à la fois.
Donner, dans ce cas, les p r o c é d u r e AccèsPont() et SortiePont() en utilisant les s é m a p h o r e s .
3/ Examiner, dans les deux cas précédents, les risques de privation.
Bonne Chance

.4M-
 -=_ 'uoll€c[IzrutJep
*
eJ 'rnodlfnefi ep erluec np-5poqt9u n1 r, u,4-fr-p6l rns ês"q lso nou rnerorluoonp
êcuâJoJuI.p otusluecâIu âT'Z'3lc 3l e-?rlsnlll âurtuocsanbtluepr luos âcu€uâpeddu,p suorlcuoJ seJ
'(
H )) t{8lH }â ( htr) tilnlpew '<<I > ,llo'I : sanbtprnSurlsJnel?^sroJl âJoprsu
oc uo ,n epuurrluoc
ap 1e'zr 1e Ir aê4ue,p sâlqerJ?^sep âunæqc Jnod.l
n?âlq?J a1 red eêuuop1sasel3e"lsep
esEqBl ltlop llol} JneJoJluoc un.p epl?.Je snssecoldnp âJneuâlule;n1e;adue1 u1.re1n39r âJrs?puO e
'(
0 I / I = D erpuard)snssaco:dac rnod sê3LrêroJJlp
xnu suorlenbese;-uJqetg( 1
-Zj= ,(t)'{n
! + ( t ) ! x = ( 1 +t ) ! x
: âluenrns
uollerurxo:ddu.1
1uarla:uo 'selqeuensâcâpuorrnlo^e.lrsrnr.urs
r'3t-{ Jnod
oJ- zJ= Zx le oJ- rJ: Ix
lo
tr (t)2, - (r)tx= (r)zf
l
m (r )n+ (t) 'x + ( t)Ix 7 -= U),f
J
: sâlue^rnsr31?,psuorrenbesa1red lucep 5e eua1s,,{s ao .( t 8la) enbr.rlcelg e1.red
Srlrsodsrp
alLllno.j(n) lnâluqc ap glrluenbel JâIJe^lupsleJua ealorruoJ
lsâ JnoJun.p .J âJnâu?1ur e;ryeradurele1
z aJrJJex[
relnrlex
uolllu3H-,{a1,{e30p âru?rogr{iâl tussrlrln ue wv
le serdord srnelel sec ep lue^res es ug (7
êcr4eruâ1âcep serdordsrnâle^sel relncye3(1
[ r o o l
t t
lr 0 }l=v
L O I I J
elue^rnsâcrJleruel lros I âJrJJOxg
sanbrwoutp sawa1sîssap apuouwo) i a,lne"rdg
anblluruolnv âpucruruoJ : uoqdg
alr^J ''ut l*rolro(I : EaNNVTUEII^trud
NEsgJJV,c sunocNoJ
ttDzt0vg7d.I
alwlttJ ol ap ra satngrnro.tprÇ1sap
?flnng
sapJaunog - oto7nog paruor!.tr4larts.radlan
..*
ecueuâUedd?(p
uortcuoJ : 2.31.{
( 3 o )n ' z r' t x o ot 0çt aZ 0L oç
'rânblldxa (x = Ix rsnog rneloruocnp uorlce.leresâllonô(t
L J"\IZ =
fi, (J.) rz
ç8 (J) zx
08 (Jo)'x
n g z I 0 I
: lu"^rns neâlqsl e1relgldruoc srnd 1ue11ns9r
uâ tnb senog sâpuullrruoo sa1 lueruenblun lle4snllr ue olcnoq eupr{s np enbrqderE uorlelmurs
ep se1c,{c(7) e4enb rllqs}g 'Jogg= (0)zr }eJoog=(0)Ir sâl"r}rul suo4rpuor sel }u"srl4n ua
'l
N H H
.I
H I{I
-I -l
'\I H
H W -l Zy Iy
se18qrsepâseg : I n€alqul
 SCIENTIFIOAE

UniversitéM'hamed Bougara- Boumerdès

Faculté desHydrocarbareset de la Chimie

CONCOURSD'ACCÈS EN PREMIEREANNEE : Doctorat,3è" Cvcle

Option : CommandeAutomatique

Le28ll0l20l3

Epreuve : InformatiqueIndustrielle

ExerciceI :

A) Calcut Machine :
-
- Donnerl'équivalenthexadécimal(sur 8 bits) desnombresdécimauxsuivants:100'
109,165et-L29
- Donner l'équivalent décimaldesnombreshexadésimaux(sur 8 bits) suivants: 7E'
Dn,92 et CD45
B) On veut construirela mémoired'un Microprocesseurqui a un bus dtadressede32
bits et un bus de donnéesde 16 bits avecdescircuits intégrésde 64 ko chacun.
1) Quelleestle nombre de circuits integrésnécessairepour monter cettemémoire?
2\ QuelleestI'adressede départ et cellede fin de cettemémoire ?
3) Quelleest I'adressede fin du premier bloc de 32ko ?
C) Soit un Microprocesseurqui peut adresserune mémoirede 64 Mo. Quelleestau
minimum la taille de sonbus d'adresse?

Exercice2 :

L) Donnerla définition d'un Microprocesseur.

MVI D, OAH;
MOV A, M;
2) Quel estsonrôle dansun systèmeautomatique? MQV E, A;
3) Soit le programmedu pp Intel8085 suivant: BP1:SUBE;
DCRD;
- Donnerle sensde chaqueinstruction. JNZ BP1;
- Quellela tachede ce programme? SUI OEH;
STAXB;
Exercice3 :

On désireimplémenterun régulateurPID sur calculateurnumériqueselonla

configurationOecommandeillustréeà la Fig. 1. La loi de commandeque génèrele
contrôleurPID estdonnéePar :
u(t) = Koe(t)a x, !Ïe?)dt + xo# (1)

Avec e(t) - t,p - lG)

où u(r) est la variable de commande, e(l) I'erreur de réglagery(t)lavariable de sortie

amené à
mesuréeetyrn la consigne.En vue d'implémenter cette loi de commande, on est
la transformer en une forme discrète adéquate'
puis
1. Trouver la forme discrète de l'équation (1) en utilisant la transformée en Z,
en déduire l'équation aux différences à implémenter sur calculateur.
Dresser I'organigramme de commande'
{2.
Si I'on admetune résolutionde 12 bits pour le convertisseurDAC, écrirele code
çS.
'\
C (programmeen langageC) de I'algorithmePID'

ADC +
+
Processus

DAC

Fig. I

Bon Courage
 ESI 2012-2013 Concours d'accès au doctor at LMD

Epreuve de Compilation-Théor ie des langages

Durée 2 H
Tout document in t er d it

Instructions au candidat (à lire avant le début de l'épreuve)

• Les candidats doivent vérifier que le sujet comprend 2 pages.

• Les candidats doivent rendre les copies même vierges.
• Si au cours de l'épreuve, un candidat repère ce qui lui semble ê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.

Exercice 1 (2 points)

Donner un automate d'états finis déterministe pour chacun des langages suivants sur
l'alphabet {0,1} :

a) Ensemble des chaînes de 0 et de 1 avec un nombre, pair deO et un nombre impair de 1.

a) Ensemble des chaînes de 0 et de 1 qui ne contiennent pas la sous-chaîne 011.

Exercice 2. (4 p o i n t s ^ ( ^

On définit la grammaire G=(N={S,G,D},T={*,=,i},P,S) suivante :

O Os
P: S -> G = D | D
cP <tp A
G - > * D 11 C S
D -> G G
a) Ecrire l'algorithme d'analyse syntaxique qui reconnaît les mots du langage L(G) par la
méthode de la descente récursive.
b) Analyse la chaîne suivante : * i = * * i .

c) Si l'expression précédente est correcte, donner son arbre syntaxique.

Exercice 3 (2 points)
Comment représenter le tableau à 3 dimensions T(a, b, c) en mémoire ? Donner l'adresse de
l'élément T ( i , j , k). Les indices commencent à partir de 0.

Exercice 4 (4 points)

a) Décrire les formes intermédiaires suivantes pouvant être générées pour les expressions
arithmétiques dans la phase sémantique: Quadruplets, forme arborescente.

b) Donner les formes correspondantes à l'expression ((x+y) / z) * (x-y)

Pour chaque forme, donner l'algorithme général d'interprétation.

Exercice 5 (4 points)

Montrer q u ' à toute expression régulière E, i l existe une automate d'états finis généralisé AQ
tel que L(AG) est le langage dénoté par l'expression régulière E.

Le 5/12/2012 Page 1/2

 ESI 2012-2013 Concours d'accès au doctor at LMP

Exercice 6 (4 points)

Soit L le langage suivant L = { a b" c , n > 2p+3m}

p m

a) Donnez l'automate le plus adéquat reconnaissant L (Justifiez).

b) Donnez la grammaire engendrant le langage L

Le 5/12/2012 Page 2 / 2
ESI 2 0 1 2 -2 0 1 3 Concours d'accè s au doctorat LMD

Epre uve de Ré se aux

Du ré e "
iTdut do cûm e htinte rdit

Instructlons au candidat (à lire avant le début de l'épreuve)

• Les candidatsdoivent vérifier que le sujet comprend 4 pages.
• Les candidatssont invités à porter une attention particulière à la présentation
• Les candidats doivent rendre lescopies même vierges.
• Si au cours de l'épreuve, un candidat repère ce qui lui semble ê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.
• Lesnuméros desquestions doivent être portés clairement sur les copies
• Les pagesdescopieset des feuilles intermédiaires doivent être numérotées (1,2,3,4,....)
• Calculatrice Interdite

Exercice 1 ( 8 points ) :

1. A quoi sert un VPN ? expliquer son principe de fonctionnement

2. Décrivez le principe de la NAT statique et dynamique.
3. Quelle est l'utilité du protocole ARP ?
4. Donnez lesplagesthéoriques d'adresse IPV4 pour les classesA, B et C
5. On souhaite créer 8 sousréseaux dansun réseau privé de classe B(172^16^0^ . Donnez pour chaque
sousréseau créé :
a. La plage d'adresse attribuable aux machines.
b. Le nouveau masque de réseau
6. Dites à quelle couche du modèle OSI les équipements suivants se rapportent-ils ?
a. Hub,
b. Câble en pairestorsadées,
c. Répéteur,
d. Switch,
e. Carte réseau,
f. pont.

Exercice 2 (8.5 points . 0.5 sur chaque question 1 : Cet exercice est sous forme de QCM (Question à
choix multiples). On vous demande de choisir pour chaque question la proposition correcte. SI vouschoisissez
la réponse luste (+0.5) ; Si vous choisissez une réponse fausse ( - 0.5) : SI vous ne choisissez aucune
réponse alors (01.

1. Combien de sous-réseaux peut-on avoir avec un masque égal à 255.255.255.224 ?

A. 2
B. 4
C. 8

2. Détection de collision concerne:

A. Un réseau Ethernet
B. Un réseau Token ring
C. Un réseau FDDI
D. Un réseau ATM

Le 0 5 / 1 2 / 2 0 1 2 Page 1/ 4
ESI 2 0 1 2 -2 0 1 3 Concours d'accè s au doctorat LMD

3. La méthode d'accès d'un réseau Ethernet est :

(TU CSMA/ CD
a. CSMA/CA
C. Jeton
D. Jeton avecpriorité
4. La méthode d'accès d'un réseau WIFI est:
E. CSMA/ CD
F. CSMA/CA
G. Jeton
H. Jeton avecpriorité
5. Sachant que la rapidité de modulation d'une liaison est 1200 bauds . Quelle est le type de la modulation à
utiliser pour avoir un débit de 4300 bits/s :
A. Modulation en fréquence ( 2 fréquences)
A. Modulation en amplitude ( 4 amplitudes )
B. Modulation en phase ( 8 phases )
C. Modulation mixte amplitude/phase ( 4 amplitudes/ 4 phases )
6. Dansla technologie ADSL :
A. Le débit sortant est plusgrand que le débit entrant
B. Le débit sortant est plus petit que le débit entrant
C. Le débit sortant est égale au débit entrant
D. Le débit sortant est le double du débit entrant
E. Le débit entrant est le double du débit sortant
7. Laquelle destechnologies WAN suivantesutilisent la commutation de paquets ?
A. Ethernet
B. Le Frame Relay
C. Leslignes Tl/ El
D. Le RTC
E. Le service de commutation de données haut débit
8. Laquelle des caractéristiques suivante n'est pasune caractéristique de UDP ?
A. Lafiabilitéfournie par la couche application
B. Aucune livraison garantie des datagrammes
C. L'utilisation des techniquesde fenêtres glissantes
D. N'assure pas l'ordre des datagrammes
(E^) Il est non orienté connexion
9. Le numéro de port TCP/UDP permet :
A. D'indiquer le début d'un échange.
B. De réorganiser les segments dans l'ordre adéquat
C D'identifier le nombre de paquets de données pouvant être envoyés sansaccusé de réception
D. D'identifier la fin d'un échange
E. D'identifier une application sur une machine.
10. La taille en octet d'une adresse IPv6 est de
A. 8 octets
B. 16 octets
128 octets
32 octets
11. Combien de catégories d'adresses IP existe-t-il dansIPv4 ?
A. 2
B. 3
C. 4
D. 5
12. 802.11b est :
A. Une norme de réseau sans fil de type WIFI
B. Un réseau permettant un débit théorique de 11 Mbit/ s
C. Une norme de réseau sans fil de type WIMAX

Le 0 5 / 1 2 / 2 0 1 2 Page 2/ 4
ESI 2 0 1 2 -2 0 1 3 Concours d'accè s au doctorat LMD

13. DansIPv4, lesadressesde classe D :

(TU Permettent de faire du multicast
B. Sont inutilisées
C. Sont réservées pour une utilisation future
14. Le protocole SMTPest :
A. Un protocole de communication synchrone
B. Un protocole d'envoi et de réception de messages
C. Un protocole sécurisé
15. L'adresse 172.16.32.0 est une :
(ky/ Adresse de machine
B. Adresse sous-réseaux
C. Adresse réseaux
16. Si l'administrateur donne deux foisla même adresse IP à 2 machinesdifférentes du réseau, que se passe-t-
il?
A. Lesdeux machinesmarchent très bien.
B. La première machine à obtenir l'adresse IP du Réseau marche maispasla deuxième.
C. Aucune machine ne marche.
D. Le débit est partagé entre les2 machines
17. Un réseau de classe B est découpé en plusieurssousréseaux et on obtient un masque final valant
255.255.252.0. En combien de sous-réseaux le réseau de départ a-t-il été découpé ?
A. 32
B. 64
C. 128
D. 256

Exercice 3 ( 3.5 points ) :

Soit un réseau composé de 3 routeurs et deux machines. La configuration IP desrouteurs est donnée dans le
tableau suivant :

Hôte Iterface réseaux Adresse IP Masque

Le routeur R0 SRO 192.168.0.100y/ 255.255.255.0

SRI 19.22.0.2 255.0.0.0

Le routeur RI SRO 192.168.0.2 / " 255.255.255.0

SRI 192.168.10.1 255.255.255.0

f
Le routeur R2 SRO 192.168.0.3 255.255.255.0

SRI 192.168.1.1 255.255.255.0

Voici les tables de routage des routeurs et des machines

Routeur 0 :

Destination Passerelle Interface

19.0.0.0 * SRI
192.168.1.0 192.168.0.3 SRO
192.168.0.0 • SRO
192.168.10.0 192.168.0.2 SRO
default 19.22.0.1 SRI

Le 0 5 / 1 2 / 2 0 1 2 Page 3/ 4
ESI 2 0 1 2 -2 0 1 3 Concours d'accè s au doctorat LMD

Routeur 1 :

Destination Passerelle Interface

192.168.0.0 * SRO
192.168.10.0 • SRO
default 192.168.0.100 SRO
Routeur 2

Destination Passerelle Interface

192.168.0.0 « SRO
192.168.1.0 * SRO
default 192.168.0.100 SRO
Machine Ml

Destination Passerelle interface

192.168.1.0 • SRO
default 192.168.1.1 SRO

Machine M2

Destination Passerelle Interface

192.168.10.0 • SRO
default 192.168.10.1 SRO

Question : A partir des tables de routage suivantes, donner le schéma d'interconnexion .

Le 0 5 / 1 2 / 2 0 1 2 Page 4/ 4
 ESI 2012-2013 Concours d'accès au doctorat LMD
Epreuve de Systèmes d'exploitation

Cl. I - : :: .Tout document interdit ; ; ::

Instructions au candidat (a lire avant le début de l'épreuve)

• Les candidats doivent vérifier que le sujet comprend 3 pages.
• Les candidats doivent rendre les copies même vierges.
• Si au cours de l'épreuve, un candidat repère ce qui lui semble ê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.

Exercicel : Création de Processus Unix (6 points)

Considérons le programme suivant :
int main()
{
( fork() Il fork() ) 64 ( forkO II fork() ) ;
/ * (Forkl 11 fork2 ) <&<& (f ork3 11 fork4 ) ; Commentaire pour numéroter les f ork() * /
printf ("\ Père : %d; Fi Is : %d", getppid(), getpidO);
exit(0) ;
}
On suppose que le PID Shell est 2000, le PID du processus correspondant à ce programme est 2400 et
l'algorithme d'ordonnancement est FIFO(ou FCFS), donner les résultats correspondant à l'exécution du
programme ci-dessus.

Exercice2; Pa rationnement MBR basé sur le BIOS : (4 points)

a) Donner le nombre maximum de partitions que l'on peut utiliser en même temps sur un système Windows.
b) Quelle est la taille maximale d'une partition(puissance de 2 :2" unités) ;
c) Donner le nombre de tables de partitions d'un disque dur (la ou les tables + éventuellement la ou les tables
de sauvegarde) ;
d) Sur une machine on désire installer trois systèmes linux( Ex: Redhat, Ubuntu, Debian) et des systèmes
Windows: Donner le nombre maximum de systèmes Windows que l'on peut installer sur cette machine.

Exercice3: Exclusion Mutuelle par attente active avec instruction spéciale (2points)
On cherche à réaliser l'exclusion mutuelle pour l'accès à une ressource critique par attente active en
utilisant la fonction booléenne TMB dont la syntaxe est: TMB(Reg,M ), et dont l'algorithme est:
Début
Bloquer Vaccès à la cellule mémoire M;
Si M>Reg Alors Début
AA:= - (Reg);
Reg :=M ;
Fin;
Libérer l'accès à la cellule mémoire M;
Fin.
Avec Reg étant un registre, et M un mot mémoire.
Le 5/12/2012 Page 1/3
 ESI 2012-2013 Concours d'accès au doctorat LMD
Les numéros des processus sont toujours positifs et vont de 1 à PMAX. On désire savoir en lisant M si la
ressource critique est libre, et si elle est occupée, quel est le numéro du processus qui l'occupe.
Questions:
On désire programmer l'Exclusion Mutuelle par attente active à l'aide de TMB selon le protocole classique
d'entrée et de sortie de la section critique sachant que la fonction GetPidO permet à tout processus de récupérer
son numéro.
0 1 : Choisir la bonne solution parmi les Solutions proposées:
( Réponse juste : +1,5 point ; Réponse fausse : - 0,5point ; Absence de réponse : 0 point)
SolutionA. M init (0)
1) Demande d'entrée : Reg := - (GetPid()) ;
TantQue (Reg<0) Faire TMB(Reg,M) ; FinFaire ;
2) Section Critique <SC> ;
3) Sortie M:=0;
SolutionB. M init -(1)
1) Demande d'entrée : Reg := - (GetPidO) ;
TantQue (M<=Reg) Faire TMB(Reg,M) ; FinFaire ;
2) Section Critique : <SC> ;
3) Sortie : M := - (1);
SolutionC. M init (Pmax+1) ;
1) Demande d'entrée : Reg := GetPid() ;
TantQue (Reg>0) Faire TMB(Reg,M); FinFaire ;
2) Section Critique : <SC> ;
3) Sortie : M := Pmax+1;
Solution!). M init (Pmax)
1) Demande d'entrée : Reg := GetPidO ;
TantQue (Reg<M) Faire TMB(Reg,M); FinFaire ;
2) Section Critique : <SC> ;
3) Sortie : M := Pmax ;
SolutionE. M init (Pmax)
1) Demande d'entré e : Reg := - (6etPid()) ;
TantQue (Reg<=M) Faire TMB(Reg,M); FinFaire ;
2) Section Critique : <SC> ;
3) Sortie : M := Pmax ;
02 : Quelle est la valeur de M si la ressource critique est occupée par le processus de numéro K.
(Réponse juste : +0,5 point ; Réponse fausse ou Absence de réponse : 0 point)

Exercice4: Pont à voie unique (8 points).

Soit un pont à voie unique qui ne peut être traversé que dans un sens à la fois (sens i ;i=l ou 2 ). Tout véhicule
(processus) de poids^îpkilos et désirant traverser le pont dans le sens i devra respecter le protocole suivant:
DTi (x): demande de t r a v e r s é e en sens i;
•«traversée en sens i>;
FTï(x) : fin de t r a v e r s é e en sens i;

Le 5/12/2012 Page 2/3

 ESI 2012-2013 Concours d'accès au doctorat LMD
Le pont ne peut supporter une charge supérieure àfcmaxjjrilos (on supposera tout x <= Cmax en entrée).
On désire imposer à tous les véhicules un passage erTFÎFO strict.
* Question:
On veut programmer les procédures DTi(x) et FTi(x) en n'utilisant que les variables et sémaphores suivants ;
Var Charge: integer init 0 ; /*indique la charge courante du pont (somme des poids des véhicules engagés
sur le pont)*/ ;
FIFO :semaphore init 1 ; / * impose le passage des véhicules en f if o strict sur le pont*/
Sens : array [1..2] of sémaphore init 1 ; /* Sens[i] permet d'autoriser ou bloquer le passage en sens i */
Mutexchqrge : sémaphore init 1 ;/* EM pour l'accès à la variable critique Charge V
Scapacité : sémaphore init 0 ;/* attente du véhicule courant si risque de dépassement de capacité V
AIT: integer init 0;/*mémorise le poids x du véhicule en attente de passage sur le pont s'il y a risque de
dépassement de capacité V
Procédure DTi( x : integer) ; Procédure FTi( x : integer) ;
Begin Begin
dSFIFO) ; P(Mutexcharge) ;
(fisens[i]); Charge :=Charge-x ;
(^Mutexcharge) ; I f (AC > 0) then begin
I f (<DU>) then <DT2> ; I f ((<FT1>) then begin
If((<DT3>)then begin <FT2> ;
AC :=x ; AC :=0 ;
@Mutexcharge) ; V(Scapacite) ;
P(Scapacite) ; end ;
end ; end ;
Else begin Else if (<FT3>) then <FT4> ;
<DT4> ; V(Mutexcharge) ;
^Mutexcharge) ; End FTi ;
end ;

f
End DTi ;
Sens[i]) ;
FIFO);

Compléter la Solution Proposée en remplaçant les conditions et les instructions manquantes

( 8 réponses à fournir --> Réponse juste : +1 point ; Réponse fausse ou Absence de réponse : 0 point)
On donne:

C4=(Charge>Cmax) Ç2t(Charge + AC > Cmax) C3=(Charge + AC <= Cmax) C4=(Charge>x)

C5= (Charge=0) (C6|(Charge<Cmax) £î) (Charge+x<=Cmax) C8=(Charge+x>Cmax)
C9= ((Charge+x>Cmax) or (AC>0)) C10= ((Charge+x>Cmax) and (AC>0))

b)Instructions à choisir ••
I l : Charge :=Charge+l 12 : Charge :=Charge-1 I3): Charge :=Charge+x
t 14 : Charge :=Charge-x )
15 : AC :=AC+x 16 : AC :=AC-x ^Ef: Charge :=Charge+AC 18: Charge :=Charge-AC
19 : P(Mutexcharge) 110 :V(Mutexcharge) Ill:P(Sens[i]) I12:P(Sens[3-i])
113 : V(Sens[i]) 114 : V(Sens[3-i]) 115 : P(Scapacite) 116: V(Scapacite)
117 : P(FTFO) 118 : V(FIFO)

Le 5/12/2012 Page 3/3

Université d'Oran
Faculté des Sciences Mardi 13 Novembre 2012
Département d'Informatique
Laboratoire RIIR

Concours d'accès à la formation doctorale :

Modèles de Données Avancés et Réseaux Emergents
Matière : Bases de Données et Génie Logiciel
Durée : lh45

Partie 1 : Bases de Données (10 pts)

Soit la BD « bibliothèque » gérant des lecteurs, des livres identifiés par un numéro et
appartenant à une certaine spécialité d'ouvrages (livres de bases de données, livres sur les
réseaux, etc.) et les prêts des livres.
LIVRE(N°LIVRE, COTE, TITRE, SPECIALITE, AUTEUR)
LECTEUR(N°LECTEUR, IDENTITE-LECT, ADRESSE)
PRETfN°LIVRE, N°LECTEUR. DATE-EMPRUNT, DATE-RETOUR, DATE-RELANCE)

1. Donnez les commandes SQL permettant de créer les vues suivantes :

a) Les livres de bases de données : LIVRE-BD(n°livre, titre, auteur)
b) Les lecteurs de livres de bases de données : LECTEUR-DE-LIVRE-BD(n°lecteur,
identité-lect, adresse, n°livre, date-emprunt, date-retour)

2. Un utilisateur ayant le droit d'interroger à partir des vues a et b précédentes pose les
questions suivantes :
a) Lister l'identité des lecteurs qui ont emprunté des livres de bases de données à la
date « d »
b) Donner le nom des lecteurs ayant emprunté plus de trois livres de bases de
données de « GARDARIN ».
Exprimez ces questions telles que doit le faire l'utilisateur en SQL. Exprimez,
également, les questions telles qu'elles devraient être posées sur les relations
LECTEUR, LIVRE et PRET.

3. Supposons que la relation LECTEUR est modifiée comme suit :

LECTEUR(N°LECTEUR, IDENTITE-LECT,"y\GE, SITUAT-FAM, REGION)

Où AGE-représente l'âge du lecteur, SITUAT-FAM représente la situation de famille

(célibataire, marié, divorcé, veuf) et REGION représente la région d'où i l vient
(Centre, Ouest, Est, Sud).
On définit sur cette relation deux index secondaires : le premier étant défini sur le
champ SITUAT-FAM et le second sur le champ REGION.
En se basant sur le fichier associé à la relation LECTEUR ci-dessous :
a. Donner le contenu de ces index secondaires en utilisant la technique (valeur-clé,
liste d'identifiants d'articles).
b. Résoudre la requête suivante en exploitant ces index secondaires :
Select *
From LECTEUR
Where REGION = 'Ouest'
And SITUAT-FAM = 'Célibataire' [
And AGE > 18;
LECTEUR

Partie 2 : Génie Logiciel (10 pts)

Questions (3 pts)

1- Quels sont les différents types de maintenance de logiciel ?

2- Quel est à votre avis le type le plus évident puis expliquer le ?
3- Quelle est la différence en Rétro ingénierie et Réingénierie en G.L ?

Exercice 1 (3 pts)
Soit un système composé de deux processus A l et A2 qui se partagent une ressource R.
Modéliser ce système à l'aide d'un réseau de Pétri en expliquant les différents éléments de la
modélisation.

Exercice 2 (4 pts)

Dans un établissement scolaire, on désire gérer la réservation des salles de cours ainsi que du
matériel pédagogique (ordinateur portable ou/et Vidéo projecteur). Seuls les enseignants sont
habilités à effectuer des réservations (sous réserve de disponibilité de la salle ou du matériel).
Le planning des salles peut quant à lui être consulté par tout le monde (enseignants et
étudiants). Par contre, le récapitulatif horaire par enseignant (calculé à partir du planning des
salles) ne peut être consulté que par les enseignants. Enfin, i l existe pour chaque formation un
enseignant responsable qui seul peut éditer le récapitulatif horaire pour l'ensemble de la
formation.
Modéliser cette situation par un diagramme de cas d'utilisation UML ?