PDFaid.

Com
#1 Solutions PDF

M. TECH
INFORMATIQUE & TECHNOLOGIE
1st SEMESTER

Ref : N° LII(2)Syllabi/2003 daté du 17-06-2003

Avec effet à partir de la promotion 2003-04 admise

Syllabi

Président
Conseil des études

Département d'informatique et d'ingénierie des systèmes

Collège d'ingénierie
Université Andhra
Visakhapatnam
 M. TECH (INFORMATIQUE ET TECHNOLOGIE)
1STSEMESTER
Structure du cours et schéma d'examen

Code NOM DES PÉRIODES / ÉVALUATION

SUJET semaine Maximale des points
T P Internal External Total
MTCST1.1 Théorie de 3 - 50 100 150
Calcul
MTCST1.2 Objet Orienté 3 - 50 100 150
Analyse et conception
MTCST1.3 Structures de données et - 3 50 100 150
Algorithmes
MTCST1.4 Ordinateur 3 - 50 100 150
Organisation
Base de données MTCST1.5 3 - 50 100 150
Systèmes de gestion
Systèmes MTCST1.6 3 - 50 100 150
Programmation
Objet MTCST1.7 Orienté 3 50 100 150
Analyse et conception
Laboratoire
MTCST1.8 Ordinateur - 3 50 100 150
Laboratoire d'Organisation

À l'exception de MTCST 1.6, les autres matières sont communes avec [Link] (IT)
MTCST 1.1 THÉORIE DE LA COMPTABILITÉ

Instruction : 3 périodes/semaine External Assessment: 100marks

Évaluation interne : 50 points Temps : 3 heures

1. INTRODUCTION AUX AUTOMATES FINIS6 Périodes :

Alphabets et langues - Représentation finie des langues. Automates finis déterministes -
Automates finis non déterministes - Équivalence des automates déterministes et non finis -
Propriétés des langues acceptées par les automates finis – Automates finis et régulier
Expressions - Preuves que ces langues sont et ne sont pas régulières.

2. LANGUES SANS CONTEXTE : 9 Périodes

Grammaire sans contexte - Langages réguliers et Grammaire sans contexte - Automate à pile
Automates – Automates à pile et grammaire hors-contexte – Propriétés de la grammaire hors-contexte
Langues – Propriétés de fermeture – Propriétés de périodicité – Déterminisme et Analyse –
Automates à pile déterministes et langages sans contexte - Analyse descendante -
Analyse ascendante.

3. MACHINES DE TURING : 5 Périodes

La définition de la machine de Turing – Calculer avec des machines de Turing – Combinaison de Turing
Machines – quelques exemples de machines de Turing plus puissantes.

4. THÈSE DE L'ÉGLISE : 6 Périodes

Thèse de Church - Les fonctions primitives récursives - Godelisation - Le µ-Récursif
Fonctions – Turing – Calculabilité de laµ-Fonctions récursives – Machines de Turing universelles.

5. INCOMPATIBILITÉ : 6 Périodes
Le problème de l'arrêt - Énumérabilité de Turing, Acceptabilité de Turing et Décidabilité de Turing
– Problèmes non résolus concernant les machines de Turing etµ-Fonctions Récursives- Correspondance de Post
problème.

6. COMPLEXITÉ COMPORTEMENTALE : 6 Périodes

Machines de Turing à durée limitée - Taux de croissance des fonctions - Simulations à durée limitée -
Les classes P et NP – L'NP-complétude – Quelques problèmes NP-complets – Entier
Programmation – Le problème du voyageur de commerce.

7. LE CALCUL DES PRÉPOSITIONS 5 Périodes

Introduction – Syntax du Calcul des Prépositions – Attributions de Vérité – Validité et
Satisfaisabilité – Équivalence et Formes Normales – résolution dans le Calcul Prépotionnel.
8 LE CALCUL DES PRÉDITS : 5 Périodes
Syntax du Prédicat Calcul Calcul – Structures et Satisfaisabilité – Équivalence –
Insolvabilité et NP-complétude - Résolution dans le calcul des prédicats.

TEXT BOOK: Harry R Lewis, CHRISTOS H. PAPADIMITRIOU, : ELEMETS OF THE

THÉORIE DE LA COMPUTATION”, Prentice-Hall of India Private Limited, Nouveau

RÉFÉRENCE : HOPCROFT. J.E et J.D. ULLMAN. Introduction à la théorie des automates,

