forked from UCL-INGI/LINGI1123-Calculabilite
-
Notifications
You must be signed in to change notification settings - Fork 0
/
01_Introduction.tex
188 lines (145 loc) · 12 KB
/
01_Introduction.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
% Introduction
% ============
\chapter{Introduction}
\label{ch:introduction}
\section{Qu'est-ce que la calculabilité}
\label{sec:qu_est-ce_la_calculabilite}
La calculabilité est l'étude des limites de l'informatique. Il faut bien
faire attention à différencier les limites théoriques des les limites
pratiques. Pour la calculabilité, on s'occupe des limites théoriques alors que pour
la complexité on s'occupe des limites pratiques. La complexité
détermine la frontière entre ce qui est faisable et infaisable en pratique.
La question principale de la calculabilité est: ``quels sont les problèmes qui peuvent
être résolus par un programme ?''. De manière informelle, un problème est dit calculable s'il existe un programme qui résout ce problème. La caractéristique d'un problème calculable ne donne donc aucune
autre information que de la preuve de l'existence d'un programme pour résoudre ce problème. Mais lorsqu'un problème est non calculable, cela nous informe qu'il est inutile d'essayer d'écrire un programme pour résoudre ce problème; un tel programme n'existe pas !
\paragraph{} Le but est donc de tracer des frontières entre les programmes calculables,
non calculables et non calculables en pratique.
\subsection{Exemples de limites}
\label{subsec:exemples_limites}
De nombreuses limites existent en informatique. Par exemple, il est impossible de déterminer lorsqu'un programme se termine (cfr. Théorème de Rice \ref{sub:theoreme_de_rice}), de déterminer si un programme est écrit sans bugs ou encore d'écrire un programme pouvant déterminer si deux programmes sont équivalents.
Mais des limites existent dans bien d'autres domaines que l'informatique.
En physique par exemple, les lois de la thermodynamique établissent le fait que l'on ne peut créer de l'énergie à partir de rien (principe de Lavoisier notamment). Dans un autre registre, on sait qu'il est impossible d'observer, avec la précision que l'on souhaite, en même temps la \textit{position} et la \textit{vitesse} d'un électron.
En mécanique, on sait qu'il est impossible de construire une machine réalisant un mouvement perpétuel.
En mathématique, il est impossible de trouver deux nombres entiers $m$ et $n$ tel que $m^2 = 2n^2$, ou de trouver une fraction $\frac{m}{n}$ exprimant le rapport entre le rayon d'un cercle et sa circonférence, ou encore de diviser un angle en trois parties égales en utilisant uniquement une règle et un compas.
\section{Notion de problème}
\label{sec:notion_de_probleme}
Premièrement, on doit parler de la notion de problème.
Attention, il ne faut pas confondre un problème avec un programme.
Les caractéristiques d'un problème sont:
\begin{itemize}
\item un problème est générique : il s'applique à un ensemble de données.
\item pour chaque donnée particulière, il existe une réponse.
\end{itemize}
On représente un problème dans le cours par une fonction (noté $\phi$ ou $\varphi$).
Donc la description d'un problème est équivalente à la description d'une fonction.
\paragraph{Exemples de problème}
\begin{itemize}
\item Additionner deux entiers
\item Étant donné une liste d'étudiants et de leur points d'examens, trouver les étudiants dont la moyenne des examens est supérieure ou égale à $12/20$.
\item Déterminer si un polynôme à coefficients entiers a des racines entières.
\end{itemize}
\section{Notion de programme}
\label{sec:notion_de_programme}
Un programme (ou algorithme) est une ``procédure effective'', c'est-à-dire exécutable par une machine. Par exemple un programme Java.
La compréhension du concept de programme est basée sur la compréhension du concept de "programme écrit dans un langage de programmation".
Il existe plein de formalismes permettant la description de ``procédure effective''.
\section{Résultats principaux}
\label{sec:r_sultat_principaux}
\subsection{ Équivalence des langages de programmation}
\label{subsec:equivalence_des_langages_de_programmation}
Y a t-il des langages de programmation qui sont plus puissants que d'autres ? Tous les langages sont-ils équivalents ?
\newline
Il y a une équivalence entre langages en termes de calculabilité. Lorsqu'un problème peut être résolu par un de ces langages, il peut alors être résolu par n'importe quel autre.
S'il existe un programme Java qui résout un problème, il existera aussi un programme C/C++, PHP, … qui peut résoudre le même problème. On parle d'une équivalence théorique.\\
D'un point de vue théorique ces langages s'appellent des langages complets. Ils permettent tous de résoudre les mêmes problèmes. Un problème est donc calculable indépendamment du langage utilisé. \\
D'un point de vue pratique on peut voir des différences (le programme sera plus court, s'écrira plus rapidement, le programme sera plus rapide, plus propre, plus fiable et encore d'autres critères). Certains langages sont donc mieux adaptés que d'autres pour certains problèmes.
\subsection{Existence de problèmes non calculables}
\label{subsec:existence_de_problemes_non_calculables}
Il existe des problèmes qui ne peuvent être résolus par un programme et qui sont alors dit \emph{non calculable}.
Quelques exemples :
détection de virus,
équivalence de programme,
déterminer si un polynôme à coefficients entiers a des racines entières, \ldots
% section r_sultat_principaux (end)
\subsubsection{Exemple: Détection de virus}
\label{subsubsec:detection_de_virus}
On veut déterminer si un programme P avec une entrée D est nuisible.
\textbf{Être nuisible:} Un programme est dit nuisible si son exécution a pour effet de contaminer d'autres programmes (par exemple en se recopiant autre part). Dans certains cas, il peut également être considéré comme dangereux lorsqu'il rend la machine partiellement ou totalement inutilisable (par exemple un cheval de Troie contenant une bombe logique ou une fork bomb).
Un bon anti-virus serait alors un programme qui testerait des programmes en regardant s'ils se multiplient, tout en les empêchant de modifier (voir d'endommager) d'autres fichiers. Un tel programme, si il existe, serait du même type que \textit{detecteur(P,D)} avec \textit{P} le programme à détecter et \textit{D} un état du système de données dans lequel le programme s'exécuterait.
Spécification du programme \textit{detecteur(P,D)}:\\
\textbf{Préconditions :} un programme P et une donnée D\\
\textbf{Postconditions :} ``Mauvais'' si P(D) est nuisible,
``Bon'' sinon.\\
Cependant il faut aussi que le détecteur ne soit pas nuisible pour que cette spécification soit valide. Or comme nous allons le démontrer, le détecteur ne peut être non nuisible.
Pour le prouver nous allons émettre l'hypothèse qu'un programme \textit{detecteur(P,D)} existe et qu'il n'est pas nuisible. Dans ce cas, nous pouvons construire le programme \textit{drole(P)} suivant :
\label{lst:detecteur_de_virus}
\begin{lstlisting}
drole(P)
if detecteur(P,P) = "Mauvais"
then stop
else infecter un autre programme en y inserant P
\end{lstlisting}
Regardons maintenant si l'exécution de \lstinline|drole(drole)|, c'est à dire si l'on donne le code source de \lstinline|drole| à lui-même, est nuisible ou non.
\begin{lstlisting}
drole(drole)
if detecteur(drole, drole) = "Mauvais"
then stop
else infecter un autre programme en y inserant drole
\end{lstlisting}
%TODO Reproduire en tikz (ou importer) l'image issue des slides
\begin{itemize}
\item Supposons que \lstinline|drole(drole)| soit nuisible.
Lorsqu'on exécute, \lstinline|drole(drole)|, \\
\lstinline|detecteur(drole,drole)| n'infecte rien car \lstinline|detecteur| n'est pas nuisible.
Comme \lstinline|detecteur| retourne ``Mauvais'',
le programme s'arrête.
Rien n'a donc été infecté, ce qui est contradictoire avec le fait que \lstinline|drole(drole)| soit nuisible.
\item Si par contre il n'est pas nuisible, alors \lstinline|detecteur(drole,drole)|
ne va pas retourner ``Mauvais'' et le code de la clause \lstinline|else| s'exécutera.
Un autre programme est alors infecté ce qui contredit le fait que \lstinline|drole(drole)| ne soit pas nuisible.
\end{itemize}
On a donc une contradiction dans tous les cas, ce qui implique que le programme \lstinline|drole| ne peut pas
exister. Vu que la seule hypothèse que nous avons formulée pour écrire le programme \lstinline|drole| soit que le programme \lstinline|detecteur| (non nuisible) existe,
le programme \lstinline|detecteur| (non nuisible) ne peut pas exister non plus.
% subsubsection d_tection_de_virus (end)
\subsection{ Existence de problèmes intrinsèquement complexes}
\label{subsec:existence_de_problemes_intrinsequement_complexes}
Un problème intrinsèquement complexe est un problème dont le meilleur algorithme n'a pas de complexité polynomiale, mais une complexité exponentielle ou pire. Peu importe les évolutions technologiques, un problème exponentiel ne peut et ne pourra être résolu que pour des données de petites tailles. Un exemple est le problème du voyageur de commerce qui doit rechercher le trajet le plus court pour relier n villes. Pour un problème intrinsèquement complexe, lorsqu'un ordinateur est $n$ fois plus rapide, la taille des problèmes pouvant être résolus en temps raisonnable est incrémentée d'une petite valeur (voir le tableau ci-dessous).
Supposons un ordinateur actuel sachant faire 100 millions d'instructions par secondes ($100$ Mips) et que le traitement d'un élément nécessite 100 instructions machines. Dénotons $N_i$ la taille du ``plus grand'' exemple dont la solution peut-être calculée en 1 heure de temps calcul.
\begin{center}
$\begin{array}{|c||c|c|c|}
\hline
\text{Complexité} & \text{Ordinateur actuel} & \text{100x plus rapide} & \text{1000x plus rapide} \\
\hline
n & N_1 = 3.6\times 10^9 & 100 N_1 & 1000 N_1 \\
n^2 & N_2 = 6\times 10^5 & 10 N_2 & 31.6 N_2 \\
n^3 & N_3 = 1530 & 4.64 N_3 & 10 N_3 \\
n^5 & N_4 = 81 & 2.5 N_4 & 3.98 N_4 \\
\hline
2^n & N_5 = 31 & N_5 + 6 & N_5 + 10 \\
3^n & N_6 = 20 & N_6 + 4 & N_6 + 6 \\
\hline
\end{array}$
\end{center}
Ce tableau montre dès lors que peu importe les évolutions technologiques, un problème intrinsèquement complexe \textbf{ne peut} et \textbf{ne pourra} être résolu que pour de petits exemples. Les solutions à ces problèmes peuvent cependant être approximées par des algorithmes (parfois très efficaces).
\section{Objectifs calculabilité et complexité}
\label{sec:objectifs_calculabilite_et_complexite}
La figure Fig(\ref{cal_non_cal}) illustre la frontière entre les problèmes non calculables (il n'existe pas un programme) et calculables (il existe un programme) dans l'univers des problèmes. Parmi les problèmes calculables il a ceux qui le sont en pratique (pas exponentiels) et ceux qui ne sont pas calculables en pratique.
\begin{figure}[h]
\centering
\begin{tikzpicture}[scale=0.8]
\draw[very thick,blue,rounded corners=10pt] (0,0) rectangle (10,6);
\draw[very thick,red] (0,4) -- (10,4);
\draw[very thick,cyan,rounded corners=5pt] (2,0.5) rectangle (7,2.5);
\draw[blue] (10,6) node[above left] {Problèmes};
\draw[red] (10,4) node[above left] {Non calculables};
\draw[red] (10,4) node[below left] {Calculables};
\draw[cyan] (2,2.5) node[above right] {Non calculables en pratique};
\draw[cyan] (2,2.5) node[below right] {Calculables en pratique};
\end{tikzpicture}
\caption{ Problèmes calculables / non calculables }
\label{cal_non_cal}
\end{figure}
L'intérêt de la calculabilité est de savoir quels problèmes sont calculables ou lesquels ne le sont pas. Si un problème est non calculable, il est alors inutile d'essayer de résoudre ce problème. Si le problème est calculable mais intrinsèquement complexe, il est inutile d'envisager un algorithme permettant de résoudre des problème de grande taille.
Face à un problème non calculable ou intrinsèquement complexe, on peut essayer de relâcher le problème pour le rendre calculable ou de complexité polynomiale. Une solution à ce problème relâché peut par exemple être une approximation du problème initial.
% section introduction (end)Introduction