4SIQ

 

1 Rappels sur les processus: 10%

1.1.Processus.

1.2.problèmes d’exclusion mutuelle, de synchronisation, de communication

1.3.Noyau de système: fonctions de base

1.3.1.Implémentation des primitives

1.3.2.Etude d’un noyau type(UNIX:réalisation pratique type MINIX)

2 Outils de synchronisation de haut niveau:30%

2.1.Régions critiques.

2.2.Moniteurs.

2.3.Autres outils: expressions de chemins, modules de contrôle.

2.4.Langages parallèles:Concurrent Pascal, CSP , ADA , autres.

 

3 Interblocage: 20%

3.1.Définition

3.2.Prévention et évitement

3.3.Détection et guérison.

 

4 Gestion des ressources: 5%

4.1.Gestion des transferts sur mémoires secondaires:

4.2.Caractéristiques des mémoires secondaires.

4.3.Stratégies de transferts (FCFS, SSTF, SCAN, C-SCAN).

 

5 Système de gestion des fichiers:20%

5.1.Introduction:

5.1.1.Définition et notions de base

5.1.2.Fonctions d’un SGF

5.1.3.Opérations sur les fichiers:

5.1.3.1.Création/destruction

5.1.3.2.Ouverture/fermeture, 5.3.3.3.Changement de nom.

5.2.organisation logique des fichiers et techniques d’accès

5.3.organisation fonctionnelle d’un SGF:

5.3.1.SGF symbolique (gestion des noms de fichiers)

5.3.2.SGF de base (gestion des descripteurs de fichiers)

5.3.3.Contrôle d’accès (protection)

5.3.4.SGF logique (gestion des enregistrements logiques)

5.3.5.SGF physique (gestion des enregistrements physiques)

5.3.6.Déroulement d’une demande d’accès à un fichier à travers ces 5.4.Couches.

5.5.Catalogues de fichiers

5.6.Ssécurité et protection des fichiers.

5.7.Organisation physique et allocation d’espace en mémoire secondaire

5.8.tude d’un exemple : SGF du système UNIX.

 

6 Protection dans les systèmes: 5%

6.1.Relation objets/processus

6.2.Définition de la protection, position du problème.

6.3.Mécanismes matériels , mécanismes logiciels.

6.4.Etat de protection d’un système

6.5.Domaines et droits d’accès:

6.5.1.Caractérisation d’un objet

6.5.2.Notion de domaine et de droits d’accès

6.5.3.Notion de pouvoir d’un processus

6.5.4.Variation de ce pouvoir selon le domaine

6.5.5.Matrice de protection

6.5.6.Implémentation de la matrice de protection :

6.5.6.1.Représentation par table globale

6.5.6.2.Représentation par colonnes (listes d’accès)

6.5.6.3.Représentation par lignes (listes de droits et capacités)

6.5.6.4.Représentation par clés et verrous.

 

6.6.Problèmes de la protection:

6.6.1.Isolation

6.6.2.Partage des objets

6.6.3.istribution et révocation des droits

6.6.4.Protection hiérarchisée

6.6.5.Protection par méfiance mutuelle

6.6.6.Problèmes de malveillance typique:

« attaque du cheval de Troie » et solutions possibles pour l’empêcher d’aboutir .

(ex: sticky bit dans UNIX , code conformant sur INTEL).

 

6.7..Etude d’exemples typiques de systèmes de protection:

6.7.1.Protection par anneaux

6.7.2.Système Multics sur CII-HB DPS8

6.7.3.Mode protégé des microprocesseurs INTEL).

6.7.4.Protection par capacités

(ex: ordinateur Plessey 250 , INTEL iAPX 432).

7 Notions de base sur les systèmes distribués: 10%

 

7.1.Rappels sur les topologies de réseaux

7.2.Définitions et motivations

7.3.Exclusion mutuelle

7.4.Synchronisation

7.5Interblocage

7.6.Gestion des données distribuées.

Bibliographie:

Operating system concepts: Peterson et Silberschatz (Ed Addison Wesley 83).

