Recherche dichotomique et ses extensions, automates reconnaissant des langages de mots binaires, diamètre d'un graphe
Afficher ou masquer la section
Le premier exercice étudie la recherche dichotomique dans une liste triée, sa correction, sa terminaison, puis l'étend à une recherche par trichotomie et à une matrice triée en colonnes. Le deuxième exercice construit des automates reconnaissant différents langages de mots binaires, dont celui des écritures binaires d'entiers. Le troisième exercice étudie le diamètre d'un graphe, avec un algorithme spécifique de calcul du diamètre d'un arbre binaire en temps linéaire.
1Exercice 1, parties 1 à 2 : recherche par dichotomieOn rappelle le principe de la dichotomie, on étudie un code Python bogué (boucle infinie), on identifie l'invariant de boucle et on corrige la fonction pour la rendre correcte et terminante.
2Exercice 1, partie 3 : extensions de la dichotomieOn écrit une fonction de recherche par trichotomie et on compare sa complexité à la dichotomie, puis on adapte la méthode à la recherche dans une matrice triée en colonnes, avec une complexité logarithmique imposée.
3Exercice 2 : automates et langages de mots binairesOn construit des automates locaux ou déterministes reconnaissant divers langages de mots binaires (écritures binaires d'entiers, expressions rationnelles, automate défini par une fonction de transition modulo 3) et on étudie leur intersection.
4Exercice 3, parties 1 à 2 : diamètre d'un grapheOn étudie des exemples de graphes de diamètre extrémal et on discute des algorithmes de parcours (Dijkstra, parcours en largeur) permettant de calculer le diamètre d'un graphe.
5Exercice 3, partie 3 : diamètre d'un arbre binaireOn étudie une première méthode de calcul du diamètre d'un arbre en le convertissant en graphe, puis une méthode diviser-pour-régner de complexité linéaire utilisant la hauteur des sous-arbres.
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.
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) def dicho(liste,x):
(2) # Pré-conditions: x est un entier, liste est une
(3) # liste d'entiers triée dans l'ordre croissant
(4) n = len(liste)
(5) if n == 0:
(6) return False
(7) }\textrm{g},\textrm{d}=0,\textrm{n}-
(8) while d-g > 0:
(9) m = (g+d)//2
(10) if liste[m] >= x:
(11) d = m
(12) else:
(13) g = m
(14) 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 Justifier que le prédicat 𝒫 : «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 justification la ou les corrections à apporter pour que la fonction dicho termine, tout en restant correcte.
7 Justifier que la fonction corrigée termine et est correcte.
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 :
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éfini 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).
Exercice 2 - Automates et langages de mots binaires
Dans cet exercice, on étudie diffé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 L_1 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 fin 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 signifie la propriété d'être local standard?
11d) Dessiner un automate local standard A_1 reconnaissant le langage L_1.
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 L_1.
12 On note L_2 le langage dénoté par l'expression rationnelle (0 + 1)^∗ ⋅ 0.
12a) Justifier que L_2 est un langage local.
12b) Dessiner un automate déterministe A_2 reconnaissant le langage L_2.
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 L_2.
13 On note L_3 le langage reconnu par l'automate déterministe A_3 défini par
l'ensemble d'états Q = {0, 1, 2};
l'état initial i = 0;
l'ensemble d'états finals F = {0};
la fonction de transition δ : Q × A ⟶ Q définie par
∀q ∈ Q ∀a ∈ A δ(q, a) = (2q + a)mod3
On rappelle que ( nmod3 ) désigne le reste de la division euclidienne de l'entier n par 3.
13a) Dessiner l'automate A_3.
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 L_3.
13c) Pour tout n ∈ ℕ^∗, démontrer la propriété 𝒫(n) suivante:
∀q ∈ Q ∀ω ∈ A^∗ ∀a ∈ A δ^⋆(q, ε) = q et δ^⋆(q, ω ⋅ a) = δ(δ^⋆(q, ω), a)
14 On note L_4 = L_1 ∩ L_2 ∩ L_3.
14a) Décrire simplement l'ensemble des mots du langage L_4.
14b) Existe-t-il un automate reconnaissant le langage L_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 ∈ ℕ^∗) 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 ∈ ℕ d'un sommet a vers un sommet b dans un graphe est la donnée de p + 1 sommets s_0, s_1, …, s_p tels que s_0 = a, s_p = b et, pour tout 1 ⩽ k ⩽ p, les sommets s_(k − 1) et s_k sont reliés par une arête.
Un plus court chemin d'un sommet a vers un sommet b dans un graphe G est un chemin de longueur minimale parmi tous les chemins de a vers b. Sa longueur est notée d_G(a, b).
Le diamètre d'un graphe G , noté diam(G), vaut le maximum des longueurs des plus courts chemins entre deux sommets du graphe G. Autrement dit,
diam(G) = Max_(a, b sommets de G)d_G(a, b)
Un chemin maximal d'un graphe G est un plus court chemin de G de longueur diam( G ).
Partie 1 - Exemples de graphes
15 Donner sans justification le diamètre et les chemins maximaux pour chacun des deux graphes G_1 et G_2 ci-dessous.
graphe G_1
graphe G_2
En OCaml, les graphes sont représentés par liste d'adjacence et implémentés par le type
type graphe = int list array;;
16 Graphes de diamètre maximal.
16a) Dessiner sans justification un graphe à 5 sommets ayant un diamètre le plus grand possible.
16b) Écrire en OCaml une fonction diam_max de type int -> graphe qui prend en argument un entier naturel n non nul et qui renvoie un graphe à n sommets de diamètre maximal.
17 Graphes de diamètre minimal.
17a) Dessiner sans justification un graphe à 5 sommets ayant un diamètre le plus petit possible.
17b) Écrire en OCaml une fonction diam_min de type int -> graphe qui prend en argument un entier naturel n non nul et qui renvoie un graphe à n sommets de diamètre minimal.
Partie 2 - Algorithmes de calcul du diamètre
Dans cette partie, on suppose que les graphes sont représentés par listes d'adjacence.
18 Donner l'entrée et la sortie de l'algorithme de Dijkstra. Comment cet algorithme permet-il de calculer le diamètre d'un graphe?
19 Quel parcours de graphe peut être utilisé pour le calcul du diamètre?
20 Laquelle des deux méthodes précédentes est la mieux adaptée pour calculer le diamètre d'un graphe?
Partie 3 - Diamètre d'un arbre binaire
Dans cette partie, on s'intéresse aux arbres binaires, qui sont des cas particuliers de graphes. On travaille avec une représentation spécifique de ces graphes particuliers, implémentée en OCaml par le type suivant:
type arbre = Feuille | Noeud of int * arbre * arbre ;;
Le graphe sous-jacent G_A à un arbre binaire A est défini comme le graphe orienté dont
les sommets correspondent aux nœuds de l'arbre (et pas aux feuilles);
les arêtes correspondent aux branches de l'arbre reliant deux nœuds (et non pas celles reliant un nœud à une feuille).
Le diamètre d'un arbre binaire est alors défini comme le diamètre de son graphe sous-jacent.
Voici un exemple d'arbre binaire A (à gauche) et de son graphe sous-jacent G_A (à droite):
21 Donner l'expression OCaml représentant l'arbre A de l'exemple. Donner le diamètre de A et les chemins maximaux du graphe sous-jacent G_A.
22 Quel est le nombre r d'arêtes du graphe sous-jacent à un arbre binaire possédant n nœuds?
Une première approche pour calculer le diamètre d'un arbre consiste à le transformer en un graphe et à employer un algorithme général sur les graphes de la partie 2.
23 Écrire en OCaml une fonction nb_noeuds de type arbre -> int qui renvoie le nombre de nœuds d'un arbre binaire donné en argument.
24 Écrire en OCaml une fonction numerotation de type arbre -> arbre qui prend en argument un arbre binaire A à n nœuds et qui renvoie un arbre binaire A^′ de même graphe sous-jacent que A et dont les nœuds sont étiquetés de 0 à n − 1.
25 Écrire en OCaml une fonction arbre_vers_graphe de type arbre -> graphe qui prend en argument un arbre binaire A à n nœuds étiquetés de 0 à n − 1 et qui renvoie le graphe G_A sous-jacent à A (le type graphe est défini dans la partie 1).
26 Décrire un algorithme qui calcule le diamètre d'un arbre de type arbre en se ramenant à un graphe. Quelle est sa complexité? Une seconde approche pour calculer le diamètre d'un arbre consiste à employer une technique diviser- _– pour-régner. Pour tout arbre A non réduit à une feuille, de la forme Noeud (x, arbre_g, arbre_d), on note
A_g le fils gauche de A, représenté par arbre_g;
A_d le fils droit de A, représenté par arbre_d.
La hauteur de l'arbre A, notée h(A), est la longueur du plus long chemin descendant de la racine vers une feuille. Dans l'arbre exemple de la partie 3, l'arbre A est de hauteur 4.
27 Quelle est la longueur d'un chemin maximal passant par la racine?
28 Écrire en OCaml une fonction diam_arbre de type arbre -> int qui calcule le diamètre d'un arbre donné en argument. Cette fonction devra être de complexité linéaire en le nombre de nœuds de l'arbre.
FIN D'ÉPREUVE
Questions fréquentes
4 questions
Sur quels chapitres porte ce sujet d'informatique MP e3a 2019 ?
Afficher ou masquer la section
Sur quels chapitres porte ce sujet d'informatique MP e3a 2019 ?
+
Il porte sur les algorithmes de recherche et leur complexité, les automates finis et les langages rationnels, et les algorithmes de graphes, notamment le calcul du diamètre.
Quelles parties sont indépendantes dans ce sujet ?
+
L'énoncé précise que l'épreuve est composée de trois exercices indépendants, et qu'un candidat peut toujours admettre le résultat d'une question non traitée pour continuer les questions suivantes.
Quels langages de programmation faut-il utiliser pour ce sujet ?
+
Python pour l'exercice 1 sur la recherche dichotomique, et OCaml pour les exercices 2 et 3 sur les automates et les graphes.
Quel est l'objectif de l'exercice sur le diamètre d'un arbre binaire ?
+
Passer d'un algorithme général sur les graphes à un algorithme spécifique aux arbres binaires, de complexité linéaire en le nombre de nœuds, en utilisant une approche diviser-pour-régner fondée sur la hauteur des sous-arbres.
Pas de description pour le moment
Commentaires• E3A Option Informatique MP 2019
Connectez-vous pour participer aux discussions
Partagez vos avis, posez des questions et échangez avec la communauté
Même chapitre : Arbres binaires et algorithmes… (+1)X ENS Option Informatique MP MPI 2023X-ENS · 2023Corrigé
Même chapitre : Automates finis déterministes et… (+1)CCINP Option Informatique MP 2022CCINP · 2022Corrigé
Même année, MinesMines Option Informatique MP 2019Mines · 2019Corrigé
Même année, CentraleCentrale Option Informatique MP 2019Centrale · 2019Corrigé.jpg)
