Cours

(programme et  emploi du temps ici)

Algorithmes exacts (exponentiels) pour problèmes NP-difficiles

Diaporama : partie 2 et partie 3

La question de la résolution exacte des problèmes combinatoires est posée dès 1956 par Kurt Gödel, dans une fameuse lettre adressée à John von Newmann : « It would be interesting to know […] how strongly in general the number of steps in finite combinatorial problems can be reduced with respect to simple exhaustive search ». En termes modernes, peut-on résoudre tous les problèmes de la classe NP par des algorithmes sensiblement plus efficaces que l’énumération triviale de toutes les solutions admissibles ?

Nous sommes encore loin d’avoir une réponse à cette question fondamentale. Dans ce cours, nous aborderons quelques techniques classiques qui permettent d’obtenir des algorithmes exacts pour certains problèmes NP-difficiles, avec une complexité (modérément) exponentielle mais nettement meilleure que la recherche exhaustive dans l’espace des solutions : algorithmes de branchement et méthode « mesurer pour conquérir », programmation dynamique, compression itérative, sort-and-search… Nous évoquerons également des bornes inférieures de complexité.

Calculs de programmes parallèles avec Coq

  • Frédéric LOULERGUE (Inria πr², Paris et LIFO, Université d’Orléans, Orléans)
  • Wadoud BOUSDIRA (LIFO, Université d’Orléans, Orléans)
  • Julien TESSON (LACL, Université Paris-est Créteil)

CLIQUER ICI -> Support, fichiers, installation pour les TP…

De nos jours, les architectures parallèles sont partout : de l’ordiphone aux super-calculateurs et fermes d’ordinateurs. Toutefois la plupart des programmeurs ne maîtrisent pas la programmation parallèle. Il y a donc un besoin de nouvelles abstractions de programmation pour rendre la programmation parallèle plus aisée, ou au moins des bibliothèques implantées en parallèle pour masquer les détails du parallélisme aux programmeurs. Le parallélisme étant présent dans tous les domaines d’applications, il est également important de s’intéresser à la correction des programmes parallèles.

La méthodologie de la programmation transformationnelle permet d’élaborer des programmes efficaces de manière plus formelle. Un programme efficace est dérivé pas à pas à travers une séquence de transformations qui en préserve la sémantique et conséquemment la correction. Avec des structures de données appropriées, le calcul de programme peut être utilisé pour écrire des programmes parallèles. Une fois qu’une formulation correcte et efficace du programme est obtenue par transformations, le programme est implanté en utilisant une bibliothèque de squelettes algorithmiques, que l’on peut voir comme des fonctions d’ordre supérieur implantées en parallèles. Cependant, il n’y a pas de correspondance formelle entre le programme obtenu par transformation et le programme conçu avec les squelettes. De plus, la transformation elle-même est généralement écrite à la main et peut être source d’erreurs.

Le système SyDPaCC est un ensemble de bibliothèques pour l’assistant de preuve Coq permettant d’écrire des programmes fonctionnels naïfs, et de les transformer en des versions plus efficaces qui peuvent être automatiquement parallélisées avant d’être extraites de Coq produisant ainsi du code Ocaml enrichi par des appels à la bibliothèque de programmation parallèle fonctionnelle Bulk Synchronous Parallel ML (BSML). Le cours est une introduction à l’assistant de preuves Coq et au système SyDPaCC pour le développement systématique de programmes parallèles corrects et vérifiés.

Construire et calculer dans un monde 2D

Diaporama : partie 1 et partie 2

Prendre en compte la dimension spatiale amène à considérer de nouvelles contraintes (place pour les données, transports de l’information…) et surtout à élargir les problématiques : Quelles seraient les primitives de « calcul » à considérer ? que peut-on construire ?

Dans un premier temps, nous proposons de faire un rapide tour d’horizon de ce contexte très fourni en terme de modèles (définition de polyèdre, règle et compas, juxtaposition de petits éléments…) comme de questionnements (engendrer des fractales, des figures simples, mener un calcul…)

Nous illustrerons cela dans deux contextes (un discret et un continu) :

  • tuiles auto-assemblantes : calcul et apparition de formes à partir de contraintes locales permettant ou non à des tuiles de s’assembler,
  • machines à signaux : les signaux permettent de mener des calculs discrets comme analogiques ainsi que de résoudre le problème de la halte.
    (Pavages et Automates cellulaires ne sont abordés que brièvement dans le cadre général car il ont déjà été traités dans des écoles récentes)

