Descriptif

Ce module sera décomposé en trois parties indépendantes :

La première partie consacrée à la résolution des grands systèmes d’équations et des systèmes creux sera organisée sur 6 heures et montrera comment gérer la taille et la vacuité d'un grand système, comment éviter et détecter les problèmes de conditionnement de système. On y abordera la prévision de temps calcul et l'estimation de RAM requise et le réordonnancement d'équations et de variables en vue d'optimiser le temps calcul requis.

La seconde partie consacrée la découverte et la modélisation de problèmes combinatoires à l’aide de la théorie des graphes sur 9 heures et organisée de la manière suivante :

• 3h d’introduction aux concepts et définitions nécessaires ;
• 3*1.5h de TD qui aborderont les concepts de connexité et cheminement, arbres et plus courts chemins, et enfin coloration et couplages ;
• 5h de présentation et appréhension du travail proposé en TAPE.

La troisième partie consacrée aux notions de complexité des problèmes combinatoires sera organisée 6 heures de la manière suivante :

• 5h de présentation des concepts essentiels en théorie de la complexité : Machine de Turing, réduction polynomiale, etc. ;
• 3h de TD pour apprendre à formaliser une réduction polynomiale et ainsi classer la complexité d’un nouveau problème ;
• 5h de présentation de la seconde partie du travail à effectuer en TAPE.

Pour terminer, la mise en pratique de la modélisation, de la résolution et de l’analyse d’un problème combinatoire sera faite au travers d’un travail en groupe et autonomie sur 7.5 heures. 2 séances seront par ailleurs consacrées à la présentation de ce travail TAPE au fil du module.