Mines-Ponts 2017 MP Informatique option MP : sujet en PDF
Sujet de l'épreuve de Informatique option MP du Concours commun Mines-Ponts, France, session 2017, filière MP, en 3 heures. Thème : Langages et automates unaires ; chaînes d'additions pour le calcul rapide des puissances.
Ce que traite le sujet, partie par partie
- Première partie : langages et automates. Langages unaires formés de progressions arithmétiques de longueurs, lecture d'automates et déterminisation, automates en forme de chemin suivi d'un circuit, union et intersection de tels langages, puis caractérisation des automates déterministes émondés qui reconnaissent un langage unaire rationnel infini et forme générale de ces langages.
- Seconde partie : algorithmique et programmation. Suites pour l'obtention d'une puissance (chaînes d'additions) : algorithme récursif par division par deux et majoration de son nombre de multiplications, algorithme par décomposition binaire inverse, cas des puissances de 3, recherche des indices de deux termes dont la somme donne un terme, calcul de x puissance n le long d'une suite et recherche exhaustive récursive d'une suite de longueur minimale, en Caml.
Chapitres à revoir avant de traiter ce sujet
- Arithmétique dans l'ensemble des entiers relatifs
- Langage OCaml : expressions, types, filtrage, récursivité
- Récursivité
- Architecture de l'ordinateur et représentation des nombres
- Complexité des algorithmes itératifs et récursifs
Chaque chapitre a son cours, ses méthodes, ses pièges et des exercices corrigés. L'essai gratuit donne accès aux chapitres offerts de ta filière.