Langues et Calcul, Addison-Wesley, Reading, Mass. 1979.
MTCST 1.2 ANALYSE ET CONCEPTION ORIENTÉES OBJETS

Instruction : 3 périodes/semaine External Assessment: 100marks

Internal Assessment: 50 Marks Temps : 3 Heures

[Link]: 7 périodes
Aperçu du développement des systèmes orientés objet, notions de base sur les objets
cycle de vie du développement de systèmes orientés objet

2. UML: 10 périodes
Object-oriented methodologies.
Langage de modélisation unifié

3. Analyse : 13 Périodes
Processus d'analyse orientée objet : Identification des cas d'utilisation.
Analyse d'objet : classification
Identification des relations d'objet, des attributs et des méthodes

4. Conception : 13 Périodes
Processus de conception orienté objet et axiomes de conception Conception de classes
Couche d'accès : stockage d'objets et interopérabilité des objets.
Couche de vue : Concevoir des objets d'interface.

5. QA: 5Périodes
Assurance qualité des logiciels

Livre de texte :
Ali Bahrami : Développement de systèmes orientés objet, McGrawHill, 1999

Reference Books:
1. Craig Larman : Appliquer UML et Patrons, Pearson Education, 2002
2. Grady Booch : Analyse et conception orientées objet, Addison – Wesley, 1
MTCST 13 STRUCTURES DE DONNÉES ET ALGORITHMES

Instruction: 3 périodes/semaine External Assessment: 100marks

Internal Assessment: 50 Marks Temps : 3 heures

1. INTRODUCTION : 4 Périodes.
Aperçu des classes C++, des pointeurs, du passage de paramètres, des modèles, et de l'utilisation des matrices.

2. ANALYSE D'ALGORITHMES : 3 Périodes

Les bases des estimations de la complexité temporelle, Normes générales pour le calcul du temps d'exécution

3. LISTES, PILES ET FILES : 10 Périodes

Abstract Data Types, Representation & implementation of ADT list, Doubly linked list, Circular
listes chaînées, Représentation, Mise en œuvre et applications de l'ADT pile et file.

4. ARBRES : 10 Périodes
Mise en œuvre et parcours des arbres, arbres binaires et arbres de recherche binaires en C++, Concepts de
Arbres AVL, Arbres Splay et Arbres B.

5. HASHING: 4 Périodes.
Hash Function, Separate chains, Open addressing, rehashing, Extendible Hashing.

6. ALGORITHMES DE TRI INTERNE : 7 Périodes.

Tri comme le tri par insertion, le tri par coquille, le tri par tas, le tri par fusion, le tri rapide et l'external simple
Algorithme de tri.

7. GRAPH ALGORITHMS: 10 périodes.

Représentation de graphes Tri - topologique, Algorithme de plus court chemin, Problème de flot de réseau
Algorithme de l'arbre couvrant minimal, Applications de la recherche en profondeur. Introduction à la NP-
Complétude.

LIVRE DE TEXTE :
Structures de données et analyse des algorithmes en C++, Mark Allen Weiss. Deuxième édition, Pearson
Édition. Asie.

LIVRES DE RÉFÉRENCE :
1. Data Structures & Algorithm in C++, Adam Drozdek. Vikas publication House.
2. Data Structure, Algorithm and OOP, Gregory L. Heileman ( Tata Mc Graw Hill Edition
MTCST 1.4 ORGANISATION INFORMATIQUE

Instruction : 3 périodes/semaine External Assessment: 100marks

Internal Assessment: 50 Marks Temps : 3 heures

1. Circuits et Composants Logiques Numériques : 6 Périodes

Ordinateurs numériques - Portes logiques - Algèbre booléenne - Simplifications par carte
Circuits combinatoires : Additionneur à demi, Additionneur complet, décodeurs, codeurs, multiplexeurs
Circuits Séquentiels : Bascules, Registres, Registres à décalage, Compteurs binaires - Unité de mémoire.

2. Représentation des données : 4 Périodes

Data Types - Complements - Fixed Point Representation - Floating Point Representation - Other
Codes binaires - Codes de détection d'erreurs

3. Organisation du processeur : 8 Périodes

Organisation du Registre Général - ALU - Codes d'instructions - Formats d'instructions - Pile
Organisation - Modes d'adressage

4. Unité de Contrôle : 8 Périodes

Transfert d'enregistrements et micro-opérations, Synchronisation et Contrôle, Mémoire de contrôle, micro
programmation, contrôle câblé

5. Microprocesseur 8085 : 6 Périodes

Architecture interne, jeu d'instructions, programmation en langage d'assemblage

6. Organisation des entrées/sorties : 8 Périodes

I/O interface, Asynchronous data transfer, Modes of transfer, priority Interrupt, Direct memory
accès.

7. Organisation de la Mémoire 8 Périodes

Memory Hierarchy, Main memory, Auxiliary memory, Associate Memory, Cache Memory, and
Mémoire virtuelle.

Livre de texte :
1). Architecture des systèmes informatiques, M. Morris Mano, Prentice Hall of India Pvt. Ltd., Eastern
Édition Économie, Troisième Édition, Sept. 2002
2). Architecture, programmation et applications de microprocesseur avec le 8085, Ramesh S
Goankar, Penram International Publishing (Inde) Pvt. Ltd., Quatrième édition, 2002

