Séminaire de calcul formel et complexité (2014-2015)

Le séminaire a lieu environ deux fois par mois, les vendredis, de 10:30 à 12:00, salle 016, rez-de chaussée du bâtiment 22, Campus de Beaulieu

 


 

Prochaines séances

 

 

Du Lundi 3 novembre au Vendredi 7 novembre 2014

JNCF 2014 au CIRM  

Vendredi 21 novembre 2014
Audrey Tixier (INRIA Rocquencourt)
Titre: Reconstruction du couple (entrelaceur, code convolutif) à partir de données bruitées  

Résumé: Dans un contexte non-coopératif, des données sont observées sur un canal de communication bruité. Celles-ci correspondent à un ensemble de mots de code entrelacés et bruités. L'objectif est de retrouver l'information contenue dans ces données. Pour cela, il est nécessaire de reconstruire l'entrelaceur et le code correcteur utilisés. Les mots de codes sont entrelacés avant émission afin de contrer les erreurs survenant par paquet. L'entrelacement permet de répartir les erreurs sur plusieurs mots de code qui peuvent alors être corrigés et décodés. Par hypothèse, la longueur de l'entrelaceur est connue. Dans la littérature, il n'existe pas de méthode permettant de retrouver le couple (entrelaceur, code) sans hypothèse supplémentaire sur la structure de l'entrelaceur. De plus, dans les cas étudiés, les données sont sans erreur. Nous supposons que le code utilisé est un code convolutif et proposons une méthode qui retrouve efficacement l'entrelaceur et le code convolutif à partir de données bruités, connaissant uniquement la longueur de l'entrelaceur. Afin de reconnaître ce couple, trois étapes sont effectuées, la première consiste à retrouver un ensemble d'équations de parité vérifiées par les mots de code. Lors de la seconde étape, nous construisons un graphe associé à ces équations. Dans ce graphe, les sommets représentent une équation de parité et chaque arête symbolise un indice commun entre les deux équations qu'elle relie. Une notion d'équivalence de graphe est définie et permet la reconnaissance du code convolutif. Enfin, à partir de ce même graphe, nous réordonnons les équations de parité, cela permet alors de reconstruire l'entrelaceur.

Vendredi 28 novembre 2014
Pierre-Jean Spaenlehauer (INRIA Nancy)
Titre:  

Résumé:

 

 

 

Séances passées

 

Vendredi 19 septembre 2014
Xavier Caruso (IRMAR)
Titre: Résultants et sous-résultants de polynômes p-adiques 

Résumé: Expérimentalement, on constate que l'utilisation de l'algorithme d'Euclide étendu pour le calcul du PGCD et des coefficients de Bézout de deux polynômes p-adiques conduit à une importante instabilité numérique. En effet, pour des polynômes aléatoires unitaire de degré d, on déplore en moyenne une perte d'environ d/p chiffres significatifs sur chaque coefficient alors que la perte théorique n'est (en moyenne) que de 1/(p-1) chiffres significatifs ! Le but de cet exposé sera double. Je commencerai par énoncer un panel de résultats et conjectures sur les résultants et sous-résultants de polynômes p-adiques aléatoires et en déduirai les estimations sur les pertes de précision énoncées précédemment. Dans un deuxième temps, je présenterai une version « stabilisée » de l'algorithme de calcul des sous-résultants par les suites de pseudo-restes d'où je déduirai un algorithme de calcul de PGCD de polynômes p-adiques qui a une complexité équivalente à celle de l'algorithme d'Euclide mais réalise, à un chouia près, la perte de précision théorique optimale.

 

Vendredi 24 octobre 2014
David Lubicz (IRMAR)
Titre: Calculer des isogénies entre variétés abéliennes en temps quasi-optimal

Résumé: Dans cet exposé, on explique comment généraliser à la dimension supérieure le classique algorithme de Vélu qui permet de calculer une isogénie entre courbes elliptiques. Plus précisément, on explique comment à partir de la donnée d'une variété abélienne munie d'une polarisation principale ainsi qu'un noyau rationnel isotrope maximal pour le couplage de Weil, on peut calculer la variété abélienne quotient de manière efficace

 

 

 

Archives 2011-2014

 

Archives 2010-2011

 

Archives 2001-2010 :

 

Année 2001-2002, Année 2002-2003, Année 2003-2004, Année 2004-2005, Année 2005-2006, Année 2006-2007, Année 2007-2008, Année 2008-2009, Année 2009-2010