jueves, 30 de junio de 2011

Algoritmo de Dios (Extra)



Algoritmos de Dios

Consiste básicamente en resolver un cubo de Rubik en mas 0 menos 20 movidas.

El cubo de Rubik usa un algoritmo que se separa en varias partes dependiendo de que lado se valla a resolver; existen muchos tipos de variaciones para demostrar cual es el algoritmo de Dios, pero muchos de estos ocupan mas de 40 movimientos.

El algoritmo tiene que ser mas simple que 40 movidas, a el método de resolución mas rápido se le llama el algoritmo de Dios.


Para poder resolver el algoritmo Google dono una computadora que estuviera processando el algoritmo el tiempo nesesario, y esto fue 35 años.

Se dice que este algoritmo esta dentro de la categoria de los mas dificiles de calcular.

Esta dentro de la categoria NP-Difficil no determinista.

Bibliografia:
http://en.wikipedia.org/wiki/God%27s_algorithm
http://www.cube20.org/
http://www.neoteo.com/descubierto-el-algoritmo-de-dios-para-el-cubo-de
.

Tarea Viernes 1/07/11 ( Algoritmo Simple)

Algoritmo Simple: 
Ordenacion por metodo de burbuja

El metodo burbuja consiste en ordenar de manera secuencial una cadena de caracteres al ir remplazando los caracteres dependiendo de su valor en la cadena.

Este algoritmo es muy sencillo por lo cual lo considere para mi ejemplo:
Diagrama



















Programa
void ordenamientoBurbuja(int v[], int util_v) { int temp, i, j; for (i = 0; i < util_v -1 ; i++) { for (j = i + 1; j < util_v ; j++) { if (v[i] > v[j]) { temp = v[i]; v[i] = v[j]; v[j] = temp; } } }}
Como visto en :
http://es.wikipedia.org/wiki/Ordenamiento_de_burbuja 







Rendimiento del Algoritmo

Rendimiento del algoritmo
Para poder ordenar satisfactoriamente tenemos que usar el mismo numero de comparaciones.

Esto es, el número de comparaciones c(n) no depende del orden de los términos, si no del número de términos.

Por lo tanto la cota ajustada asintótica del numero de comparaciones pertenece al orden de n cuadrado.

El numero de intercambios i(n), que hay que realizar depende del orden de los términos y podemos diferencia, el caso mejor, si el vector esta previamente ordenado, y el caso peor, si el vector esta ordenado en orden inverso.
Por lo que no se puede determinar una cota ajustada asintótica del número de intercambios, dado que este dependerá del orden del vector en cuestión.
[editar]Rendimiento en el caso desfavorable
Artículo principal: Cota superior asintótica

Si pasamos al algoritmo un vector ordenado en orden inverso realizara un numero de comparaciones:

Como ya hemos dicho anteriormente, y tendrá que realizar un número igual de intercambios entre los términos del vector, dado que en cada comparación los términos estarán desordenados, y se realizara el intercambio.
Por lo tanto en el caso más desfavorable tanto el numero de comparaciones como el de intercambios coinciden:

El numero de comparaciones o de intercambios en el caso más desfavorable pertenece al orden de n cuadrado.

Rendimiento en casos óptimos
Artículo principal: Cota inferior asintótica
En el caso optimo, el más favorable, es la ordenación que un vector ya ordenado, en este caso el número de comparaciones será el mismo que en cualquier otro caso:

La cota inferior asintótica del número de comparaciones pertenece al orden de n cuadrado, como en los demás casos, pero en todas las comparaciones el orden es el correcto y por tanto no se realiza ningún intercambio:

Por lo tanto el coste de intercambios no depende de n, y es constante:
El ordenamiento de burbuja tiene una complejidad Ω(n²) igual que ordenamiento por selección. Cuando una lista ya está ordenada, a diferencia del ordenamiento por inserción que pasará por la lista una vez y encontrará que no hay necesidad de intercambiar las posiciones de los elementos, el método de ordenación por burbuja está forzado a pasar por dichas comparaciones, lo que hace que su complejidad sea cuadrática en el mejor de los casos. Esto lo cataloga como el algoritmo mas ineficiente que existe, aunque para muchos programadores sea el más sencillo de implementar.

Bibliografia:

Complejidad Asintotica (Eficiencia de Algoritmos) (Extra)

