Les modules Mathématiques pour l’informatique I et II contiennent des cours magistraux, des travaux dirigés et des travaux pratiques. Le langage de programmation pour ces derniers est python.
Voici les projets qui ont été prévus pour l’an 2012-2013. Ce qui est marqué supplément doit probablement être réservé aux cours de L3 Math-Info.
Peu de démonstration dans ce cours. Mise en place algorithmique de nombreuses notions élémentaires de mathématiques, certaines introduites depuis le lycée, permettant de résoudre des problèmes. Nettement plus orienté vers le calcul que vers la démonstration. Néanmoins, exigence d’une écriture cohérente : le sens d’une phrase mathématique est comparable au type d’une expression dans un langage informatique. Il est indispensable d’éviter les erreurs de syntaxe.
Algorithmes pour l’arithmétique des entiers
C’est à peu près le début du Demazure, chap. 1 et une partie du 2. Le but est d’initier à l’écriture d’algorithmes récursifs terminaux, sur des objets mathématiquement simples.
Nombres et polynômes
Le but est de maîtriser les calculs algébriques de base.
Nombres rationnels, décimaux, complexes :
- Encodages divers : couples (rationnels, complexes), virgule fixe ou flottante.
- Supplément : fractions continues.
- Résolution d’équations de degré deux, voire trois.
- Algorithmes numériques pour racine n-ième, exponentielle et logarithme.
Supplément : entiers de Gauss, entiers quadratiques
et aussi division selon les puissances croissante ; décomposition en éléments simples de fractions rationnelles. Supplément : FFT, application à la mutliplication.
Appartenance, inclusion, union— intersection— produit cartésien (binaires), ensemble des parties ; relation, fonction, application, in/sur/bi-jection, familles et suites, dénombrabilité ; union— intersection— produit cartésien (familles). Représentation des fonctions.
Calculs récursifs. Énumérations de sous-suites, de parties. Groupe des permutations, énumération, diverses représentations.
Extensions des opérations sur les polynômes aux séries formelles ; inverse, composition, réciproque, exponentiation, logarithme.
Géométrie plane et dans l’espace
Concrétisation de notions déjà vues, certaines depuis le lycée.
Relations, graphes, et récursion.
Relations d’équivallence et relations d’ordre. Représentations. Fermetures, quotients des relations. Graphes orientés sans cycles (dag). Ordre bien fondé. Récursion structurelle. Arbres. Suppléments : Ensembles de termes et réécritures. Chemins dans les graphes. Algorithme de Tarjan. Suppléments : application à 2-sat.