Loading presentation...
Prezi is an interactive zooming presentation

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Maquinas Algoritmicas

No description
by

brian ojeda

on 2 July 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Maquinas Algoritmicas

Máquinas Algorítmicas
* Molina Pauluk, Numa Roy
* Ojeda Rodriguez Brian M. G.
Introducción
En el transcurso de esta monografía iremos abarcando los distintos temas acerca de las máquinas de estado algorítmicas o ASM (algorithmic state machines), como su clasificación, conceptos relacionados, métodos de implementación de las mismas y su arquitectura.

Dado que el concepto de algoritmo es mucho más antiguo que la ciencia de la computación, las máquinas algorítmicas son también invenciones antiguas; entendiéndose como aquellas que funcionan siguiendo los pasos marcados en su algoritmo. Consisten actualmente en un sistema digital capaz de materializar y ejecutar un determinado algoritmo.

Concepto
Se puede definir una máquina algorítmica como el aparato capaz de ejecutar un algoritmo. Puesto que a la computadora se le indica lo que debe hacer mediante un programa se tendrá que emplear necesariamente un algoritmo que guie su funcionamiento, es por ello que las computadoras son un tipo de máquinas algorítmicas.
Clasificacion
Una maquina es un aparato o sistema que funciona desarrollando cierta tarea. Las maquinas pueden funcionar de forma más o menos autónoma, o por el contrario pueden necesitar ser comandadas por un operario.
Atendiendo al modo en que se controlan las maquinas se pueden clasificar en:

1. Máquinas no-automáticas
2. Máquinas automáticas
3. Máquinas programables


Máquinas no-automáticas: El usuario debe manejar el aparato en todo momento, ya que para que el trabajo se ejecute la presencia del operario es imprescindible. Es cierto que la mayoría de estas máquinas suelen realizar de forma autónoma ciertas funciones pero no son suficientes como para conferirles la categoría de sistemas automáticos.
Máquinas automáticas: El operador de la maquina no debe supervisar su funcionamiento continuamente. Las máquinas que pueden ser consideradas automáticas completan su cometido de forma autónoma una vez que reciben del exterior las órdenes apropiadas.
La automatización es un grado y la gama de máquinas más o menos automáticas es muy amplia, todas admiten una interrelación con el usuario y funcionan de forma autónoma.
Cuando se diseña una maquina automática se decide cuál será su comportamiento futuro y su nivel de automatismo se implementa en sus componentes de una manera fija, es decir, el algoritmo está integrado en la misma máquina. Si se quiere alterar las prestaciones del aparato se debe desmontar la máquina para aislar y cambiar el algoritmo.
Utilizamos el siguiente esquema para representar a los aparatos automáticos donde el algoritmo es parte integrante de la propia maquina:
Cambiar el algoritmo de las maquinas automáticas no es trivial, por lo tanto su funcionamiento es autónomo pero poco flexible.

Máquina programable: Las maquinas programables son máquinas automáticas muy sofisticadas. También recibirán los requerimientos del usuario, pero al contrario de las maquinas automáticas normales su comportamiento es ciertamente flexible.

Para garantizar que su funcionamiento será flexible, las maquinas programables se diseñan distinguiendo en ella dos partes bien diferenciadas:
• Por un lado se tiene lo que llamaremos maquina base, se puede admitir que este componente es difícil de alterar para el usuario.
• Por el otro lado se tiene el componente al que llamaremos programa, que además de establecer el comportamiento de la maquina posee la característica de ser fácil de cambiar:

El comportamiento de la maquina programable esta determinado por la intervención de los dos componentes, como el programa es fácil de cambiar según las ocasiones la consecuencia es que el funcionamiento de la maquina programable es extremadamente flexible y adaptativo.

Recordando la clasificación hecha al principio de este apartado, y utilizando un ejemplo clásico, tenemos:

1. Piano: maquina no-automática para producir música, a medida que el pianista pulsa las teclas se oye la música.

2. Caja de música: máquina automática, al abrir su tapa se oirá la melodía. La música se toca automáticamente pero siempre es la misma pieza.

3. Tocadiscos: maquina programable, cambiando de disco se pueden tener diferentes conciertos, puede pasar fácilmente de aparentar un concierto de folk a oírse a un concierto barroco. Además de sonar la música de forma automática, se puede cambiar muy fácilmente.

Diremos que la computadora es una maquina programable, pues se distinguen en su estructura los dos componentes de dicho tipo de maquinas. Además de la maquina base (en el mundo de la computación se le conoce como hardware) la computadora dispone de un catalogo de programas que son fáciles de cargar. El conjunto hace que la computadora sea un aparato verdaderamente versátil, por ejemplo con el mismo hardware pero atendiendo al software cargado la computadora puede aparentar una máquina de escribir si en ese momento se está ejecutando un procesador de textos, o puede ser la mesa de diseño donde se dibujan los planos de un proyecto si tenemos un programa de CAD, o puede servir para llevar la contabilidad, o retocar imágenes digitales, o resolver sistemas de ecuaciones, o generar música, o graficar tablas, etc.…

Arquitectura de las
maquinas algoritmicas
Donde, recordando el proceso que describe el algoritmo de Euklides, tenemos los tres pasos marcados con sus respectivos números:
1.Llamaremos M al mayor de los datos, N será el más pequeño de ellos.

2.Tras dividir M entre N se obtiene el resto R

3.Si R distinto de cero, asignar el valor N a M, asignar el valor R a N y volver al segundo paso, de lo contrario el m.c.d. coincide con el valor de N
Por tanto, siendo 36 y 16 los datos de entrada para calcular “a mano” el m.c.d. se realzan dos cometidos

