Emploi du temps

semaine 2 (atelier):

status report: tous les jours à 18h (dans la grande salle)

• lundi:matin: git + fichiers python + projets Euler / apres-midi: présentations + continuation du projet Euler
• mardi: matin: gestion de listes (Thierry) / apres-midi: présentations
• mercredi: matin: correction exos (Vincent) + diamant aztèque (Vincent) + demo Euler 178 (Jacopo-Odile) / apres-midi: classes (Vincent) + décorateurs (Nadia)
• jeudi: ?
  
• vendredi: ?
  

semaine 1 (école):

Matin (du lundi au vendredi):

• cours 1 de 9h00 à 10H30
• cours 2 de 10h45 à 12h15

Repas: 12h30

Après-midi à partir de 14h (du lundi au vendredi)

• séances d'exercices
• travaux pratiques sur machine

Repas: 19h30

• Lundi: Michael Rao 1 et Ana  Bušić 1
• Mardi: Bruno Salvy 1 et Xavier Goaoc 1
• Mercredi: Ana Bušić 2 et Michael Rao 2
• Jeudi: Bruno Salvy 2 et TP sur le diamant Aztèque
• Vendredi: Xavier Goaoc 2 et Ana  Bušić 3

Ana Bušić Chaînes de Markov (3 x 1h30)

Le cours commencera par une introduction rapide aux chaînes de Markov et quelques algorithmes pour calculer la distribution stationnaire d'une chaîne de Markov ergodique avec un espace d’états fini. Nous allons ensuite considérer la comparaison des chaînes de Markov et au calcul des bornes pour des distributions stationnaires ou transitoires.

La deuxième partie du cours portera sur des techniques de simulation des chaînes de Markov et des applications à la génération aléatoire des objets combinatoires. Si le temps le permet, nous allons finir par une introduction aux processus markoviens de décision, avec comme l'exemple le problème du contrôle optimal à l'horizon fini et le problème du plus court chemin stochastique.

Xavier Goaoc Programmation linéaire et problèmes LP-type (2 x 1h30)

Le premier cours proposera une introduction rapide à la programmation linéaire (formulations LP, méthode du simplexe, programmation entière et relaxation, dualité) en insistant sur ses aspects géométriques. Le second cours traitera d'approches combinatoires pour la programmation linéaire développées en géométrie algorithmique et s'appliquant à un grand nombre de problèmes d'optimisation géométrique (par exemple au calcul de boule englobante minimale).

Michael Rao Preuves assistées par ordinateur et exploration combinatoire (2 x 1h30)

L'ordinateur est de plus en plus sollicité dans les démonstrations de théorèmes mathématiques. J'introduirai le sujet en parlant du théorème des 4 couleurs, son histoire et sa preuve. Il s'agit du premier résultat important démontré avec l'aide d'un ordinateur. Cet exemple illustre bien les avantages et problématiques de ce genre d'approche. Dans un deuxième temps, je présenterai quelques outils classiques de l'exploration combinatoire: réduction à un problème SAT ou un programme linéaire, backtracking, programmation dynamique... Finalement, je parlerai d'exemples plus concrets et de différentes approches pour accélérer les explorations: diminution de l'espace de recherche, heuristiques, et un peu de méthodologie pour optimiser vos programmes.

Bruno Salvy Calcul formel (2x 1h30)

Euler, Gauss, Ramanujan et de nombreux autres calculaient énormément d'exemples pour raffiner leur intuition des phénomènes qu'ils étudiaient. Le mathématicien hongrois George Pólya disait quant à lui ``Finished mathematics consists of proofs, but mathematics in the making consists of guesses''. Aujourd'hui, les systèmes de calcul formel allègent énormément la charge de calcul non seulement numérique, mais aussi symbolique, en manipulant sans se tromper des formules gigantesques. Ils permettent de ce fait d'atteindre des exemples qui ne soient pas de simples jouets. Cette possibilité change la donne. Ainsi, une vieille conjecture de combinatoire a été résolue récemment par des expériences de grande taille, menant d'abord à une conjecture sur l'algébricité d'une série, puis à une preuve informatisée sur des polynômes de degré énorme; les records récents de calculs de décimales de pi reposent quant à eux sur une formule découverte expérimentalement en 1995, puis prouvée facilement.