Livre de référence :
Architecture et organisation des ordinateurs, William Stallings, PHI Pvt. Ltd.
Édition de l'économie orientale, sixième édition, 2003
MTCST 1.5 SYSTÈMES DE GESTION DE BASES DE DONNÉES

Instruction : 3 Périodes/semaine External Assessment: 100marks

Internal Assessment: 50 Marks Time: 3 Hours

1. Introduction: 6 Périodes
Données, stockage des données dans les SGBD, modèle relationnel, niveaux d'abstraction, indépendance des données, requêtes dans
dbms, transaction management, structure of dbms and people who work with dbms

2. Modèle ER, Modèle relationnel et algèbre relationnelle : 12 périodes

modèle ER, entités, attributs et ensembles d'entités ; relation et ensembles de relations, diagrammes ER, clé
et contraintes de participation, entités faibles, hiérarchies de classes, agrégation, conception conceptuelle
avec le modèle ER, étude de cas : analyse des besoins et conception conceptuelle, algèbre relationnelle
calcul relationnel

3. SQL: 6 Périodes
Requête SQL de base, requêtes imbriquées, opérateurs agrégés, valeurs nulles, contraintes d'intégrité, déclencheurs

4. Conception de base de données : 12 Périodes

Raffinement de schéma, dépendances fonctionnelles, fermeture d'un ensemble de DF et d'attributs, Troisième &
Formes normales de Boyce-code, propriétés de la décomposition, décomposition en 3NF et BCNF,
Affinement de schéma dans la conception de base de données

5. Traitement des transactions : 12 Périodes

ACID properties, Transaction & schedule, Concurrent execution of transaction, Lock-based
concurrency control, crash recovery, Serializability and recoverability, Lock management, lock
{"conversions":"conversions","dealing with dead locks":"gestion des verrous morts","Optimistic concurrency control":"Contrôle de concurrence optimiste","timestamp-based":"basé sur des horodatages"}
concurrence, contrôle de concurrence multiversion, ARIES, journaux, le protocole de journalisation anticipée
checkpointing, recovering from a system crash, media recovery

Livre de texte
Systèmes de Gestion de Base de Données; Raghu Ramakrishnan, Johannes Gehrke
4thÉdition, McGraw-Hill

Référence :
Concepts de systèmes de bases de données; A. Silberschatz, H. Korth
5thÉdition, McGraw-Hill
MTCST 1.6 PROGRAMMATION SYSTÈME

Instruction : 3 périodes/semaine Évaluation externe : 100 points

Évaluation interne : 50 points Time: 3 Hours

1. Introduction à la programmation système : 8 Periods

Introduction à la programmation en langage assembleur - Introduction aux formats d'instructions, données
formats - Role of Base Register, Index Register.

2. Introduction à l'assembleur 12 Périodes

Bases de données utilisées dans la conception d'assembleurs, Conception d'assembleurs - Passages uniques et doubles.

3. Introduction aux Macros 11 Périodes

Différents types de macros, conception du processeur de macros - passage unique et passage double.

4. Introduction aux chargeurs : 11 périodes

Types de chargeurs, bases de données utilisées dans les chargeurs, conception des chargeurs - absolue et DLL.

5. Introduction aux outils logiciels 6 Périodes

Éditeurs de texte, interprètes, générateurs de programmes, moniteurs de débogage.

TextBook:
Programmation Systèmes, Donovan, Tata Mc Graw Hill

Référence :
Programmation Système, Dhamdhere (Deuxième Édition Révisée), Tata Mc Graw Hill
MTCST 1.7 LABORATOIRE D'ANALYSE ET DE CONCEPTION ORIENTÉE OBJET