An introduction to operating systems: H.M.Deitel (Ed Addison Wesley 83).

Operating system : Madnick et Donovan (Ed Mac Graw Hill 74).

Principes des systèmes d’exploitation : S. Krakowiak (Ed Dunod 85).

Systèmes d’exploitation des ordinateurs : Crocus (Ed Dunod 75).

Principes fondamentaux des systèmes d’exploitation : Lister (Ed Eyrolles 82).

Les systèmes d’exploitation : conception et mise en oeuvre A. Tanenbaum

(Ed Prentice Hall 90).

Le système UNIX : S.R. Bourne (Ed Addison Wesley 83).

Systèmes informatiques répartis : Cornafion (Ed Dunod 81).

Algorithmique du parallélisme- le problème de l’exclusion mutuelle : Raynal(Ed Dunod 84).

Algorithmes distribués et protocoles:Raynal(Ed Dunod 86).

Synchronisation de processus parallèles: expression et mise en oeuvre dans

les systèmes centralisés et distribués: André, Herman, Verjus (Ed Dunod 83).

 

Travaux pratiques:

1)Langage de programmation C à enseigner obligatoirement dès le début de l’année en TD.

2)Système de référence Unix pour les concepts théoriques et, si possible, utilisation pratique du système UNIX (ou compatible: XENIX ) et MINIX (sous ensemble d’Unix) dont la réalisation (stratégie et programmation en C sur IBM PC) sont disponibles (voir ouvrage de A. Tanenbaum « Les systèmes d’exploitation : conception et mise en oeuvre « )

Le nombre de travaux pratiques en langage C est fixé à 2 avec contenu et échéance indicatifs suivants:

 

Tp1 au premier semestre : écriture d’un allocateur de processeur avec implémentation

des sémaphores sur IBM PC.

 

Tp2 au deuxième semestre : réalisation d’une synchronisation de processus sur un noyau de système Unix ou compatible (Xénix ou Minix).

 

 

 

---

 

 

Chapitre 1 : Introduction aux compilateurs

1. Compilateur et translateurs.
2. Structure d’un compilateur.
3. Passes d’un compilateur .
4. Outils de développement de compilateurs.

Chapitre 2 : Analyse lexicale.

1.  Expressions régulières.
2.  Automates d’états finis
3.  Transformation d’une expression régulière en automate.
4.  LEX.

Chapitre 3 : Analyse syntaxique

1. Grammaires Context-free.
2. Dérivations et langages.
3. Arbres syntaxiques.
4. Principe des analyses descendantes et ascendantes.

Chapitre 4 : Analyse syntaxique descendante.

1. Analyse par descente récursive.
2. Analyse syntaxique LL(k)

Chapitre 5 : Analyse syntaxique ascendante.

1. Analyse par précédente d’opérateurs
2. Analyse par précédente simple
3. Analyse par précédente faible
4. Analyse syntaxique LR (k)

Chapitre 6 : Traduction dirigée par la syntaxe

1. Formes intermédiaires.
2. Définition dirigées par la syntaxe.
3. Schémas de traduction et routines sémantiques.
4. Traduction descendante
5. Traduction ascendante.

Chapitre 7 : Environnements d’exécution

1. Procédures et arbre d’activation
2. Organisation de l’espace mémoire
3. Allocation de la mémoire
4. Accès aux données non locales

Chapitre 8 : Production et optimisation de code

1. Machine cible
2. Blocs de base et graphe de flot de contrôle
3. Un générateur de code optimisé.

Références.

Polycopie compilation

U.S.T.H.B H. DRIAS

+ COMPILATILATEUS AHO. VILMAN

PRINCIPES – TECHNIQUES ET OUTILS

+ THE THEORY AND PRACTICE – TREMBLAY

OF COMPILES WRITING – SOREENSON

+ COMPILATION – NOTES DE COURS

R.J CHEVANCE

UNIVERSITE DE PARIS VI

 

Principes, techniques et outils.

auteurs : Aho, Ullman & Sethi

Edition : Intereditions

auteurs : Aho & Ullman

Edition Addison Vesley

