DS d'informatique


Devoirs donnés en Spé MP/MP*:

DS1

un texte tiré de Combinatorics on words

DS2

langages infinitaires rationnels

DS4

sous-mots, distance d'édition, plus longue sous-chaîne commune

DS6

partage d'un polygône, satisfiabilité d'une clause de Horn.

DS7

Automate de vérification d'addition

DS8

Sous-suites croissantes d'une suite donnée

DS9

Minimisation d'un automate

DS10

Automate minimal par la méthode des résiduels

DS11

Fermeture transitive d'un graphe

DS12

longueur minimum des mots d'un langage; palindromes; ensembles en Caml; automate minimal par la méthode des résiduels;

DS13

listes en Caml; automate des résiduels; mots qui commutent; fonction à découvrir en Caml;

DS14

expression rationnelle d'un langage avec le lemme d'Arden; programmation des ensembles en Caml;

DS15

Tas alternants; rang local dans un arbre binaire de recherche; longueur de cheminement dans un arbre;

DS16

expressions arithmétiques sans parenthèses; satisfiabilité d'une clause de Horn; les rationnels en Caml;

DS17

L'algorithme de Robinson, Schensted et Knuth

DS18

arbres et files binômiales; exercices sur les automates; homomorphismes sur les langages;

DS19

Algorithme de sélection; automate des nombres binaires divisibles par trois; racine d'un langage;

DS20

automates et motifs; rang local dans un arbre binaire de recherche;

DS21

circuits logiques; plus grande somme de sous-listes;

DS22

Additionneurs, systèmes de numération, parties reconnaissables de N*

DS23

logique; langages.

DS24

logique; automates; arbres binaires.

DS25

