Problème d'intuition
Par David Monniaux le mercredi, mars 6 2013, 22:03 - Théorie - Lien permanent
En ce moment, je travaille (entre autres) sur des algorithmes mettant en jeu des projections de polyèdres convexes. Une difficulté est de se représenter ce qui se passe : pour concevoir un algorithme, de prouver sa correction ou ses propriétés, il vaut mieux avoir une idée (au moins intuitive) de ce qui se passe, avant de passer au formel.
Nous nous représentons bien ce qui se passe en 1 dimension (une ligne), 2 dimensions (un plan, ce qui permet de tracer les choses sur une feuille ou un tableau), déjà un peu moins ce qui se passe en 3 dimensions quand la forme est un peu complexe, et nettement moins ce qui se passe en dimension supérieure.
Le problème est que les polyèdres en petite dimension ont des propriétés géométriques et combinatoires particulières. C'est particulièrement flagrant en 2 dimensions (polygones) : on peut arranger faces et sommets des polyèdres bornés en une liste circulaire sommet - face - sommet - face etc. Projeter 1 dimension à la fois a également des propriétés particulières.
Bref, pour ne pas me laisser guider par de fausses intuitions, il fallait au moins réfléchir à un polyèdre 4 dimensions qui s'envoie en 2 dimensions, et là je n'ai pas de vision graphique. Je dois m'en tenir à des espèces d'intuitions combinatoires (« il existe une solution basique du problème de programmation linéaire ») et des calculs sur le système d'inégalités.
Et vous, comment faites-vous ?
Commentaires
Personnellement, j'ai un running gag, à chaque fois que je fais une présentation, je dis "au tableau, je me limiterai à 2 dimensions".
Je travaille beaucoup sur des sous-ensembles de N^r pour un entier r, pour l'instant, j'ai de la chance, il me semble que en général sur les cas où je travaille (i.e. logique du premier ordre avec mod, <, et parfois +), je peux décrire l'algorithme pour N^2, N^3 (où j'ai encore de l'intuititon), et en général je me rend compte qu'en remplaçant 3 par r, il y a peu de changement à faire pour que la preuve reste correcte.
Haha ! Même problème pour raconter l'algèbre linéaire de dimension finie avec des taupins/licences.
Visualiser un plan coupé par une droite est suffisant pour une bonne partie des besoins quotidiens... Mais dès qu'on attaque des problèmes de type «Grasman» (dimension d'une somme de sous-ev), il serait sympa de pouvoir visualiser les choses en dimension 8, avec l'un de dimension 4, l'autre de dimension 3, et une intersection de dimension 2...
Le pire est lorsqu'on aborde la dimension infinie : qu'un hyperplan puisse être dense, c'est tout à fait invraisemblable avec l'idée géométrique qu'ils s'en sont légitimement fait !
@Gonzolino : dans l'espace vectoriel IR, sur le corps des rationnels, il y a même des droites denses !
Blague de matheux :
À une conférence, un mathématicien fait un exposé sur la topologie dans les espaces de dimension 9. À la fin, un étudiant un peu largué pose la question : "comment faites-vous pour visualiser aussi bien ce qui se passe en dimension 9 ?"
Réponse du mathématicien : "C'est simple, il suffit de comprendre ce qui se passe en dimension n, et de remplacer n par 9."