---

 

 

 

OBJECTIF :

De nombreuses activités scientifiques commencent par un recueil de données. Ces données, en général, se présentent sous forme de tableaux à deux dimensions. Les lignes sont appelées des individus et les colonnes, en nombre fini, des variables. On considère les individus comme des points dans un espace doté d’une métrique, permettant de calculer les distances . Le tableau est représenté par un nuage de points que l’on cherche à décrire.

L’analyse des données est un ensemble de méthodes permettant de décrire et parfois d’expliquer ces tableaux. Beaucoup de ces méthodes reposent sur des fondements essentiellement géométriques ou algébriques et conduisent à des solutions obtenues en minimisant un critère.

LES MODELES QUALITATIFS D’ANALYSE DE DONNEES

1)Analyse en composants principales (ACP) : c’est une méthode descriptive permettant de traiter des tableaux de variables quantitatives et fournit une représentation visuelle des individus par projection sur des sous espaces de plus faible dimension.

2) a-Analyse factorielle des correspondances (AFC) : s’applique surtout aux tableaux de contingence. La particularité de cette méthode est d’avoir une représentation simultanée des individus et des variables.

b-AFCM : destinée à traiter un tableau de variables qualitatives observées sur des individus.

3) c-Classification : c’est un ensemble de méthodes et algorithmes permettant de découper une population en plusieurs classes en tenant compte des variables qui les caractérisent. Il y a la classification ascendante hiérarchique et la méthode des nuées dynamiques.

4)Analyse discriminante

5) Analyse de variance

BIBLIOGRAPHIE :

BENZECRI – CAILLEZ ZT PAGES – JAMBU – LEBART – FENELON – MORINEAU – SAPORTA – ANDERSON TW.

Il faut en moyenne : *1h30 de cours par semaine

*1h30 de travaux dirigés

*Et à partir du 2ème semestre prévoir un T.P

 

---

 

 

OBJECTIF :

Donner aux étudiants les notions pour d’une part concevoir et mettre en place des bases de données (BDD) et d’une part concevoir et réaliser des systèmes de gestion de base de données (SGBD)

A INTRODUCTION AUX BASES DE DONNEES :

1. Bases de données

1.1. Définition

1.2. Niveaux de description

2. Systèmes de gestion de bases de données

2.1 Définition

2.2 Fonctions

2.3 Architecture générale

B LES MODELES DE DONNEES

1. Modèle hiérarchique (IMS)

2. Modèle réseau CODASYL

2.1 Définition des données (Structure)

2.2 Manipulation des données (Navigation)

3. Modèle relationnel

3.1 Définitions

3.2 Formes normales et Algorithmes de normalisation

3.3 Langages du modèle relationnel

3.3.1 Langage algébrique (SQL)

3.3.1 Langage prédicatif (QBU ou QUEL)

4. Modèle entité/association

4.1 Définitions

4.2 Caractéristiques

4.3 Optimisation

4.4 Règles de passage vers les autres modèles

C ARCHITECTURE DES S.G.B.DE DE PREMIERE GENERATION

1. Architecture des S.G.B.D de type hiérarchiques

2. Architecture des S.G.B.D de type réseau CODASYL

D ARCHITECTURE ET FONCTIONS DES SYSTEMES RELATIONNEL

1. Architecture des SGBD relationnels

2. Création des relations de base

3. Chargement des données

4. Définition des chemins d’accès

5. Dérivation des nouvelles relations

6. Catalogue de base

7. Stockage et accès aux données

8. Notions de transactions

E MEMOIRE RELATIONNELLE

1. Un modèle de mémoire relationnelle

2. Les méthodes d’accès

Séquentiel (rappel), Séquentiel indexe (ISAM), ARBRES (VSAM),

Hachage virtuel.

3. Implémentation des chemins d’accès dans les SGBD relationnels

4. Implémentation des opérateurs de l’algèbre relationnelle

F OPTIMISATION DES REQUETES

1. Définition du problème

2. Rappels sur les propriétés des opérateurs algébriques

3. Techniques d’optimisation pour les langages algébriques

