Update 07_ClassesComplexite.tex

UCL-INGI · May 29, 2019 · 7d969d0 · 7d969d0
1 parent 3d19ddd
commit 7d969d0
Showing 1 changed file with 2 additions and 7 deletions.
diff --git a/07_ClassesComplexite.tex b/07_ClassesComplexite.tex
@@ -256,13 +256,8 @@ \section{Relations entre les classes de complexité}
 \begin{myprop}
 	$A \in DSPACE(f) \Rightarrow A \in DTIME(c^f)$
     \begin{proof}
-      On sait que le programme se termine car l'ensemble est récursif.
-      La mémoire a un nombre exponentiel de configuration possible (stack, heap, program counter, ...).
-      Si la complexité temporelle que le nombre de configuration possible,
-      par le principe de tiroirs, on passe deux fois par la même configuration.
-      On aura bouclé une fois.
-      Mais comme la configuration détermine entièrement l'état du programme, on refera cette boucle une infinité de fois
-      et le programme ne se terminera pas, ce qui contredit l'hypothèse.
+      On sait que le programme se termine pour tout car l'ensemble est récursif.
+Si la mémoire utilisée est en $O(f)$,  le nombre de configurations possibles de cette mémoire (stack, heap, program counter, ...) est exponentiel $O(c^f)$.  Si la complexité temporelle dépasse cette complexité exponentielle, alors l'exécution du programme va repasser sur un état de mémoire déjà rencontré, et va y repasser une infinité de fois.  Le programme va alors ne pas se terminer, ce qui est contraire à l'hypothèse que l’ensemble est récursif. 
     \end{proof}
 \end{myprop}