Complejidad Asintótica
Para calcular la complejidad asintotica de un algoritmo es necesario denotar las instancias (entrada y salida de datos) con una variable n, Calculamos el numero de operaciones necesarias para efectuar el algoritmo usando los valores de n. Podemos gráfica todos los valores de n para crear una gráfica. 
Después de eso podemos buscar cual es el valor asintotico de la gráfica.

En clase vimos un ejemplo de como ordenar por complejidad los asintotas de un algoritmo.
Teníamos esta tabla:
f1 = 7n
f5 =(raíz)n
f2 = nn
f6 = log7n
f3 = n7
f7 = 7log7n
f4 = n log7n
f8 = 700n

Después de hacer una prueba calculando la n con valores simples del 1 al 15 coincidí que:
Entonces  descubrí el orden de la eficiencia de el algoritmo, y dado lo visto en clase el orden es el siguiente:
F2
F1
F3
F4
F7-F8
F5
F6


Bibliografia:

Trabajo en Clase (Grafica Logaritmo)

miércoles, 29 de junio de 2011

Maquina de Turing Resta (Extra)

Como visto en: http://w0oh0o.blogspot.com/2010/02/problema-31-maquina-de-turing-que-resta.html

Κ
σЄ∑
(Ρ,σ)
S
s,►,->
S
0
s,0,->
S
1
q,1,->
S
I_I
r,|_|,<-
Q
0
q,0,->
Q
1
q,1,->
Q
I_L
t,|_|,<-
T
0
t,-1,-
R
0
r,1,<-
r
1
r,0,-




Lenguaje Recursivo (Extra)

Un lenguaje recursivo en la informática es aquel lenguaje que acepta cualquier letra o símbolo y se puede utilizar en una maquina de Turing y acepta cualquier numero de símbolos.
Su definicion viene de la palabra recursividad la cual en la informatica significa la propiedad que tiene un programa de solicitar su propia ejecucion en su desarollo.

Propiedades de las definiciones o algoritmos recursivos:
Un requisito importante para que sea correcto un algoritmo recursivo es que no genere una secuencia infinita de llamadas así mismo. Claro que cualquier algoritmo que genere tal secuencia no termina nunca. Una función recursiva f debe definirse en términos que no impliquen a f al menos en un argumento o grupo de argumentos. Debe existir una "salida" de la secuencia de llamadas recursivas.

Si en esta salida no puede calcularse ninguna función recursiva. Cualquier caso de definición recursiva o invocación de un algoritmo recursivo tiene que reducirse a la larga a alguna manipulación de uno o casos mas simples no recursivos.

Teoria de Conjuntos (Extra)

La teoria de conjuntos consiste en comparar 2 o mas grupos de elementos, viendo si los elementos de esos conjuntos se repiten, no estan en otros conjunto, dependiendo de lo que te pida.
Los conjuntos elemenots de los conjuntos se ponen dentro de llaves y se separan con coma porejemplo:
A={1,2,4,5}
B={1,3,5,7}
Para demostrar si un elemento esta o no en un conjunto se usan los simbolos   Î  Ï
Para demostrar si un conjunto es subconjunto (Todos sus elementos se encuentran en el otro conjunto) de otro conjunto se usa Ì.
Para representar el Universo de los conjuntos, es decir todos los elementos en los conjuntos se usa la U

Existen varias operaciones que se pueden realizar con los conjuntos, porejemplo
Union: La union de los elementos de ambos conjuntos.
Interseccion: Los elementos que se comparten entre los conjuntos.
Complemento: Todos los elementos del universo que no estan en cierto conjunto.
Diferencia: Como realizar una resta entre conjuntos, se quitan los que estan en ambos conjuntos.

Los conjuntos se pueden representar facilmente con diagramas de Venn.

AUB={1,5}

Bibliografia:

Que es una función y sus propiedades. (Extra)

En matemáticas, una función,1 aplicación o mapeo f es una relación entre un conjunto dado X (el dominio) y otro conjunto de elementos Y(el codominio) de forma que a cada elemento x del dominio le corresponde un único elemento del codominio f(x). Se denota por:
f \colon X \to Y \,
Comúnmente, el término función se utiliza cuando el codominio son valores numéricos, reales o complejos. Entonces se habla de función realfunción compleja mientras que a las funciones entre conjuntos cualesquiera se las denomina aplicaciones.

Clasificaciones
Dados dos conjuntos X, Y, consideremos a todas las posibles aplicaciones (funciones) que pueden formarse entre estos dos conjuntos. Podemos diferenciar los siguientes casos:
  • Si a cada imagen le corresponde una única preimagen, inyectiva.
  • Si la imagen de la función es igual al codominio, sobreyectiva o suprayectiva.
  • Una función que sea inyectiva y sobreyectiva simultáneamente, se denomina biyectiva .
