diff options
| -rw-r--r-- | programme-inf105.tex | 145 | ||||
| -rwxr-xr-x | vc | 2 |
2 files changed, 147 insertions, 0 deletions
diff --git a/programme-inf105.tex b/programme-inf105.tex new file mode 100644 index 0000000..5b159ed --- /dev/null +++ b/programme-inf105.tex @@ -0,0 +1,145 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +%\usepackage{ucs} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\usepackage{graphics} +\usepackage[usenames,dvipsnames]{xcolor} +\usepackage{tikz} +\usetikzlibrary{matrix} +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\thingy{% +\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} } +\renewcommand{\qedsymbol}{\smiley} +\renewcommand{\thefootnote}{\fnsymbol{footnote}} +% +\DeclareUnicodeCharacter{00A0}{~} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +% +% +\begin{document} +\title{THL (Théorie des langages)\\Programme indicatif} +\author{David A. Madore} +\maketitle + +\centerline{\textbf{MITRO206}} + +{\footnotesize +\immediate\write18{sh ./vc > vcline.tex} +\begin{center} +Git: \input{vcline.tex} +\end{center} +\immediate\write18{echo ' (stale)' >> vcline.tex} +\par} + + +% +% +% + +\thingy Présentation générale. Alphabet, mots, langages. Opérations +et notions sur les mots : concaténation de deux mots, longueur d'un +mot ; préfixe, suffixe, facteur, sous-mot et mot miroir. + +Opérations sur les langages : opérations booléennes (complémentaire, +union, intersection), concaténation, étoile de Kleene. Définition des +langages rationnels. Expressions rationnelles. + + +\thingy Automates finis : automates déterministes (DFA), automates +déterministes à spécification incomplète, automates non déterministes +(NFA), automates non déterministes à transitions spontanées +($\varepsilon$-NFA). + +Équivalence entre ces différentes sortes d'automates. Langages +reconnaissables. + + +\thingy Stabilité des langages reconnaissables par complémentaire, +union, intersection ; stabilité par concaténation et étoile de Kleene. +Les langages rationnels sont reconnaissables. Automate de Thompson. + +Automates à transitions étiquetées par des expressions rationnelles +(informellement), équivalence avec les autres sortes d'automates, +équivalence avec les expressions rationnelles (par élimination des +états). Équivalence entre langages rationnels et reconnaissables. + + +\thingy Énoncé et démonstration du lemme de pompage pour les +langages rationnels (=reconnaissables). + +DFA minimal\footnote{On conviendra d'utiliser la notion d'automate + déterministe \emph{complet}, et la première étape de minimisation + sera de compléter l'automate en lui ajoutant éventuellement un + puits.} (=canonique). Algorithme de minimisation. + + +\thingy TD sur les automates finis. + + +\thingy TP sur les expressions régulières et automates finis. + + +\thingy Grammaires hors contexte\footnote{Je propose pour gagner du + temps de ne faire que mentionner au passage le fait qu'il existe des + grammaires plus générales, sans entrer dans les détails.}, langages +algébriques (=définis par une grammaire hors contexte). Dérivations, +dérivations gauches et droites. Arbre d'analyse (=de dérivation). +Ambiguïté (grammaires inambiguës et ambiguës, exemple de langage +intrinsèquement ambigu). + + +\thingy Stabilité des langages algébriques par réunion, concaténation +et étoile de Kleene. Les langages algébriques sont rationnels : +d'après ce qu'on vient de dire et directement en associant une +grammaire à un DFA ou NFA. + +Énoncé du lemme de pompage pour les langages algébriques. + +(Selon le temps disponible.) L'appartenance d'un mot au langage +défini par une grammaire hors contexte est algorithmiquement +décidable. Quelques idées sur l'analyse syntaxique en pratique : +notion d'analyseurs descendants et ascendants. + + +\thingy TD sur les grammaires hors contexte. + + +\thingy Notions de calculabilité\footnote{Mieux vaut sans doute ne pas + perdre de temps à introduire un modèle de calculabilité particulier + (machine de Turing ou fonctions générales récursives, par exemple) : + insister sur le fait que tout langage de programmation raisonnable, + suffisamment idéalisé, est équivalent.} : algorithme, terminaison +d'un algorithme, thèse de Church-Turing. + +Ensembles/langages\footnote{Souligner qu'ici contrairement au reste du + cours, on peut indifféremment considérer des ensembles d'entiers + naturels ou de mots.} décidables (=récursifs) et semi-décidables +(=récursivement énumérables). Notion de machine universelle. +Indécidabilité du problème de l'arrêt. + + +\thingy TP sur les grammaires hors contexte avec JavaCC. + + +% +% +% +\end{document} @@ -0,0 +1,2 @@ +#! /bin/sh +git log --pretty=format:'\verb=%h %ad=' -1 |