Colloquium
d'INformatique pour les
Élèves
CINÉ
Demandez le programme !
Programme 2010-2011.
Le séminaire se déroule un soir à 17h30 chaque mois
Lundi 6 Juin 2011 dans la salle de Réunion du LIX à 17h30. Antoine Chambert-Loir
Le fabuleux destin de la moyenne arithmético-géométrique.
Résumé:
''À la fin du 18e siècle, Gauss découvre que la moyenne arithmético-géométrique de deux nombres réels positifs (qu'avait découverte Legendre un peu avant) peut se calculer au moyen d'une intégrale. Elle permet notamment de calculer la longueur de certaines courbes, alors appelées lemniscates. Ces courbes commencent à dévoiler toute leur importance au siècle suivant, sous la forme à peine déguisée des courbes elliptiques. Au 20e siècle, ces dernières sont un objet central de la géométrie algébrique et de l'arithmétique. Elles ont par exemple joué un rôle fondamental dans la solution par Wiles du grand théorème de Fermat. À la fin du 20e siècle, la découverte de la cryptographie à clef publique a donné d'autres applications de ces courbes elliptiques ; elle a aussi mis en avant de nouvelles questions, d'une nature effective (« computationelle ») dont l'intérêt était peut-être inattendu des arithméticiens. C'est là que resurgit la moyenne arithmético-géométrique de Legendre et Gauss.''
Jeudi 24 Mars 2011 dans la salle de Réunion du LIX à 17h30. Benoit Rittaud
Les suites de Fibonacci aléatoires
Résumé:
Une suite de Fibonacci est une suite dans laquelle chaque terme est la somme des deux qui le précèdent. Un résultat fondamental est que le facteur de croissance asymptotique d'une telle suite est égal au nombre d'or. Une généralisation possible est la notion de suite de Fibonacci aléatoire. Dans une telle suite, chaque nouveau terme est soit la somme, soit la différence (en valeur absolue) des deux termes précédents, selon le résultat du lancer d'une pièce de monnaie. La question se pose alors de savoir si une telle suite a, en un sens probabiliste, un facteur de croissance asymptotique. En d'autres termes, on recherche un équivalent du nombre d'or dans un cadre aléatoire.
Jeudi 4 Novembre 2010 dans la salle de Réunion du LIX à 17h30. Daniel Augot
Addition de Nim Codage, cryptographie et stéganographie élémentaires
Résumé:
Le jeu de Nim, ou de Marienbad, peut être encodé dans un état, qui correctement maintenu, permet d'établir une stratégie gagnante à coup sûr. Cet état repose sur l'addition de Nim, qui n'est autre que l'addition modulo 2, ou le «ou exclusif» (xor). Appliquée à des chaînes de bits, cette opération élémentaire permet rapidement d'obtenir des outils performants, comme le code de Hamming utilisé dans la mémoire ECC des cartes graphiques NVIDIA, et dans l'algorithme F5 en stéganographie. En cryptographie, le «ou exclusif» donne un principe de chiffrement sûr sans hypothèse algorithmique, le masque jetable (chiffrement de Vernam, one-time pad). Cet exposé fera un survol de ces outils, en indiquant aussi certaines questions non résolues qui se posent sur ces sujets.
Edition 2009-2010:
Jeudi 4 Mars, dans la salle de conférence du lix à 17h30. François Baccelli
Routage Espace--Temps
Résumé:
''Nous introduisons un graphe aléatoire utile à la modélisation du routage multi-sauts dans les réseaux ad hoc.
Ce graphe aléatoire a une dimension spatiale et une dimension temporelle. La dimension spatiale provient de la localisation des noeuds du réseau dans le plan euclidien et la dimension temporelle des fluctuations aléatoires des mécanismes d'accès multiples et des phénomènes d'évanouissement du signal liés à la propagation.
Ce graphe aléatoire code notamment le rapport signal à bruit et interférence de tous les canaux point-à-point du réseau, à tous les instants du temps. La donnée de ce graphe et d'un algorithme de routage multi-sauts détermine donc entièrement la progression des paquets dans le réseau lorsque les destinations de ces derniers sont elles aussi données.
Nous montrons que les routes optimales peuvent alors être analysées comme des problèmes de percolation de premier passage sur ce graphe aléatoire et nous donnons à la fois des résultats positifs et des résultats négatifs sur la finitude de la constante de temps associée.
Nous analysons aussi des algorithmes gloutons de routage géographique où le relais d'un émetteur, pour un paquet donné, est le noeud le plus proche de la destination du paquet dans l'ensemble des noeuds qui reçoivent ce dernier.''
Jeudi 4 Février. Jean-Christophe Filliâtre
Mon programme est-il correct ?
Lieu de l'exposé: Centre de Conférence du LIX
Résumé:
''L'histoire du logiciel, pourtant relativement courte, est déjà émaillée d'un grand nombre de faillites célèbres. Notre quotidien lui-même est régulièrement affecté par des erreurs logicielles et le mot << bug >> est passé sans mal dans le langage courant. Cet exposé donnera une introduction à la preuve de programmes, une activité visant à établir de manière irréfutable la correction d'un logiciel par une série de déductions logiques.''
Jeudi 14 Janvier. Jean-Yves Le Boudec, EPFL, Suisse
Simulation de Modèles de Mobilité : Paradoxes et Etrangetés
Lieu de l'exposé: Centre de Conférence du LIX
Résumé:
''Les ingénieurs qui développent des systèmes de communication mobile ont souvent recours à la simulation dans les phases de conception et de simulation. Bien que conceptuellement très simple, la simulation peut poser des problèmes parfois déroutants. Par exemple, des simulations de durées différentes donnent des résultats différents, et plus la simulation est longue, plus les résultats sont différents. Ces phénomènes peuvent être expliqués, et quelque fois entièrement évités, par la théorie des probabilités, et en particulier le calcul de Palm pour les processus ponctuels stationnaires – une théorie initialement développée dans le cadre des files d’attente.''
Jeudi 17 Décembre. Fredo Durand (MIT)
Fourier a la rescousse pour la photographie et la synthese d'images
Lieu de l'exposé: Centre de Conférence du LIX
Résumé:
''Une nouvelle analyse frequentielle de la propagation de la lumiere et de la formation d'images ouvre la porte a de nouvelles strategies de capture d'images qui reduisent le flou de bouge et de mise au point et a de nouveaux algorithmes plus rapides pour la simulation de l'eclairage.
Nous analysons des phenomenes tels que le transport lumineux, l'integration au cours de la duree d'exposition, ou le flou de mise au point en utilisant la transformee de Fourier de l'espace des rayons lumineux ou de l'espace-temps. Pour les applications en capture d'images, cela permets de comprendre la qualite de l'information enregistree et de deriver des bornes superieures. Nous avons ainsi pu developper denouvelles techniques de capture qui combine la modification du materiel avec un post-traitement logiciel pour reduire de facon importante le flou et le bruit en cas de mouvement ou d'augmenter la profondeur de champs. En synthese d'images, une analyse semblable permet de developper des techniques d'acceleration a base d'échantillonnage adaptatif et de reconstruction anisotrope pour limiter le bruit numerique lors de la simulation d'images realistes. ''
Jeudi 22 Octobre: Gilles Dowek (LIX, Ecole Polytechnique)
Une seconde révolution galiléenne
Lieu de l'exposé: Centre de Conférence du LIX
Résumé:
''L'introduction d'un nouveau concept scientifique permet souvent de donner de nouvelles réponses à des questions anciennes, qui n'avaient jusqu'alors reçu que des réponses imparfaites. Par exemple, l'introduction des notions d'atome et molécule a permis de donner de nouvelles réponses aux quesstions "qu'est que l'oxygène?", "qu'est-ce que l'eau?", "qu'est-ce qu'une réaction chimique?",.... Cet exposé présentera quelques questions qui ont trouvé de nouvelles réponses depuis que nous comprenons mieux la notion d'algorithme: "qu'est-ce qu'un aéroport?", "qu'est-ce qu'un nombre entier?", "qu'est-ce qu'une démonstration mathématique?", "qu'est-ce qu'une loi de la physique?",... La prise de conscience du caractère algorithmique de ces objets scientifiques, nous amène à considérer de nouveaux langages pour les décrire. Cette révolution, dans le langage dans laquelle la science s'écrit, peut-être comparée à la révolution qui s'est produite , au début du XVIIe siècle, quand le langage mathématique a commencé à être utilisé pour décrire des phénomènes physiques.''
Jeudi 17 Septembre: Vincent Blondel, Centre de conférence du CMAP
Vincent Blondel, Université catholique de Louvain (Belgique)
Fouille d'information dans les réseaux
Résumé:
''Les réseaux tels que le web, les réseaux sociaux ou les réseaux téléphoniques sont aujourd’hui omniprésents et nous disposons depuis peu des resources informatiques necessaires pour les enregistrer et les analyser. Dans cet exposé, je décrirai deux méthodes conçues récemment à l’Université de Louvain et qui permettent d'extraire de manière efficace de l’information dans de très grands réseaux.
En partant de la méthode de PageRank utilisée par Google, je montrerai d’abord comment calculer la similarités entre les sommet d’un graphe. Cette méthode simple a été appliquée, entre autre, à l'extraction automatique de synonymes dans un réseau construit au moyen d’un dictionnaire. Je décrirai ensuite un algorithme qui permet de détecter des communautés dans de très grands réseaux et je montrerai les resultats étonnants obtenus avec cet algorithme sur un réseau téléphonique de plus d’un milliard de connexions. ''
Edition 2008-2009:
Jeudi 2 avril: Pierre Alliez
Pierre Alliez, INRIA Sophia Antipolis – Méditerranée Traitement numérique de la géométrie
Résumé:
Le développement du multimédia a été possible grâce à des avancées théoriques et technologiques considérables dans le domaine du traitement du signal. Il est aujourd’hui à portée du grand public d’acquérir des images en haute définition, de transmettre des sons sur les réseaux et de visualiser des films en haute définition. Qu’en est-il de la géométrie ? On peut la voir comme la quatrième vague du multimédia après le son, les images et les vidéos, mais une forme géométrique complexe n’est pas un signal ordinaire. Ses propriétés distinctives (topologie, absence de paramétrisation globale, structure irrégulière) font qu’une simple adaptation des techniques développées en traitement du signal ne suffit pas. Au début de l’exposé j’expliquerai comment le traitement numérique de la géométrie est aujourd’hui un domaine d’étude à part entière, avec pour objectif de développer une théorie et des algorithmes pour l'échantillonnage, le traitement, la compression et la transmission de formes complexes sur les réseaux. Je présenterai ensuite une sélection de travaux de recherche en reconstruction, approximation et remaillage de surfaces. J’assortirai ma présentation de démonstrations.