e3a-Polytech 2022 MP Informatique : sujet en PDF

Sujet de l'épreuve de Informatique du Concours e3a-Polytech, France, session 2022, filière MP, en 4 heures. Thème : Automates augmentés, tas binomiaux et arbre de Calkin-Wilf.

Lire le sujet 8 pages · sujet sans corrigé, reproduit sans retouche−+Télécharger le PDF (0,3 Mo)

Ce que traite le sujet, partie par partie

• Partie I : automates. Automate fini non déterministe augmenté d'un sous-ensemble d'états : langage reconnu à un seuil donné, dénombrement et majoration des calculs réussis, construction d'un automate fini à (s+1)p états qui reconnaît ce langage.
• Partie II : autour des tas. En Python, arbres binomiaux et leurs propriétés par récurrence, tas binomial, recherche du minimum, insertion avec sa complexité et invariant de boucle.
  À revoir : Bases de Python : expressions, types, instructions, fonctions, Complexité des algorithmes itératifs et récursifs, Récursivité
• Partie III : autour de l'énumération des fractions positives. En OCaml, arbre de Calkin-Wilf et pgcd, bijection entre les entiers naturels et les rationnels positifs, suite de Stern, chemin vers un nœud, ancêtre commun et formule du successeur.
  À revoir : Langage OCaml : expressions, types, filtrage, récursivité, Arithmétique dans l'ensemble des entiers relatifs, Récursivité

Chapitres à revoir avant de traiter ce sujet

• Bases de Python : expressions, types, instructions, fonctions
• Complexité des algorithmes itératifs et récursifs
• Récursivité
• Langage OCaml : expressions, types, filtrage, récursivité
• Arithmétique dans l'ensemble des entiers relatifs

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.