Dans les années 1950, un certain nombre de méthodes de minimisation des circuits pour les fonctions booléennes ont été inventées. Existe-t-il une extension de ces méthodes ou quelque chose de similaire pour optimiser la complexité temporelle ou spatiale des algorithmes?
Par exemple, une implémentation du tri à bulles en entrée d'un tel algorithme produirait une implémentation d'un algorithme de tri avec une complexité temporelle plus proche de.
Réponses:
Recherchez le théorème d'accélération de Blum (oui, cet article est moins qu'informatif; regardez un livre sur la théorie de la complexité). Il dit essentiellement qu'il existe des programmes pour lesquels il existe un programme qui fait le même travail qui est plus rapide par n'importe quelle marge spécifiée pour presque toutes les données d'entrée.
Selon le théorème de Rice , il est impossible de savoir si deux programmes donnés font le même travail.
Oui, pour certaines notions très restreintes de "programme", étant donné un exemple, on peut construire le "meilleur programme" possible pour le travail. Des cours importants, même. Mais très loin de tout ce qui est capable d'exprimer des bulles.
la source