« Quand est-ce que les gens comprendront que la complexité est une notion mathématique faisant appel à des concepts d'infinis qui n'existent pas en informatique ? »
On t'a déjà répondu en partie, mais juste pour préciser : j'ai fait exprès de parler de complexités spatiale et temporelle ; il y a bien une notion « physique » dans ces deux types de complexité.
Ensuite, une fois qu'on a un algorithme qui dans le cas général est correct, il faut encore se pencher sur une implémentation efficace.
Oui, il existe des cas où la complexité théorique n'est pas si importante. J'ai en tête un exemple assez frappant :
1°) Pour pouvoir mettre sous forme SSA un programme ( http://en.wikipedia.org/wiki/Static_single_assignment_form ) il faut construire des frontières de domination (dominance frontiers en Anglais). Il existe un algorithme, avec une complexité théorique qui pour le moment n'a pas été améliorée (ou alors juste ses constantes).
2°) Les auteurs d'un papier ont mis au point un algorithme ayant une complexité théorique moins bonne, mais
3°) La différence de complexité n'entre réellement en compte que lorsque le graphe de flot de contrôle (CFG, Control Flow Graph) totalise plus de 30 000 noeuds.
4°) Ça n'arrive presque jamais (en fait, je n'ai jamais vu un cas pareil, mais mon expérience de l'informatique est très petite).
5°) L'algorithme des auteurs est beaucoup plus simple à mettre en oeuvre
6°) Les auteurs de l'article ont tripatouillé à mort leurs structures de données
Résultat : en pratique, tant que les CFG sont en dessous de 30 000 noeuds, ils ont un algorithme qui va plus vite que les implémentations connues de l'algo classique, et qui, étant plus simple dans son énoncé, risque moins d'être sujet à bugs pour sa mise en oeuvre.
Dans cet exemple, on touche directement à la limite séparant la recherche de l'ingénierie. L'ingénierie concerne l'optimisation des structures de données ; la recherche la mise au point de l'algo ; le flou concerne le fait qu'on prend en compte la complexité, tout en faisant attention aux cas réels.
D'autre part, la complexité n'est pas qu'un outil mathématique. Elle donne des bornes, ce qui est très important pour l'implémentation. À quoi bon implémenter un algorithme de complexité O(m^n), par exemple ? Ou mieux : lorsqu'on demande à quelqu'un d'effectuer une tâche, et que ce quelqu'un parvient à démontrer que le problème donné à résoudre est NP-complet [1], il est temps de reformuler le problème, pour le circonscrire un peu plus. Je réagis assez vivement parce que tu donnes l'impression de croire que l'informatique théorique n'est que de la masturbation intellectuelle ; or ce n'est clairement pas le cas [2].
Quand on parle d'algorithmes répartis, par exemple, tu as intérêt à être sûr que ton algorithme converge, sinon tu vas au devant de grosses surprises. Là encore, les « maths » aident beaucoup (même si maintenant il existe tout un tas d'outils sympa pour aider l'infoteux à se dépatouiller de tout ça).
[1] Oui bon, OK, non seulement ça n'arrive pas tous les jours, mais en plus, ça prend du temps de le démontrer correctement.
[2] Y'a des exceptions, comme toujours. ;-)
[^] # Re: Plop !
Posté par lasher . En réponse au journal "L'informatique Paradoxale". Évalué à 5.
On t'a déjà répondu en partie, mais juste pour préciser : j'ai fait exprès de parler de complexités spatiale et temporelle ; il y a bien une notion « physique » dans ces deux types de complexité.
Ensuite, une fois qu'on a un algorithme qui dans le cas général est correct, il faut encore se pencher sur une implémentation efficace.
Oui, il existe des cas où la complexité théorique n'est pas si importante. J'ai en tête un exemple assez frappant :
1°) Pour pouvoir mettre sous forme SSA un programme ( http://en.wikipedia.org/wiki/Static_single_assignment_form ) il faut construire des frontières de domination (dominance frontiers en Anglais). Il existe un algorithme, avec une complexité théorique qui pour le moment n'a pas été améliorée (ou alors juste ses constantes).
2°) Les auteurs d'un papier ont mis au point un algorithme ayant une complexité théorique moins bonne, mais
3°) La différence de complexité n'entre réellement en compte que lorsque le graphe de flot de contrôle (CFG, Control Flow Graph) totalise plus de 30 000 noeuds.
4°) Ça n'arrive presque jamais (en fait, je n'ai jamais vu un cas pareil, mais mon expérience de l'informatique est très petite).
5°) L'algorithme des auteurs est beaucoup plus simple à mettre en oeuvre
6°) Les auteurs de l'article ont tripatouillé à mort leurs structures de données
Résultat : en pratique, tant que les CFG sont en dessous de 30 000 noeuds, ils ont un algorithme qui va plus vite que les implémentations connues de l'algo classique, et qui, étant plus simple dans son énoncé, risque moins d'être sujet à bugs pour sa mise en oeuvre.
Dans cet exemple, on touche directement à la limite séparant la recherche de l'ingénierie. L'ingénierie concerne l'optimisation des structures de données ; la recherche la mise au point de l'algo ; le flou concerne le fait qu'on prend en compte la complexité, tout en faisant attention aux cas réels.
D'autre part, la complexité n'est pas qu'un outil mathématique. Elle donne des bornes, ce qui est très important pour l'implémentation. À quoi bon implémenter un algorithme de complexité O(m^n), par exemple ? Ou mieux : lorsqu'on demande à quelqu'un d'effectuer une tâche, et que ce quelqu'un parvient à démontrer que le problème donné à résoudre est NP-complet [1], il est temps de reformuler le problème, pour le circonscrire un peu plus. Je réagis assez vivement parce que tu donnes l'impression de croire que l'informatique théorique n'est que de la masturbation intellectuelle ; or ce n'est clairement pas le cas [2].
Quand on parle d'algorithmes répartis, par exemple, tu as intérêt à être sûr que ton algorithme converge, sinon tu vas au devant de grosses surprises. Là encore, les « maths » aident beaucoup (même si maintenant il existe tout un tas d'outils sympa pour aider l'infoteux à se dépatouiller de tout ça).
[1] Oui bon, OK, non seulement ça n'arrive pas tous les jours, mais en plus, ça prend du temps de le démontrer correctement.
[2] Y'a des exceptions, comme toujours. ;-)