|
|
|
|
|
|
Résolution de problèmes complexes, soit
par leur nature combinatoire (problèmes NP- complets par
exemple) soit par la nature non prévisible des instances
à traiter (thèmes de l'algorithmique en ligne). Les
problèmes traités concernent principalement les graphes,
objets particulièrement importants dans la modélisation
réseau, et les ordonnancements.
Les concepts enseignés sont en large partie
génériques et permettront à l'étudiant
d'acquérir un complément de formation avancée
en algorithmique et d'être scientifiquement autonome dans la
résolution des problèmes complexes qu'il pourra
rencontrer dans ses futures activités professionnelles
(industrielles ou de recherche). |
|
- Rappel
sur les problèmes NP-complets. Notion de rapport
d'approximation.
- Etude de
diverses techniques permettant de maîtriser le concept et
l'usage de rapport d'approximation (algorithmes gloutons,
utilisation de la programmation dynamique, utilisation de la
programmation linéaire, dualité).
-
Problèmes étudiés : couverure d'ensembles,
couverture sommets, problème d'ordonnancement, coupe
« multi- way », problème du
sac-à-dos, voyageur de commerce, /arbre de Steiner,
…
-
Schémas d'approximation polynomiaux : études de
cas.
-
Non-approximabilité.
- Instance
évolutives : motivations, domaines d'applications.
- Notion
de rapport de compétitivité.
-
Parallèle avec le rapport d'approximation.
- Etude de
divers algorithmes en ligne.
- Limites
du concept de compétitivité.
|
|
|
|
|
|
|
|
-
Plusieurs familles de méthodes méta-heuristiques
étant présentées, l'étudiant sera à
même de les comparer et de retenir celles qui sont les plus
adaptées pour ses futurs problèmes.
-
L'étudiant aura à l'issue de ce cours des notions
pratiques directement utilisables (méta heuristiques diverses
par exemple) mais aussi des connaissances théoriques sur le
pouvoir et les limites de ces méthodes qui lui fourniront une
palette de méthodes qu'il pourra alors adapter lui-même
pour résoudre une large classe de problèmes
académiques ou industriel.
|
|
Ce cours présente des algorithmes
généralistes pouvant s'appliquer à une très une
large gamme de problèmes d'optimisation combinatoires. Nous
présenterons les algorithmes évolutionnaires tels que les
algorithmes génétiques, ainsi que d'autres
métaheuristiques telles que le recuit simulé, la
recherche avec tabous, et les algorithmes de colonis de
fourmis. La suite du cours sera consacrée à des
résultats théoriques mettant en évidence les
principales avancées de ce domaine de recherche, et notamment
les limitations intrinsèques de ces méthodes
(théorème ``no- free-lunch''), des résultats
généraux de convergence, et l'étude de l'espace de
recherche de ces algorithmes (théorie des paysages). |
|
|
|
|
|
|
|
Présenter dans une première partie la
problématique générale de la qualité de
services dans les réseaux et son importance en termes
d'impacts de performances sur les couches clientes. Le reste de
l'enseignement sera la description de techniques algorithmiques
permettant de gérer efficacement certains paramètres de
qualité de services. On s'attachera à présenter
aussi les limites de ces techniques. Enfin, divers travaux
récents sur la QoS et sa tarification seront
décrits. |
|
1) Caractérisation et modélisation des
trafics générés par les couches clients
(applications)
2) Mécanismes de gestion des trafic
:
- mécanisme de gestion de files
d'attente
- différenciation des services
3) Routage et multicast avec QoS.
4) Tarification de la QoS |
|
|
|
|
|
|
|
La première partie du cours sera
consacrée à l'introduction à la théorie des
jeux coopérative et non-coopérative. Il s'agit ici de
fournir aux étudiants des notions classiques en
économie qui seront utilisées pour l'étude et la
compréhension d'internet et d'autres systèmes complexes
comme les systèmes biologiques. Dans la deuxième partie
du cours, nous allons étudier et comparer différents
modèles de graphes (modèle Erdös-Renyi,
« small world », etc…) modélisant
des systèmes complexes tels que l'internet ou les réseaux
métaboliques. |
|
-
Equilibres en général et équilibre de Nash en
particulier. Mécanismes de conception et mécanismes de
coordination. Analyse dans le pire des cas et rapport de
coordination. Equité dans les jeux coopératifs.
-
Théorie des jeux évolutionnaires, jeux
répétitifs.
-
Modèles pour les grands réseaux d'intéraction
-Erdös-Renyi
-« small world »
-la
loi des « puissances »
-
Applications : internet et bio-informatique.
|
|
|
|
|
|
|
|
Présentation d'une méthodologie
basée sur l'optimisation pour la conception et
l'évaluation des systèmes embarqués et, en
pariculier, pour la conception des circuits VLSI employés dans
ces systèmes. |
|
-
Description et propriétés de modèles de calculs :
flots de données synchrone (SDF), Machines à états
finis pour la co-conception (CFSM).
-
Formulation du partitionnement/logiciel de systèmes à
applications hétérogènes comme un problème
d'optimisation. Méthodes de
résolution.
Techniques d'estimation rapide de performances (re-
synchronisation). Analyse de performances du logiciel
embarqué.
Conception des circuits dédiés :
Placement des composants sur la puce (techniques de
placement, partitionnement de graphes et floorplanning);
problèmes de routage (global et canaux); compaction de
circuits; minimisation de la surface des buffers (recherche de flot
max).
|
|
|
|
|
|
|
|
L'informatique d'aujourd'hui est confrontée
au problème du passage à l'échelle, tant dans la
puissance demandée que dans la gestion du nombre de noeuds. Ce
module présente les deux grandes approches utilisées
aujourd'hui pour aborder ce problème qui sont le
pair-à-pair et les grilles. A l'origine, le pair-à-pair
s'est développé pour le partage d'informations entre un
très grand nombre de noeuds éventuellement volatiles,
alors que les grilles sont apparues pour faire du calcul
parallèle à grande échelle avec une bonne
tolérance aux fautes. Cette frontière donnée-calcul
tend à disparaitre aujourd'hui et tous les domaines cherchent
à tirer partie de ces deux approches |
|
1-
Systèmes pair-à-pair
-
caractéristiques des systèmes P2P
- approche
non structurée (Gnutella)
- approche
hiérarchique (super-pairs)
- approche
structurée (Chord, P-grid, CAN, ...)
-
applications : mémoire virtuelle répartie (Juxmem), bases
de données (Pier)
2-
Grilles
- modèle
des web services
- l'approche
grid services (OGSA, WSRF)
-
optimisation des communications, allocations des ressources
- desktop
grid computing
-
applications : data grids, entreprises virtuelles, |
|
|
|
|
|
|
|
Les environnements informatiques seront de plus
en plus distribués (aussi bien dans le contexte professionnel
: entreprises multi-sites, que dans celui des loisirs) et mis en
oeuvre collectivement par des utilisateurs distants. Par ailleurs,
le nomadisme devient la règle : une même personne devra
pouvoir accéder, depuis une localisation quelconque et avec un
terminal quelconque, au même type de service. Enfin, les
terminaux mobiles (assistants personnels avec connexions
réseau sans fil) sont en pleine expansion. Ces différents
facteurs conduisent à repenser l'architecture logicielle des
systèmes informatiques, ouvrent la porte à de nouveaux
services, et soulèvent des problèmes méthodologiques
nouveaux. Le but du module est d'introduire la problématique
de la mobilité, de présenter les concepts permettant de
la prendre en compte, et d'illustrer leur mise en œuvre dans
plusieurs domaines applicatifs. |
|
1.
Problématique de la mobilité
- différentes
formes de mobilité : utilisateurs, terminaux
- panorama des nouveaux
problèmes à résoudre
2. Concepts
supportant la répartition et la mobilité
- répartition des
données
- problématique des bases de données réparties
- approche médiation (LAV, GAV)
- cohérence de
copies multiples en environnement sans fil
- gestion de cache sur
terminaux mobiles
- adaptation dynamique
au contexte d'exécution
- architectures logicielles permettant l'adaptation
- déploiement dynamique d'applications réparties à
base de composants
3. Etude
detaillée de deux domaines applicatifs
- travail
collaboratif
- jeux multi-joueurs en
réseau sur terminaux mobiles |
|
|
|
|
|
|
|
Mettre en œuvre des techniques d'analyse
pour découvrir des erreurs dans les programmes de manière
statique (sans exécution) : inférence de types,
interprétation abstraite. Etudier quelques applications
typiques de ces méthodes |
|
-
Sémantique formelle
-
Interprétation abstraite
- Analyses
data-flow
-
Slicing
-
Applications : débordement de tableaux, calcul
d'intervalles, vérification de byte- code
|
|
|
|
|
|
|
|
L'objectif de ce cours est de présenter et
comparer différents modèles sémantiques
représentant la vraie concurrence (par opposition aux
sémantiques séquentielles qui considèrent des
séquences d'événements ou d'états). On
étudiera ensuite des méthodes exploitant ces modèles
pour permettre la vérification efficace de systèmes et de
logiciels concurrents |
|
-
.Différentes représentations de la concurrence
basées sur les ordres partiels (traces, pomsets, structures
d'événements, réseaux d'occurrences...).
-
Modèles formels, graphiques et modulaires (réseaux de
Petri), et sémantiques concurrentes associées.
-
Méthodes d'analyse et de vérification symbolique.
-
Extensions concernant le temps (« timed »,
« time », concept du temps
« causal » en comparaison avec les automates
temporisés).
-
Expression de la mobilité.
|
|
|
|
|
|
|
|
Les paradigmes standards (fonctionnels, objets et
logiques) ne répondent pas de façon entièrement
satisfaisante aux problèmes de réutilisabilité,
modularité, correction, expressivité, évolution,
portabilité et surtout, en facilité de programmation de
codes complexes. Les approches non conventionnelles que l'on
étudie ici proposent des alternatives aux approches classiques
grâce a la définition de nouvelles notations, de
nouvelles abstractions et enfin de nouvelles façons
d'interagir avec les programmes. |
|
Calcul moléculaire, programmation par
diffusion-réaction, paradigme multi-agents, automates
cellulaires, calcul chimique et chimie artificielle, calcul
amorphe, systèmes de réécriture (L-systèmes,
P-systèmes, VV-systèmes, MGS), calcul quantique. |
|
|
|
|
|
|
|
La preuve est une des principales techniques de
vérification de logiciels issues des méthodes formelles.
Elle nécessite d'être mécanisée. Le cours
présente des outils de preuve qui s'appuient sur la
théorie des types et plus particulièrement le calcul des
constructions inductives mis en œuvre dans l'assistant de
preuve Coq. Un tel calcul permet non seulement de vérifier des
preuves de résultats mathématiques, mais également
de certifier que des algorithmes satisfont leur
spécifications. Le module aborde également la
recherche automatique de preuve. |
|
-
Systèmes de preuve, Déduction naturelle, lambda-calculs
typés, rappels
-
Correspondance preuve/programme proposition/type
- Le
calcul des constructions inductives et le prouveur Coq
- Preuve
et calcul
- Quelques
champs d'application
- Preuve
de programmes et synthèse de programmes
-
Ingénierie des preuves : gestion de grosses preuves,
réutilisation de preuves
-
Recherche automatique de preuves : la méthode des
tableaux
|
|
|
|
|
|
|
|
L'objectif de ce cours est d'étudier des
mécanismes permettant d'améliorer le problème de
passage à l'échelle des spécifications (techniques
d'importation, structuration et raffinement des
spécifications), composants formels et de définir des
liens entre notations semi formelles d'usage industriel et
spécifications formelles. |
|
-
Sémantique des diagrammes de classe
-
Sémantique des diagrammes d'états
-
Problématique de l'intégration de données dans les
comportements
-
Intégration de données formelles dans les diagrammes
d'états
- Langages
d'architecture logicielle et les composants formels
|
|
|
|
|
|
|
|
Ce cours a pour objectif l'introduction les
différentes techniques de test fonctionnel pour les
systèmes informatiques. En particulier, nous allons
présenter des techniques de test utilisées dans le
domaine du test des logiciels et celles utilisées pour le test
des protocoles de communication. L'idée du cours est de
montrer ces différentes techniques et leur
complémentarité. |
|
-
Introduction au
test fonctionnel
-
Langages de
spécification (SDL pour les systèmes communicants,
…)
-
Méthodes de
test de conformité et
d'interopérabilité
-
Architecture et
méthodes de génération de tests.
-
Techniques de test
actives et passives
-
Méthodes de
test de composants
|
|
|
|
|
|
|
|
L' objectif du cours est d'étudier une
approche multi- paradigmes pour le développement et la
conception de systèmes informatiques en général et
des systèmes embarqués en particulier.
La diversité du domaine d'application des
systèmes embarqués et leur complexité croissante
accentuent le besoin de combiner des outils et méthodes
offrant les meilleurs mécanismes de structuration,
d'abstraction et de réutilisation et permettant l'expression
de plusieurs modèles de traitement.
Le cours est organisé en deux parties. La première partie
présente l'approche objet, l' approche orientée
composant, l'approche aspect et les langages de description
d'architectures (ADLs).
Dans la seconde partie, une application des approches Objet,
Composant et Aspect aux systèmes embarqués sera
étudiée après une présentation et une
définition des différents systèmes temps réel,
réactifs et embarqués. |
|
1) Les Approches Objet, Composant et Aspect
Rappel de
l'approche Objet
L'approche
Composant
L'approche
Aspect
Introduction aux
ADLs
2) Application d'une approche
muti-paradigmes (Objet, Composant, Aspect) à la
Modélisation et la Conception des Systèmes
Embarqués
Définition des systèmes temps réel,
réactifs et embarqués
Caractéristiques des systèmes embarqués
-
Contraintes temporelles
-
Modèles de traitement (Models of Computation)
-
Modélisation des systèmes embarqués
- notion
de modèle et méta-Modèle
-
approches de modélisation
- langages
de modélisation.
|
|
|
|
|
|
|
|
1. MOPS