Connecteur de Sheffer et problème sur le cobra (objet genre Rubik's cube).

DS26

Structure secondaire de l'ARN de transfert.

DS27

Automate des tas de sable.

DS28

Déterminisation de l'automate d'un langage fini.

DS29

Automates et arbres.

DS30

Forme exclusive d'une expression booléenne.

DS31

Sous-mots, mélanges de mots, théorème de Higman.

DS32

Racine carrée d'un langage; circuits logiques; algorithme de découpage en lignes.

DS33

Dr Brain

DS34

Pavages, périodicité, quasi-périodicité.

DS35

Lemme de l'étoile et programmation.

DS36

Langages rationnels sur un alphabet à une lettre.

DS37

Algorithme de Berry-Sethi.

DS38

Arbres, dictionnaires, files binomiales.

DS39

Distance de Hamming; bassin d'attraction.

DS40

complexité des opérations sur les langages rationnels

DS41

Problème du bin packing.

DS42

logique et automates finis.

DS43

extractions conservant la rationnalité.

DS44

Morphismes, L-systèmes, lettres récurrentes.

DS45

logique et automates.

DS46

Autour du mot de Kolakoski.

DS47

Approche matricielle des automates.

DS48

Polynôme d'autocorrélation d'un motif.

DS49

connectivité dans les graphes et protocole d'information de routage



Devoirs donnés en Sup MPSI:

DSup1

Files d'attente

DSup2

tri rapide de listes; élément médian d'un tableau.

DSup3

Différents algorithmes de tri.






DS1: Un texte tiré de Combinatorics on words


Proposé par B. Petazzoni

Il s'agit du problème qui clôt le premier chapitre du livre de Lothaire Combinatorics on words.


Retour en haut de la page

Page d'accueil






DS2: Langages infinitaires rationnels


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.


Retour en haut de la page

Page d'accueil






DS4: Sous-mots, distance d'édition, plus longue sous-chaîne commune


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.


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:

1,4,19,94,481


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!

Retour en haut de la page

Page d'accueil






DS6: partage d'un polygone, satisfiabilité d'une clause de Horn.


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.


Retour en haut de la page

Page d'accueil






DS7: Automate de vérification d'addition


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.


Retour en haut de la page

Page d'accueil






DS8: Sous-suites croissantes d'une suite donnée


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.


Retour en haut de la page

Page d'accueil






DS9: Minimisation d'un automate


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.


Retour en haut de la page

Page d'accueil






DS10: Automate minimal par la méthode des résiduels


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.


Retour en haut de la page

Page d'accueil






DS11: Fermeture transitive d'un graphe


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;


Retour en haut de la page

Page d'accueil






DS12: longueur minimum des mots d'un langage; palindromes; ensembles en Caml; automate minimal par la méthode des résiduels;


Proposé par S. Gonnord

Trois exercices et un problème:


Retour en haut de la page

Page d'accueil






DS13: listes en Caml; automate des résiduels; mots qui commutent; fonction à découvrir en Caml;


Proposé par J. Odoux

Quatre exercices:

  1. Programmation en Caml: répétition des éléments d'une liste, et suppression des répétitions d'éléments consécutifs.

  2. 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.

  3. Deux mots commutent si et seulement si ce sont des puissances d'un même mot.

  4. On donne une fonction en Caml, et on demande ce qu'elle fait.


Retour en haut de la page

Page d'accueil






DS14: expression rationnelle d'un langage avec le lemme d'Arden; programmation des ensembles en Caml;


Proposé par J. Odoux

Deux problèmes:

  1. Lemme d'Arden et application au calcul de l'expression rationnelle d'un langage reconnu par un automate fini (sur un exemple).

  2. Quelques questions de programmation en Caml à propos des ensembles.


Retour en haut de la page

Page d'accueil






DS15: Tas alternants; rang local dans un arbre binaire de recherche; longueur de cheminement dans un arbre;


Proposé par J. Odoux

Trois problèmes:

  1. 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.

  2. 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.

  3. Inégalités liant la longueur de cheminement, la taille et la hauteur d'un arbre.


Retour en haut de la page

Page d'accueil






DS16: expressions arithmétiques sans parenthèses; satisfiabilité d'une clause de Horn; les rationnels en Caml;


Proposé par J. Odoux

Trois problèmes:

  1. Automate reconnaissant le langage des expressions arithmétiques sans parenthèses, et ajout d'actions dans l'automate pour évaluer l'expression reconnue.

  2. Algorithme de satisfiabilité d'une clause de Horn.

  3. Programmation Caml: implémentation des opérations sur les rationnels (sous forme irréductible) écrits comme listes de deux entiers.


Retour en haut de la page

Page d'accueil






DS17: L'algorithme de Robinson, Schensted et Knuth


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.


Retour en haut de la page

Page d'accueil






DS18: arbres et files binômiales; exercices sur les automates; homomorphismes sur les langages;


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.


Retour en haut de la page

Page d'accueil






DS19: Algorithme de sélection; automate des nombres binaires divisibles par trois; racine d'un langage;


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.


Retour en haut de la page

Page d'accueil






DS20: automates et motifs; rang local dans un arbre binaire de recherche;


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.


Retour en haut de la page

Page d'accueil






DS21: circuits logiques; plus grande somme de sous-listes;


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.


Retour en haut de la page

Page d'accueil






DS22: Additionneurs, systèmes de numération, parties reconnaissables de N*


Proposé par B. Petazzoni.

Présentation du sujet

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.

Parties du programmes utilisées

Fonctions booléennes, circuits logiques combinatoire. Méthode diviser pour régner. Résolution de récurrences. Automates finis, expressions régulières.

Une remarque

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).

Quelques références complémentaires

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.

Pour conclure

Un très grand merci à Véronique Bruyère, Christiane Frougny et Nathalie Loraud.


Retour en haut de la page

Page d'accueil






DS23: logique; langages

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.


Retour en haut de la page

Page d'accueil






DS24: logique; automates; arbres binaires.

Cinq exercices indépendants sur les sujets ci-dessus.


Retour en haut de la page

Page d'accueil