4. Technique de sélection optimale des chemins d’accès

5. Technique de décomposition des requêtes

G. NOUVELLE PERSPECTIVES DES BASES DE DONNEES

1. Les bases de données déducatives

2. Les bases de données réparties et S.G.B.D.R

3. Les bases de données objet et S.G.B.D.O

BIBLIOGRAPHIE :

ADIBA M. , DELLOBEL C.

« Le modèle relationnel »

AKOKA J.

« Les systèmes de gestion de bases de données : théorie pratique »

GADARIN G. , VOLDURIEZ P.

 » Les données relationnelles : analyse et comparaison de systèmes »

MARTIN

MIRANDA S. , BUSTA J.M.

« L’art des bases de données » T1 et T2

KORTH H.F. SILBERSCHARZ A.

« Data base system concepts »

 

 

---

Objectif du cours :

Le programme couvre deux aspects :

– Conception d’algorithmes :

On présente les techniques à mettre en oeuvre pour trouver la solution d’un problème donné

– Construction de programmes :

On présente dans cette partie les différents modes de programmation qui existent, c’est à dire on s’intéresse à la forme des programmes. Pour chaque forme, nous essayerons également de donner les preuves et les sémantiques.

Langages de programmation : PASCAL, C, LISP, PROLOG, SMALLTOCK

 

 

I. Méthodes de conception de programmes

1. Concepts préliminaires

* O-notation

* Graphes et Arbres

2. Diviser pour régner

3. Récursion

4. Programmation dynamique

5. Backtracking

* Breadth First Search

* Depht First Search

6. Heuristiques

* Best First Search

* Branch and Bound Search

* Optimal Search A*

II. Construction de programmes

1. Introduction

2. Programmation structurelle

3. Programmation fonctionnelle

4. Programmation logique

5. Programmation orienté objet

6. Méthodes et outils de spécification

7. Langage de spécification

Nombre de T.P : 5

 

---

1) Rappel de la méthodologie CISC

2) Les principes fondamentaux du modèle RISC

 

21. Méthodologie Risc

22. Jeu d’instruction réduit

23. Architecture pipeline régulière

24. Les techniques pipeline: aléas du pipeline,

réordonnancement statique, prédiction dynamique des branchements,…

3) Les architectures parallèles

 

31. Fondement du parallelisme

32. Algorithmes de vectorisation.

33. Les classes d’architectures parallèles

331. Les multiprocesseurs à mémoire partagée

332. Les machines vectorielles

333. Les machines data flow

334. Les machines systolliques

335.Programmation des machines parallèles

BIBLIOGRAPHIE

1.Computer Architecture and parallel processing

Kai . HWANG / Fayé A Briggs

Mac Graw Hill – 1984

2.Advance in computer architecture

B.J MYERS 2ème édition Wiley Interscience 1982

3.The design and analysis of instruction set processor

M.R BARBACCI and D.SIEWOREK

Mac Graw Hill Computing 1982

4.Parallel computers 2

Hockriey/Sesshope (Adson Hiley) 1988

5.Les machines massivement parallèles

C.GERMAIN/J.P. SAVANNAT ( Armand colin ) 1992

---

 

Partie A : (1) Cette partie suppose acquises les notions transformées de la place fonction de transfert, représentation d’un lien de transfert. (Cours 1ère année Electronique).

-Représentation des Systèmes

-Introduction à la commande et a l’identification (10%).

I INTRODUCTION :

-Introduction de calculateur numérique dans la commande automatique : calculateurs en temps réel

-Système linéaire

-Système linéaire invariant.

-Système non linéaire – linéarisation.

II LES DIVERS REPRESENTATIONS :

-Formulation directe

-Formulation d’état

-Formulation fréquentielle

-Formulation discrète (transformée en z, discrétisation de l’équation d’état).

III INTRODUCTION A L’IDENTIFICATION ET A LA COMMANDE DE PROCEDES

 

-La notion de modèle, identification des paramètres identification de la commande à partir du modèle, problèmes de sensibilité …

PARTIE B : – Systèmes monovariable continus 35%

