Pour répondre "quels problèmes peuvent être résolus par l'informatique", nous avons développé la théorie de la calculabilité. Pour les problèmes qui sont calculables, existe-t-il une théorie pour répondre à la question "est-ce que le programme est le plus simple"?
Je ne pense pas que la complexité informatique réponde à la question. Je pense qu'il considère le temps dont nous avons besoin (bien que mesuré de manière abstraite).
Je ne sais pas si la théorie algorithmique de l'information répond à la question. Il semble que la théorie parle de taille, où l'équivalence de taille minimale et la plus simple ne m'est pas évidente (enfin, au moins, ils me semblent différents).
Je pense que la théorie devrait au moins définir une relation "simple" ou "plus simple que".
Je suis maintenant convaincu que je devrais me pencher sur la complexité de Kolmogorov. Cependant, je voudrais expliquer ce que je pensais lorsque je posais la question.
Lorsque j'améliore un programme, j'essaie de réduire les connexions inutiles entre les différentes parties du programme (peut-être en divisant à nouveau les parties afin qu'il puisse y avoir moins ou des connexions plus faibles). Comme les connexions sont réduites, le programme semble "plus simple". D'où le choix du mot «simple» lorsque je formule la question. Il est très probable que la taille du programme diminue également, mais c'est un bon effet secondaire, et non l'objectif principal. De toute évidence, le processus d'amélioration ne peut pas durer indéfiniment. Il y a un point que je devrais arrêter. Si, seulement en considérant la "structure" (désolé pour un autre concept non défini) ou la "relation", puis-je me convaincre que rien de plus ne peut être fait?
Voici une meilleure description de ma notion de complexité.
Olaf Sporns (2007) Complexité . Scholarpedia , 2 (10): 1623
Réponses:
Ce problème est étudié dans la théorie algorithmique de l'information. Ce que vous définissez s'appelle la complexité de Kolmogorov-Chaitin.
http://en.wikipedia.org/wiki/Kolmogorov_complexity
Et il semble que la notion de simplicité dont vous avez besoin puisse être formalisée via la notion de mesure de complexité, formalisée par les axiomes de Blum.
http://en.wikipedia.org/wiki/Blum_axioms
Il semble également qu'il soit possible de généraliser la complexité de Kolmogorov pour prendre en compte d'autres mesures de complexité. Voir référence ci-dessous. (L'article de Wikipedia sur la complexité de Kolmogorov aborde ce problème.)
Burgin1990- Complexité kolmogorov généralisée et autres mesures de double complexité Cybernétique et analyse des systèmes Volume 26, Numéro 4, 481-490
la source
La réponse à la première question est oui, il y a une théorie, c'est la théorie de l'information algorithmique et celles-ci sont appelées programmes élégants (par Gregory Chaitin).
Pour la deuxième question sur "est-ce que le programme est le plus simple"?
Il n'y a pas de réponse , car c'est une question non calculable, il n'est pas possible de prouver qu'un programme est un programme élégant.
J'ai mis une réponse pour ajouter la mention des programmes élégants .
la source
Il existe différents types d'approche pour décider ce qu'est un code simple et ce qui ne l'est pas.
Mais malheureusement, il n'y a pas de moyen automatique de le déterminer, par exemple, la complexité de Kolmogorov échoue avec les fonctions récursives, certaines fonctions récursives (logique profonde) sont simples mais la compréhension n'est pas si simple.
D'après mon expérience, notre équipe travaillait dans un système et nous avons trouvé une procédure "simple" dans Oracle (pas plus de 50 lignes) ... et nous avons essayé de la comprendre, il a fallu 2 mois (et plusieurs réunions) pour bien comprendre non pas par la complexité du code mais par la logique derrière chaque variable.
Je pense que la façon de déterminer à quel point un code est simple est: "lire un code et considérer le temps utilisé pour le comprendre".
Alors "Le programme le plus simple pour résoudre un problème?" peut être divisé en:
a) simplicité du code (code clair) mais il est trop subjectif.
b) surcomplexité de la fonction, si j'ai un problème avec X, je dois résoudre la tâche DX (Delta X) pour le résoudre, où DX doit tendre vers X.
Par exemple, si mon problème est (un) de "peler une pomme" et que je dois le faire en PHP (et en langage) alors
si je suis extrêmement chanceux et que PHP a la fonction function_peel_apple () alors c'est le code le plus simple jamais X = 1 DX = 1, il suffit d'appeler la fonction et c'est tout !.
En revanche, si je ne suis pas aussi chanceux mais qu'il existe la fonction function_peel () et function_get_apple () alors X = 1 (un problème) et DX = 2 (deux tâches).
Si, dans le pire des cas, il n'existe aucune fonction, alors je dois en créer une (ou plusieurs) par moi-même et ajouter plusieurs tâches avant de résoudre le problème, maintenant c'est un programme complexe.
la source