Abstract FR:

Nous considerons une extension du modele de l'auto-test defini par blum, luby, et rubinfeld. Initialement, l'auto-test est une notion de test de programme informatique devant respecter certaines contraintes. Le programme est vu comme une boite noire completement inconnue, et le test doit etre de preference plus efficace que n'importe quel programme correct connu. L'auto-test a demontre son utilite dans des domaines aussi varies que le calcul numerique, la complexite structurelle, et les algorithmes d'approximation. Neanmoins a ce jour, seules les situations de calcul exact ou approche avec erreur absolue avaient ete considerees. Nous etendons pour la premiere fois la notion de l'auto-test a toute classe d'objets sans restriction, et validons ce nouveau concept sur deux modeles de calculs : - pour le calcul approche, nous construisons des auto-testeurs de fonctions lineaires, polynomiales, ou multilineaires ; - pour le calcul quantique, nous construisons des auto-testeurs de composants internes d'un circuit quantique, et en particulier d'ensembles universels et tolerants a l'erreur de portes quantiques. Pour parvenir a nos fins, nous developpons deux nouvelles methodes permettant de construire des auto-testeurs et qui reposent respectivement sur les tests approches et les equations probabilistes. Ainsi nous distingons tres nettement les problemes mathematiques de ceux algorithmiques sous-jacents a l'auto-test, et clarifions les analyses des auto-testeurs.