Puntos Extra

Para el trabajo de puntos extras yo y mi compañero alexandro carrizales elegimos hacer el problema de la maquina turing. El problema era el siguiente:

Maquina Turing (20 Puntos)

Ejecuta paso a paso la Maquina Turing para la siguiente función de transición, con la entrada siendo la representación binaria del número decimal 37 ¿Cuál es la salida de la máquina en decimal? ¿Qué hace la máquina? ¿Qué complejidad asintótica tiene en términos de computación y memoria?


El primer paso es convertir el numero decimal 37 a binario. Una forma muy sencilla es dividiendo el numero 37 entre 2 y quedaria el cociente 18 y residuo 1; y ahora dividir el 18 entre 2 y te da cociente 9 y residuo 0; ahora dividimos el 9 entre 2 y queda cociente 4 y residuo 1; ahora dividimos el 4 entre 2 y queda cociente 2 y residuo 0; ahora dividimos el 2 entre 2 y queda cociente 1 y residuo 0 y por ultimo dividimos el 1 entre 0 y queda cociente 0 y residuo 1. Ahora sigue juntar todos los residuos para formar el numero binario (recuerden que es primero el ultimo residuo y al final el primero).

El numero binario queda asi:

100101

Ahora sigue la ejecucion de la Maquina Turing. Esta era la tabla que venia en el examen:




Y asi seria la ejecucuion de la Maquina:

0 1 0 0 1 0 1 F
1 S
2 S
3 S
4 S
5 S
6 S
7 S
8 S
9 t
10 T
11 ALTO



El resultado que arroja la Maquina Turing es:

01001110


Ahora tenemos que convertirlo a decimal:


0(27) +1( 26)+0(25)+0(24)+1(23)+1(22)+1(21)+0(20)=

0 + 64 + 0 + 0 + 8 + 4 + 2 + 0= 78


La salida de la Maquina Turing es 78.


¿Que hace la Maquina Turing?

La maquina turing lo que hace es mutiplicar el numero inicial por 2 y despues sumarle 4.


¿Cual es la complejidad en terminos de computacion y memoria?

Este problema tiene complejidad polinomial. El peor caso en este ejemplo hubiera sido que el numero inicial hubieran sido puros 1 y un o al principio, ya que en este caso tendria que recorrer toda la cinta

Cualquier sugerencia o aclaraciones solo pongan los comentarios.

Gracias

Proyecto #4

bien a mi me toco explicacion de aplicaciones reales del quicksort(ordenamiento rapido para arreglo)

por lo que he leido este es uno de los metodos mas rapidos, la parte que me toco a mi creo que la hice bien aunque me falta un poco mas de informacion pero en general creo que esta bien, para hacer mi trabajo me apoye en algunos de mis compañeros pero en su mayoria lo realice yo, creo que aun no entiendo muy bien esto y ese es el aspecto en que debo mejorar.

este trbajo lo estuvo cordinando mi compañero y amigo Alejandro Carrizales y creo que el trabjo nos salio bien ya que tenemos la informacion suficiente y estamos un poco mejor preparados para la presentacion.

esta es una pequeña descripcion del algoritmo

El algoritmo fundamental es el siguiente:

* Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
* Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
* La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
* Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.





estas son las ligas a los blogs de mis compañeros


http://alejandrocarrizalesgarcia.blogspot.com/
http://kanoopfime.blogspot.com/
http://twowolvescorp.blogspot.com/

proyecto #2

la caja

Se tiene una pieza rectangular de cartón que mide 8 por 5 metros.Se desea construir una caja sin tapa cortando cuadrados iguales en cada esquina y doblando las caras haca arriba para formar los lados ¿Cual será el tamaño de los cuadrados a cortar para obtener el volumen máximo de la caja?

Llamando x al lado del cuadrado a recortar en cada esquina, el área "A" de la base debe tener las siguientes dimensiones
A = (8 - 2x) (5 - 2x) = 40 - 16x - 10x + 4x²
A = 40 - 26x + 4x²
Y como la altura de la caja también es x, su volumen V = área de la base . altura, es
V = (40 - 26x + 4x² ) x
V = 40x - 26x² + 4x³
Derivando, se tiene
V' = 40 - 52x + 12x³
Igualando a cero para encontrar el punto crítico
0 = 40 - 52x + 12x³
dividiendo por 4 nos y ordenando nos queda
3x² - 13x + 10 = 0
Ecuación cuadrática que por la resolvente nos da las raíces
x1 = 3,33
x2 = 1
Descartando la primera por dar un volumen nulo, y sacando la derivada segunda para ver que clase de punto encontramos, tenemos
V" = 6x - 13
que para el punto considerado (x = 1), el resultado es negativo, por lo cual el valor hallado para el volumen es máximo. luego se debe recortar en las 4 esquinas un cuadrado de 1 m.