DS25: Connecteur de Sheffer et problème sur le cobra (objet genre Rubik's cube).


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.


Retour en haut de la page

Page d'accueil






DS26: Structure secondaire de l'ARN de transfert


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.


Retour en haut de la page

Page d'accueil






DS27: Automate des tas de sable


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.


Retour en haut de la page

Page d'accueil






DS28: Déterminisation de l'automate d'un langage fini.


Proposé par B. Petazzoni


Retour en haut de la page

Page d'accueil






DS29: Automates et arbres.


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.


Retour en haut de la page

Page d'accueil






DS30: Forme exclusive d'une expression booléenne.


Proposé par D. Genoud

Le titre dit tout!


Retour en haut de la page

Page d'accueil






DS31: Sous-mots, mélanges de mots, théorème de Higman.


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.


Retour en haut de la page

Page d'accueil






DS32: Racine carrée d'un langage; circuits logiques; algorithme de découpage en lignes.


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.



Retour en haut de la page

Page d'accueil






DS33: Dr Brain


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


Retour en haut de la page

Page d'accueil






DS34: Pavages, périodicité, quasi-périodicité
(d'après Bruno Durand)


Proposé par B. Petazzoni

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.


Retour en haut de la page

Page d'accueil






DS35: Lemme de l'étoile et programmation.


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.


Retour en haut de la page

Page d'accueil






DS36: Langages rationnels sur un alphabet à une lettre.


Proposé par B. Petazzoni


Retour en haut de la page

Page d'accueil






DS37: Algorithme de Berry-Sethi.


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.


Retour en haut de la page

Page d'accueil






DS38: Arbres, dictionnaires, files binomiales.


Proposé par L. Cheno.


Retour en haut de la page

Page d'accueil






DS39: Distance de Hamming; bassin d'attraction.


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.


Retour en haut de la page

Page d'accueil






DS40: complexité des opérations sur les langages rationnels


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?


Retour en haut de la page

Page d'accueil






DS41: Problème du bin packing.


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).


Retour en haut de la page

Page d'accueil






DS42: logique et automates finis.


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.


Retour en haut de la page

Page d'accueil






DS43: extractions conservant la rationnalité.


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.


Retour en haut de la page

Page d'accueil






DS44: Morphismes, L-systèmes, lettres récurrentes


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.


Retour en haut de la page

Page d'accueil






DS45: logique et automates.


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.


Retour en haut de la page

Page d'accueil






DS46: Autour du mot de Kolakoski


Proposé par B. Petazzoni.


Retour en haut de la page

Page d'accueil






DS47: Approche matricielle des automates.


Proposé par B. Petazzoni.

On présente l'approche matricielle de la théorie des automates, telle qu'elle a été exposée par Guo-Qiang Zhang. On montre l'utilité de cette approche, pour résoudre des exercices classiques liés à la notion de fonction conservant la rationalité.


Retour en haut de la page

Page d'accueil






DS48: Polynôme d'autocorrélation d'un motif.


Proposé par B. Petazzoni.

Polynôme d'autocorrélation d'un motif et expression de la série génératrice associée au langage évitant ce motif.


Retour en haut de la page

Page d'accueil






DS49: Connectivité dans les graphes et protocole d'information de routage.


Proposé par B. Petazzoni.

Dans un réseau informatique, le routage est l'opération qui consiste à chercher un chemin pour transporter des données d'une source s vers une destination t. Dans ce sujet, nous donnerons une description simplifiée du RIP (Routing Information Protocol) qui a été le premier protocole d'information de routage mis en oeuvre dans l'Internet et est décrit dans la RFC 1058.


Retour en haut de la page

Page d'accueil






DSup1: Files d'attente


Proposé par J. Debarbieux

Implémentation des files d'attente en Pascal;


Retour en haut de la page

Page d'accueil






DSup2: tri rapide de listes; élément médian d'un tableau.


Proposé par G. Bertrand.

tri rapide de listes; élément médian d'un tableau; formation d'un train à l'aide d'une pile.


Retour en haut de la page

Page d'accueil






DSup3: Différents algorithmes de tri.


Proposé par Luc Albert.

Tri par insertion, par sélection, tri à bulles et tri fusion.


Retour en haut de la page

Page d'accueil





Dernière modification le 8 novembre 1998