 | |
| INFO0213-2 | Automates et langages formels
 |
|
| Durée : | 30h Th, 10h Pr, 20h TD |
|
| Crédits/ECTS : |
| Master en sciences mathématiques, à finalité approfondie, 1re année | | Premier quadrimestre | | 10 |
|
| Master en sciences mathématiques, à finalité didactique, 1re année | | Premier quadrimestre | | 10 |
|
| Master en sciences mathématiques, à finalité spécialisée en gestion, 1re année | | Premier quadrimestre | | 10 |
|
| Master en sciences mathématiques, à finalité spécialisée en informatique, 1re année | | Premier quadrimestre | | 10 |
|
| Master en sciences mathématiques, à finalité spécialisée, 1re année | | Premier quadrimestre | | 10 |
|
| Master sciences mathématiques | | Premier quadrimestre | | 10 |
|
|
|
| Titulaire(s) : | Michel Rigo |
|
| Langue : | Langue française |
|
| Aperçu général : | On présente quelques notions fondamentales de la théorie des langages formels et de combinatoire des mots. On étudie les langages réguliers et algébriques en insistant sur leurs aspects théoriques mais aussi algorithmiques (automates finis, automates à pile). Ces concepts trouvent en particulier de nombreuses applications en informatique (théorique) comme par exemple l'analyse syntaxique, la vérification ou encore la compilation mais aussi en mathématiques : systèmes de numération et théorie élémentaire des nombres, logique, théorie des graphes, combinatoire, ... |
|
| Objectif du cours : | Dans ce cours, on introduit la notion de langage formel (constitué de mots finis sur un alphabet fini). Cette présentation est illustrée par quelques résultats classiques en combinatoire sur les mots (facteurs inévitables, motifs, mots périodiques ou récurrents, ...). On s'intéresse tout d'abord aux langages possédant les propriétés syntaxiques les plus simples, à savoir les langages réguliers. Les thèmes abordés sont : expressions régulières, automates finis déterministes, automates non déterministes, automate minimal et congruence de Nerode, minimisation d'automates, expressions sans étoile, monoïde syntaxique, théorèmes de stabilité, théorèmes de gonflement, problème de dénombrement, étude asymptotique, .... Une large part du cours est consacrée à la présentation théorique de ces concepts. On donnera néanmoins quelques applications en algorithmique du texte mais aussi en arithmétique par l'intermédiaire des systèmes de numération. Dans la deuxième partie, on présente les langages algébriques : grammaires hors contexte, arbres de dérivation, théorème de Parikh et ensembles semi-linéaires, langages commutatifs, formes normales, automates à pile, langages de Dyck,... |
|
| Pré-requis : | Aucun pré-requis mais nous utiliserons parfois des notions vues dans le cours de théorie des graphes ou de calculabilité. |
|
| Organisation : | Le cours est consacré principalement aux aspects théoriques des langages formels. Les séances de répétition permettent de présenter la résolution d'exercices mais surtout l'illustration et la concrétisation des concepts vus au cours. L'horaire des cours et des séances d'exercices sera communiqué en début d'année. La réalisation d'un travail personnel en cours d'année pourra être envisagée. |
|
| Notes de cours : | Des notes de cours seront distribuées aux étudiants lors du premier cours. Elles sont aussi téléchargeables sur http://www.discmath.ulg.ac.be/ (http://) |
|
| Evaluation : | L'examen en session comporte une partie orale et une partie écrite. La partie écrite concerne uniquement la résolution d'exercices. La partie orale porte sur la théorie et ses applications directes. La matière de l'examen et les modalités d'interrogation seront précisées par un affichage aux valves. La cote finale pourra également prendre en compte les travaux personnels. |
|
| Contacts : | M. Rigo
Institut de Mathématique (B37) - Grande Traverse 12 - Sart Tilman, 4000 Liège
Tél. : (04) 366.94.87 - E-mail : M.Rigo@ulg.ac.be |
|
| Remarques : | Des compléments d'information sont disponibles sur http://www.discmath.ulg.ac.be/ |
|
|
| |