Puede haber funciones que sean biyectivas, inyectivas pero no suprayectivas, supreyectiva pero no inyectiva o que no se cumple ninguna de esas condiciones, en cuyo caso no tiene un nombre específico.
'Definiciones alternas: sea f: X \rightarrow Y dada y sea b un elemento cualquiera del codominio Y. Consideremos la ecuación
f(x) = b \quad \text{(*)}.
  • la función es suprayectiva o sobreyectiva si, y sólo si, la ecuación (*) siempre tiene al menos una solución.
  • la función es inyectiva si, y sólo si, la ecuación (*) tiene a lo más una solución.
  • la función es biyectiva cuando, y sólo cuando, es inyectiva y suprayectiva a la vez.

Bibliografia:

Alan Turing y la Maquina de Turing (Extra)

Nació en Londres (Gran Bretaña), desde muy temprana edad Turing demostró su inteligencia. Alos 3 años tenía una inusual capacidad para recordar palabras y a los 8 años se interesó por la química montando un laboratorio en su casa. Con 13 años ingresó en la escuela Sherborne, en la que ya demostraba su facilidad para las matemáticas, teniendo una gran capacidad para realizar cálculos mentalmente.

  Obtuvo una beca para estudiar en la universidad de Cambridge, en donde se graduó de la licenciatura de matemáticas con honores en 1934. En abril de 1936, publicó el artículo "On computable numbers, with an application to the Entscheidungsproblem" en el que introduce el concepto de algoritmo y de máquina de Turing. Este artículo da respuesta (negativa) al problema de la decisión formulada por Hilbert en 1900, probando que existen problemas sin solución algorítmica y es uno de los cimientos más importantes de la teoría de la computación.
    En septiembre de 1936, Turing ingresó en la universidad de Princeton (EE.UU). Su artículo atrajo la atención de uno de los científicos más destacados de la época, John von Neumann, quien le ofreció una beca en el Instituto de Estudios Avanzados. Turing obtuvo su doctorado en matemáticas en 1938. Tras su graduación, von Neumann le ofreció una plaza como su asistente, pero Turing rechazó la oferta y volvió a Inglaterra, en donde vivió de una beca universitaria mientras estudiaba filosofía de las matemáticas entre 1938 y 1939.
    En 1939, con el comienzo de la Segunda Guerra Mundial, Turing fue reclutado por el ejército británico para descifrar los códigos emitidos por la máquina Enigma utilizada por los alemanes. En el deseo de obtener mejores máquinas descifradoras, se comenzó a construir la primera computadora electrónica, llamada Colossus, bajo la supervisión de Turing, se construyeron 10 unidades, y la primera empezó a operar en 1943. Por su trabajo en el Colossus, Turing recibió la Orden del Imperio Británico en 1946.

Maquina de Turing
La maquina de Turing permite crear algoritmos autómatas capaces de crear cálculos.
Es el modelo de computación mas comúnmente usado pero así mismo es el mas sencillo.
La maquina de Turing funciona con una cinta finita, esta cinta esta dividida en celdas las cuales permiten ver el elemento que esta almacenado en esa celda sin afectar los otros elementos.

Para operar la Maquina necesita un lenguaje, estado, dirección y estado inicial; utilizando cada uno de estos de manera diferente por ejemplo aquí esta un ejercicio que hice en clase sobre una maquina de Turing que identifica si los elementos de la cadena son pares.

pϵK
δϵΣ
δ(p,σ)
1
A
1,A,→
1
1, ,
1
I_I
si”,I_I, --
2
A
1,A,
2
I_I
“no”, I_I, --




Prueba y Explicacion
Σ={A}E→IAAIϵ
Si probamos con “AAAAAA”
La maquina nos va a analizar que primero empezaremos a movernos a la derecha si tenemos una “A”, y se cambia a el estado 2 donde se va a mover a la derecha si tenemos una “A”.
Al llegar a un vacio estando en el estado 1 va a marcar que si es par y ya no se moverá, en cambio si llega a el vacio en estado 2 ma a marcar que no es par. Al final con la prueba de “AAAAAA” va a marcar que los elementos de la cadena en su totalidad son pares.







Aqui un video de una escena de la película (Breaking the Code)
http://www.youtube.com/watch?v=6k2OUZdA7vQ


martes, 28 de junio de 2011