Arithmétique

Note aux collègues : les documents disponibles sur cette page et dont je suis l'auteur (ou co-auteur) sont placés sous GNU FDL et vous êtes libres de les utiliser. Vous trouverez ici le source LaTeX des devoirs, et là le code C d'illustration.

Bienvenue sur cette page consacrée au module LM220 (arithmétique) de la licence math-info de l'UPMC, pour lequel j'assure en cette fin d'année 2006 les TD du groupe 2, du groupe 1, partagé avec Nicolas Billerey, et parfois des groupes 8 et 9, prêtés par un collègue et néanmoins ami. Vous trouverez ci-dessous les ressources indispensables en pdf, ainsi que des illustrations en C de certains aspects du cours.

Le cours est assuré par Jean-Jacques Risler pour les étudiants orientés math, et par Alain Kraus pour le public à tendance un peu plus informatique. Un polycopié de cours très complet, débordant parfois de ce qui est traité en amphi et sera exigible à l'examen, a été rédigé par Alain Kraus et distribué en TD. Vous pouvez aussi le télécharger en pdf.

Vous trouverez d'autres informations intéressantes pour le TD sur la page d'Esther Aflalo, qui a généreusement conçu et tapé les feuilles d'exercices disponibles sur sa page ou ci-dessous. Par ailleurs, Nicolas Billerey tient à jour une autre page LM220 (plus disponible) avec notament la progression séance par séance des groupes dont il s'occupe. Enfin, il convient de mentionner la page officielle du module, avec notamment les annales de l'an dernier.

Les indispensables

À tout seigneur, tout honneur : le polycopié de cours. Je ne saurais trop vous rappeler à quel point sa fréquentation est enrichissante.

Fidèles compagnons du cours, les feuilles d'exercices. Elles reprennent certains des exercices du cours (mais pas tous), et en proposent bien d'autres. Ci-dessous disponibles en pdf, avec une brève description et les références aux parties du cours correspondantes.

  1. Euclide, Bézout, et le PGCD ; groupes. (Chap. 1 et 2.)
  2. Arithmétique dans Z et Z/nZ. (Chap. 4, sections 1 à 4.)
  3. Rivest, Shamir et Adleman. (Chap. 4, section 5.)
  4. Polynômes sur un corps, en une variable. (Chap. 5.)
  5. Corps finis. (Chap. 6)
  6. Codes correcteurs. (Chap. 7)

Enfin, après avoir bien travaillé, il n'est pas inutile de faire le point et de tester un peu la solidité de ses (vastes) connaissances. Pour ce faire, rien de mieux que quelques devoirs, surveillés ou non.

Histoire de valider définitivement les connaissances acquises durant le semestre, et pour respecter la tradition, l'examen pointe le bout de son nez.

Des illustrations

J'encourage tous les étudiants ayant un goût pour l'informatique, surtout ceux l'ayant choisie comme orientation, à essayer d'implémenter dans le langage de leur choix les méthodes vues en cours qui sont suffisament algorithmiques pour s'y prêter. Pour citer Knuth, « Science is what we understand well enough to explain to a computer. »

Joignant le geste à la parole, j'ai commis en C quelques fragments de code illustrant certains aspects du cours. Ceux-ci n'ont pas la prétention d'être un exemple de bonne programmation en C, en particulier la gestion des erreurs est souvent sommaire voire inexistante. De plus, je n'ai jamais tenté d'optimiser la vitesse d'exécution, ce qui n'est ni le but ici, ni dans le cadre de mes compétences.

Par contre, les algorithmes sont en principe tous mathématiquement corrects, pour peu que l'utilisateur entre des valeurs dans le domaine attendu (en particulier, non nulles quand il le faut). Merci de me signaler les éventuelles erreurs, voire de me proposer des implémentations plus élégantes si vous le souhaitez.

Les sources C des exemples sont disponibles en vrac ici. Ces fichiers font également l'objet de pages explicatives, et parfois digressives. Les thèmes illustrés sont :