Le 1/9, 14h-17h (M1-M2),
Introduction au temps réel
Cette présentation introduit la problématique de la validation temporelle pour les systèmes embarqués critiques temps réel. La première partie montre comment on modélise temporellement les systèmes temps réel. La seconde partie présente les résultats classiques de la littérature (années 70 au milieu des années 90) qui sont utilisés sur les systèmes temps réel industriels aujourd'hui. La troisième partie montre comment, depuis les années 90, les modèles et techniques ont évolué pour faciliter le passage à l'échelle des gros systèmes, mais aussi pour réduire le surdimensionnement inhérent à la validation temporelle, et pour faciliter l'aide à la conception et le dimensionnement. Enfin, nous concluons sur les enjeux industriels de demain, où les systèmes seront de plus en plus complexes, et les architectures matérielles embarquées seront multicoeur.
Le 5/9, 14h-17h (M1-M2),
Test de systèmes informatiques basé sur des méthodes formelles
L'activité de test de logiciel est souvent perçue, à tort, comme purement
empirique
et ad hoc.
Or le test de logiciel pose des problèmes théoriques intéressants, et des
approches
rigoureuses, basées sur des méthodes formelles, existent et sont l'objet
de nombreuses
recherches.
Après une introduction au sujet, cette conférence donnera un panorama des
principaux
résultats et des recherches actuelles.
Le 6/9, 10h-13h (L3-M1-M2),
Choix social computationnel
Lorsque différents agents aux préférences potentiellement
contradictoires cherchent à s'accorder sur un choix (typiquement,
entre différents candidats lors d'une élection politique), il est
courant de procéder à un vote. Mais il existe bien des procédures de
vote, aux propriétés très différentes. La théorie du choix social
étudie ces questions en adoptant (souvent) une approche axiomatique
reposant sur l'identification de propriétés "souhaitables" des règles
de vote.
Je commencerai par un bref survol de résultats fondateurs de la
théorie du choix social, en illustrant au passage la grande variété de
règles de vote envisageables.
Je présenterai ensuite un panorama de quelques questions épineuses qui
se posent lorsque ces problèmes sont envisagés sous leur aspect
computationnel. Par exemple, est-il toujours facile de déterminer le
résultat d'une élection ? Quelle quantité d'information faut-il
échanger pour y parvenir ? Le système électoral est-il manipulable par
les votants ou par les organisateurs ? Est-il raisonnablement
utilisable avec un grand nombre de candidats et/ou en présence
d'informations incomplètes ?
Le 7/9, 14h-17h (L3-M1-M2),
Arbres formels et arbre de la vie : définitions, modèles et algorithmes (transparents 1 et 2)
Depuis Darwin les arbres sont centraux pour représenter l'évolution des espèces et
des objets biologiques. Je présenterai les nombreuses définitions de la notion d'arbre,
la manière de dénombrer les arbres, de les comparer et d'en faire le consensus. Je
présenterai plusieurs modèles d'arbres aléatoires, issus de la biologie, de la physique
et des mathématiques. J'expliquerai quelques méthodes simples pour reconstruire
des arbres évolutifs à partir de séquences biologiques. Je donnerai quelques applications
des arbres en biologie et montrerai pourquoi l'inférence des arbres phylogénétiques est
centrale dans de nombreux domaines allant de la génomique aux études de biodiversité.
Le 8/9, 14h-17h (M1-M2),
Traitement des Langues Naturelles
Le traitement des langues naturelles (TAL) cherche à "faire parler les ordinateurs" et plus précisément, à fournir une modélisation informatique de nos capacités linguistiques. Je commencerai par passer en revue les caractéristiques des langues naturelles et les problèmes que celles ci soulèvent pour un traitement informatique. J'illustrerai ensuite chacun des deux grands courants, statistique et symbolique, exploités dans le domaine du TAL par la présentation de deux sous-tâches du TAL. La première, l'étiquettage morpho-syntaxique, vise à associer les mots d'un texte avec la catégorie morpho-syntaxique appropriée étant donné son contexte. Nous examinerons plusieurs approches possibles dont notamment, une approche probabiliste utilisant les modèles de Markov cachés. La seconde, la génération de phrases, consiste à verbaliser des données numériques ou symboliques et sera utilisée pour illustrer l'approche symbolique. Nous y verrons en particulier, comment des algorithmes d'analyse syntaxique (parsing) peuvent être adaptés pour générer plutôt que pour analyser des phrases.
Le 13/9 de 9h15 à 10h45 (L3 Math et Info),
Synthèse d'images de textures: modèles mathématiques, modèles algorithmiques
Le 13/9 de 11h15 à 12h45 (L3 Math et Info),
Automates cellulaires, indécidabilité et pavages
Introduits par Ulam et von Neumann dans les années 40, les automates cellulaires forment une riche famille de systèmes dynamiques discrets. L'objectif de cet exposé est d'étudier une propriété dynamique simple de ces objets : la convergence vers un unique point fixe. Plus précisément, existe-t-il un algorithme qui décide si un automate cellulaire possède cette propriété ? Pour répondre à ce type de question, il convient d'abord de préciser ce qu'est un algorithme. C'est la question fondatrice de la théorie de la calculabilité, qui formalise la notion de calcul, de problème indécidable et de réduction adéquate. L'indécidabilité du problème de l'arrêt de machines de Turing permet alors d'établir l'indécidabilité de la pavabilité du plan par un jeu de tuiles colorées, qui permet de démontrer le résultat escompté : il n'existe pas d'algorithme qui décide si toutes les configurations d'un automate cellulaire convergent vers un unique point fixe.
Contacter le Département InformatiqueDernières modifications : le 21/09/2011