Edición de «Práctica 2: Complejidad (Algoritmos III)»

{{Back|Algoritmos y Estructuras de Datos III}}

==Ejercicio 02.01:==
log(2,n) + 1

==Ejercicio 02.02:==
No. Base 1 requiere espacio O(n), y las demas O(log n)

==Ejercicio 02.03:==
(Cuentas Cuentas..)
<br>a)
<br>b)
<br>c)

==Ejercicio 02.04:==
<br>a)
<br>b)
==Ejercicio 02.05:==
Modelo Uniforme:
<br>b) O(d)
<br>d) O(n^2)

Modelo Logaritmico:
<br>a) O(log(x))+O(log(y))
<br>c) O(nlog(n))

==Ejercicio 02.06:==
<br>a)
<br>b)
<br>c)
==Ejercicio 02.07:==
<br>a)
<pre>
	int bin2dec(string s)
	res = 0;
	para i = |s|-1..0
		si (s[i]=='1')
			res += 2^i;
	devolver res;
</pre>
<br>b) No. Podria no parar nunca
<br>c) Si
<br>d) 
<pre>
	string dec2bin(int n)
	res = <>;
	while (n != 0)
		si (n % 2 != 0)
			res += '1';
		sino
			res += '0';
		n /= 2;
	devolver res;
</pre>

==Ejercicio 02.08:==
<br>a)
<br>b)
<pre>
import math
import sys

def primes(n): 
	if n==2: return [2]
	elif n<2: return []
	s=range(3,n+1,2)
	mroot = n ** 0.5
	half=(n+1)/2-1
	i=0
	m=3
	while m <= mroot:
		if s[i]:
			j=(m*m-3)/2
			s[j]=0
			while j<half:
				s[j]=0
				j+=m
		i=i+1
		m=2*i+3
	return [2]+[x for x in s if x]

def isprime(aNumber):
	if aNumber < 2: return False
	if aNumber == 2: return True
	if (( aNumber / 2 ) * 2 == aNumber) : 
		return False
	else:
		klist = primes(int(math.sqrt(aNumber+1)))
		for k in klist[1:]:
			if (( aNumber / k ) * k == aNumber ): return False
		return True


a = int(sys.argv[1])
b = int(sys.argv[2])
i = 2

while(i < max(a,b)):
	if isprime(a):
		if (b%a == 0):
			b = b/a
			a = a/a
		else:
			break
	elif isprime(b):
		if a%b == 0:
			a = a/b
			b = b/b
		else:
			break
	else:
		if isprime(i):
			if(a%i == 0 and b%i == 0):
				a = a/i
				b = b/i
			else:
				i = i + 1
		else:
			i = i + 1
	
print str(a) + "/" + str(b)
</pre>
<br>c)
==Ejercicio 02.09:==
<br>a) No recursivo
<pre>
import math
import sys

##mientras b ? 0 repetir las tres instrucciones siguientes:
##
##    r ? resto de a entre b     (dar a r el valor del resto de a por b)      
##    a ? b     (el nuevo valor de a es el antiguo valor de b)
##    b ? r     (el nuevo valor de b es el valor de r)
##
##* el resultado es a (su último valor).

a = sys.argv[1]
b = sys.argv[2]
a = float(a)
b = float(b)

while b != 0:
    r = a % b
    a = b
    b = r

print a    
</pre>
Recursivo
<pre>
import sys
import math

def Euclides(a,b):
    if b == 0:
        return a
    else:
        r = a%b
        return Euclides(b,r)
    
a = sys.argv[1]
b = sys.argv[2]
a = float(a)
b = float(b)

print Euclides(a,b)
</pre>
<br>b)
<br>c)
<br>d)
==Ejercicio 02.10:==
<br>a)
<br>b)
<br>c)
<br>d)
<br>e)
==Ejercicio 02.11:==
==Ejercicio 02.12:==
==Ejercicio 02.13:==
<br>a)
<br>b)
<br>c)
==Ejercicio 02.14:==
<br>a)
<br>b)
<br>c)
<br>d)
<br>e)
<br>f)
==Ejercicio 02.15:==
<br>a)
<br>b)
<br>c)
==Ejercicio 02.16:==
<br>a)
<br>b)
<br>c)
<br>d)
<br>e)
==Ejercicio 02.17:==
<br>a)
<br>b)
<br>c)
==Ejercicio 02.18:==
<br>a)
<br>b)
<br>c)
==Ejercicio 02.19:==
<br>a)
<br>b)
<br>c)
==Ejercicio 02.20:==
==Ejercicio 02.21:==
Construir una maquina de Turing deterministica que resuelva el problema de si un numero entero es divisible por 4

El abecedario de esta maquina es {B,0,1}. El elemento default de la cinta es el 0 y el numero a trabajar se encuentra expresado en base uno y el mismo comiensa con una B.

ej: 5 % 4 =? 0    ---00000000B111110000000000---

los estado posibles son {q0,q1,q2,q3,q4,qt,qf}
el estado inicial es q0,B y el algoritmo devuelve qt si lo divide o qf sino

<pre>
(q0,B,q0,b.+) (q1,1,q2,1.+) (q2,1,q3,1.+) (q3,1,q4,1.+) (q4,1,q1,1.+)
(q1,1,q2,1.+) (q0,0,qf,*.*) (q2,0,qf,*.*) (q3,0,qf,*.*) (q4,0,qt,*.*)
(q0,0,qf,*.*)
</pre>

(nota al pie):la complejidad de este algoritmo me suena q es O(n) no se como demostrarlo

==Ejercicio 02.22:==
<br>a)
<b>Algoritmo:</b>
<pre>
1.si (actual != b)
	avanzo
2.sino
	volver 1 lugar hacia atras
3.si (cinta == ultimo guardado)
	tachamos cinta con b
	nos movemos al anterior y guardamos
	(pero si es blanco ir a SI)
	volvemos a 1
sino
	ir a NO
</pre>

<br>b)


[[Category: Prácticas]]
@@ Línea 15: / Línea 15: @@
 ==Ejercicio 02.04:==
 <br>a)
-<br> i.  f = n <= 1*n (todo n) -> f es O(n)
-<br> ii. f = 3*n^2 + 7*n + 4 <= 4*n^2 (n>=8) -> f es O(n^2)
-<br> iii.f = n^i <= 1*n^j (todo n) <=> i < j -> f es O(n^j) <=> i < j
-<br> iv. f = n*log n <= 1*n^2 (todo n) -> f es O(n^2)
 <br>b)
-Sup. Ex. k en R / n! <= k* r^n <=> n!/r^n <= k. Pero lim{n->∞} n!/r^n = ∞ (ABS)
 ==Ejercicio 02.05:==
 Modelo Uniforme: