Mathématiques du numérique 3

Ce chapitre consiste essentiellement en la description des outils élémentaires d'analyse statistique, notamment l'ajustement linéaire et la corrélation pour des données bidimensionnelles.

Après la présentation des tableaux multidimensionnels, correspondant dans un espace à n dimensions à un nuage de points, ce chapitre présente la démarche d'analyse de ce nuage dans l'espace des individus et dans l'espace des variables. Cette étude nous amène directement à l'analyse factorielle en composantes principales, que nous détaillons sur un exemple. Le chapitre se termine par la présentation de deux logiciels usuels.

Ce chapitre aborde l'analyse de données dans un contexte spécifique : la catégorisation automatique d'une population à l'aide d'un processus automatisé. En introduction, une section définit les notions de similarité, de dissimilarité et de distance. Les sections suivantes sont consacrées, de manière détaillée, à la classification par partitionnement avec la méthode des centres mobiles (k-means) et à la classification hiérarchique.

S'il existe un outil pour optimiser une fonction soumise à des contraintes, c'est bien la programmation linéaire. Dans ce chapitre, nous détaillons cette méthode d'optimisation et son illustration géométrique. Une section est consacrée à l'algorithme du simplexe, détaillé avec des exemples. En extension de la programmation linéaire en nombres réels, une section introduit la programmation linéaire en nombres entiers en utilisant les coupes de Gomory et l'algorithme du "Branch and Bound".

Ce chapitre débute par la définition d'un graphe, ses représentations sous forme graphique et sous forme de tableau. La section suivante décrit la fermeture transitive d'un graphe orienté et sa décomposition en composantes fortement connexes. Une section est dédiée à des graphes particuliers, les arbres, où nous développerons la notion d'arbres couvrants. Le chapitre se termine par la recherche d'arbres couvrants extrêmes.

Ce chapitre constitue une première application de la théorie des graphes : la recherche du chemin le plus court ou le plus long. Nous passerons en revue quelques méthodes de résolution : méthode des niveaux, méthode par énumération, algorithme de Ford, algorithme de Bellman-Kalaba, algorithme de Dijkstra.

Ce chapitre décrit trois types de problèmes : le problème du flot maximal avec l'algorithme de Ford-Fulkerson, le problème du transport à coût minimal avec les algorithmes du coin Nord-Ouest, du moindre coût, de Balas-Hammer, du stepping stone avec la méthode des potentiels, et le problème d'affectation avec l'algorithme hongrois.

Dans ce chapitre, deux types de problèmes sont examinés : la planification de projet et l'ordonnancement d'ateliers. Dans la section sur la planification d'un projet, une méthode générale de résolution est présentée, à savoir la méthode des dates au plus tôt et des dates au plus tard. Dans la section sur l’ordonnancement d’ateliers, deux problèmes sont examinés : le flow-shop et le job-shop avec l’algorithme de Johnson.