diff options
| -rw-r--r-- | exercices3.tex | 197 |
1 files changed, 197 insertions, 0 deletions
diff --git a/exercices3.tex b/exercices3.tex new file mode 100644 index 0000000..eb19a9f --- /dev/null +++ b/exercices3.tex @@ -0,0 +1,197 @@ +%% 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{arrows,automata,positioning} +\usepackage[hyperindex=false]{hyperref} +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\thingy{% +\refstepcounter{comcnt}\smallbreak\noindent\textbf{\thecomcnt.} } +\newcommand\exercice{% +\refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}} +\renewcommand{\qedsymbol}{\smiley} +% +\newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax} +% +\DeclareUnicodeCharacter{00A0}{~} +\DeclareUnicodeCharacter{03B5}{$\varepsilon$} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +% +\DeclareFontFamily{U}{manual}{} +\DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} +\newcommand{\manfntsymbol}[1]{% + {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} +\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped +\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% + \hbox to0pt{\hskip-\hangindent\dbend\hfill}} +% +\newcommand{\spaceout}{\hskip1emplus2emminus.5em} +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\relax\else\egroup\fi\par} +% +% +% NOTE: compile dot files with +% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot > file.tex +\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}] +\tikzstyle{state}=[] +\tikzstyle{final}=[accepting by arrow] +% +% +% +\begin{document} +\ifcorrige +\title{Exercices divers — Corrigé} +\else +\title{Exercices divers} +\fi +\author{David A. Madore} +\maketitle + +\centerline{\textbf{INF105}} + +{\footnotesize +\immediate\write18{sh ./vc > vcline.tex} +\begin{center} +Git: \input{vcline.tex} +\end{center} +\immediate\write18{echo ' (stale)' >> vcline.tex} +\par} + +\pretolerance=8000 +\tolerance=50000 + + + +% +% +% + +\exercice + +On rappelle qu'une fonction $f\colon \mathbb{N} \to \mathbb{N}$ est +dite \emph{calculable} lorsqu'il existe un algorithme (par exemple, un +programme pour une machine de Turing) prenant en entrée un +$n\in\mathbb{N}$ qui termine toujours en temps fini et renvoie la +valeur $f(n)$. On rappelle qu'une partie $E$ de $\mathbb{N}$ ou de +$\mathbb{N}^2$ est dite \emph{décidable} lorsque sa fonction +indicatrice est calculable, ou, ce qui revient au même, lorsqu'il +existe un algorithme prenant en entrée un élément de $\mathbb{N}$ ou +de $\mathbb{N}^2$ qui termine toujours en temps fini et renvoie +vrai ($1$) ou faux ($0$) selon que l'élément fourni appartient ou non +à $E$. On rappelle enfin qu'une partie $E$ de $\mathbb{N}$ ou de +$\mathbb{N}^2$ est dite \emph{semi-décidable} lorsqu'il existe un +algorithme prenant en entrée un élément de $\mathbb{N}$ ou de +$\mathbb{N}^2$ qui termine toujours en temps fini et renvoie +vrai ($1$) si l'élément fourni appartient à $E$, et sinon ne termine +pas (on peut aussi accepter qu'il termine en renvoyant faux, cela ne +change rien). + +Soit $f\colon \mathbb{N} \to \mathbb{N}$ : montrer qu'il y a +équivalence entre les affirmations suivantes : +\begin{enumerate} +\item la fonction $f$ est calculable, +\item le graphe $\Gamma_f := \{(n,f(n)) : n\in\mathbb{N}^2\} = + \{(n,p)\in\mathbb{N}^2 : p=f(n)\}$ de $f$ est décidable, +\item le graphe $\Gamma_f$ de $f$ est semi-décidable. +\end{enumerate} + +(Montrer que (3) implique (1) est le plus difficile : on pourra +commencer par s'entraîner en montrant que (2) implique (1). Pour +montrer que (3) implique (2), on pourra chercher une façon de tester +en parallèle un nombre croissant de valeurs de $p$ de manière à +s'arrêter si l'une quelconque convient.) + +\begin{corrige} +Montrons que (1) implique (2) : si on dispose d'un algorithme capable +de calculer $f(n)$ en fonction de $n$, alors il est facile d'écrire un +algorithme capable de décider si $p=f(n)$ (il suffit de calculer +$f(n)$ avec l'algorithme supposé exister, de comparer avec la valeur +de $p$ fournie, et de renvoyer vrai/$1$ si elles sont égales, et +faux/$0$ sinon). + +Le fait que (2) implique (3) est évident car tout ensemble décidable +est semi-décidable. + +Montrons que (2) implique (1) même si ce ne sera au final pas utile : +supposons qu'on ait un algorithme $T$ qui décide $\Gamma_f$ (i.e., +donnés $(n,p)$, termine toujours en temps fini, en répondant oui si +$p=f(n)$ et non si $p\neq f(n)$), et on cherche à écrire un algorithme +qui calcule $f(n)$. Pour cela, donné un $n$, il suffit de lancer +l'algorithme $T$ successivement sur les valeurs $(n,0)$ puis $(n,1)$ +puis $(n,2)$ et ainsi de suite (c'est-à-dire faire une boucle infinie +sur $p$ et lancer $T$ sur chaque couple $(n,p)$) jusqu'à trouver un +$p$ pour lequel $T$ réponde vrai : on termine alors en renvoyant la +valeur $p$ qu'on a trouvée, qui vérifie $p=f(n)$ par définition +de $T$. + +Reste à montrer que (3) implique (1) : supposons qu'on ait un +algorithme $T$ qui « semi-décide » $\Gamma_f$ (i.e., donnés $(n,p)$, +termine en temps fini et répond oui si $p=f(n)$, et ne termine pas +sinon), et on cherche à écrire un algorithme qui calcule $f(n)$. Pour +cela, on va tester les valeurs $0\leq p\leq M$ chacune pour $M$ étapes +et faire tendre $M$ vers l'infini : plus exactement, on utilise +l'algorithme $U$ suivant : +\begin{itemize} +\item pour $M$ allant de $0$ à l'infini, +\begin{itemize} +\item pour $p$ allant de $0$ à $M$, +\begin{itemize} +\item exécuter l'algorithme $T$ sur l'entrée $(n,p)$ pendant au + plus $M$ étapes, +\item s'il termine en renvoyant vrai ($1$), terminer et renvoyer $p$ + (sinon, continuer les boucles). +\end{itemize} +\end{itemize} +\end{itemize} + +(Intuitivement, $U$ essaie de lancer l'algorithme $T$ sur un nombre de +valeurs de $p$ de plus en plus grand et en attendant de plus en plus +longtemps pour voir si l'une d'elles termine.) + +Si l'algorithme $U$ défini ci-dessus termine, il renvoie forcément +$f(n)$ (puisque l'algorithme $T$ a répondu vrai, c'est que $p=f(n)$, +et on renvoie la valeur en question) ; il reste à expliquer pourquoi +$U$ termine toujours. Mais la valeur $f(n)$ existe (même si on ne la +connaît pas) car la fonction $f$ était supposée définie partout, et +lorsque l'algorithme $T$ est lancé sur $(n,f(n))$ il est donc censé +terminer en un certain nombre (fini !) d'étapes : si $M$ est supérieur +à la fois à $f(n)$ et à ce nombre d'étapes, la valeur $f(n)$ va être +prise par $p$ dans la boucle intérieure, et pour cette valeur, +l'algorithme $T$ va terminer sur l'entrée $(n,p)$ en au plus $M$ +étapes, ce qui assure que $U$ termine effectivement. + +L'algorithme $U$ calcule donc bien la fonction $f$ demandée, ce qui +prouve (1). +\end{corrige} + + +% +% +% +\end{document} |