Algorithmique de base

Description du cours

  • Recherche dichotomique, tris, arbres. Complexité.
  • Algorithmes élémentaires pour les graphes.
  • Représentation des nombres entiers et réels, opérations élémentaires.
  • PGCD, PGCD étendu, théorème chinois et arithmétique modulaire.
  • Multiplication multiprécision (Schoolbook, Karatsuba, Toom-Cook, transformation de Fourier rapide si le temps le permet).
  • Inversion multiprécision (méthode de Newton, exponentiation, … ). Autres applications de la méthode de Newton (racine carrée).
  • Réduction modulaire (Réduction de Montgomery, bases normales et gaussiennes).
  • Opérations sur les polynômes (opérations élémentaires, PGCD, interpolation, relations coefficients/racines).
  • Méthodes de calcul approchées des fonctions usuelles.
  • Initiation au traitement de l’information (filtre, FFT, … ).

Si le temps le permet :

  • Localisation des racines de polynômes.
  • Factorisation des polynômes, en particulier sur les corps finis.

Compétences à acquérir

Analyse et mise en œuvre d’algorithmes sur un calculateur.

Mots-clés

Tri, graphes, arithmétique, polynomes, calcul modulaire.

Biographie des enseignants

Sylvain Duquesne est professeur en Mathématiques à l’Université de Rennes 1 depuis le 1er septembre 2008 et actuel directeur de l’IRMAR. Son domaine de recherche concerne la théorie des nombres et plus particulièrement l’arithmétique et l’algorithmique sur les courbes algébriques, ainsi que les applications en cryptographie. Il participe au projet SafeTLS soutenu par l’ANR.

Delphine Boucher est maître de conférences à l’Université de Rennes 1 et responsable de l’équipe Géométrie et Algèbre Effectives (GAE).

Marc Abboud actuellement en thèse sous la direction de Serge Cantat à l’Université de Rennes 1. Son sujet porte sur les degrés dynamiques des endomorphismes des surfaces affines complexes. Il est intéressé par la géométrie algébrique et par la cryptographie.

Ce site utilise des cookies afin d’améliorer votre expérience utilisateur et de réaliser des statistiques d’audience.
J'accepteJe refuseEn savoir plus