Devoirs donnés en Spé MP/MP*:
|
un texte tiré de Combinatorics on words |
|
|
langages infinitaires rationnels |
|
|
sous-mots, distance d'édition, plus longue sous-chaîne commune |
|
|
partage d'un polygône, satisfiabilité d'une clause de Horn. |
|
|
Automate de vérification d'addition |
|
|
Sous-suites croissantes d'une suite donnée |
|
|
Minimisation d'un automate |
|
|
Automate minimal par la méthode des résiduels |
|
|
Fermeture transitive d'un graphe |
|
|
longueur minimum des mots d'un langage; palindromes; ensembles en Caml; automate minimal par la méthode des résiduels; |
|
|
listes en Caml; automate des résiduels; mots qui commutent; fonction à découvrir en Caml; |
|
|
expression rationnelle d'un langage avec le lemme d'Arden; programmation des ensembles en Caml; |
|
|
Tas alternants; rang local dans un arbre binaire de recherche; longueur de cheminement dans un arbre; |
|
|
expressions arithmétiques sans parenthèses; satisfiabilité d'une clause de Horn; les rationnels en Caml; |
|
|
L'algorithme de Robinson, Schensted et Knuth |
|
|
arbres et files binômiales; exercices sur les automates; homomorphismes sur les langages; |
|
|
Algorithme de sélection; automate des nombres binaires divisibles par trois; racine d'un langage; |
|
|
automates et motifs; rang local dans un arbre binaire de recherche; |
|
|
circuits logiques; plus grande somme de sous-listes; |
|
|
Additionneurs, systèmes de numération, parties reconnaissables de N* |
|
|
logique; langages. |
|
|
logique; automates; arbres binaires. |
|
|
Connecteur de Sheffer et problème sur le cobra (objet genre Rubik's cube). |
|
|
Structure secondaire de l'ARN de transfert. |
|
|
Automate des tas de sable. |
|
|
Déterminisation de l'automate d'un langage fini. |
|
|
Automates et arbres. |
|
|
Forme exclusive d'une expression booléenne. |
|
|
Sous-mots, mélanges de mots, théorème de Higman. |
|
|
Racine carrée d'un langage; circuits logiques; algorithme de découpage en lignes. |
|
|
Dr Brain |
|
|
Pavages, périodicité, quasi-périodicité. |
|
|
Lemme de l'étoile et programmation. |
|
|
Langages rationnels sur un alphabet à une lettre. |
|
|
Algorithme de Berry-Sethi. |
|
|
Arbres, dictionnaires, files binomiales. |
|
|
Distance de Hamming; bassin d'attraction. |
|
|
complexité des opérations sur les langages rationnels |
|
|
Problème du bin packing. |
|
|
logique et automates finis. |
|
|
extractions conservant la rationnalité. |
|
|
Morphismes, L-systèmes, lettres récurrentes. |
|
|
logique et automates. |
|
|
Autour du mot de Kolakoski. |
|
|
Approche matricielle des automates. |
|
|
Polynôme d'autocorrélation d'un motif. |
|
|
connectivité dans les graphes et protocole d'information de routage |
Devoirs donnés en Sup MPSI:
|
Files d'attente |
|
|
tri rapide de listes; élément médian d'un tableau. |
|
|
Différents algorithmes de tri. |
Proposé par B. Petazzoni
Il s'agit du problème qui clôt le premier chapitre du livre de Lothaire Combinatorics on words.
Énoncé au format PostScript
Énoncé au format ps.gz
Proposé par B. Petazzoni
On définit la notion de mot infini sur un alphabet donné puis, après avoir défini les langages reconnaissables au sens de Büchi, on détermine quelques propriétés de ces langages. On conclut en observant la topologie de Cantor sur les mots infinis.
Énoncé au format PostScript
Énoncé au format ps.gz
Proposé par B. Petazzoni
On définit la notion de sous-mot , puis on détermine
le nombre maximal de sous-mots d'un mot de longueur n sur un alphabet
à deux lettres a et b; on montre que les mots pour lesquels le
maximum est atteint sont ceux dans lesquels les lettres a et b
alternent.
On définit ensuite la distance d'édition
de deux mots: c'est le nombre minimal d'insertions et/ou de
suppressions de lettres pour passer du premier mot au deuxième;
on étudie l'algorithme classique de calcul de cette distance
par la programmation dynamique .
On définit le plus
long sous-mot commun (PLSMC) à deux mots donnés, et
on s'intéresse à trois algorithmes de calcul du PLSMC:
le premier reprend la méthode de programmation dynamique, sa
complexité spatiale est proportionnelle au produit des
longueurs des deux mots.
On se propose ensuite de voir comment
diminuer cette complexité: on étudie d'abord
l'algorithme de Hirschberg, puis l'algorithme de Hunt et Szymanski.
Énoncé au format PostScript
Énoncé au format ps.gz
Un fichier zip regroupant les sources de l'énoncé et le fichier postscript.
Ce problème a connu un prolongement curieux: pour
calculer la distance d'édition de deux mots, plusieurs
étudiants ont eu recours à une formulation récursive
; si l'on note c(i,j) le coût du
calcul de la distance d'édition de deux mots de longueurs
respectives i et j avec cette méthode, on est
naturellement amené à étudier la suite de terme
général c(n,n) dont les premiers
termes sont:
Cette suite n'était alors pas connue du serveur On-Line
Encyclopedia of Integer Sequences géré par N. J. A.
Sloane.
En fait, c(i,j)=3d(i,j)-1
où d est la famille des nombres de Delannoy;
d(i,j) est le nombre de chemins menant du point
(0,0) au point (i,j) en n'effectuant que des
déplacements d'un pas vers la droite, ou vers le haut, ou en
diagonale. La suite de terme général c(n,n)
est maintenant répertoriée dans le serveur de N. J. A.
Sloane!
Proposé par F. Boisson
Deux exercices: partage d'un polygone à n sommets en deux
parties de longueur le plus semblables possibles.
Algorithme de
satisfiabilité d'une clause de Horn.
Énoncé et Corrigé au format dvi
Énoncé et Corrigé au format PostScript
Énoncé et Corrigé au format ps.gz
Un fichier zip regroupant les fichiers dvi et ps.
Proposé par F. Boisson
Définition et programmation en Caml d'un automate qui permet de vérifier l'addition de deux nombres binaires, c'est-à-dire reconnaissant le langage des mots x0y0z0x1y1z1...xnynzn où xi, yi, zi sont les chiffres binaires de x, y et z avec z=x+y.
Énoncé et Corrigé au format dvi
Énoncé et Corrigé au format PostScript
Énoncé et Corrigé au format ps.gz
Un fichier zip regroupant les fichiers dvi et ps.
Proposé par D. Genoud
Étant donné une suite sur un ensemble totalement ordonné, on se propose d'obtenir une suite formée de la concaténation de sous-suites strictement croissantes de la suite de départ. On utilise deux algorithmes: un naïf et un utilisant un tas.
Énoncé et corrigé au format PostScript
Énoncé et corrigé au format ps.gz
Un fichier zip regroupant les sources du texte et du corrigé en TeX et Caml et le fichier ps.
Proposé par D. Genoud
On définit l'équivalence de Nérode, puis l'automate de Nérode associé à un automate donné; dans la deuxième partie, on étudie un algorithme pour le calculer (par approximations successives) et dans la troisième partie on programme tout ça.
Énoncé et corrigé au format PostScript
Énoncé et corrigé au format ps.gz
Un fichier zip regroupant les sources du texte et du corrigé en TeX et Caml et le fichier ps.
Proposé par D. Genoud
La première partie introduit les résiduels d'un
langage et caractérise les langages rationnels par le fait
qu'ils ont un nombre fini de résiduels; en même temps on
construit l'automate des résiduels et on montre qu'il est
minimal.
Dans la deuxième partie, on montre que tout
automate reconnaissant le même langage et ayant le même
nombre d'états que l'automate minimal lui est isomorphe.
Énoncé et corrigé au format PostScript
Énoncé et corrigé au format ps.gz
Un fichier zip regroupant les sources du texte et du corrigé en TeX et Caml et le fichier ps.
Proposé par D. Genoud
La première partie définit deux implémentations
en Caml d'un graphe, en donnant sa matrice d'adjacence sous forme
matricielle, ou sous forme d'un vecteur v contenant dans v.(i) la
liste des voisins du sommet i, et les fonctions de passage entre ces
deux représentations.
La deuxième partie fait
calculer la matrice d'adjacence de la fermeture transitive d'un
graphe par la méthode naïve d'abord puis par une méthode
plus rapide;
Énoncé et corrigé au format <- HREF="ds11.ps">PostScript
Énoncé et corrigé au format ps.gz
Un fichier zip regroupant les sources du texte et du corrigé en TeX et Caml et le fichier ps.
Proposé par S. Gonnord
Trois exercices et un problème:
Exercice 1: Algorithme pour déterminer la longueur minimum des mots du langage défini par une expression rationnelle.
Exercice 2: On démontre que le langage des palindromes n'est pas rationnel.
Exercice 3: Programmation d'un type ensemble en Caml (par des listes) ainsi que des opérations usuelles: union, intersection, égalité, inclusion, différence.
Problème: Caractérisation des langages rationnels par leur nombre fini de résiduels; application à la construction de l'automate minimal, et à démontrer que la racine d'un langage rationnel est aussi un langage rationnel.
Énoncé au format PostScript
Énoncé au format ps.gz
Un fichier zip regroupant les sources du texte en TeX et le fichier ps.
Proposé par J. Odoux
Quatre exercices:
Programmation en Caml: répétition des éléments d'une liste, et suppression des répétitions d'éléments consécutifs.
Définition des résiduels d'un langage, caractérisation des langages rationnels et construction de l'automate des résiduels d'un langage rationnel.
Deux mots commutent si et seulement si ce sont des puissances d'un même mot.
On donne une fonction en Caml, et on demande ce qu'elle fait.
Énoncé au format PostScript
Énoncé au format ps.gz
Un fichier zip regroupant les sources de l'énoncé en TeX et le fichier ps.
Proposé par J. Odoux
Deux problèmes:
Lemme d'Arden et application au calcul de l'expression rationnelle d'un langage reconnu par un automate fini (sur un exemple).
Quelques questions de programmation en Caml à propos des ensembles.
Énoncé au format PostScript
Énoncé et au format ps.gz
Corrigé au format PostScript
Corrigé au format ps.gz
Un fichier zip regroupant les sources de l'énoncé et du corrigé en TeX et les fichiers ps.
Proposé par J. Odoux
Trois problèmes:
Un tas alternant est un arbre tel que tout sommet de niveau pair a une valeur inférieure ou égale à celle de ses descendants, et tout sommet de niveau impair, une valeur supérieure ou égale à celle de ses descendants; on étudie un algorithme d'adjonction dans un tas alternant et on le programme en Caml.
Le rang d'un élément dans un arbre binaire de recherche est le nombre d'éléments qui lui sont inférieurs ou égaux. Son rang local est son rang dans le sous-arbre dont il est la racine. On calcule le rang en fonction du rang local et on cherche un algorithme d'insertion dans l'arbre mettant à jour le rang local.
Inégalités liant la longueur de cheminement, la taille et la hauteur d'un arbre.
Énoncé au format PostScript
Énoncé au format ps.gz
Corrigé au format PostScript
Corrigé au format ps.gz
Un fichier zip regroupant les sources de l'énoncé et du corrigé en TeX et les fichiers ps.
Proposé par J. Odoux
Trois problèmes:
Automate reconnaissant le langage des expressions arithmétiques sans parenthèses, et ajout d'actions dans l'automate pour évaluer l'expression reconnue.
Algorithme de satisfiabilité d'une clause de Horn.
Programmation Caml: implémentation des opérations sur les rationnels (sous forme irréductible) écrits comme listes de deux entiers.
Énoncé au format PostScript
Énoncé et au format ps.gz
Un fichier zip regroupant les sources de l'énoncé en TeX et le fichier ps.
Proposé par L. Cheno
Nous considérons ici les relations qui apparaissent entre des permutations involutives et des tableaux de nombres, appelés tableaux de Young (ou de Ferrer) et qui possèdent diverses propriétés de monotonie. On implémente l'algorithme qui associe un couple de tableaux de Young à une permutation donnée, ainsi que l'algorithme réciproque, puis l'on montre que l'on obtient deux fois le même tableau dans le cas d'une involution.
Proposé par H. Fauque
Un problème:
On définit les arbres binômiaux
et on étudie quelques unes de leurs propriétés;
puis les files binômiales (qui sont des listes d'arbres
binômiaux) et on l'applique à un algorithme de tri.
Et
trois exercices dont deux sur des exemples d'automates
(déterminisation et calcul du langage) et un sur les
homomorphismes de langages.
Énoncé au format PostScript
Énoncé au format ps.gz
Un fichier zip regroupant les sources de l'énoncé en LaTeX et le fichier ps.
Proposé par H. Fauque
Un problème étudiant divers algorithmes pour
résoudre le problème de la sélection: chercher
le i-ème élément (par ordre croissant) d'un
ensemble d'entiers; on étudie successivement des algorithmes
en n carré, puis en nlog n et finalement linéaire.
Un
exercice construisant un automate reconnaissant des nombres binaires
divisibles par trois;
et un autre montrant que la racine d'un
langage rationnel est un langage rationnel.
Énoncé au format PostScript
Énoncé au format ps.gz
Corrigé au format PostScript
Corrigé au format ps.gz
Un fichier zip regroupant les sources de l'énoncé et du corrigé en TeX et les fichiers ps.
Proposé par H. Fauque
Un DS court (2 heures) comportant une partie sur les automates reconnaissant un motif dans un mot ou à la fin d'un mot, et une sur le rang local dans un arbre binaire de recherche.
Énoncé au format PostScript
Énoncé au format ps.gz
Corrigé au format PostScript
Corrigé au format ps.gz
Un fichier zip regroupant les sources de l'énoncé et du corrigé en TeX et les fichiers ps.
Proposé par F. Boisson
Un exercice sur les circuits logiques (croiser deux signaux sans
croiser les connexions);
Un problème: étant donnés
une liste L de réels supérieurs à 1 et un réel
S, on cherche la plus grande somme d'une sous-liste de L qui soit
inférieure à S.
Énoncé et Corrigé au format PostScript
Énoncé et Corrigé au format ps.gz
Un fichier zip regroupant les sources de l'énoncé et du corrigé en TeX et les fichiers ps.
Proposé par B. Petazzoni.
On construit un circuit additionneur pour des nombres écrits en base 2, et on montre que sa performance ne peut être améliorée, sauf peut-être en changeant de méthode pour représenter les nombres.
On étudie alors une technique de représentation des nombres proposée par Algirdas Avizienis, et permettant l'addition de deux nombres à coût constant; l'idée d'Avizienis consiste à utiliser des chiffres signés.
On s'intéresse ensuite aux langages associés aux parties de N*, lorsqu'un système de numération a été fixé: après avoir défini la reconnaissabilité d'une partie de N*, on donne quelques exemples de parties reconnaissables et de parties qui ne le sont pas.
Enfin, on étudie une autre méthode de représentation des nombres (proposée initialement par Édouard Zeckendorf). Ici, l'idée est de remplacer la suite des puissances d'un même nombre B (la base) par la suite de Fibonacci.
Fonctions booléennes, circuits logiques combinatoire. Méthode diviser pour régner. Résolution de récurrences. Automates finis, expressions régulières.
On peut assez facilement découper ce texte en deux problèmes indépendants: l'un, constitué des deux premières parties; l'autre, formé des deux dernières parties (en prenant la précaution de définir la notation d'Avizienis).
Le livre de Jean-Michel Muller Arithmétique des ordinateurs (Masson) décrit la notation d'Avizienis, et explique comment réaliser des additions en temps constant avec cette notation lorsque la base choisie est 2.
L'additionneur diviser pour régner est décrit dans le livre Foundation of Computer Science de Alfred Aho et Jeffrey Ullman (Computer Science Press) et (la modestie des auteurs dût-elle en souffrir) dans le Cours et exercices d'informatique, Classes préparatoires, 1er et 2nd cycles universitaires coordonné par Luc Albert (ITP/Vuibert).
La méthode de Zeckendorf est exposée dans le tome I du Art of Computer Programming (ex. 1.2.8.34), ainsi que dans Concrete Mathematics (section 6.6). On pourra aussi consulter avec profit le livre de Raymond Séroul math-info: Informatique pour mathématiciens (InterEditions).
On trouvera des compléments sur les bases de numération exotiques (et une bibliographie conséquente sur ce sujet) dans le chapitre 7 (rédigé par Christiane Frougny) du livre Algebraic Combinatorics on Words de Lothaire en préparation; on peut se procurer une préversion de ce chapitre sur le Web.
Toujours sur le Web, signalons un article de Christiane Frougny et Jacques Sakarovitch (à paraître dans un numéro du International Journal of Algebra and Computation dédié à notre maître à tous Marcel-Paul Schützenberger), montrant le lien entre la numération de Zeckendorf et la numération en base phi (le nombre d'or).
Enfin, la reconnaissabilité de parties de N a suscité un intérêt considérable, dont l'origine remonte (au moins) aux premiers articles d'Axel Thue.
Un très grand merci à Véronique Bruyère, Christiane Frougny et Nathalie Loraud.
Énoncé au format PostScript
Énoncé au format ps.gz
Ce sujet est composé d'un court exercice de logique et de deux problèmes indépendants. Le premier traite de langages, et ne demande aucune programmation; le second, d'aspect moins théorique, propose plusieurs questions d'algorithmique et de programmation.
Énoncé au format PostScript
Énoncé au format ps.gz
Cinq exercices indépendants sur les sujets ci-dessus.
Énoncé au format PostScript
Énoncé au format ps.gz
Proposé par D. Goffinet
La partie sur le connecteur de Scheffer est un extrait de Mines
97;
Le problème sur le cobra comporte des photos de l'objet
au format tif.
Un fichier zip regroupant les sources de l'énoncé, du corrigé, les fichiers ps et les photos;
Proposé par B. Petazzoni
Les molécules d'ARN de transfert participent à la synthèse des protéines, en asurant le transport des acides aminés, et en reconnaissant les codons situés sur la molécule d'ARN messager.
La structure primaire d'une molécule d'ARN de transfert est une liste d'environ 100 bases A, C, G ou U; deux bases consécutives sont reliées par une liaison phosphodiester.
La structure secondaire d'une molécule d'ARN est définie par des liaisons secondaires (appariements de bases non adjacentes au moyen de liaisons hydrogène). C'est à cette structure secondaire que nous nous intéressons.
Dans la première partie, on fait abstraction des contraintes d'appariement entre bases. La structure secondaire est ainsi vue comme une involution de l'intervalle discret [1,n] (où n est le nombre de bases de la molécule), possédant des propriétés particulières (pas de transpositions entre éléments adjacents; deux transpositions ne se chevauchent pas). On étudie le nombre S(n) de structures différentes de longueur n, ainsi que le nombre d'épingles à cheveux, qui sont des structures particulières.
Dans les deux parties suivantes, on propose deux représentations possibles de cette structure: par un arbre, par une chaîne de caractères. On écrit des fonctions de conversion entre les différentes représentations.
Dans la dernière partie, on tient compte des contraintes d'appariement entre bases, et on se propose de déterminer le nombre maximal de liaisons secondaires sur une structure primaire donnée.
Un fichier zip regroupant le source de l'énoncé, le fichier dvi, et un résumé HTML du sujet;
Proposé par B. Petazzoni
J'ai eu l'idée de ce texte à l'issue de la séance du 19 mai 1997 du séminaire d'informatique générale de l'Institut Gaspard Monge (Université de Marne-la-Vallée), séance au cours de laquelle Robert Cori a présenté l'automate des tas de sable.
Per Bak, Chao Tang et Kurt Wiesenfeld ont introduit en 1987 un automate cellulaire particulier appelé automate des tas de sable, pour modéliser certains phénomènes physiques, relevant de ce qu'il est convenu d'appeler l'auto-organisation critique.
Deepak Dhar a ensuite étudié cet automate, et mis en évidence des propriétés algébriques intéressantes; en particulier, l'ensemble de ses configurations récursives peut être muni d'une structure de groupe abélien.
Le modèle des tas de sable abéliens a été utilisé dans divers secteurs: tremblements de terre, avalanches, propagation des feux de forêts, cours de la bourse, réseaux de processeurs.
Un fichier zip de l'énoncé au format tex, dvi, ps, un résumé HTML du sujet et des références;
Proposé par B. Petazzoni
Un fichier zip de l'énoncé au format ps.
Proposé par H. Fauque
Deux parties: une sur des automates reconnaissant des mots équilibrés;
l'autre sur les arbres est la deuxième partie de Centrale 97 avec quelques
petites modifications.
Un fichier zip de l'énoncé au format ps.
Proposé par D. Genoud
Le titre dit tout!
Un fichier zip de l'énoncé au format ps et source TeX.
Proposé par B. Petazzoni
La première partie étudie la relation d'ordre associée à la notion de sous-mot. La deuxième partie propose de calculer le nombre de façons dont un mot u peut être obtenu comme sous-mot d'un mot v. Dans la troisième partie on définit le mélange de deux mots. Enfin la dernière partie établit un résultat classique de Higman: dans un ensemble infini de mots, il existe nécessairement un couple de mots (u,v) tels que u soit un sous-mot de v.
Proposé par B. Petazzoni
Pour changer un peu, ce sujet a été spécialement conçu pour les MP. Il est organisé en trois problèmes, comme les épreuves d'informatique des trois grands concours communs.
Proposé par D. Goffinet
C'est un problème, conçu pour 4 heures environ, que j'ai essayé de faire dans le style du chapitre de Weis sur mini-logo. C'est bien sùr plus modeste, c'est dans le cadre de ce que nous racontons à nos étudiants sous le nom de "syntaxe"
Le source Tex ne marchera pas chez vous car j'utilise l'environnement PcTeX en plus de mes fichiers de macros. J'ai laissé ce source pour vous éviter de retaper des morceaux qui vous conviendraient Les enigmes1à3.bmp sont des images de terrains et d'énigmes
Un fichier zip contenant le tout.
On étudie dans ce texte quelques notions relatives aux pavages du plan au moyen de tuiles carrées de côté 1. On présente en particulier les pavages de Wang.
On introduit ensuite la notion de motif régulier, qui permet de définir les pavages quasi-périodiques; on définit alors deux fonctions qui mesurent chacune, d'une certaine manière, la plus ou moins grande complexité du pavage.
Références pour ce problème:Pour m'écrire, cliquez ici.
Proposé par B. Petazzoni
Ce sujet est organisé en deux problèmes, comme les épreuves d'informatique de certains des concours communs.
Le premier problème vous propose de revoir le lemme de l'étoile, puis de découvrir un lemme analogue dû à Guo-Qiang Zhang et E. Rodney Canfield.
Le deuxième problème est orienté vers la programmation; il définit une structure de données permettant de décrire les parties finies ou cofinies de N, puis demande l'écriture de fonctions réalisant les calculs usuels dans cette algèbre: tests d'appartenance et d'inclusion, complémentation, union, intersection.
Référence pour le premier problème: The end of pumping, Guo-Qiang Zhang et E. Rodney Canfield, Theoretical Computer Science, vol. 174, Issue 1-2, 1997, 275-279. Cet article est disponible ici.
Pour m'écrire, cliquez ici.
Proposé par B. Petazzoni
Proposé par B. Petazzoni
Le théorème de Kleene affirme l'équivalence entre reconnaissabilité et rationalité. On connaît des preuves constructives de ce théorème: une telle preuve fournit un algorithme associant à un automate A une expression rationnelle e qui décrit le langage reconnu par A, ou, en sens inverse, associant à une expression rationnelle e un automate A qui reconnaît le langage décrit par e.
C'est à cette deuxième construction, d'utilisation fréquente, que nous nous intéresserons. La méthode la plus connue, et aussi la plus facile à expliquer, repose sur l'utilisation des automates de Thompson. Nous étudierons ici une autre méthode, connue sous le nom d'algorithme de Berry-Sethi (mais qui, en fait, a été exposée en premier par Glushkov).
L'énoncé s'inspire très largement de l'article paru dans le numéro 155 de la revue Theoretical Computer Science et cosigné par Jean Berstel et Jean-Éric Pin.
Proposé par L. Cheno.
Proposé par B. Petazzoni.
Ce sujet est organisé en deux problèmes indépendants. Le premier présente la notion de distance de Hamming entre deux mots de même longueur, puis vous invite à établir diverses propriétés des langages, et en particulier des langages rationnels, liées à cette distance. Au menu: automates finis, lemme de l'étoile, induction structurelle, programmation en Caml.
Le deuxième texte définit la notion de bassin d'attraction d'une fonction itérable et établit quelques propriétés simples; on étudie ensuite un exemple pratique. Ne demande pas de connaissances spécifiques; quelques questions de programmation en Caml.
Proposé par B. Petazzoni.
La notion de complexité est restée longtemps intuitive: si chacun fait aisément la différence entre un objet simple (disons, le pinpon d'une sirène) et un objet compliqué (par exemple, un mouvement de quatuor à cordes), ce n'est que récemment que cette différence a reçu une définition rigoureuse (en fait, plusieurs). Ainsi, Gregory Chaitin a proposé de définir la complexité d'une suite de n bits, comme la taille minimale d'un programme écrivant cette suite.
Dans le cas d'un langage rationnel, plusieurs points de vues sont possibles, puisqu'il existe diverses façons de décrire un tel langage: avec un expression rationnelle, ou avec un automate fini, déterministe ou non.
Dans ce texte, nous définissons la complexité d'un langage rationnel L comme la taille minimale (en nombre d'états) d'un automate fini, déterministe, complet, reconnaissant L.
Nous nous intéresserons à l'effet des opérations usuelles sur cette complexité: par exemple, si l'on connaît les complexités de deux langages rationnels L et M, que peut-on dire de la complexité de de la réunion de ces deux langages?
Proposé par B. Petazzoni.
Le problème du rangement de boîtes (bin packing) est un des classiques de l'optimisation combinatoire. Dans ce problème, on veut ranger un ensemble de boîtes, de volumes variés, dans des conteneurs ayant tous le même volume.
On se propose d'étudier diverses propriétés du rangement optimal. L'obtention d'un tel rangement optimal constitue un problème NP-complet.
On analyse ensuite diverses stratégies (ou heuristiques) donnant un résultat pas trop éloigné de l'optimum: rangement séquentiel, puis stratégie first fit. Le cas où cette dernière stratégie est appliquée à une entrée décroissante fait l'objet d'une étude particulière.
Les premières parties s'inspirent d'un sujet de l'option Mathématiques de l'Informatique de l'Agrégation de Mathématiques (session de 1987). Plusieurs questions complémentaires proviennent des manuels d'informatique de Sara Baase et d'Udi Manber (publiés tous deux par Addison-Wesley).
Proposé par B. Petazzoni.
Ce sujet a été spécialement conçu pour les MP. Il est organisé en trois exercices; il vous permettra de réviser vos connaissances sur les circuits logiques, les automates finis, et enfin la logique telle que la percevait le concepteur du sujet du concours commun Centrale and co, session de 1998.
Proposé par B. Petazzoni.
On s'intéresse dans ce texte à l'effet sur les langages rationnels de l'opération d'extraction: dans cette opération, on fixe une partie infinie S de N* et, d'un mot donné, on ne garde que les lettres dont les indices appartiennent à S. Dans une première partie, on étudie le cas où S est l'ensemble des naturels pairs: l'extraction consiste donc à ne garder, d'un mot, que les lettres d'indice impair. On montre que si L est rationnel, alors le langage déduit de L par cette extraction est lui aussi rationnel. Ce résultat est généralisé ensuite aux extractions basées sur une partie de N* est ultimement périodique. La partie programmation demande l'écriture de fonctions effectuant les opérations courantes dans l'algèbre des parties ultimement périodiques de N*: tests d'appartenance et d'inclusion, construction du complémentaire, de la réunion, de l'intersection. Il est possible de traiter cette partie indépendamment des autres; il suffit de lire la définition d'une partie ultimement périodique et d'admettre que l'ensemble des parties ultimement périodiques de $N*$ est stable par union finie, intersection finie et complémentation.
Proposé par B. Petazzoni.
La notion de morphisme s'introduit naturellement, dans la structure algébrique X*. Dans une première partie, on observe le lien avec le calcul matriciel classique.
Un morphisme est itérable; on s'intéresse dans une deuxième partie aux lettres récurrentes pour un morphisme, et on propose un algorithme de détermination de ces lettres, basé sur le calcul matriciel.
Aristid Lindenmayer a été le premier à étudier le langage formé par les images d'une lettre (ou d'un mot) par les itérés d'un morphisme. On appelle désormais L-système un tel langage. La troisième partie étudie quelques questions simples sur les L-systèmes.
Dans la quatrième partie, on s'intéresse au problème suivant: comment déterminer de manière efficace la i-ième lettre de l'image de a par le n-ième itéré du morphisme f.
Enfin, la cinquième partie propose une mise en oeuvre en Caml.
Proposé par L. Cheno.
Ce devoir se compose d'un petit exercice de logique et d'un problème sur les automates. L'exercice fait traduire formellement des propositions données en français courant. Il demande la mise sous forme normale disjonctive et une traduction de la réponse en français courant. Le problème s'intéresse dans une première partie à stabilité par morphisme et morphisme inverse des langages rationnels, et propose quelques applications élémentaires. Une seconde partie étudie les mots de Thue-Morse, et termine par une preuve de non rationnalité d'un langage pour lequel aucune démonstration à l'aide du lemme de pompage n'est possible.
Proposé par B. Petazzoni.
Enoncé au format ps.
Proposé par B. Petazzoni.
Enoncé au format ps.
Proposé par B. Petazzoni.
Enoncé au format ps.
Proposé par B. Petazzoni.
Enoncé au format ps.
Proposé par J. Debarbieux
Implémentation des files d'attente en Pascal;
Source plain TeX de l'énoncé
Énoncé au format PostScript
Énoncé au format ps.gz
Proposé par G. Bertrand.
tri rapide de listes; élément médian d'un tableau; formation d'un train à l'aide d'une pile.
Source plain TeX de l'énoncé
Énoncé au format PostScript
Énoncé au format ps.gz
Source plain TeX du corrigé
Corrigé au format PostScript
Corrigé au format ps.gz
Un fichier zip regroupant les sources de l'énoncé et du corrigé en TeX et les fichiers ps.
Proposé par Luc Albert.
Tri par insertion, par sélection, tri à bulles et tri fusion.
Source plain TeX de l'énoncé (accents au format ISO)
Source plain TeX de l'énoncé (accents au format Mac)
Énoncé au format PostScript
Énoncé au format ps.gz
Source plain TeX du corrigé (accents au format ISO)
Source plain TeX du corrigé (accents au format Mac)
corrigé au format PostScript
Énoncé au format ps.gz
Un fichier zip regroupant les sources de l'énoncé et du corrigé en TeX et les fichiers ps.
Dernière modification le 8 novembre 1998