Contrôle des modèles probabilistes partiellement observable

Diaporama : partie 1 et partie 2

De nombreux domaines d’application nécessitent l’analyse de modèles probabilistes partiellement observables. Considérons par exemple le diagnostic de dysfonctionnements dans les réseaux de télécommunications. Le système chargé de la surveillance d’un tel réseau n’a accès qu’à une connaissance partielle de l’état de chacun des composants, et les pannes sont abstraites de manière naturelle par des événements aléatoires. De façon analogue, la gestion du trafic ferroviaire repose sur des capteurs de position des trains, et les informations qu’ils remontent doivent être interprétées pour contrôler au mieux la vitesse et l’espacement des trains. La modélisation de telles applications nécessite un cadre qui combine trois aspects importants : contrôle, probabilités, et observation partielle.

L’objectif de ce chapitre est de passer en revue les problèmes de contrôle pour plusieurs modèles formels qui combinent probabilités et observation partielle.

Dans un premier temps, on s’intéressera aux automates probabilistes (PA), où le contrôleur, dépourvu d’observations, doit interagir avec un environnement afin d’atteindre un objectif avec une probabilité maximale. Nous étudierons d’abord les
automates probabilistes du point de vue de la théorie des langages en établissant comment leur expressivité se compare à celle de familles classiques de langages. On présentera également leurs propriétés de clôture. Puis, on détaillera les problèmes de
décision relatifs au contrôle des automates probabilistes. En particulier, on montrera que l’équivalence est décidable pour les automates probabilistes, mais que l’existence d’un contrôleur garantissant une probabilité supérieure à un seuil fixé est un problème indécidable. D’autres résultats plus récents d’indécidabilité seront aussi présentés.

Nous introduirons ensuite les processus de décision markoviens partiellement observables (POMDP). Ce modèle généralise celui des PA puisque le contrôleur a accès au cours de l’exécution du système à une information partielle sur l’état courant. Les POMDP étendent également les processus de décision markoviens (MDP) pour lesquels l’observation est parfaite. On développera un algorithme de synthèse d’une politique optimale de contrôle à horizon fini, c’est-à-dire lorsque le nombre d’étapes est fini et
fixé à l’avance. Puis, on étudiera des problèmes d’optimisation à horizon infini, en détaillant pour des propriétés qualitatives (c.-à-d. où on requiert une probabilité positive ou égale à 1 d’atteindre un objectif), les résultats de décidabilité et de complexité. D’un point de vue applicatif, on montrera comment les POMDP permettent de spécifier et d’analyser le problème du diagnostic actif de panne, correspondant à la recherche d’un contrôleur garantissant la diagnosticabilité du système.

Enfin, nous évoquerons le cas plus général des jeux stochastiques à signaux. Ce modèle classique en théorie des jeux étend les modèles précédents en exprimant l’interaction de deux joueurs partiellement informés dans un environnement probabiliste. Après avoir établi pour quels objectifs de gain ces jeux sont déterminés} (c.-à-d. pour lesquels l’un des deux joueurs a une stratégie gagnante), nous présenterons les principaux résultats de décidabilité et d’indécidabilité pour les jeux stochastiques à signaux.

Résolution de systèmes polynomiaux sur les réels et applications

Diaporama

Les systèmes polynomiaux apparaissent dans de très nombreuses applications en sciences de l’ingénieur (robotique, mécanique, biologie…), en géométrie algorithmique, bio-informatique, vérification… Dans la plupart des cas, ce sont des informations sur l’ensemble des solutions réelles de ces systèmes qui sont recherchées. Le caractère non-linéaire de ces systèmes rend parfois l’usage de méthodes numériques relativement délicat. Aussi, ce cours se concentrera sur l’usage de techniques relevant du calcul formel pour résoudre ces systèmes.

Les problèmes algorithmiques abordés, pertinents du point de vue des applications, sont le test d’existence de solutions, l’élimination des quantificateurs sur les réels (ici on ne considérera qu’un bloc de quantificateur) ou encore les tests de connexité. Ces dernières décennies ont vu l’émergence d’algorithmes de complexité simplement exponentielle en le nombre de variables pour résoudre ces problèmes. Dans ce cours, on expliquera pourquoi ces complexités sont optimales et on introduira les objets et techniques relevant de l’optimisation polynomiale permettant d’obtenir des implantations efficaces d’algorithmes dans ces classes de complexité.