Français Anglais
Accueil Annuaire Plan du site
Accueil > News du laboratoire > Séminaire Digiteo, 13 Février 2014, 14:30, Supélec, F.3.05
Séminaire Digiteo, 13 Février 2014, 14:30, Supélec, F.3.05
Séminaire Digiteo, 13 Février 2014, 14:30, Supélec, F.3.05 Séminaire Digiteo, 13 Février 2014, 14:30, Supélec, F.3.05
13 février 2014

Combien de mémoire ?
par Pierre Mc Kenzie, Université de Montréal et chaire Digiteo "Expressivity and computational complexity of counter machines"

Résumé : La théorie de la complexité du calcul cherche à quantifier les ressources (temps, mémoire, processeurs, etc.) requises à la résolution de tâches calculatoires. Cook en 1970 demandait si tout calcul polynomial peut être réorganisé de manière à réduire exponentiellement la quantité de mémoire nécessaire au calcul. Nous étudierons cette question sous l’angle d’un modèle de calcul appelé "branching program". à l’aide de tels programmes dédiésà la tâche d’évaluer un arbre (nous préciserons ce problème), nous développerons l’intuition qu’il n’est pas possible de comprimer la mémoire. Puis nous constaterons que malgré la force de cette intuition, celle-ci ne permet toujours pas aujourd’hui de répondre à la question posée et nous devons nous contenter de bornes de complexité affaiblies. Selon le temps disponible, nous terminerons avec un bref État de l’art.

(Résultats tirés en partie de Cook, McKenzie, Wehr, Braverman, Santhanam,
Pebbles and branching programs for tree evaluation, ACM TOCT 2012.)



Pour en savoir plus: http://www.digiteo.fr/deux-seminaires-digiteo-a-venir
News
George Manoussakis, lauréat 2018, prix de thèse (accessit) Charles Delorme
18 septembre 2018
George Manoussakis, est lauréat de prix de thèse (accessit) Ch. Delorme 2018. Il a soutenu sa thèse au LRI/Galac en Novembre 2017 sous la direction de J. Cohen et A. Deza. Depuis Septembre 2018 il est MdeC à l'Université de Versailles/Li-PaRAD.

TrackML dans Nature
21 janvier 2018
L'apprentissage automatique peut-il aider la physique des hautes énergies à découvrir et à caractériser de nouvelles particules ? TAO participe à l'organisation du challenge TrackML avec le CERN. La seconde phase de la compétition utilisera Codalab.

Un article de Isabelle Guyon sur la démocratisation de l'IA
19 mars 2018
Lien vers l'article paru dans le journal le monde :
http://www.lemonde.fr/acces-restreint/sciences/article/2018/04/08/a4544bd07cad09fe52980c0f82c08b34_5282548_1650684.html