2I-TRC 2ème Année Tronc-Commun
ALGORITHMIQUE STRUCTURE DE DONNEES
CODE : ALGO2
Objectif du cours :
Le cours couvre deux parties :
-Les structures de données en mémoire centrale
-Les structures de données en mémoire secondaire ou plus précisément les structures de fichier.
Deux aspects sont généralement traités :
–On écrit des algorithmes abstraits, c’est à dire on définit des modèles sur chaque structure de donnée.
-Sur chaque modèle, on fait une implémentation ( choix d’une représentation mémoire et la traduction des opérations du modèle dans cette représentation )
-Un mode de conception d’algorithme est introduit : la récursivité. Sans ce mode de pensée on ne peut introduire certaines structures de données.
Langages de programmation : PASCAL et C .
I. STRUCTURE DE DONNEES (EN MEMOIRE CENTRALE) ( 65 % )
1 Les listes linéaires chaînées ( 3 séances )
1.1 Notion d’allocations statique et dynamique
1.2 Exemple d’introduction
1.3 Définition d’une liste linéaire chaînée
1.4 Modèle sur les listes linéaires chaînées
1.5 Exemple : Solution du problème d’introduction
1.6 Algorithmes sur les listes
1.7 Listes particulières :
1.8 Les listes en Pascal
1.9 Implémentation des listes chaînées avec la représentation contiguë
TRAVAUX DIRIGES : listes linéaires chaînées
2 Les files d’attente ( 1 séance )
2.1 Principe, domaine d’application
2.2 Modèle
2.3 Implémentation
TRAVAUX DIRIGES : files d’attente
3 Les piles ( 1 séance)
3.1 Principe, domaine d’application
3.2 Modèle
3.3 Implémentation
TRAVAUX DIRIGES : piles
4 Récursivité ( 3 séances )
4.1 Exemples d’introduction
4.2 Conception d’algorithmes récursifs
4.3 Sémantique de la récursion :
4.4 Passage d’algorithmes récursifs en algorithmes itératifs
4.5 Récursivité en Pascal
4.6 Conclusion
TRAVAUX DIRIGES : récursivité
5 Les arbres ( 4 séances )
5.1 Arbres binaires : définition, terminologie
5.2 Modèle sur les arbres binaires.
5.3 Parcours des arbres binaires
5.4 Arbre de recherche binaire (arb)
5.5 Applications des arbres binaires
5.5.1 Trouver tous les doubles d’une liste de nombres.
5.5.2 Représentation des expressions arithmétiques
5.5.3 Représentations des listes par des arbres binaires
5.5.4 Code de Huffman
5.6 Implémentation :
5.7 Les arbres m-aires
5.8 Parcours des arbres n aires :
5.9 Transformation d’arbre m-aire en arbre binaire
5.10 Implémentation :
TRAVAUX DIRIGES : arbre
6 Hachage ( 3 séances )
6.1 Introduction, définition
6.2 Fonction de hachage
Un algorithme simple de hachage
Méthode de division
Méthode dite du « middle square »
Méthode dite du « transformation radix ».
6.3 Méthode de résolution de collisions
Essai linéaire
Double hachage
Chaînage interne
Chaînage séparé
Comparaison entre les différentes méthodes.
6.4 Etude de la distribution des clés
Prévention de collisions
Réduction des collisions
Augmentation du nombre d’adresses possibles
Utilisation des buckets
6.5 Conclusion
6.6 Historique et Bibliographie
TRAVAUX DIRIGES : hachage
II. STRUCTURES DE FICHIERS ( 35 % )
7 Une introduction aux fichiers et aux structures de fichiers ( 1 séance )
7.1 Raisons de l’utilisation de l’espace secondaire
7.2 Problèmes avec le stockage externe
7.3 Différence entre Ram et Ms
7.4 Fichier (vues logique et physique )
7.5 Fichiers statique et dynamique
7.6 Méthode d’accès
7.7 Organisation du fichier
7.8 Adressage
7.9 Critère de mesure d’un méthode d’accès
7.10Dans les langages de programmation
7.11Conclusion et Objectif du cours
8 Structures simples de fichiers ( 1 séance )
8.1 Fichier vu comme un tableau
8.2 Fichier vu comme une liste linéaire chaînée
8.3 Remarques sur ces méthodes d’accès
TRAVAUX DIRIGES : structures simples
9 Les méthodes d’index ( 2 séances )
9.1 Introduction
9.2 Index à un niveau
9.3 Index à 2 niveaux
9.4 Opérations de base
9.5 Remarques
9.6 I S A M :Indexed Sequential Access Method (de IBM)
Avantages des méthodes d’index
TRAVAUX DIRIGES : index primaire
10 Indexation pour l’accès multiclés ( 1 séance )
10.1 Introduction
10.2 Organisation d’un index secondaire
10.3 Combinaison de clés secondaires
10.4 Remarque:(pourquoi passer par l’index primaire?)
TRAVAUX DIRIGES : index secondaire
11 Les méthodes d’arbres ( 2 séances )
11.1 Arbre de recherche m-aire
11.1.1 Définition
11.1.2 Modèle
11.2.3 Opérations :
11.2.4 Utilisation d’un arm comme méthode d’accès
11.2.5 Implémentation
11.2 Les arbres B
11.3.1 Une introduction aux arbres B
11.3.2 Définition
11.3.3 Illustration du mécanisme d’insertion
11.3.4 Opérations sur un arbre B
11.3.5 Amélioration des Arbres B
11.3.5.1 Arbre B*
11.3.5.2 Arbre B préfixé
11.3.5.3 Arbres B+
11.3.6 S I S : Scope Indexed Sequential (de CDC)
TRAVAUX DIRIGES: les méthodes d’arbre
12 Les méthodes de hachage ( 1 séance )
12.1 Introduction
12.2 Chaînage avec des listes séparées
12.3 Adressage ouvert
12.4 Comparaison entre les différentes méthodes
TRAVAUX DIRIGES : les méthodes de hachage
Bibliographie :
La bibliographie est abondante en matière de structures de données. Les références suivantes semblent les meilleures :
The art of computer programming ( Vol 3 : Searching and sorting ) D.E KNUTH,
Addison Weslay (1973).
Data structures and algorithms.
AHO ULLMANN
A.V AHO, J.E HOPCROFT, J.D ULLMANN
Addison Weslay ( 1985)
Files Structures using Pascal.
NANCY E. MILLER
Addison Weslay (1987)
Files Structures, a conceptual toolkit.
MICHAEL J.FOLK; BILL ZOELLICK
The Benjamin/Cummings Publishing Company, Inc. (1987)
2I-TRC 2ème Année Tronc-Commun
STRUTURE MACHINE
CODE : STRM2
1) Etude des mémoires aléatoires (15 heures)
11. Caractéristiques
12. Organisation et technologie
13. Réseaux logiques
14. Mémoires associatives
15. Mémoires cahes
2) Les périphériques (7,5 heures)
21. Définition, organisation, accès
22. Imprimane, clavier, écran, disques magnétiques et optiques
23. Codage des informations
3) Les mécanismes d’entrée/sortie (9 heures)
31. Les organes de contrôle de périphériques
311. Fonctions et organisation
312. Etude détaillée d’un contrôleur
32. Les différents modes d’entrée/sortie
321. Par test d’état
322. Par accès direct mémoire
323. Canal d’entrée/sortie
3231.. Programme canal
3232.. Architecture du canal
3233.. Canal selecteur et canal multiplexeur
33. Notions d’interface
Ce chapitre doit être illustré par l’étude d’un contrôleur d’E/S, et d’un système d’E/S au moins.
4) Les mécanismes d’interruption
41. Définition et présentation fonctionnelle des systèmes d’interruption
42. Les différents types d’interruption
43. Systèmes d’interruption non hierarchisés, et
systèmes d’interruption hierarchisés
44. Traitement des interruptions
45. Etude du système d’interruption du 68000, et du 10070
Bibliographie:
– Circuits Steve Ciarcia
– Systèmes à microprocesseur L.Clément
– Peripheral devices Fleres
– Techniques d’interfaces aux microprocesseurs
– Le 68000
– Architecture des ordinateurs
V.C. Hamacher/Z.G.Vranesic/S.G.Zaky
2I-TRC 2ème Année : Tronc Commun
INTRODUCTION AUX SYSTEMES D’EXPLOITATION
CODE SYST2
Partie 1: 40%
1.1.Rappel du codage des informations.
1.2.Les différents types d’adressage.
1.3.Présentation d’une machine :
Exemple : prendre l’architecture type de l’IBM PC.
1.4.Notions sur les systèmes d’exploitation:
Services attendus d’un système d’exploitation.
1.5.Le langage d’assemblage:
Caractéristique des langages d’assemblage:
Instructions et directives; regroupement par familles.
1.6.Présentation du langage d’assemblage de la machine étudiée.
Partie 2: 60%
2.1Les différentes phases d’un programme:
2.1.1.Processus d’assemblage
2.1.2.Processus d’édition de liens
2.1.3.Processus de chargement
2.1.4.Présentation de l’Editeur De Liens et du Chargeur de la machine.
2.1.5.Système de gestion de fichiers et utilitaires associés:
2.1.6.Notion de fichier et utilisation du système de gestion de fichiers de la machine
2.2.Utilitaires de traitement de fichiers (création,tri,fusion,…).
Bibliographie:
Brochures techniques de la machine présentée.
Principes des systèmes d’exploitation des ordinateurs
Auteur:S. KRAKOWIAK Ed: DUNOD.
Remarque:
Le langage assembleur de la machine doit être présenté de façon concise et synthétique.
La partie réservée aux fichiers doit permettre à l’étudiant de mettre en pratique la notion de fichier sur une machine.
Travaux pratiques:
Le nombre de travaux pratiques est fixé à 4 avec l’échéance indicative suivante:
Ttp1 au premier trimestre.
Tp2 et tp3 au deuxième trimestre.
Tp4 au troisième trimestre.
2I-TRC 2ème Année Tronc-Commun
SYTSTEMES D’INFORMATION
CODE : SINF2
Objectifs du cours:
Ce cours s’articule autour de 3 parties essentielles:
La partie A présente les outils d’analyse fondamentaux,
La partie B dont le but est de donner les concepts de bases de systèmes indispensables pour la conception de systèmes.
La partie C sert à aller plus loin dans l’étude de systèmes particuliers à savoir les systèmes d’information .
Ce cours constitue d’une part une solide introduction aux cours de 3ième et 4ième années « systèmes d’information » et d’autre part une aide à l’orientation des étudiants dans le choix de l’option .
Outre les TD, l’assimilation des connaissances doit absolument se traduire à travers des travaux pratiques et un mini-projet avec réalisation.
A) LES OUTILS D’ANALYSE
Introduction
1.la codification
1.1.définitions
1.2.puissance lexicographique
1.3.types de codification
1.4.objectif de la codification
1.5.caractéristiques d’un code
1.6.les systèmes de codification
1.7.comment choisir une codification
2.Les contrôles
2.1.nécessité des contrôles
2.2.les différents types de contrôle
2.3.l’ordre d’exécution des contrôles
2.4.contrôles manuels et contrôles automatiques
3.les fichiers
3.1.définition et structure des fichiers
3.2.opérations sur les fichiers
3.3.typologie des fichiers
3.4.caractéristiques des fichiers
3.5.les supports magnétiques
3.5.1.la bande magnétique
3.5.2.le disque magnétique
3.6.méthodes d’organisation des fichiers
3.6.1.l’organisation séquentielle
3.6.2.l’organisation indexée
3.6.3.l’organisation directe
3.6.4.choix d’une organisation
4.les outils de décision ,but, domaines d’utilisation
4.1.Les tables de décision
4.1.1.définition
4.1.2.formats de présentation
4.1.3.enchaînement de tables de décision
4.1.4.mise en oeuvre des tables de décision
4.2.Les arbres de décision
4.2.1.définition
4.2.2. le diagramme de Veitch
B) LES SYSTEMES.
1.Eléments méthodologiques: système, environnement-frontière, sous-système, interfaces.
2.Composition d’un système
3.Les modèles de base
4.Classification des systèmes
4.1.les systèmes déterministes et les systèmes probabilistes
4.2.les systèmes fermés et les systèmes ouverts
5.Contrôle d’un système
5.1.définition
5.2.composition d’un contrôle
5.3.qualités d’un contrôle
6.les sous-systèmes
6.1.la décomposition
6.2.la simplification
6.3.les méthodes de découplage
7.entropie d’un système
C) LES SYSTEMES D’INFORMATION
1.le concept d’information
1.1.définitions de l’information
1.2.les différentes formes de l’information
2.la théorie de l’information
2.1.introduction
2.2.la mesure de la quantité d’information
2.3.l’analyse de la chaîne de communication
2.4.la distinction des trois niveaux d’information
2.4.1.niveau technique
2.4.2.niveau sémantique
2.4.3.niveau efficacité
3.les systèmes d’information
3.1.définitions
3.2.rôle d’un SI
3.3.place d’un SI
3.4.statique et dynamique d’un SI
3.5.cycle de vie d’un SI
Remarques:
a-Prérequis: cours « Initiation aux fonctions de l’entreprise »
b-Ressources requises: moyens matériels, langage de programmation orienté Gestion (certaines séances de TD porteront sur l’étude de ce langage).
c-Travaux pratiques: portent sur : -la codification et les contrôles
-les fichiers (séquentielle, séquentielle indexée, directe)
-les outils de décision.
d-Un mini-projet: à lancer au plus tard à la fin de la partie A, il a pour but de synthétiser tous les aspects étudiés dans cette partie. En plus des points vus dans les T.P, il devra inclure la constitution des fichiers (répartition des informations), les choix des organisations et des accés. Il sera naturellement réalisé sur machine.
BIBLIOGRAPHIE:
J.L. LEMOIGNE:
« La théorie du système général », (Ed. Presses Universitaires Françaises).
J. SORNET: « Guide de l’analyse informatique », (Ed. d’Organisation).
C. COCHET, A. GALLIOT: »L’analyse fonctionnelle et organique » T1 et T2, (Ed. Dunod).
X. CASTELLANI:
« Méthode générale d’analyse d’une application informatique » T1 et T2, (Ed. Masson)
Y. LASFARGUES:
« Une informatique par et pour les gestionnaires », (Ed. d’Organisation).
G.B. DAVIS, M.H. OLSON, J. AJENSTAT, J.L. PEAUCELLE:
« Systémes d’informations pour le management », (Ed. G. Vermette Inc.).
J.A. SENN: « Analyse et conception des S.I. », (Ed. Mc Graw Hill).
A. ROLES: « Théorie de l’information »
L. VON BERTALANFFY: « Théorie générale des systèmes », (Ed. Dunod).
J.L. PEAUCELLE: »Informatique », (Ed. Vuibert).
G. SOLLIN: « Informatique appliquée à la gestion: choix des structures et des moyens de gestion », (Ed. Masson).
M. AUMIAUX: »Informatique de gestion ».
R. REIX: « Traitement des informations ».
2I-TRC 2ème Année Tronc-Commun
MATHEMATIQUES
CODE : MATH2
I. INTEGRALE DE RIEMAN (2 semaines)
Construction de l’intégrale de RIEMAN. Fonctions intégrables, propriétés, théorème de posivité et formule de la moyenne, primitives en utilisant les différents procédés d’intégration (changement de variables, intégration par partie etc.)
Recherche des primitives de fonctions rationnelles, de certaines fonctions irrationnelles et trigonométriques, intégrales impropres, intégrales dépendantes d’un paramètre, critère intégrale de la convergence d’une série numérique.
II. SUITES ET SERIES DE FONCTIONS (5 SEMAINES)
Les critères de la convergence uniforme, l’intégration et dérivation d’une suite de fonctions.
Séries de fonctions, les critères de CAUCHY et de WEIESTRASS de la convergence uniforme d’une série de fonctions.
Séries entières, rayon et intervalle de la convergence, série de TAYLOR.
Applications des séries à l’intégration d’équations différentielles.
Intégration et dérivation d’une série de fonctions, série de FOURIER.
Développement des fonctions en série de FOURIER. Les conditions de DIRICHLET, série de FOURIER des fonctions paires et impaires.
III. EQUATIONS DIFFERENTIELLES DU 1er ORDRE : (3 SEMAINES)
Définitions, équations différentielles du 1er ordre :
Notions générales, équations à variables séparables, équations homogènes, équations linéaires (équation de BERNOULLI – solutions singulières des équations du 1er ordre, équations de CHAIRAUT et de LAGRANGE, trajectoires orthogonales et isogonales).
IV. EQUATIONS DIFFERNETIELLES D’ORDRE SUPERIEUR A UN : (3 SEMAINES)
Notions générales, quelques types d’équations différentielles du second ordre se ramenant à des équations du premier ordre.
Equations linéaires homogènes du second ordre et d’ordre n à coefficients constants.
Equations linéaires non homogènes du second ordre et d’ordre n’a coefficients constants.
Systèmes d’équations différentielles ordinaires.
V. FONCTIONS DE PLUSIEURS VARIABLE : (5 SEMAINES)
Limites et continuité dans R.n différentielle d’une fonction de plusieurs.
Variables, dérivées partielles, dérivées dans une direction, dérivées partielles d’ordre supérieure à un. Jacobienne.
Différentiabilité des fonctions composées, applications aux changements de variables (coordonnées polaires, cylindriques et sphériques). Formule de TAYLOR, applications à la recherche d’extremum libres.
VI. INTEGRALES MULTIPLES, CURVILIGNES, DE SURFACES (7 semaines)
Définition de l’intégrales doubles
Application des intégrales doubles au calcul d’aires et de volume
Changement de variables dans une intégrale double
Calcul des aires de surfaces
Intégrales triples.
Changement de variables dans une intégrale triple
Intégrales curvilignes
Formule de GREEN
Intégrales de surface
Formule de stocks
Formule d’Ostrogradsky.
VII. FONCTIONS DE LA VARIABLE COMPLEXE (5 SEMAINES)
Définitions
Limites et continuité
Dérivation
Fonctions analytiques (holomorphes)
Conditions de CAUCHY
Différentielle
Intégrales d’une fonction de variable complexe
Théorème de CAUCHY
Formule intégrale de CAUCHY
Série de TAYLOR d’une fonction holomorphe.
Résidu en un pôle
Théorème des résidus
Application des théorèmes au calcul de certaines intégrales définies réelles.
2I-TRC 2ème Année Tronc-Commun
INTRODUCTION A LA LOGIQUE MATHEMATIQUE
CODE : LOGM2
COURS ET TRAVAUX DIRIGES
1ère Partie: CALCUL PROPOSITIONNEL (9 cours)
Introduction (Paradoxe)
Langage du calcul Propositionnel
Etude Sémantique (Table de Vérité, équivalence logique,Tautologie)
Etude Syntaxique (Déduction)
Théorème de Consistance
Théorème de Complétude (Algorithme de réfutation)
2ème Partie: RECURSIVITE et CALCULABILITE (6 cours)
Fonctions Primitives Récursives
Fonctions Récursives
Ensembles et Relations Récursifs
Machines de Turing
Equivalence entre les fonctions récursives et les fonctions calculables
par une Machine de Turing
Thèse de Church
3ème Partie: CALCUL DES PREDICATS (9 cours)
Introduction
Langage du premier ordre avec égalité
Etude Syntaxique (Déduction)
Formes Prenexes
Etude Sémantique (Interprétation et Modèle)
Théorèmes de Consistances et de Complétude
Travaux PratiqueS
Un TP au 2ème semestre pour donner la possibilité aux étudiants de faire le lien entre le cours théorique et la pratique informatique et de les initiations à la programmation logique.
Les besoins du TP comprennent Matériel : un micro
Logiciel : prolog
Humain : un assistant par groupe
BIBLIOGRAPHIE
INTRODUCTION TO MATHEMATICAL LOGIC; ELLIOT MENDELSON
LOGIQUE MATHEMATIQUE; S.C.KLEEN; COLLECTION U
COMPRENDRE LA LOGIQUE MODERNE (TOME I); F.CHENIQUE; DUNOD
COURS DE LOGIQUE MATHEMATIQUE; R.FRAISSE
INTRODUCTION A LA LOGIQUE; A.TARSKI
SYMBOLIC LOGIC AND MECHANICAL THEOREM PROVING; C-L.CHANG
2I-TRC 2ème Année Tronc-Commun
STATISTIQUES
CODE : STAT2
PARTIE 1 : STATISTIQUES (15%)
– présentation du modèle statistique
– les séries statistiques
– variables statistiques (continue et discontinue)
-les différents tableaux statistiques (caractéristiques de tendances centrales, de dispersion, de forme et de concentration)
– représentation graphique.
-Problème du jugement sur échantillon (échantillonnage, test de normalité).
– interprétation des résultats.
PARTIE 2 : CALCUL DE PROBABILITES (30%)
I. NOTIONS DE COMBINATORIQUE
II. PROBABILITES
– notion de probabilités
– notion d’événement
– algèbre des événements et algèbre des probabilités
– fonctions de variables aléatoires
– étude des lois de probabilité unidimensionnelle
. variable aléatoire discrète :
– uniforme
– bernoulli
– binomiale
– poisson
– géométrique
– hypergéométrique
. variable aléatoire absolument continue
– loi uniforme
– loi normale
– loi gamma
– lois dérivées de la loi normale (X2, studnet, Fiskher).
PARTIE 3 : (25%)
– variables aléatoires multidimensionnelle
– étude de la variable aléatoire à deux dimensions
– notion de régression
– convergence
PARTIE 4 : STATISTIQUES INTEFERENTIELLES (30%)
– théorème de l’échantillonnage (notion de sondage)
– théorie de l’estimation
. estimation ponctuelle (méthode des moments-méthode
du maximum de vraissemblage).
. estimation par intervalle de confiance
– théorie des tests
.tests paramétriques
(test d’hypothèse : risque d’erreurs puissance du test).
. tests non paramétriques
(Xhi – deux : ajustement, comparaison, indépendance).
BIBLIOGRAPHIE :
1 – P. JAFFARD
STATISTIQUES
RESUME DE COURS – EXERCICE – PROBLEMES
MASSON 1977
2 – C. LAROUSSE
STATISTIQUE
EXERCICES CORRIGES AVEC RAPPELS DE COURS (TOME1,2 et 3)
DUNOD 1983
3 – M. BENYAKHLEF
PROBABILITES ET STATISTIQUES MATHEMATIQUE TOME 1
P.E.M. 1977
4 – C. LEBOEUF, J.L. ROQUE, P. LANDRY
EXERCICES CORRIGES DE PROBABILITES
ELLIPSE 1983
5 – C. LEBOEUF, J.L ROQUE, P. GUEGAND
EXERCICE DE PROBABILITES ET DE STATISTIQUE
ELLIPSE 1983
6 – C. MOUCHOT
EXERCICES PEDAGOGIQUES DE STATISTIQUES ET ECONOMIE
ECONOMICA 1979.
2I-TRC 2ème Année Tronc-Commun
ANGLAIS
CODE : ANGL2
THEME : ETUDE DE LA PHRASE COMPLEXE
A – ETUDE DE LA PHRASE COMPOSEE : LA COORDINATION
B – ETUDE DE LA PHRASE COMPLEXE : LA SUBORDINATION
1. Etude de la proposition nominale
1.1 Les propositions en « THAT »
1.2 Les propositions en « WH »
1.3 Les réductions
1.4 La proposition infinitive
2. Etude de la proposition adjectivale
2.1 Les marqueurs
2.2 La distribution
2.3 La réduction
3. Etude de la proposition adverbiale
3.1 les marqueurs
3.2 La distribution
3.3 La réduction
C – LES ASPECTS RHETORIQUES
1. La généralisation
2. La classification
3. L’argumentation