Abstract FR:

Le sujet de cette thèse est l'étude des problèmes d'algèbre linéaire du point de vue de leur calcul et de leur vérification. Les problèmes de calcul sont dans nc2. On dit que leur vérification est facile lorsqu'elle est dans nc1. On présente différents modèles de vérification, dont les modèles probabilistes comme les testeurs d'instance (Blum), les preuves interactives et les preuves transparentes, puis des modèles de calculs parallèles. On décrit ensuite la classe Det des problèmes réductibles au calcul du déterminant d'une matrice d'entiers. Alors que certains problèmes sont faciles à vérifier, le problème de vérification du déterminant v-Det est difficile à calculer dans le sens suivant: si v-Det est dans nc1 alors les classes de complexité l et nl sont égales. On isole la classe v-Det des problèmes réductibles à v-Det qui contient d'autres problèmes difficiles. On montre ensuite l'existence de testeurs d'instance parallèles nc1 pour chaque programme p qui calcule une fonction complète f dans la classe Det et on donne une procédure pour les construire. Par définition, un testeur d'instance utilise p comme oracle pour vérifier avec une grande probabilité que p calcule f effectivement. Les testeurs que nous introduisons, vérifient en parallèle avec une probabilité 1. La dernière partie de l'étude est consacrée au problème de l'implantation de ces algorithmes sur une machine massivement parallèle, la connection machine 2. On s'attache à montrer l'importance des algorithmes de routage probabilistes pour obtenir des algorithmes dont le comportement suit l'analyse théorique de la complexité