Algoritmos computacionales: febrero 2010

Proyecto 1

Problema # 2

Colocar un grupo de libros en un librero en orden alfabético según el título.

Bueno este es el otro problema que mi compañera y yo elegimos. En este problema tenemos que encontrar la solución para poder ordenar los libros en orden alfabético según su título.

El algoritmo que realizamos fue el siguiente:

1. Inicio

2. Declaras los libros

3. Pedir y asignar los libros que vamos acomodar

4. Ingresas el titulo del libro

5. lo va acomodar directamente en la primera posición.

6. Si el siguiente libro que ingreses la letra es menor al primero lo correra a la segunda posición, sino quedara igual y asi sucesivamente todos los libros que ingreses.

7. fin

Para representar nuestro problema y algoritmo hicimos el siguiente diagrama de flujo:

Esta es la representacion de nuestro algoritmo.
Primero inicio, luego declaramos un arreglo indefinido porque aun no sabemos los libros que acomodaremos, primero pedimos y asiganamos los libros que queremos acomodar, para poder definir de que tamaño quedara nuestro arreglo, despues este arreglo toma como valor el numero de libros ingresados, despues nuestra variable "x" contara las filas del arreglo, despues nos pide el nombre del libro, ingresamos el nombre del primer libro que deseamos acomodar y el programa automaticamente lo va acomodar en la primera posición de nuestro librero porque aun no tenemos mas libros, pero despues se regresa y te pide el nombre del segundo libro y si este tiene su letra inicial menor que el primero que acomodamos regresara al siguiente libro hasta terminar de capturar el numero de libros que asignamos y si es mayor se iniciara otro contador que lo declararemos como "y"que controlara el valor de la fila del arreglo despues compararemos los valores guardados, si es mayor cambiaran los valores y seguiran realizandoce el mismo proceso de comparacion desde el inicio, en cambio si no es mayor pasara al siguiente par de las posiciones que tenemos. Al final despues de ingresar todos los nombres de libros imprimira nuestro programa la lista de los libros ya ordenados alfabeticamente.

A continuación presentare 2 ejemplos de nuestro problema:
Ejemplo 1

Primero nos pide el n

umero de libros que vamos acomodar en este caso pondremos 5 osea que ingresaremos 5 titulos de libros.

Despues ingresaremos los titulos de los 5 libros que son:

Este libro empezara en la primera posición parcialmente.

Despues de que ingresemos este segundo titulo nuestro programa comparara si va primero o despues del primero.

Despues ingresamos el tercer libro y comparara de nuevo con los 2 anteriores para poder acomodarlo en su respectiva posición que en este caso deberia de quedar en segundo osea en medio de los 2 anteriores.

Luego seguimos con el cuarto libro y nuestro programa hace de nuevo el mismo procedimiento comparar con los demas libros si es mayor o menor para asignarle su respectivo lugar.

Por ultimo ingresamos el quinto y ultimo libro que queriamos acomodar de nuevo hace el mismo proceso compara con todos los libros y lo acomoda, que en este caso tendria que quedar en primera posición.

Y para finalizar el programa nos lanzara la lista de los libros que ingresamos ya ordenada alfabeticamente.

Ejemplo 2
Nuestro programa preguntara cuantos libros deseas acomodar o almacenar.

Despues escribiremos los libros que queramos añadir a la lista igual como lo hicimos en el ejemplo 1 pero si se quisiera almacenar mas o menos libros de los indicados aparecera un error dependiendo de la razon:

El programa hara el mismo procedimiento que en el ejemplo 1 para acomodar y almacenar los libros de orden alfabetico segun su titulo.

Todos los diagramas de flujo fueron realizados en el diagram dessigner
Para mas información sobre ese software y donde podran descargarlo den click en el vinculo.

Mi compañera de equipo: Laura Gonzalez Hernandez

Proyecto 1

Problema # 1

Buscar un numero telefónico en la guia telefónica
En este problema mi compañera Laura y yo lo que tuvimos que hacer es encontrar la solución de como llegar a encontrar el numero que estamos buscando en una guia telefónica y nuestro algoritmo fue el siguiente:

Algoritmo

1. Inicio

2. Declarar variables ( tels, nom)

3. Declarar la matriz

4. Pedir y asignar “nom”.

5. Ingresar contador =1

6. Comprobar nom= tels en el contador 1

7. Si existe te da el numero.

8. Si no esta en la agenda ingresas otro nombre.

9. Fin

Para representar nuestro algoritmo esta el siguiente diagrama de flujo que realizamos:

Este diagrama es el mismo que el que acabamos de mostrar en la imagen de arriba solamente que en este le asiganamos nombres y telefonos a nuestra agenda telefonica:

Este es el diagrama que realizamos para este problema
primero que nada es el inicio luego declaramos las variables, que vamos a utilizar despues declaramos una matriz la cual seria nuestra agenda telefonica, dandole valores como en este caso nombre y telefono, despues te pide que ingreses el nombre de la persona que buscas su telefono, se activara el contador=1 que es el valor inicial de la variable,y lo checara si es que existe o no esa persona en la agenda que se refiere a que si el valor es igual se imprime y te dara el numero que estas buscando pero si no es igual el contador incrementara en 1 para buscar en los siguientes valores, en cambio si el numero no lo esta te dira el programa que no esta en la agenda y al final pues te dira si quieres buscar otro numero o si no lo deseas termina.

A continuacion les presentare 2 ejemplos de nuestro problema:

En este primer ejemplo mostraremos como correria el programa al ingresar un nombre que si existe en la agenda telefonica.

Primero inicio y luego nos pediran el nombre de la persona de la que queremos buscar su numero, en este caso dimos el nombre de Martin Perez, despues empezara el contador a checar si existe ese numero en la agenda telefonica si existe lo imprimira.
En este caso si viene el nombre en la agenda telefonica lo imprime y pues nos aparecera en el otro cuadro de texto el numero que estamos buscando como se muestra en la figura siguiente:

Ahora mostrare el otro ejemplo en donde el nombre que ingresamos no esta en la agenda

Primero nos aparece un cuadro

de texto que nos dice ingrese el nombre en este caso ingresamos el de Angela Peña, y acontinuacion veremos lo que nos aparecera al momento de que el contador cheque si esta o no el nombre en la ag

enda, en este caso nuestro programa nos dice que ese numero no esta en la agenda por lo tanto no imprimira ningun numero, porque nos dice esto, porque al momento de que declaramos la matriz de nombres y telefonos que iban a ser nuestra agenda no esta el de Angela Peña y al final nos aparecera un cuadro que nos dice si queremos buscar otro numero, si le damos si se repite el proceso pero si le damos no se acaba el programa.

El diagrama de flujo lo realizamos en: diagram dessigner

Mi compañera es Laura Gonzalez Hernandez

Maquinas de Turing

Una máquina de Turing consiste, básicamente, en una cinta infinita, dividida en casillas. Sobre esta cinta hay un dispositivo capaz de desplazarse a lo largo de ella a razón de una casilla cada vez. Este dispositivo cuenta con un cabezal capaz de leer un símbolo escrito en la cinta, o de borrar el existente e imprimir uno nuevo en su lugar. Por último, contiene además un registro capaz de almacenar un estado cualquiera, el cual viene definido por un símbolo. Los símbolos que definen el estado del dispositivo no tienen por que coincidir con los símbolos que se pueden leer o escribir en la cinta. En los programas presentados en el artículo, los posibles símbolos a leer o escribir en la cinta son el 0 y el 1, y los posibles estados se representan con letras mayúsculas. En el emulador, existe un cambio en la representación del estado, usando para ello los números del 0 al 99, para permitir un mayor número de ellos.

La máquina tiene un funcionamiento totalmente mecánico y secuencial. Lo que hace es leer el símbolo que hay en la casilla que tiene debajo. Después toma el símbolo del estado en que se encuentra. Con estos dos datos accede a una tabla, en la cual lee el símbolo que debe escribir en la cinta, el nuevo estado al que debe pasar y si debe desplazarse a la casilla izquierda o derecha.

Descripcion de la maquina de Turing.

La idea de la maquina funcion con un Cabeza de Lectura y Escritura que lee una cinta infinita.

Cada vez que lee, borrar el contenido anterior, escribe un nuevo contenido, para luego Avanzar un lugar hacia la izquierda o Derecha.

Con esta maquina se puede realizar cualquier computo de las maquinas computadoras actuales

La maquina de Turing puede considerarse un automata capaz de leer lenguajes formales (es un conjunto de palabras (Palabras son cadenas de caracteres) de longitud finita que se forman a partir de un alfabeto (_Conjunto de caracteres) finito.

Definicion de una maquina de Turing de una sola cinta :una 6- tupla $M=(Q, \Gamma, s, b, F, \delta)\,$ ,

$Q \,$ es un conjunto finito de estados.
$\Gamma \,$ El alafabeto de la cinta, un conjunto finito de símbolos de cinta
$s \in Q$ Estado Incial.
$b \in \Gamma$ Ssímbolo denominado blanco.
$F \subseteq Q$ es el conjunto de estados finales de aceptación.
$\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}\,$ función de transición, donde L es un movimiento a la izquierda y R es el movimiento a la derecha.