Génie logiciel I

Contenu des enseignements de la spécialité Ingénierie Logicielle
PREMIERE ANNEE Algo I (Math pour l'info)
Responsable : Christian Lavault Objectif : XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX Contenu :
1 Combinatoire et dénombrement
1.1 Permutations, arrangements et combinaisons
1.2 Applications au dénombrement d'ensembles finis
1.2.1 Rappels
1.2.2 Formules d'exclusion inclusion et applications
1.3 Manipulation de suites et de sommes
1.3.1 Suites, sommes et opérateurs
1.3.2 Méthodes usuelles de sommation
1.3.3 Manipulation de sommes doubles.
2 Relations de récurrente
2.1 Rappels et généralités
2.1.1 Exemples de relations de récurrence
2.1.2 Classification
2.2 Equations de récurrence linéaires
2.2.1 Récurrences linéaires homogènes à coefficients constants
2.2.2 Récurrences linéaires générales à coefficients constants
2.2.3 Récurrences linéaires à coefficients variables
2.3 Equations de récurrence non linéaires
2.3.1 Récurrences de partition et changements de variable
2.3.2 Transformation du domaine
3 Séries génératrices et applications
3.1 Séries génératrices
3.1.1 L'anneau des séries formelles
3.1.2 Développement en série au voisinage de l'origine
3.1.3 Fonctions génératrices ordinaires et exponentielles
3.2 Développement en série des fractions rationnelles
3.2.1 Décomposition en éléments simples
3.2.2 Développement au voisinage de l'origine
3.2.3 Cas de racines multiples
3.3 Applications aux équations de récurrence
3.3.1 Récurrences linéaires homogènes à coefficients constants
3.3.2 Récurrences linéaires générales à coefficients constants
3.3.3 Récurrences linéaires à coefficients variables
3.3.4 Récurrences complètes
3.4 Analyse en moyenne d'algorithmes
3.4.1 Généralités
3.4.2 Utilisation des séries génératrices
4 Comportements asymptotiques
4.1 Fonctions dominées, négligeables, équivalentes
4.2 Critères de comportement asymptotique
4.2.1 Conditions suffisantes
4.2.2 Echelle de comparaison et développement asymptotique
4.3 Approximations asymptotiques
4.3.1 Encadrements de sommes partielles
4.4 Asymptotique des séries génératrices
4.4.1 Approximations asymptotiques des récurrences linéaires
4.4.2 Calcul direct du terme asymptotique dominant
4.4.3 Méthode générale pour les fractions rationnelles
4.4.4 Bornes du rayon de convergence
4.4.5 Méthode générale d'analyse asymptotique des coefficients
4.5 Formule d'Euler-Maclaurin
4.5.1 Formule sommatoire d'Euler-Maclaurin et applications
4.5.2 Développement asymptotique des nombres harmoniques
4.5.3 Développement asymptotique complet de la factorielle
4.6 Approximations asymptotiques
4.6.1 Développement asymptotique des nombres de Catalan
4.6.2 Développements asymptotiques bivariés
4.7 Deux méthodes asymptotiques
4.7.1 Le reboutement ou Bootstrapping
4.7.2 Méthode de Laplace : borner les queues, approcher et
étendre
Algo II.1 (Algorithmique des structures linéaires)
Responsable : Jacqueline Vauzeilles Objectif : XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX Contenu : XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Algo II.2 (Algorithmique des arbres)
Responsable : Christophe Fouqueré Objectif : éléments algorithmiques sur les structures d'arbres Contenu : Spécifications, algorithmes, dénombrements, analyses de
complexité sur les structures d'arbres binaires, arbres n-aires, et les
variantes adaptées à la recherche de données (arbres binaires de recherche,
arbres équilibrés, B-arbres).
Tri externe. Système d'exploitation Responsable : Jacqueline Castaing Objectif : Le cours prolonge et complète la formation dispensée en L2. Il
aborde les aspects pratiques de la programmation système UNIX dans sa
version libre LINUX. Contenu :
Après un rappel sur les différents modes existants (mono-tache mono-
processeur, multi-tâches mono-processeur, multi-tâches multiprocesseurs),
ce cours détaille le mécanisme de la programmation parallèle. Les notions
de tubes ("pipe"), et de mémoires partagées, sont introduites dans le
contexte de la communication des processus. Leur synchronisation est
étudiée avec la présentation des sémaphores. La notion de processus
légers ou "threads" est alors introduite pour montrer comment réduire le
temps de commutation des contextes, lorsque le système d'ordonnancement
choisit de mettre en attente un processus, pour rendre actif un autre plus
prioritaire. La gestion des fichiers est analysée au plus bas niveau du
système (celui du noyau). La gestion de la mémoire (pagination, mémoire
virtuelle), est également abordée dans l'environnement de la programmation
multi-tâches. La communication par messages (systèmes distribués) dans le
mode Client/ Serveur à travers les sockets permet alors à l'étudiant de
comprendre le fondement de l'Internet. Architecture des machines Responsable : Christophe Tollu Objectif :
Le but du cours est de donner aux étudiants les outils d'architecture
matérielle nécessaire à l'évaluation de la performance des applications
logicielles. Par surcroît, les étudiants acquièrent des compétences en
programmation assemblage. Contenu :
1. Généralités : interface matériel-logiciel, organisation en niveaux.
2. Représentation des données en machine.
3. Description d'un jeu d'instructions RISC : MIPS.
4. Cycle d'exécution (compilateur, assembleur, chargement en mémoire).
5. Circuits logiques combinatoires et séquentiels.
6. Construction d'un CPU (chemin de données et contrôle)
8. Optimisation par "pipelining".
9. Hiérarchie de la mémoire (caches et mémoire virtuelle)
10.Bus et entrées/sorties. Mécanismes d'interruption
Programmation impérative (C sous Unix)
Responsable : Lucas Letocart Objectif : L'objectif de ce cours est de permettre aux étudiants de se
remettre à niveau en programmation C sous Unix. Ce cours permet une
introduction au développement de projets en langage C sous Unix. Contenu : Unix: Introduction à Unix, commandes, système de fichiers,
processus, interpréteurs de commandes. Langage C: opérateurs, boucles,
variables, fonctions, bibliothèques, pointeurs, tableaux, chaînes de
caractères, structures, directives du préprocesseur, inclusion de fichiers,
compilation, déclaration et définition des objets. Programmation fonctionnelle Responsable : Jacqueline Vauzeilles Objectif : Ce cours de programmation fonctionnelle s'appuiera sur le
langage Caml Contenu : Généralités sur les ensembles - Produit d'ensembles - Somme
directe d'ensembles - Fonctions et fonctionnelles - Isomorphismes.
Introduction à Caml - Déclarations - Identificateurs - Environnements.
Modules.
Fonctions simples - Fonctions récursives.
Types simples - Types polymorphes.
Types récursifs.
AspCrédits impératifs de Caml. Programmation objet Responsable : Marc Champesme Objectif : XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX Contenu : Classes, objets, instances, méthodes, envoi de message (principes
généraux) éléments syntaxiques du langage de programmation choisi,
programmation par contrat (invariant de classe, pré-conditions, post-
conditions) héritage simple Extension souhaitée (éléments supplémentaires abordés actuellement en
Licence/ILOG):
principe général de l'héritage multiple: pseudo-héritage multiple (en
JAVA/SMALLTALK), vrai héritage multiple (en Eiffel/C++)
Exceptions
architecture logicielle (exemple de l'architecture Model View Controller) Programmation logique Responsable : Christian Codognet Objectif : XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX Contenu : XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Sémantique des langages de programmation Responsable : Christophe Tollu Objectif : Le but du cours est double : (i) présenter les idées
fondamentales qui fondent les approches opérationnelle et dénotationnelle
en sémantique formelle des langages de programmation et (ii) montrer, à
l'aide d'exemples d'application précis, comment ces approches peuvent être
utilisées pour valider des prototypes, analyser l'implémentation de
fonctionnalités plus sophistiquées et vérifier certaines propriétés des
programmes.
Chaque type de sémantique formelle sera illustré sur un langage-test,
appelé WHILE (une version très simplifiée de PASCAL) et certaines de ses
extensions et variantes : construction par blocs, procédures (récursives ou
non) avec liaison statique ou dynamique des variables et des procédures,
non déterminisme, etc. Contenu :
Description et spécification rapides du langage WHILE.
Sémantique opérationnelle structurelle et sémantique naturelle du
Langage WHILE et de ses extensions.
Application : preuve de la correction d'un compilateur pour WHILE.
Equivalence entre sémantiques naturelle et structurelle.
Sémantique dénotationnelle du langage WHILE et de ses extensions.
Application : analyse statique des programmes (ex : dépendance
entrées-sorties). Génie logiciel I Responsable : Christine Choppy Objectif : 1. Niveau de base de pratique de spécification précise
2. Qualité logicielle : pratique systématique et planifiée du test. Contenu : Techniques de spécification algébrique de base appliquée à la
spécification formelle des structures de données de base de l'informatique
(booléens, entiers, listes, piles, arbres binaires, graphes). Le langage
utilisé est CASL (langage commun établi). Les structures de donn