I ETUDE DE SYSTEMES SIMPLES :

-Système du premier ordre

-Retard pur

-Système du second ordre (lieu de transfert, réponses aux entrées typiques , performances…)

II THEORIE DES SYSTEMES LINEAIRES.

-Stabilité

-Condition fondamentale de stabilité

-Critères de stabilité

-Performance en régime transitoire

-Performances en régime permanent

-Systèmes à déphasage minimal – systèmes à déphasage non minimal.

 

III SYSTEMES ASSERVIS LINEAIRES

-Notion du Système asservi

-Stabilité des systèmes asservis

-Critère simplifié de stabilité

-Degré de stabilité en boucle fermée d’un Système régulier

-Critère de NYQUIST

-Lieu D’EVANS

-Correction des systèmes asservis (Avance de phase, retarde de phase , P.I.D).

PARTIE C (35%.)

-Systèmes monovariable discrets

-Commande numérique

I ANALYSE DES SIGNAUX ECHANTILLONNES

– Modèle mathématiques du signal échantillonnés (signal numérique, signal impulsionnel) – la reconversion en continu – définition de la transformée en Z – propriétés – modes propres d’un signal – analyse fréquentielle du signal échantillonnés ( spectre, ceci : suppose acquises les connaissances sur la transformée de fourrier vue en 1ère année – cours d’Electronique, théorie de SHANNON ).

II TRANSMISSION D’UN SIGNAL DETERMISTE A TRAVERS UN ELIMENT LINEAIRE .

-Fonction de transfert des systèmes numériques

-Fonction de transfert des systèmes continus échantillonnés

-Association des éléments .

III STABILITE ET PRECISION

-Définition

-Critère de stabilité

-Régime permanent – régime transitoire.

IV SYNTHESE D’UN CORRECTEUR NUMERIQUE .

Extension des méthodes continues

-Synthèse directe paramétrique

-Système à temps de réponse minimum

-Système à réponse plate.

PARTIE D – Commande numérique des grands systèmes 20%

I – Résolution des équations d’état :

– Cas continu et cas discret

– Discrétisation d’une équation d’état continue.

II GOUVERNABILITE ET OBSERVABILITE

– Définition , propriétés

– Problèmes liés à la discrétisation

TRAVAUX PRATIQUES :

Nécessité d’un logiciel en vue de prévoir des T.P en simulation de la commande des systèmes –

Exemple de logiciel : PC – MATLAB.

BIBLIOGRAPHIE POUR LE COURS

 » COMMANDE NUMERIQUE DES PROCESSUS « 

-Dynamique de la commande linéaire *

J.C. GILLE , P. DECAULIN , M. PELEGRIN

Editeur : DUNOD

-Systèmes et asservissements linéaires échantillonnés *

Y.SEVELY

Editeur : DUNOD

– Commande optimale des processus

R. BOUDAREl, J. DELMAS, P. GUICHET

4 tomes – Editeur DUNOD

– Commande et régulation par calculateur numérique *

c. FOULARD – S. GENTIL – J. P. SANDRAZ.

Editeur : EYROLLES.

 

---

 

OBJECTIF DU COURS :

ce cours est constitué de deux parties : les files d’attente et la simulation.

Le but de la 1ère partie est d’initier l’étudiant à reconnaître et à utiliser les différents modèles des files d’attente.

L’objectif de la seconde partie est d’apprendre aux étudiants les concepts importants de la simulation et à simuler des problèmes pratique d’une certaine difficulté.

PARTIE A : Les files d’attente (50%)

CHAPITRE I : PROCESSUS DE POISSON (5%)

A1.1 définition

A1.2 loi de la durée d’événement (le nombre d’événement étant connu)

A1.3 loi du nombre d’événement (la durée étant connue)

CHAPITRE II : PROCESSUS DE NAISSANCE ET DE MORT (10%)

A2.1 formalisation du processus

A2.2 équation régissant l’évolution du système stationnaire

A2.3 cas particulier : processus stationnaire de poisson

A2.4 processus de naissance pur

