From 8e44c44aff96736ab0d529c44cfcd5cfdac68dfa Mon Sep 17 00:00:00 2001
From: Juan Marin Noguera <juan@mnpi.eu>
Date: Wed, 25 Jan 2023 12:53:51 +0100
Subject: Erratas
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Esta vez en algunas asignaturas no llegué a comprobar erratas:
- En funcional a partir de 2.11
- En DSI
- En conmutativa a partir de la enumeración antes del lema de Artin
  en 3.8
---
 mc/n6.lyx | 39 ++++++++++-----------------------------
 1 file changed, 10 insertions(+), 29 deletions(-)

(limited to 'mc/n6.lyx')

diff --git a/mc/n6.lyx b/mc/n6.lyx
index 3adbae2..6dbb810 100644
--- a/mc/n6.lyx
+++ b/mc/n6.lyx
@@ -170,7 +170,7 @@ límite superior asintótico
 
 \begin_layout Standard
 Para 
-\begin_inset Formula $t:\mathbb{N}\to\mathbb{R}^{+}$
+\begin_inset Formula $t:\mathbb{N}\to\mathbb{R}^{\geq0}$
 \end_inset
 
 , llamamos 
@@ -190,8 +190,7 @@ clase de complejidad
 \end_inset
 
 .
- Nótese que esta magnitud se refiere al lenguaje o problema, no a un algoritmo
- concreto.
+ Esta magnitud se refiere al lenguaje o problema, no a un algoritmo concreto.
  En general, la clase de complejidad de un problema depende del modelo de
  computación usado, aun para modelos equivalentes.
  Este orden no difiere mucho entre modelos deterministas, pero sí entre
@@ -252,7 +251,7 @@ Demostración:
  y luego para aplicarla, actualizando el contenido de las celdas y las posicione
 s de los cursores.
  Cada cinta tiene tamaño como mucho 
-\begin_inset Formula $O(t(n))$
+\begin_inset Formula $O(\max\{t(n),n\})=O(t(n))$
 \end_inset
 
 , pues en cada transición se añade como mucho un caracter en cada cinta,
@@ -265,11 +264,7 @@ s de los cursores.
 \end_inset
 
  de estos, el tiempo total es 
-\begin_inset Formula $O(t(n)^{2}+n)=O(t(n)^{2})$
-\end_inset
-
-, usando que 
-\begin_inset Formula $t(n)\geq n$
+\begin_inset Formula $O(t(n)^{2})$
 \end_inset
 
 .
@@ -383,16 +378,7 @@ backtracking
 \lang spanish
  y para evitar la interferencia entre una simulación y la siguiente, por
  lo que el total de transiciones es como mucho 
-\begin_inset Formula $O(n+mc^{m})=O(n+f(n)c^{f(n)})$
-\end_inset
-
-, usando que 
-\begin_inset Formula $n\leq f(n)$
-\end_inset
-
-.
- Entonces el total es 
-\begin_inset Formula $O(f(n)c^{f(n)})=O(2^{\log_{2}f(n)+f(n)\log_{2}c})=2^{O(\log_{2}f(n)+f(n)\log_{2}c})=2^{O(f(n))}$
+\begin_inset Formula $O(n+mc^{m})=O(n+f(n)c^{f(n)})=O(f(n)c^{f(n)})=O(2^{\log_{2}f(n)+f(n)\log_{2}c})=2^{O(\log_{2}f(n)+f(n)\log_{2}c)}=2^{O(f(n))}$
 \end_inset
 
 , y por el teorema anterior, al simular esto en un 
@@ -419,16 +405,7 @@ Nótese que
 \begin_inset Formula $3^{n}\neq O(2^{n})$
 \end_inset
 
- pero 
-\begin_inset Formula $3^{n}=2^{\log_{2}3^{n}}=2^{n\log_{2}3}=2^{O(n)}$
-\end_inset
-
-.
- En efecto, claramente 
-\begin_inset Formula $n\log_{2}3\in O(n)$
-\end_inset
-
-, pero para cualesquiera 
+ porque para cualesquiera 
 \begin_inset Formula $c,n_{0}\in\mathbb{N}$
 \end_inset
 
@@ -444,6 +421,10 @@ Nótese que
 \begin_inset Formula $n>\log_{\frac{3}{2}}c$
 \end_inset
 
+, pero 
+\begin_inset Formula $3^{n}=2^{\log_{2}3^{n}}=2^{n\log_{2}3}=2^{O(n)}$
+\end_inset
+
 .
 \end_layout
 
-- 
cgit v1.2.3