Pratique : 3 périodes/semaine External Assessment: 100marks

Internal Assessment: 50 Marks Temps : 3 Heures

Il est prévu que l'étudiant prenne environ cinq mini-projets, les modélise et produise des utilisations.
Cas, documents d'analyse - à la fois aspects statiques et dynamiques, diagrammes de séquence et état-
Graphiques, Conception de base de données utilisant des produits Rational Un échantillon d'idées est donné.
De nombreuses autres idées peuvent être trouvées dans les pages de la liste de références ci-dessous.
Mini-projet - I : Un système de point de vente (PDV)
Un système de point de vente est une application informatisée utilisée pour enregistrer les ventes et traiter les paiements ; il est
typiquement utilisé dans un magasin de détail, il comprend des composants matériels tels qu'un ordinateur et un code-barres
scanner, et logiciel pour faire fonctionner le système. Il s'interface avec diverses applications de service, telles qu'une
calculateur d'impôts tiers et contrôle des stocks. Ces systèmes doivent être relativement tolérants aux pannes ;
c'est-à-dire que même si les services à distance ne sont temporairement pas disponibles, ils doivent toujours permettre de capturer des ventes
et gérer au moins les paiements en espèces. Un système de point de vente doit prendre en charge plusieurs et variés clients.
terminaux et interfaces tels que navigateur, PDA, écrans tactiles.
Mini-Projet - II : Exemple de librairie en ligne
En suivant le modèle d'[Link] ou [Link], concevez et mettez en œuvre une librairie en ligne.
Mini-projet - III : Une entreprise simulée
Simuler une petite entreprise de fabrication. L'application résultante permettra à l'utilisateur de retirer un
prêt, acheter une machine, et au cours d'une série de productions mensuelles, suivre les performances de leur
entreprise.
Mini-Projet - IV : Une Simulation d'Aéroport Multi-Threadée

Simulez les opérations dans un aéroport. Votre application doit prendre en charge plusieurs avions en utilisant plusieurs
pistes et portes évitant les collisions/conflits.
Landing: an aircraft uses the runway, lands, and then taxis over to the terminal. Take-Off: an aircraft
roule jusqu'à la piste puis décolle

Mini-projet -V : Un portail communautaire automatisé

Les affaires au 21e siècle sont avant tout OCCUPÉES. Les distractions sont partout. La génération actuelle de
Les "portails intranet d'entreprise" sont souvent bruyants et peu valorisés, malgré les importants investissements en capital qu'ils nécessitent.
prend du temps pour les mettre debout. Le courrier électronique occupe 30 à 70 % du temps d'un employé. Le chat et la messagerie instantanée sont
soit dans l'entreprise, soit juste au coin de la rue. Pendant ce temps, la direction est chargée de tâches imprévues.
et des rôles de leadership et d'agent de changement non financés, ainsi que le développement du leadership et la succession
management. Ce qui est nécessaire, c'est un processus simplifié et répétable qui améliore les communications au sein de
une entreprise, tout en permettant à la direction et aux pairs de sélectionner eux-mêmes de futurs leaders et de reconnaître facilement
membres d'équipe performants de manière dynamique.
De plus, le système doit fonctionner comme un système de gestion de contenu polyvalent et commercial.
application d'intelligence et d'évaluation par les pairs.
L'objectif de Glasscode est de construire ce système. Le logiciel est publié sous une licence propriétaire, et sera
avoir les fonctionnalités suivantes : Modération à distance et sans surveillance des discussions Cependant, cela aura
des caractéristiques de découverte et d'intelligence d'affaires puissantes, et être infiniment extensible, grâce à un
powerful API and adherence to Java platform standards. Encourages peer review and indicates for
potentiels dirigeants en management, forts joueurs d'équipe et renforce les objectifs de l'entreprise et de l'équipe sans effort
et sans aucune administration.
Mini-projet -VI : Un système de gestion de contenu
L'objectif est de permettre aux utilisateurs finaux non techniques de publier, d'accéder et de partager facilement des informations sur le
web, tout en offrant aux administrateurs et aux gestionnaires un contrôle total sur la présentation, le style, la sécurité,
et autorisations.
Features:
? Système de permissions robuste
? Modèles pour des designs de site personnalisés faciles
? Contrôle total sur le contenu
? URL friendly pour les moteurs de recherche
Système de publication basé sur les rôles
Contrôle de version
? Profilage des visiteurs

