Programme de la 2e année
Note
Ce site est un complément. Les notions de ce site (suites numériques, récursivité, analyse d'algorithmes, structures de données) ne sont pas des modules de l'épreuve E3 de mathématiques pour l'informatique. Elles servent la programmation, la poursuite d'études (licence ou école d'ingénieurs en informatique) et la culture algorithmique d'un technicien supérieur. Le programme de l'épreuve (arithmétique, calcul matriciel, logique et ensembles, graphes et ordonnancement, algorithmique appliquée) est traité dans le site de 1re année et révisé dans la phase A.
Exception : les suites numériques. Elles ne sont pas au programme de l'épreuve E3, mais elles sont l'un des six modules de l'unité facultative UF2 « mathématiques approfondies ». La phase 1 sert donc aussi de préparation à cette option : voir la phase B.
Principe
Quatre phases, 19 séances de 4 h, dans le même format qu'en 1re année : fiche, cours, exercices, TP Python avec tests automatiques, aide-mémoire. Les séances se suivent : chaque fiche indique ses prérequis.
Pourquoi ces notions
| Notion | À quoi elle sert |
|---|---|
| Suites numériques | Modéliser une évolution discrète : intérêts, amortissement, croissance d'un stockage ; fondement de l'analyse numérique. |
| Récursivité | Écrire des algorithmes sur les arbres, les listes imbriquées, les répertoires ; base de nombreux tris et parcours. |
| Analyse d'algorithmes | Comparer deux solutions avant de les programmer ; comprendre pourquoi un traitement passe ou non à l'échelle. |
| Structures de données et graphes | Piles, files, dictionnaires, parcours : briques de tout logiciel et de la théorie des réseaux. |
Répartition
| Phase | Séances | Contenu |
|---|---|---|
| 1 | S01 à S05 | Suites numériques : définition, arithmétiques, géométriques, applications, limites |
| 2 | S06 à S10 | Récursivité : principe, pile d'appels, tableaux, diviser pour régner, arbres |
| 3 | S11 à S15 | Analyse d'algorithmes : terminaison, coût, complexité, tris, mesures |
| 4 | S16 à S19 | Structures de données, graphes en Python, méthode, épreuve blanche |
Séance par séance
| Séance | Thème | Chapitre |
|---|---|---|
| S01 | Suites numériques : définition et programmation | Suites numériques – définition, représentation |
| S02 | Suites arithmétiques | Suites numériques – suites arithmétiques |
| S03 | Suites géométriques | Suites numériques – suites géométriques |
| S04 | Sommes et applications : intérêts, amortissement, croissance de données | Suites numériques – applications |
| S05 | Comportement à long terme et algorithmes de seuil | Suites numériques – limites, suites récurrentes |
| S06 | Récursivité : principe | Récursivité – principe, cas de base |
| S07 | Récursivité, suites et pile d'appels | Récursivité – suites, pile d'appels |
| S08 | Récursivité sur les tableaux et les chaînes | Récursivité – tableaux, chaînes |
| S09 | Diviser pour régner | Récursivité – diviser pour régner |
| S10 | Structures arborescentes et parcours en profondeur | Récursivité – arbres, parcours |
| S11 | Terminaison et correction d'un algorithme | Analyse d'algorithme – terminaison, correction |
| S12 | Coût d'un algorithme : compter les opérations | Analyse d'algorithme – coût |
| S13 | Complexité asymptotique | Analyse d'algorithme – complexité |
| S14 | Tris et recherches : comparaison | Analyse d'algorithme – tris, recherches |
| S15 | Mesurer et connaître les limites | Analyse d'algorithme – mesures, limites |
| S16 | Piles, files et dictionnaires | Algorithmique avancée – structures de données |
| S17 | Graphes en Python : parcours et plus court chemin | Algorithmique avancée – graphes |
| S18 | Méthode : de l'énoncé au programme testé | Algorithmique avancée – démarche |
| S19 | Révisions et épreuve blanche | Tous les chapitres de la 2e année |
Limites
- La séance S19 propose un sujet de l'auteur, non officiel, pour s'entraîner : il ne reproduit pas une épreuve précise.
- Aucune de ces séances ne remplace la préparation à l'épreuve E3 : celle-ci repose sur le site de 1re année.