Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Il est interdit aux candidats de signer leur composition ou d’y mettre un signe

Il est interdit aux candidats de signer leur composition ou d’y mettre un signe quelconque pouvant indiquer sa provenance. Épreuve d’Informatique MP Durée 3 h Si, au cours de l’épreuve, un candidat repère ce qui lui semble être une erreur d’énoncé, d’une part il le signale au chef de salle, d’autre part il le signale sur sa copie et poursuit sa composition en indiquant les raisons des initiatives qu’il est amené à prendre. L’usage de calculatrices est interdit. AVERTISSEMENT • L'épreuve est composée de 3 exercices indépendants. • Un candidat pourra toujours admettre le résultat des questions qu'il n'a pas faites pour faire les questions suivantes. • Les programmes devront être écrits dans le langage de programmation Python pour l'exercice 1 et OCaml pour les exercices 2 et 3. La présentation, la lisibilité, l’orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l’appréciation des copies. En particulier, les résultats non justifiés ne seront pas pris en compte. Les candidats sont invités à encadrer les résultats de leurs calculs. Tournez la page S.V.P Il est interdit aux candidats de signer leur composition ou d’y mettre un signe quelconque pouvant indiquer sa provenance. Épreuve d’Informatique MP Durée 3 h Si, au cours de l’épreuve, un candidat repère ce qui lui semble être une erreur d’énoncé, d’une part il le signale au chef de salle, d’autre part il le signale sur sa copie et poursuit sa composition en indiquant les raisons des initiatives qu’il est amené à prendre. L’usage de calculatrices est interdit. AVERTISSEMENT • L'épreuve est composée de 3 exercices indépendants. • Un candidat pourra toujours admettre le résultat des questions qu'il n'a pas faites pour faire les questions suivantes. • Les programmes devront être écrits dans le langage de programmation Python pour l'exercice 1 et OCaml pour les exercices 2 et 3. La présentation, la lisibilité, l’orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l’appréciation des copies. En particulier, les résultats non justifiés ne seront pas pris en compte. Les candidats sont invités à encadrer les résultats de leurs calculs. Tournez la page S.V.P 108 Tournez la page S.V.P. Exercice 1 – Autour de la recherche par dichotomie Partie 1 – Questions de cours 1 Rappeler le principe de la recherche dichotomique dans une liste d’entiers. Quel intérêt présente cette méthode ? 2 La mise en œuvre d’une recherche dichotomique est-elle possible sur une liste de couples d’entiers ? de chaînes de caractères ? Partie 2 – Étude d’une fonction dicho Voici le code d’une fonction Python élaboré pour tester par dichotomie si un entier x se trouve dans une liste d’entiers liste : (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14) def dicho(liste,x): # Pré-conditions: x est un entier, liste est une # liste d’entiers triée dans l’ordre croissant n = len(liste) if n == 0: return False g, d = 0, n-1 while d-g > 0: m = (g+d)//2 if liste[m] >= x: d = m else: g = m return liste[g] == x 3 Pour quelles raisons ne remplace-t-on pas la précondition de la ligne (3) par un appel à une fonction qui trierait la liste liste dans l’ordre croissant ? 4 Justiﬁer que le prédicat P : « l’entier x apparaît dans la sous-liste liste[g :d+1] des éléments de liste d’indices g à d » est préservé à chaque tour de la boucle while. 5 Il s’avère que la fonction dicho ne termine pas. Donner un exemple où la fonction boucle. 6 Indiquer sans justiﬁcation la ou les corrections à apporter pour que la fonction dicho termine, tout en restant correcte. 7 Justiﬁer que la fonction corrigée termine et est correcte. 2 Partie 3 – Extensions du principe Une première extension consiste à réduire la taille du problème non plus en 2 mais en 3 : c’est le principe de trichotomie. 8 Écrire en Python une fonction tricho(liste,x) qui renvoie True si l’élément x se trouve dans la liste liste et False sinon. Cette fonction sera récursive ou fera appel à une ou des fonctions auxiliaires récursives. 9 Estimer la complexité de la fonction tricho(liste,x) pour une liste liste à n éléments. Comparer avec la méthode par dichotomie. Une seconde extension consiste à adapter le principe de dichotomie au cas d’une matrice d’entiers dont les éléments sont triés en colonne de haut en bas et de gauche à droite. L’illustration ci-dessous indique l’ordre des éléments d’une matrice à 4 lignes et 6 colonnes :     0 4 8 12 16 20 1 5 9 13 17 21 2 6 10 14 18 22 3 7 11 15 19 23     Une matrice sera implémentée en Python par une liste de ses lignes, elles-mêmes implémentées par des listes. 10 Écrire en Python une fonction dicho_matrice(mat,x) qui prend en argument un entier x et une matrice mat à n lignes et p colonnes (n ⩾1 et p ⩾1), d’entiers triés en colonne de haut en bas et de gauche à droite, et qui renvoie : • le couple d’indices (i,j) minimal pour l’ordre déﬁni plus haut tel que x se trouve en ligne i et colonne j, si l’entier x est bien présent dans la matrice mat ; • le couple (-1,-1) si x n’est pas présent dans la matrice mat. Cette fonction devra être de complexité logarithmique en max(n, p). 3 Tournez la page S.V.P. Exercice 2 – Automates et langages de mots binaires Dans cet exercice, on étudie diﬀérents langages sur l’alphabet A = {0, 1} à deux lettres. On note A∗ l’ensemble des mots construits sur l’alphabet A. Le mot vide est noté ε. En OCaml, un mot sur A est implémenté par le type type mot = bool list;; à savoir par une liste de booléens où la lettre 0 est représentée par le booléen false et la lettre 1 par le booléen true. 11 On note L1 le langage des mots de A qui représentent l’écriture binaire d’un entier naturel, où le bit de poids faible se situe en ﬁn de mot. Pour assurer l’unicité de la représentation, l’écriture binaire d’un entier ne commence jamais par 0. C’est pourquoi l’entier nul est représenté par le mot vide. 11a) Donner l’écriture binaire de l’entier 41. 11b) Donner l’entier représenté par le mot 10101010. 11c) Pour un automate, que signiﬁe la propriété d’être local standard ? 11d) Dessiner un automate local standard A1 reconnaissant le langage L1. 11e) Écrire en OCaml une fonction langage_1 de type mot -> bool qui prend en argument un mot m et qui renvoie true si et seulement si m appartient au langage L1. 12 On note L2 le langage dénoté par l’expression rationnelle (0 + 1)∗· 0. 12a) Justiﬁer que L2 est un langage local. 12b) Dessiner un automate déterministe A2 reconnaissant le langage L2. 12c) Écrire en OCaml une fonction langage_2 de type mot -> bool qui prend en argument un mot m et qui renvoie true si et seulement si m appartient au langage L2. 13 On note L3 le langage reconnu par l’automate déterministe A3 déﬁni par • l’ensemble d’états Q = {0, 1, 2} ; • l’état initial i = 0 ; • l’ensemble d’états ﬁnals F = {0} ; • la fonction de transition δ : Q × A − →Q déﬁnie par ∀q ∈Q ∀a ∈A δ(q, a) = (2q + a) mod 3 On rappelle que (n mod 3) désigne le reste de la division euclidienne de l’entier n par 3. 13a) Dessiner l’automate A3. 13b) Écrire en OCaml une fonction langage_3 de type mot -> bool qui prend en argument un mot m et qui renvoie true si et seulement si m appartient au langage L3. 13c) Pour tout n ∈N∗, démontrer la propriété P(n) suivante : ∀ω1, . . . , ωn ∈A δ⋆(0, ω1 · · · ωn) = n k=1 ωk 2n−k mod 3 où la fonction δ⋆: Q × A∗− →Q est déﬁnie par ∀q ∈Q ∀ω ∈A∗ ∀a ∈A δ⋆(q, ε) = q et δ⋆(q, ω · a) = δ δ⋆(q, ω), a 14 On note L4 = L1 ∩L2 ∩L3. 14a) Décrire simplement l’ensemble des mots du langage L4. 14b) Existe-t-il un automate reconnaissant le langage L4 ? 4 Exercice 3 – Diamètre d’un graphe Dans cet exercice, on considère des graphes non orientés connexes. Les sommets d’un graphe à n sommets (n ∈N∗) sont numérotés de 0 à n −1. On suppose qu’aucune arête ne boucle sur un même sommet. Un chemin de longueur p ∈N d’un sommet a vers un sommet b dans un graphe est la donnée de p + 1 sommets s0, s1, . . . , sp tels que s0 = a, sp = b et, pour tout 1 ⩽k ⩽p, les sommets sk−1 et sk sont reliés par une arête. Un plus court chemin d’un sommet a uploads/s3/ i-19-rmoe.pdf