N.B. : le candidat attachera la plus grande importance à la clarté, à la précision et à la concision de la rédaction. Si un candidat est amené à repérer ce qui peut lui sembler être une erreur d'énoncé, il le signalera sur sa copie et devra poursuivre sa composition en expliquant les raisons des initiatives qu'il a été amené à prendre.

Ce sujet évalue les compétences acquises dans les enseignements d'Informatique pour tous et d'option Informatique. Toutes les questions doivent être traitées par les candidats.
Les questions demandant d'écrire une fonction en langage Python doivent exploiter le contenu des enseignements d'Informatique pour tous. Les questions demandant d'écrire une fonction en langage CaML doivent exploiter le contenu des enseignements d'option Informatique.
Les fonctions écrites en langage Python ne devront pas être récursives sauf dans la question Q31 page 9.
Les fonctions écrites en langage CaML devront être récursives ou faire appel à des fonctions auxiliaires récursives. Elles ne devront pas utiliser d'instructions itératives (c'est-à-dire for,while, ...), ni de références, ni d'exceptions.

Imaginez-vous ethnologue. Vous étudiez une peuplade primitive qui présente un comportement manichéen extrême : lorsque plusieurs personnes participent à une même conversation sur un sujet donné, elles vont toutes avoir le même comportement manichéen tant que la conversation reste sur le même sujet, c'est-à-dire que toutes les affirmations seront soit des vérités, soit des mensonges. Par contre, si le sujet de la conversation change, la nature des affirmations, soit mensonge, soit vérité, peut changer, mais toutes les affirmations seront de la même nature tant que le sujet ne changera pas à nouveau. Pour être autorisé à séjourner dans cette peuplade, vous devez respecter cette règle. Vous participez à une conversation avec trois de leurs membres que nous appellerons et . Ceux-ci vous indiquent comment rejoindre leur village. Si vous n'arrivez pas à le rejoindre, vous ne serez pas autorisé à y séjourner.
Le premier sujet abordé est la région dans laquelle se trouve le village :
X indique : «Le village se trouve dans la vallée»;
Z réplique: «Non, il ne s'y trouve pas »;
X reprend: «Ou alors dans les collines».
Nous noterons et les variables propositionnelles associées à la région dans laquelle se trouve le village.
Nous noterons et les formules propositionnelles correspondant aux affirmations de et de sur le premier sujet.
Puis, le second sujet est abordé : le chemin qui permet de rejoindre le village dans la région concernée.
X dit : «Le chemin de gauche conduit au village»;
Z répond: «Tu as raison»;
X complète : «Le chemin de droite y conduit aussi »;
Y affirme : «Si le chemin du milieu y conduit, alors celui de droite n'y conduit pas »;
Z indique : «Celui du milieu n'y conduit pas ».
Nous noterons les variables propositionnelles correspondant respectivement au fait que le chemin de gauche, du milieu et de droite, conduit au village.
Nous noterons et les formules propositionnelles correspondant aux affirmations de , de et de sur le second sujet.
Q1. Représenter le comportement manichéen des interlocuteurs dans le premier sujet abordé sous la forme d'une formule du calcul des propositions dépendant des formules propositionnelles et .
Q2. Représenter les informations données par les participants sous la forme de deux formules du calcul des propositions et dépendant des variables et .
Q3. En utilisant la résolution avec les propriétés des opérateurs booléens et les formules de De Morgan en calcul des propositions, déterminer dans quelle région vous devez vous rendre pour rejoindre le village.
Q4. Représenter le comportement manichéen des interlocuteurs dans le second sujet abordé sous la forme d'une formule du calcul des propositions dépendant des formules propositionnelles et .
Q5. Représenter les informations données par les participants sous la forme de trois formules du calcul des propositions et dépendant des variables et .
Q6. En utilisant la résolution avec les tables de vérité en calcul des propositions, déterminer quel chemin vous devez suivre pour rejoindre le village.

Q7. En admettant que les trois participants aient menti, pouviez-vous prendre d'autres chemins? Si oui, le ou lesquels?

Cette partie étudie l'algorithme de recherche dichotomique de la position d'une valeur dans une séquence croissante d'entiers. Pour simplifier les notations et les preuves, les séquences manipulées ne contiennent qu'une seule fois chaque valeur. Les résultats obtenus se généralisent aux séquences croissantes quelconques.

Définition II. 1 (séquence) : soient avec ,

Une séquence sera représentée en Python par une liste. Dans la suite de cet exercice, nous considérons la fonction position du programme suivant en langage Python.

def position(v,p):
    d = 0
    f = len (p)-1
    while (d < f):
        m = d + (f - d) // 2
        print (v, d, m, f, p[d], p[m], p[f])
        if (v < p[m]):
            f = m - 1
        elif (p[m] < v):
            d = m + 1
        else:
            f = d = m
    return d
exemple = [ 1, 4, 7, 9, 12, 15]
resultat = position(9,exemple)

Listing 1 - Recherche dichotomique en Python

