En cette époque de superordinateurs, il pourrait être difficile de croire que certains problèmes mathématiques sont encore trop complexes pour être résolus à l'aide d'un ordinateur. Pourtant, la puissance de traitement brute a bel et bien échoué, et Mme Vida Dujmović s'efforce de négocier un compromis mathématique avec la machine. Si c'est trop demander à l'ordinateur de donner toute la réponse, il peut au moins en fournir une partie.
En raisonnant ainsi, la récente titulaire d'un doctorat en informatique de l'Université McGill a trouvé des solutions aux problèmes mathématiques qui mettent des bâtons dans les roues des scientifiques depuis des années. Ses découvertes pourraient avoir des applications dans des secteurs allant du génie à la génétique et lui ont permis de remporter un Prix de doctorat du CRSNG de 2005 – l'un des prix les plus prestigieux décernés au Canada aux étudiants au doctorat.
Mme Dujmović concentre son attention sur les graphiques mathématiques. Il ne s'agit pas de graphiques statistiques, mais plutôt de structures mathématiques utilisées pour représenter les liens entre différents objets. Par exemple, Internet peut être représenté visuellement par un graphique. Chaque ordinateur constitue un nœud sur le graphique, et chaque connexion est appelée une arête.
Le défi que posent les graphiques du monde réel est qu'ils doivent être représentés visuellement d'une façon qui est facile à lire ou à réaliser.
« Lorsque le dessin d'un graphique est affiché sur une page ou sur un écran d'ordinateur ou qu'il est utilisé pour la conception de circuits intégrés, il est important de restreindre la surface du dessin pour éviter la perte d'espace, et la plupart du temps, l'idée qu'on se fait d'un beau dessin graphique, quel que soit le but de ce dernier, est celle d'un dessin n'ayant aucun croisement d'arêtes ou très peu », explique Mme Dujmović, qui reçoit actuellement l'appui du CRSNG à titre de stagiaire postdoctorale à la Carleton University à Ottawa.
Cependant, de nombreux problèmes graphiques, appelés « problèmes insolubles », sont simplement trop difficiles à résoudre par des calculs à moins qu'on y attelle un ordinateur pendant des jours ou des mois.
Plutôt que d'essayer de résoudre tout le problème, Mme Dujmović et sa directrice de thèse, Mme Sue Whitesides, ont développé des algorithmes efficaces, ou commandes de calcul, qui résolvent ces problèmes en tentant de trouver la meilleure solution possible lorsqu'il est impossible d'obtenir la solution parfaite. Appelés « algorithmes résolubles à paramètre fixe », ils sont capables de résoudre rapidement des problèmes graphiques autrement insolubles en établissant un paramètre fixe, tel un maximum de 100 croisements d'arêtes, comme constante. À partir de données à entrer dans un graphique, l'algorithme génère automatiquement un dessin bidimensionnel comportant un petit nombre de croisements d'arêtes.
Ces travaux de doctorat ont également chamboulé le domaine des graphiques tridimensionnels. Dans ce domaine, le défi, semblable à l'organisation de vêtements dans une valise pleine à craquer, consiste à insérer le graphique dans le plus petit volume possible. Mme Dujmović a découvert des types de graphiques pour lesquels il existe toujours des tracés tridimensionnels de petit volume « sans croisement ».
Actuellement, elle essaie encore de découvrir des algorithmes de graphes toujours plus rapides et toujours meilleurs.
« Je ne sais pas quelle différence pratique mes travaux pourront susciter, commente la scientifique au sujet de ses travaux théoriques. Ce qui nous intéresse vraiment, c'est d'étudier l'essentiel des choses. En général, on ne peut pas toujours prévoir quels progrès scientifiques entraîneront ce genre d'avantages pratiques. Parfois, ce sont les progrès qui semblent les plus difficilement applicables qui font la différence. »