Mini-Projet-VII : Une Application d'Enchères

Il existe plusieurs modèles commerciaux qui constituent la base d'un certain nombre d'entreprises comme [Link],
[Link] etc. Concevez et mettez en œuvre une application d'enchères qui fournit des services d'enchères.
Il devrait clairement modéliser les différents commissaires-priseurs, le processus d'enchères, la mise aux enchères, etc.

Mini-Projet-VIII:Unsystèmedegestiondesnotesetdesfichiers
In the course of one's student years and professional career one produces a 1 lot of personal notes and
documents. Tous ces documents sont généralement conservés sur papier ou dans des fichiers individuels sur l'ordinateur.
De toute façon, la majorité des informations est souvent effacée, corrompue et finalement perdue. L'objectif de cela
1 le projet consiste à construire une application logicielle distribuée qui répond à ce problème. Le système va
fournir une interface pour créer, organiser et gérer mes notes personnelles via Internet pour plusieurs
Les utilisateurs. Le système permettra également aux utilisateurs de collaborer en attribuant des autorisations à plusieurs utilisateurs pour
voir et éditer les notes.

Mini-projet - IX : Un éditeur de programme personnalisable

Un éditeur pour programmeurs qui sera axé sur les besoins particuliers d'un programmeur individuel et
style. L'éditeur agira selon la langue spécifique dans laquelle se trouve le fichier source actuel, et agira
effectuer de nombreuses fonctionnalités, telles que l'auto-complétion ou le résumé de fichiers, sur le fichier. Ces fonctionnalités
pourra être activé ou désactivé par le programmeur, et le style de programmation de l'utilisateur sera
utilisé pour créer un environnement d'édition aussi efficace que possible.

Mini-projet - X : Un éditeur graphique

Concevoir et mettre en œuvre une collection de classes Java qui prend en charge la construction de l'édition de graphes
applications, c'est-à-dire, des applications qui incluent la capacité de dessiner des diagrammes structurés et non structurés.
Exemple :
L'objectif du projet GEF est de construire une bibliothèque d'édition de graphes qui peut être utilisée pour créer de nombreux, de haute
applications de graphisme de qualité. Certaines des fonctionnalités de GEF sont :
Un design simple et concret qui rend le cadre facile à comprendre et à étendre.
Modèle de graphique Node-Port-Edge suffisamment puissant pour la grande majorité des graphes connectés
applications.
Le design Model-View-Controller basé sur la bibliothèque Ul Swing Java permet à GEF d'agir comme une Ul pour
structures de données existantes, tout en minimisant le temps d'apprentissage pour les développeurs familiers avec Swing.
Des interactions utilisateur de haute qualité pour le déplacement, le redimensionnement, la remodelage, etc. GEF prend également en charge plusieurs nouveautés.
interactions telles que l'outil d'alignement de balai et les boutons d'action de sélection. Feuille de propriétés génériques
basé sur l'introspection des JavaBeans. Formats de fichiers basés sur XML conformes à la norme PGML
Text Book(s):
Appliquer UML et les motifs : Une introduction à l'analyse et à la conception orientées objet et le
Processus Unifié", Craig Larman, Pearson Education Asie, 2002, 2ndÉdition
Référence(s) :
Analyse et conception de systèmes orientés objet utilisant UML, Simon Sennet, Steve McRobb et Ray
Farmer, McGraw Hill, 2002, 2ndÉdition
"Analyse et Conception Orientées Objet," Andrew Haigh, Tata McGraw-Hill, 2001,

Diverses ressources et projets en ligne :

[Link]
[Link]
[Link] rejette
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
MTCST 1.8 LABORATOIRE D'ORGANISATION INFORMATIQUE

Pratique : 3 périodes/semaine External Assessment: 100marks

Internal Assessment: 50 Marks Time: 3 Hours

Liste des expériences :

TTL Characteristics

Circuit intégré TTL

Tongs

Counters

Registres à décalage

Multiplexeurs

Décodeurs

Additionneurs binaires : Additionneur demi, Additionneur complet

Programmation en langage d'assemblage 8085 utilisant le kit MPS-85

P.C. Architecture Familiarization

Remarque :
1 semaine pour l'instruction de laboratoire, 1 semaine pour répéter les expériences, 8 semaines pour les expériences 1 à 8

4 Weeks for expt. 9, 2 Weeks for expt. 10