summaryrefslogtreecommitdiffstats
path: root/programme-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-11-04 17:01:58 +0100
committerDavid A. Madore <david+git@madore.org>2016-11-04 17:01:58 +0100
commitaf232b0c40629b93417ce5be58a1648957cc5846 (patch)
tree06c969fb7291fc8911ebe30cc37f88d20a0d5b31 /programme-inf105.tex
downloadinf105-af232b0c40629b93417ce5be58a1648957cc5846.tar.gz
inf105-af232b0c40629b93417ce5be58a1648957cc5846.tar.bz2
inf105-af232b0c40629b93417ce5be58a1648957cc5846.zip
Planned curriculum for INF105.
Diffstat (limited to 'programme-inf105.tex')
-rw-r--r--programme-inf105.tex145
1 files changed, 145 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}