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
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 à é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 à lignes et colonnes ( et ), d'entiers triés en colonne de haut en bas et de gauche à droite, et qui renvoie :
le couple d'indices ( ) 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 si n'est pas présent dans la matrice mat.
Cette fonction devra être de complexité logarithmique en .
Exercice 2 - Automates et langages de mots binaires
Dans cet exercice, on étudie différents langages sur l'alphabet à deux lettres. On note 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 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 reconnaissant le langage .
11e) Écrire en OCaml une fonction langage_1 de type mot bool qui prend en argument un mot et qui renvoie true si et seulement si appartient au langage .
12 On note le langage dénoté par l'expression rationnelle .
12a) Justifier que est un langage local.
12b) Dessiner un automate déterministe reconnaissant le langage .
12c) Écrire en OCaml une fonction langage_2 de type mot bool qui prend en argument un mot et qui renvoie true si et seulement si appartient au langage .
13 On note le langage reconnu par l'automate déterministe défini par
l'ensemble d'états ;
l'état initial ;
l'ensemble d'états finals ;
la fonction de transition définie par
On rappelle que ( ) désigne le reste de la division euclidienne de l'entier par 3.
13a) Dessiner l'automate .
13b) Écrire en OCaml une fonction langage_3 de type mot -> bool qui prend en argument un mot et qui renvoie true si et seulement si appartient au langage .
13c) Pour tout , démontrer la propriété suivante:
où la fonction est définie par
14 On note .
14a) Décrire simplement l'ensemble des mots du langage .
14b) Existe-t-il un automate reconnaissant le langage ?
Exercice 3 - Diamètre d'un graphe
Dans cet exercice, on considère des graphes non orientés connexes. Les sommets d'un graphe à sommets sont numérotés de 0 à . On suppose qu'aucune arête ne boucle sur un même sommet.
Un chemin de longueur d'un sommet vers un sommet dans un graphe est la donnée de sommets tels que et, pour tout , les sommets et sont reliés par une arête.
Un plus court chemin d'un sommet vers un sommet dans un graphe G est un chemin de longueur minimale parmi tous les chemins de vers . Sa longueur est notée .
Le diamètre d'un graphe G , noté , vaut le maximum des longueurs des plus courts chemins entre deux sommets du graphe G. Autrement dit,
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 et ci-dessous.
graphe
graphe
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 non nul et qui renvoie un graphe à 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 non nul et qui renvoie un graphe à 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 à un arbre binaire 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 (à gauche) et de son graphe sous-jacent (à droite):
21 Donner l'expression OCaml représentant l'arbre de l'exemple. Donner le diamètre de et les chemins maximaux du graphe sous-jacent .
22 Quel est le nombre d'arêtes du graphe sous-jacent à un arbre binaire possédant 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 à nœuds et qui renvoie un arbre binaire de même graphe sous-jacent que et dont les nœuds sont étiquetés de 0 à .
25 Écrire en OCaml une fonction arbre_vers_graphe de type arbre -> graphe qui prend en argument un arbre binaire à nœuds étiquetés de 0 à et qui renvoie le graphe sous-jacent à (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é? pour-régner. Pour tout arbre non réduit à une feuille, de la forme Noeud (x, arbre_g, arbre_d), on note
le fils gauche de , représenté par arbre_g;
le fils droit de , représenté par arbre_d.
La hauteur de l'arbre , notée , est la longueur du plus long chemin descendant de la racine vers une feuille. Dans l'arbre exemple de la partie 3, l'arbre 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
E3A Option Informatique MP 2019 - Version Web LaTeX | WikiPrépa | WikiPrépa
