Bachmann Paul

En 1864, à Breslau, Paul Bachmann obtient son habilitation, deux ans après un doctorat dirigé par Kummer et consacré à la théorie des groupes. Il avait étudié à Berlin, puis il enseigne à Breslau et à Münster.

Sa trace la plus familière aujourd’hui est le grand O, noté O(f). Cette écriture compare le comportement asymptotique de fonctions et sert notamment à caractériser la complexité d’un algorithme.

Paul Bachmann est un mathématicien allemand né en 1837 et mort en 1920. Spécialiste de théorie des nombres, il étudie à Berlin. Il obtient en 1862 un doctorat dirigé par Kummer, avec une thèse sur la théorie des groupes, puis son habilitation en 1864 à Breslau. Il enseigne ensuite à Breslau et à Münster.

Son œuvre principale est Zahlentheorie, ou Théorie des nombres, un traité en six volumes publié de 1872 à 1923. Un ouvrage en deux volumes sur la théorie élémentaire des nombres, publié de 1902 à 1910, complète cet ensemble. Ces deux intervalles de publication permettent de situer l’ampleur chronologique de ses travaux édités.

Bachmann est l’inventeur de la notation grand O, écrite O(f), où la lettre f représente une fonction de comparaison. Le grand O appartient aux notations de Landau, employées pour comparer asymptotiquement des fonctions. En informatique, cette notation caractérise notamment la complexité algorithmique. Paul Bachmann ne doit pas être confondu avec son petit-fils, le mathématicien Friedrich Bachmann.

Pour lire concrètement un grand O, comparons deux traitements appliqués à une liste de n éléments : le premier parcourt la liste une fois ; le second compare chaque élément à tous les autres.

1. La taille de l’entrée est n, le nombre d’éléments de la liste.
2. Le premier traitement effectue un nombre d’opérations proportionnel à n : son coût est en O(n).
3. Le second effectue un nombre de comparaisons proportionnel à n² : son coût est en O(n²).
4. Si n est multiplié par 10, le premier coût est multiplié approximativement par 10, tandis que le second l’est approximativement par 100.
5. On conclut que le traitement en O(n²) croît plus vite que celui en O(n) lorsque la liste s’allonge.

Ce classement ne prédit ni une durée en secondes ni le coût exact pour une taille donnée : il retient le rythme de croissance quand n devient grand. Des constantes, le matériel ou la manière de programmer peuvent encore départager deux traitements appartenant à une même classe.

Dans un texte d’informatique, le grand O compare la façon dont un coût augmente quand la taille n de l’entrée grandit. Parcourir une liste une seule fois demande un nombre d’opérations proportionnel à n : ce coût se classe en O(n). Comparer chaque élément à tous les autres demande un nombre de comparaisons proportionnel à n² : ce coût se classe en O(n²). Le second augmente donc plus vite que le premier lorsque n grandit. Cette lecture compare des rythmes de croissance ; elle ne donne pas le temps d’exécution exact.

Dans une bibliographie, le titre Zahlentheorie signale le traité en six volumes publié de 1872 à 1923. Si la référence annonce deux volumes et les années 1902 à 1910, elle renvoie plutôt à l’ouvrage sur la théorie élémentaire des nombres.

Dans une histoire des mathématiques, il est utile de séparer la formation de Bachmann de sa spécialisation ultérieure. Sa thèse de 1862 relève de la théorie des groupes, tandis que son œuvre maîtresse relève de la théorie des nombres.

Paul Bachmann et Friedrich Bachmann. Paul Bachmann, né en 1837, est le grand-père de Friedrich Bachmann. Une mention du petit-fils ne désigne donc pas l’inventeur de la notation grand O.

Le grand O et les notations de Landau. Le grand O est l’une des notations de Landau, et non un autre nom pour leur ensemble. La présence précise de O(f) désigne le grand O ; une référence générale aux notations de Landau est plus large.

Une publication postérieure à 1920. Le traité Zahlentheorie est donné comme publié jusqu’en 1923, alors que Bachmann meurt en 1920. Il ne faut donc pas supposer que les six volumes ont tous paru de son vivant.

Une spécialité ne résume pas la thèse. Bachmann est présenté comme spécialiste de théorie des nombres, mais sa thèse de 1862 porte sur la théorie des groupes. Il faut rattacher chaque indication au moment précis du parcours.

Une attribution circonscrite. La source attribue à Bachmann l’invention de la notation grand O. Elle ne lui attribue pas l’ensemble des notations de Landau ; étendre l’attribution au-delà du grand O serait injustifié.

Le glossaire Grand O prolonge le portrait par la notation associée au nom de Bachmann et par son rôle dans les comparaisons asymptotiques.

La page notation de Landau replace le grand O dans la famille de notations à laquelle il appartient.

L’entrée arithmétique ouvre sur le domaine auquel se rattache la théorie des nombres étudiée par Bachmann.