Agenda telefónica en Dev C++

Forma de realizar la estructura:

1. Iniciamos insertando las librerías adecuadas para los datos. En este caso utilizaremos la biblioteca de iostream.h y el fichero cstring.h de la biblioteca string.h.

Iostream.h: según mis investigaciones esta librería define unos operadores que son particulares, reciben el nombre manipuladores que son los que controlan los datos que se visualizan en el programa. Para poder manipular dichos datos se sitúa un manipulador en la cadena de operadores , “<< ”.

Cstring.h: este fichero pertenece a la biblioteca string.h. Representa una secuencia de caracteres alfanuméricos de 1 o 2 bytes cada uno de ellos. Esta secuencia además es de longitud variable, pudiendo añadir, eliminar, concatenas nuevos caracteres y cadenas. 2. Usamos #define que nos sirve para definir constantes literales. Ejemplo:#define PI 3.1415926535897932384626Esto hace que donde aparezca el texto "PI", el compilador entienda el número 3.1415926535897932384626. Con esto definiremos tres datos que serán: nombres teléfono personas

3. Después creamos un grupo con las datos que definimos anteriormente, y para esto usamos la opción “struct” y se le asigna un nombre a esta estructura en este caso se llamara persona. En esta estructura se declaran variables. En este caso declararemos: agenda menú y un buscador utilizando la opción “void” ya que no tomaran ningún valor

4. Las variables declaradas las dividiremos para agregar a cada una la estructura así que comencemos: Agenda: insertamos las condiciones que queremos que se cumplan. Yo usare el “for” para insertar las condiciones las cueles serán que una variable a=0, que el numero de personas sea a<= y que tenga un limite de 2 (++a). Después se pedirá lo que se desea saber sobre el contacto ósea el nombre y el numero. Esto se repetirá de nuevo por el ++a y se agregara otro nuevo contacto, en total serán 2. Se usaran dos “gets” uno para reconocer que estamos hablando de nombre y otro para reconocer que estamos hablando del numero telefonico.

Menú: aquí en esta sección como no ocuparemos ningún dato de contacto la variable que declaramos (a) pues se pondrá como variable “a” ya que a=0. Con la librería iostream.h utilizaremos dos funciones las cuales serán “cout<<” con el cual abriremos un rango y el “cin>>” con el cual se cerrara este rango. Dentro de este rango se introducirán las condiciones que llevara el menú. Esta agenda llevara:
Opciones:
1). Buscar por nombre
2). Buscar por teléfono
3.) Salir




Buscador: Este paso será el mas complicado y largo. Aquí imprimiremos una opción que nos dará el resultado después de haber elegido cualquiera de las 2 primeras opciones del Menú, la cual será que ingresemos el dato que debamos ingresar después de haber elegido la opción y se tendrá que declarar otra variable yo declarare la b=0.
Si se eligió la 1). y se escribe cualquiera de los dos nombres registrados en la agenda, el programa reconocerá y traerá automáticamente el “get” del nombre que se ingreso y nos arrojara el resultado que en este caso será el numero telefónico de esa persona, numero que también fue guardado en agenda. Un punto que hay que mencionar es que si se teclea otro nombre que no esta guardado en la agenda, el programa sabrá que no existe tal persona, pero eso se lo veremos mas adelante.
Si se eligió la 2). sucederá lo mismo que con la opción 1) solo que aquí se tecleara el numero y el programa sabrá reconocer si el numero telefónico esta guardado y a quien pertenece y lo mismo sucede si se teclea otro numero que no existe el programa lo hará saber .
Ahora hablaremos de como será la estructura que va en el programa para que este reconozca ya sea el nombre en la opción 1) o el numero telefónico en la opción 2) y si se teclea el dato correcto.
Para hacer esto posible se toma en cuenta la variable b y se utilizara el cout<< b="="0)" id="BLOGGER_PHOTO_ID_5440220743593924242" style="DISPLAY: block; MARGIN: 0px auto 10px; WIDTH: 382px; CURSOR: hand; HEIGHT: 240px; TEXT-ALIGN: center" alt="" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgn5Li3xYbfir_iTNo8wgpDnbSz2a2x9FGrwF94ecjxzadQd8yCiLXpYJFbhDzFtHzgsNRMJSj4S2ta0NxDk-GiAqRSfobZFDNFEX8u11E6lG4KSEajyB3NuPr79FYUMuVzFlHqAwNKKPrS/s320/Presentaci%C3%B3n3.jpg" border="0">