Planned curriculum for INF105.

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}
diff --git a/vc b/vc
new file mode 100755
index 0000000..2ab3e90
--- /dev/null
+++ b/vc
@@ -0,0 +1,2 @@
+#! /bin/sh
+git log --pretty=format:'\verb=%h %ad=' -1