A2.5 graphes associés aux différents processus

A2.6 processus de panne de machines

CHAPITRE III : INTRODUCTION AUX FILES D’ATTENTE (5%)

A3.1 présentation et définition

A3.2 le but de l’étude sur les files d’attente

A3.3 caractéristiques d’un phénomène d’attente

CHAPITRE IV : PHENOMENES D’ATTENTES A ENTREE POISSONNIERE ET SERVICE EXPONENTIEL (30%)

A4.1 présentation

A4.2 le modèle E/E/1 (file d’attente à un guichet)

A4.3 le modèle E/E/S (file d’attente à S guichets)

A4.4 le modèle E/E/S/L (L S) (multiserveurs à file limitée)

A4.5 étude d’un cas : fonctionnement d’un central téléphonique

A4.6 le modèle E/E/

PARTIE B : SIMULATION (50%)

 

CHAPITRE I : NOMBRES ALEATOIRES ET PSEUDO ALEATOIRE (10%)

B1.1 introduction

B1.2 génération des nombres aléatoires et des tables

B1.3 génération des nombres pseudo-aléatoire

B1.4 tests de générateurs de nombres pseudo-aléatoires

CHAPITRE II : GENERATION D’ECHANTILLON SUIVANT DIFFERENTES

LOIS DE PROBABILITES (10%)

B2.1 génération d’échantillons de variables aléatoires continues

B2.2 génération d’échantillons de variables aléatoires discrètes.

CHAPITRE III : METHODOLOGIE D’UNE SIMULATION (5%)

CHAPITRE IV : SIMULATION A EVENEMENT DISCRET (15%)

B4.1 introduction

B4.2 modélisation

B4.3 méthode des 3 phases

CHAPITRE V : SIMULATION DE MONTE CARLO (10%)

B5.1 introduction

B5.2 méthode de Monté carlo et ses conséquences

B5.3 réduction de la variance

B5.4 échantillonnage descriptif

BIBLIOGRAPHIE :

1.G.E.P. BOX AND M.E MULLER, « A NOTE ON THE GENERATION OF NORMAL DEVIATE », ANN. MATH. STAT, VOL. 28,610-11, 1958

2. R.FAURE, « PRECIS DE LA RECHERCHE OPERATIONNELLE », DUNOD 1979

3. G.S FISHMAN, « CONCEPTS AND METHODS OF DISCRET SIMULATION »

WILEY-INTERSCIENCE, 1975.

4. F.S HILLIER AND LIEBERMAN, « INTRODUCTION TO OPERATIONS RESEARCH », HOLDEN-DAY, 1967.

5. L-JONES, « SIMULATION MODELLING », OPEN UNIVERSITY, OPEN UNIVERSITY PRESS, 1975.

6. A. KAUFMANN ET R.CRUON, « LES PHENOMENES D’ATTENTES », DUNOD, PARIS, 1961.

7. M.G KENDALL, AND SMITH, « RANDOMNESS AND RANDOM SAMPHING NUMBERS », J.R.S.S, VO.101, 147-166, 1939

8. KLEINROCK, « QUEUNINF SYSTEMS », VOLUME 1 ET 2, JOHN WILEY AND SONS, 1976.

9. D.E. KNOTH, « THE ART OF COMPUTER PROGRAMMINS », VOL.2, SEMI-NUMERICAL ALGORITHM, ADDISON WESLEY, 1971.

10. M.PIDD, « COMPUTER SIMULATION IN MANAGEMENT SCIENCE », WILEY

1984.

11. ROSEAUX, « EXERCICES RESOLUS DE RECHERCHE OPERATIONNELLE »,

TOME 2, MASSON 1983

12. T.H NAYLOR, « COMPUTER SIMULATION TECHNIQUES », WILEY 1966

13. M.TARI, « MAKING DESCRIPTIVE SAMPLING SAFE AND EFFICIENT »,

M.PHIL, THESIS, LANCASTER UNIVERSITY, LANCASTER 1987.

14. K.D TOCHER,  » THE ART OF SIMULATION », EUROPEEN JOURNAL 1963.