Q8. Quelles sont les informations affichées lors de l'exécution du programme complet du Listing 1 ? Que contient la variable resultat après cette exécution? Que contient la variable exemple après cette exécution?

Q9. Soient la séquence et les entiers et tels que , avec :
(i) avec ;
(ii) ;
(iii) .

Montrer que .
Vous utiliserez pour cela la propriété suivante dont vous montrerez qu'il s'agit d'un invariant pour la boucle :

Q10. Montrer que le calcul de la fonction position se termine quelles que soient les valeurs de ses paramètres v et p .
Q11. Donner des exemples de valeurs des paramètres v et p de la fonction position qui correspondent au pire cas en temps d'exécution.
Montrer que la complexité en temps d'exécution dans le pire cas de la fonction position, en fonction de la taille des séquences transmises comme paramètre, est de .

Cette partie étudie l'opérateur de produit synchronisé sur l'alphabet de deux automates sur un même alphabet tel que . Cet opérateur est utilisé pour modéliser des activités concurrentes.

Définition III. 1 (alphabet, mot, langage) : un alphabet est un ensemble de symboles. est le symbole représentant le mot vide. est l'ensemble contenant et les mots composés de séquences de symboles de . Un langage sur est un sous-ensemble de .

Nous étudierons deux implantations des mots et langages : d'une part en algorithmique récursive programmée en langage CaML; d'autre part en algorithmique itérative programmée en langage Python.

Nous utiliserons par la suite en CaML le type char pour représenter les symboles de l'alphabet et les listes de symboles pour représenter les mots.
Q12. Écrire en CaML une définition pour les types alphabet, mot et langage qui représentent les alphabets, mots et langages sur les symboles de cet alphabet.
Q13. Écrire en CaML une fonction prefixer, de type mot -> langage -> langage, telle que l'appel (prefixer p l) sur un mot p et un langage 1 , renvoie un langage contenant les mêmes mots que 1 préfixés par le mot p. L'algorithme utilisé ne devra parcourir qu'une seule fois le langage 1. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Q14. Calculer une estimation de la complexité de la fonction prefixer en fonction du nombre de mots du langage 1 . Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.

Nous utiliserons par la suite en Python des chaînes de caractère de taille 1 (type str) pour représenter les symboles de l'alphabet.
Q15. Proposer une représentation en Python des mots et langages sur cet alphabet.
Q16. Écrire en Python une fonction prefixer, telle que l'appel prefixer (p,l) sur un mot p et un langage 1 , renvoie un langage contenant les mêmes mots que 1 préfixés par le mot p. L'algorithme utilisé ne devra parcourir qu'une seule fois le langage l. Cette fonction devra être itérative ou faire appel à des fonctions auxiliaires itératives.
Q17. Calculer une estimation de la complexité de la fonction prefixer en fonction du nombre de mots du langage 1 . Cette estimation ne prendra en compte que le nombre d'itérations effectuées.

Définition III. 2 (automate fini) : un automate fini sur un alphabet est un quintuplet composé :

Pour une transition donnée, nous appelons l'origine de la transition, l'étiquette de la transition et la destination de la transition.
Remarquons que est le graphe d'une application de transition dont les valeurs sont définies par :

La notation est plus adaptée que à la formalisation et la construction des preuves dans le cadre des automates non déterministes.

Définition III. 3 (transition sur un mot) : l'extension de à est définie par :

Définition III. 4 (langage accepté par un automate) : le langage sur accepté par un automate fini est :

Les automates peuvent être représentés par un schéma suivant les conventions :

Exemple III. 1 : l'automate tel que

est représenté par le graphe suivant :

Exemple III. 2 : l'automate tel que

est représenté par le graphe suivant :

Notons que certains états et transitions ne sont pas utiles dans la description d'un langage car ils ne participent pas à la construction de mots du langage. Il s'agit, d'une part, des états qui ne figurent dans aucune séquence de transitions allant de l'état initial à un état terminal et, d'autre part, des transitions dont les états inutiles sont l'origine ou la destination. Un automate dans lequel ces états et transitions inutiles ont été éliminés est appelé automate émondé.

Exemple III. 3 : le sous-automate de (Exemple III. 1 de la page 6) composé des états et transitions utiles est représenté par le graphe suivant :

Exemple III. 4 : le sous-automate de (Exemple III. 2 de la page 6) composé des états et transitions utiles est représenté par le graphe suivant :

Q18. Donner, sans la justifier, une expression régulière ou ensembliste représentant les langages et sur accepté par l'automate de l'Exemple III. 1 et de l'Exemple III.2, situés sur la page 6.
Nous étudierons deux implémentations des automates : d'une part en algorithmique récursive programmée en langage CaML; d'autre part en algorithmique itérative programmée en langage Python.

Nous utiliserons par la suite en CaML le type int pour représenter les états d'un automate.
Q19. Écrire en CaML une définition pour les types etat, transition et automate qui représentent les états et les transitions ainsi que les automates sur l'alphabet des symboles. Définir en CaML la valeur expl_III_1 de type automate correspondant à l'automate de l'Exemple III. 1 de la page 6.
Q20. Écrire en CaML une fonction valider, de type automate -> bool, telle que l'appel (valider a) sur l'automate a renvoie la valeur true si l'automate a est valide, c'est-à-dire s'il respecte les contraintes de la Définition III. 2 de la page 5, et la valeur false sinon. L'algorithme utilisé ne devra parcourir qu'une seule fois les transitions de l'automate a. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