Por una parte los valores deben ser guardados en algún lugar para que cuando sea oportuno se recuperen de ese almacén. En el ejemplo el dato 36 se almacena en la variable M (conceptualmente M es una variable pues cada vez puede ir tomando distintos valores), esta operación se conoce como almacenamiento de la información.

El segundo cometido a realizar será el procesamiento de la información, que en nuestro ejemplo se sustancia en la ejecución de operaciones aritméticas y operaciones lógicas.
Para obtener el valor de R se debe efectuar la división entre M y N, para detener el proceso repetitivo se debe comparar el valor de R con la constante cero (operación lógica).

Si en vez de hacerlo a mano, fuera una maquina la encargada de calcular el m.c.d. de 36 y 16, dicha maquina también necesitaría poseer esas dos características, almacenamiento de la información (para guardar y recuperar valores) y procesamiento de la información (para ejecutar operaciones). En la arquitectura de las computadoras existen dos componentes perfectamente diferenciados que se ocupan de esas dos funciones: la memoria y la unidad procesadora.
Si tuviéramos que efectuar el cálculo máximo común divisor de dos números utilizaríamos dos elementos. Uno físico, nuestro escritorio con papel y lápiz, y, otro intelectual que sería el algoritmo de Euklides. La combinación de ambos recursos elementales nos daría una solución parecida a esta:
En el anterior esquema se ve el núcleo de la computadora pero como ya sabemos las maquinas automáticas y las maquinas programables, para que se pongan en marcha, reciben del exterior las excitaciones del usuario. También a la computadora, se le deberá aportar el algoritmo programado y los datos que el programa necesita. Además, una vez de que la computadora haya realizado su trabajo tendrá que mostrar los resultados al usuario (sacar la información al exterior de la maquina).

En consecuencia, las acciones de una computadora serán cuatro, donde las dos primeras están relacionadas con la noción de entrada/salida y en algunos textos aparecen como una única función. He aquí las funciones:

1. Aceptación de entradas: el usuario le aportara la información a la computadora, cuando decimos información nos referimos tanto a los datos como al programa. El dispositivo encargado de esta función es la unidad de entrada.

2. Generación de salidas: la computadora devolverá al exterior el resultado de la información ya procesada. El dispositivo encargado de esta función es la unidad de salida.

3. Almacenamiento de la información: la información se almacena en la memoria de la computadora, desde la memoria la información puede ser llevada tanto a otros componentes internos de la unidad procesadora como a la unidad de salida.

4. Procesamiento de la información: El procesamiento de la información consiste en dos facetas. La computadora debe realizar operaciones aritméticas y operaciones lógicas, la computadora debe “entender” las instrucciones del programa y ejecutarlas.

Y, el esquema más simple:


La combinación de estos componentes constituye el hardware de la maquina programable, es decir la parte difícilmente alterable, la que hemos llamado de la maquina base. A la parte fija se le añade el programa que sabemos se puede cambiar de forma sencilla.

Componentes/ Diagramas de la ASM
Diagramas y sus componentes
Un diagrama ASM está compuesto por uno a más bloques ASM conectados y dispuestos de tal forma que cada salida de un bloque es la entrada de un único bloque de estado.
Reglas
o El diagrama debe definir un único próximo estado para cada uno de los estados presentes y conjunto de condiciones.
o Todo camino definido por el conjunto de bloques de condición debe llevar necesariamente a otro estado.

Un diagrama ASM se compone de una interconexión de los tres tipos de elementos básicos: los estados, los controles condición, y salidas condicionales.
Un estado de ASM, representada como un rectángulo, corresponde a un estado de un diagrama de estado regular o máquina de estados finitos. El nombre del estado se indica fuera de la caja en la esquina superior izquierda.
Una condición de verificación de ASM, indicado por un diamante con una entrada y dos salidas (de verdadero y falso), se utiliza para la transferencia condicional entre dos estados o entre un Estado y una salida condicional.
El cuadro de decisión contiene la expresión condición establecida para la prueba, la expresión contiene una o más entradas de las FSM.

Diagramas ASM Incorrectos
Diagramas ASM Correctos
Algoritmo de multiplicación de lápiz y papel mejorado
Ejemplo de diseño: Multiplicador Binario
Ejemplos y otros graficos
2.UNIDAD DE PROCESAMIENTO O RUTA DE DATOS DEL MULTIPLICADOR
Diagrama de bloques del multiplicador binario con el algoritmo de lápiz y papel mejorado.
3.DIAGRAMA ASM
DEL MULTIPLICADOR
Diagrama ASM del multiplicador binario
sin bloques de salida condicional
Conclusión
Los diagramas ASM son básicamente una herramienta aplicada en la enseñanza de la electrónica digital

Las ASM como herramienta de diseño digital, mejoran algunas propiedades de los diagramas de estado, gracias a que describen con detalle no sólo las transiciones entre estados, sino también las operaciones que se realizan en ellos. Existe una estrecha relación entre los diagramas ASM y los modernos lenguajes de descripción de circuitos, y propone sustanciales mejoras sobre la notación actual para especificar completamente los diseños.

Los diagramas ASM son una buena alternativa a los diagramas de estado porque, manteniendo su interfaz gráfico e intuitivo, permiten definir de forma más cómoda y consistente las transiciones entre estados y también las operaciones que se han de realizar durante y al final de cada estado.

Bibliografía
*Material otorgado por la asignatura.
*Enlaces externos:
http://es.wikipedia.org/wiki/M%C3%A1quina_de_estados_algor%C3%ADtmica
http://rita.det.uvigo.es/200905/uploads/IEEE-RITA.2009.V4.N2.A1.pdf
http://www.buenastareas.com/ensayos/Identificacion-De-Maquinas-De-Esta-Algoritmico/1219800.html
http://taee2008.unizar.es/papers/p120.pdf
Full transcript