More slides on intro to computability.

1 files changed, 147 insertions, 0 deletions

diff --git a/transp-inf110-01-calc.tex b/transp-inf110-01-calc.tex
index 1ed0662..bd41cfb 100644
--- a/transp-inf110-01-calc.tex
+++ b/transp-inf110-01-calc.tex
@@ -147,6 +147,45 @@ Difficultés :
 \end{frame}
 %
 \begin{frame}
+\frametitle{Sans préoccupation d'efficacité}
+
+\itempoint La calculabilité \alert{ne s'intéresse pas à l'efficacité}
+des algorithmes qu'elle étudie, uniquement leur \textbf{terminaison en
+  temps fini}.
+
+\medskip
+
+P.ex. : pour savoir si $n$ est premier, on peut tester si $i\times
+j=n$ pour tout $i$ et $j$ allant de $2$ à $n-1$.  (Hyper inefficace ?
+On s'en fout.)
+
+\bigskip
+
+\itempoint La calculabilité \alert{n'a pas peur des grands entiers}.
+
+\medskip
+
+P.ex. : \textbf{fonction d'Ackermann} définie par :
+\[
+\begin{aligned}
+A(m,n,0) &= m+n \\
+A(m,1,k+1) &= m \\
+A(m,n+1,k+1) &= A(m,\,A(m,n,k+1),\,k)
+\end{aligned}
+\]
+définition algorithmique par récursion, donc calculable.
+
+\smallskip
+
+Mais $A(2,6,3) = 2^{2^{2^{2^{2^2}}}} = 2^{2^{65\,536}}$ et $A(2,4,4) =
+A(2,65\,536,3)$ est inimaginablement grand (et que dire de
+$A(100,100,100)$ ?).
+
+$\Rightarrow$ Ingérable sur un vrai ordinateur.
+
+\end{frame}
+%
+\begin{frame}
 \frametitle{Approches de la calculabilité}
 
 \itempoint Approche informelle : \textbf{algorithme = calcul
@@ -217,4 +256,112 @@ Pour toutes ces raisons, le sujet mérite d'être étudié !
 
 \end{frame}
 %
+\begin{frame}
+\frametitle{Données finies}
+
+Un algorithme travaille sur des \textbf{données finies}.
+
+\medskip
+
+Qu'est-ce qu'une « donnée finie » ?  Tout objet représentable
+informatiquement : booléen, entier, chaîne de caractères, structure,
+liste/tableau de ces choses, ou même plus complexe (p.ex., graphe).
+
+\medskip
+
+$\rightarrow$ Comment y voir plus clair ?
+
+\bigskip
+
+Deux approches opposées :
+\begin{itemize}
+\item\textbf{typage} : distinguer toutes ces données,
+\item\textbf{codage de Gödel} : tout représenter comme des entiers !
+\end{itemize}
+
+\bigskip
+
+Le typage est plus élégant, plus satisfaisant, plus proche de
+l'informatique réelle.
+
+\smallskip
+
+Le codage de Gödel simplifie l'approche/définition de la calculabilité
+(on étudie juste des fonctions $\mathbb{N} \dasharrow \mathbb{N}$).
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Codage de Gödel (« tout est un entier »)}
+
+\itempoint Représenter \textbf{n'importe quelle donnée finie par un
+  entier}.
+
+\bigskip
+
+\itempoint Codage des couples : par exemple,
+\[
+\langle m,n\rangle := m + \frac{1}{2}(m+n)(m+n+1)
+\]
+définit une bijection calculable $\mathbb{N}^2 \to \mathbb{N}$.
+
+\bigskip
+
+\itempoint Codage des listes finies : par exemple,
+\[
+\langle\!\langle a_0,\ldots,a_{k-1}\rangle\!\rangle
+:= \langle a_0, \langle a_1, \langle\cdots,\langle a_{k-1},0\rangle+1\cdots\rangle+1\rangle+1
+\]
+définit une bijection calculable $\{\text{suites finies dans $\mathbb{N}$}\} \to \mathbb{N}$.
+
+\bigskip
+
+\itempoint Il sera aussi utile de représenter les programmes par des
+entiers.
+
+\bigskip
+
+\itempoint Les détails du codage sont \textbf{sans importance}.
+
+\bigskip
+
+\itempoint\alert{Ne pas utiliser dans la vraie vie} (hors calculabilité) !
+
+\end{frame}
+%
+\begin{frame}
+\frametitle{Fonctions partielles}
+
+\itempoint Même si on s'intéresse à des algorithmes qui
+\textbf{terminent}, la définition de la calculabilité \alert{doit
+  forcément} passer aussi par ceux qui ne terminent pas.
+
+{\footnotesize (Aucun langage Turing-complet ne peut exprimer
+  uniquement des algorithmes qui terminent toujours, à cause de
+  l'indécidabilité du problème de l'arrêt.)\par}
+
+\bigskip
+
+\itempoint Lorsque l'algorithme censé calculer $f(n)$ ne termine pas,
+on dira que $f$ n'est pas définie en $n$, et on notera $f(n)\uparrow$.
+Au contraire, s'il termine, on note $f(n)\downarrow$.
+
+\bigskip
+
+\itempoint Notation : $f\colon \mathbb{N} \dasharrow \mathbb{N}$ :
+une fonction $D \to \mathbb{N}$ définie sur une partie $D \subseteq
+\mathbb{N}$.
+
+\itempoint Notation : $f(n) \downarrow$ signifie « $n \in D$ », et $f(n)
+\uparrow$ signifie « $n \not\in D$ ».
+
+\itempoint Notation : $f(n) \downarrow = g(m)$ signifie
+« $f(n)\downarrow$ et $g(m)\downarrow$ et $f(n) = g(m)$ ».
+
+\itempoint Convention : $f(n) = g(m)$ signifie « $f(n)\downarrow$ ssi
+$g(m)\downarrow$, et $f(n) = g(m)$ si $f(n)\downarrow$ ».  (Certains
+préfèrent $f(n) \simeq g(m)$ pour ça.)
+
+\end{frame}
+%
 \end{document}