Q21. Écrire en CaML une fonction accepter, de type mot -> automate -> bool, telle que l'appel (accepter m a) sur un mot m et un automate a, renvoie la valeur true si le mot m appartient au langage accepté par l'automate a et la valeur false sinon. L'algorithme utilisé ne devra parcourir qu'une seule fois le mot m . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.
Q22. Calculer une estimation de la complexité de la fonction accepter en fonction du nombre de symboles du mot m et du nombre de transitions de l'automate a. Cette estimation ne prendra en compte que le nombre d'appels récursifs effectués.

Nous utiliserons par la suite en Python le type int pour représenter les états d'un automate.
Q23. Proposer une représentation en Python des automates sur l'alphabet des symboles. Définir en Python la variable expl_III_1 initialisée avec une valeur correspondant à l'automate de l'Exemple III. 1 de la page 6.
Q24. Écrire en Python une fonction valider, telle que l'appel valider(a) sur l'automate a renvoie la valeur true si l'automate a est valide, c'est-à-dire s'il respecte les contraintes de la Définition III. 2 de la page 5, et la valeur false sinon. L'algorithme utilisé ne devra parcourir qu'une seule fois les transitions de l'automate a. Cette fonction devra être itérative ou faire appel à des fonctions auxiliaires itératives.
Q25. Écrire en Python une fonction accepter, telle que l'appel accepter(m, a) sur un mot m et un automate a, renvoie la valeur true si l'automate a accepte le mot et la valeur false sinon. L'algorithme utilisé ne devra parcourir qu'une seule fois le mot m. Cette fonction devra être itérative ou faire appel à des fonctions auxiliaires itératives.

Nous définissons d'abord l'opération de synchronisation de mots qui produit un langage.
Définition III. 5 (synchronisation de mots) : soient et deux mots de et un alphabet de synchronisation, l'opération de synchronisation de et sur , notée , produit un langage sur tel que : pour tous mots de , pour tous symboles de avec et pour tous symboles de , nous avons:

Q26. Soient les alphabets et , construire le langage (a.b.c) (a.b.d) en détaillant chaque étape.

Q27. Montrer que pour tous mots de ,

Q28. Montrer que pour tout symbole de , pour tous mots de , il existe des mots de tels que :

Q29. Montrer que pour tout symbole de , pour tous mots de , il existe des mots de tels que :

Nous nous limiterons à l'étude d'une implantation en algorithmique récursive que nous programmerons à la fois en langage CaML et en langage Python.

Q30. Écrire en CaML une fonction synchro_mot, de type mot -> mot -> alphabet -> langage, telle que l'appel (synchro_mot m 1 m 2 s ) sur les mots m 1 et m 2 et sur l'alphabet de synchronisation s , renvoie le langage . L'algorithme utilisé ne devra parcourir qu'une seule fois les mots et . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

Q31. Écrire en Python une fonction synchro_mot, telle que l'appel synchro_mot ( ) sur les mots m 1 et m 2 et sur l'alphabet de synchronisation s , renvoie le langage . L'algorithme utilisé ne devra parcourir qu'une seule fois les mots m1 et m2. Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

Soit l'opération interne de synchronisation sur des langages définie par :
Définition III. 6 (synchronisation de langages) : soient et deux langages sur l'alphabet et un alphabet de synchronisation, le langage sur résultant de la synchronisation sur des mots de et est défini par :

Q32. Écrire en CaML une fonction synchro_lang, de type langage -> langage -> alphabet -> langage, telle que l'appel (synchro_lang 1112 s ) sur les langages 11 et 12 et sur l'alphabet de synchronisation s , renvoie le langage . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

Soit l'opération interne sur les automates finis déterministes définie par :
Définition III. 7 (synchronisation d'automates) : soient et deux automates finis déterministes sur l'alphabet et un alphabet de synchronisation, l'automate qui résulte de la synchronisation sur de et est où la relation de transition est définie par : pour tous états de et de , pour tout symbole de et pour tout symbole de :

Q33. En considérant l'Exemple III. 1 et l'Exemple III. 2 de la page 6, construire l'automate avec . Le résultat devra être émondé (seuls les états et les transitions utiles devront être construits).
Q34. Écrire en CaML une fonction synchro_auto, de type automate -> automate -> alphabet -> automate, telle que l'appel (synchro_auto a1 a2 s) sur les automates a1 et a2 et sur l'alphabet de synchronisation s , renvoie l'automate . Cette fonction devra être récursive ou faire appel à des fonctions auxiliaires récursives.

Q35. Montrer que si et sont des automates finis, alors est un automate fini.
Q36. Montrer que pour tout mot de , il existe des mots de tels que : pour tous états de et de :

Q37. Soient et deux automates finis, montrer que :