ALGORITMOS

MANUFACTURA AVANZADA

LENGUAJE

• El lenguaje en su forma mas general se define como una seriede símbolos que sirven para trasmitir una o mas ideas omensajes entre dos entidades diferentes.

• La transmisión de ideas se conoce como comunicación, peroantes que exista la comunicación primero hay que tener encuenta que esta “transmisión de ideas” debe cumplir con dosreglas fundamentales:

1. Las ideas deben ir en un solo sentido a la vez.

2. Deben existir 4 elementos: Emisor, Receptor, Medio de comunicación yMensaje.

Lenguajes de Programación• Los lenguajes de programación se pueden clasificar en:

– Lenguaje de máquina: Ese es el lenguaje del PC. Todas las instrucciones se expresan como combinaciones de 1’s y 0’s.

– Lenguaje de Bajo Nivel: Conocido como ensamblador es un punto intermedio entre el lenguaje del ser humano y el del PC. Las instrucciones son códigos alfabéticos que se rigen por normas nemotécnicas específicas.

– Lenguajes de Alto Nivel: Las instrucciones de estos lenguajes son palabras similares al lenguaje humano. Algunos de ellos son: C++, BASIC, PASCAL, COBOL, FORTRAN, ETC.

ALGORITMO

• Se sabe que la palabra algoritmo se dio enhonor del matemático persa del siglo IX,Khowarizmi. Con éste término se hacereferencia a un conjunto de reglas, ordenadasde forma lógica, para desarrollar un cálculo opara solucionar un problema, ya sea de formamanual o utilizando una máquina.

Características de un algoritmoUn algoritmo debe tener al menos las siguientes características:

• Ser Preciso: Esto significa que las operaciones o pasos del algoritmo deben desarrollarse en un orden estricto, ya que el desarrollo de cada paso debe obedecer a un orden lógico.

• Ser Definido. Ya que en el área de programación, el algoritmo sedesarrolla como paso fundamental para crear un programa, es necesariotener en cuenta que el computador solo hará las tareas programadas ycon los datos suministrados; es decir, no puede improvisar y tampoco seinventará o adivinará el dato que necesite para realizar un proceso. Poreso, el algoritmo debe estar plenamente definido; esto es, que cuantasveces se ejecute, el resultado depende estrictamente de los datossuministrados. Si se ejecuta con un mismo conjunto de datos de entrada,el resultado será siempre el mismo.

Características de un algoritmo• Ser finito: Esta característica implica que el número de pasos de un

algoritmo, por grande y complicado que sea el problema que soluciona,debe ser limitado. Todo algoritmo, sin importar el número de pasos queincluya, debe llegar a un final. Para hacer evidente esta característica, enla representación de un algoritmo siempre se incluyen los pasos inicio yfin.

• Presentación Formal: Para que el algoritmo sea entendido por cualquierpersona interesada es necesario que se exprese en alguna de las formascomúnmente aceptadas; pues, si se describe de cualquier forma puede noser muy útil ya que solo lo entenderá quien lo diseñó. Las formas depresentación de algoritmos son: el pseudocódigo, diagrama de flujo ydiagramas de Nassi/Schneiderman, entre otras.

Características de un algoritmo

• Corrección: el algoritmo debe ser correcto, es decir debesatisfacer la necesidad o solucionar el problema para el cualfue diseñado. Para garantizar que el algoritmo logre elobjetivo, es necesario ponerlo a prueba; a esto se le llamaverificación o prueba de escritorio.

• Eficiencia: hablar de eficiencia o complejidad de un algoritmoes evaluar los recursos de cómputo que requiere paraalmacenar datos y para ejecutar operaciones frente albeneficio que ofrece. En cuanto menos recursos requiereserá más eficiente el algoritmo.

TÉCNICAS PARA LA FORMULACIÓN DE ALGORITMOS

• Diagrama de flujo

• Pseudocódigo

• Diagrama estructurado (nassi-schneiderman)

Diagrama de Flujo

• Un diagrama de flujo es la representación gráfica de un algoritmo.

• También se puede decir que es la representación detallada en forma gráfica de como deben realizarse los pasos en un procesador para producir resultados.

• Esta representación gráfica se da cuando varios símbolos (que indican diferentes procesos en máquina o PC), se relacionan entre si mediante líneas que indican el orden en que se deben ejecutar los procesos.

Diagrama de Flujo

DESVENTAJAS

No se elaboran con base en los principios de laprogramación estructurada, ilustran el flujodel programa, pero no su estructura, requierede un espacio considerable y cuenta condemasiadas ramificaciones.

Los símbolos Indica el inicio y el final de nuestro diagrama de flujo.

Indica la entrada y salida de datos.

Símbolo de proceso y nos indica la asignación de un valor en la memoria y/o la ejecución de una operación aritmética.

Símbolo de decisión indica la realización de una comparación de valores.

Se utiliza para representar los subprogramas.

Conector dentro de página. Representa la continuidad del diagrama dentro de la misma página.

Conector fuera de pagina. Representa la continuidad del diagrama en otra pagina.

Los símbolos

Indica la salida de información por la Impresora.

Indica la salida de información en la pantalla o monitor.

Líneas de flujo o dirección. Indican la secuencia en que se realizan las operaciones.

Recomendaciones para el diseño de Diagramas de Flujo

• Se deben se usar solamente líneas de flujo horizontales y/o verticales.

• Se debe evitar el cruce de líneas utilizando los conectores.• Se deben usar conectores solo cuando sea necesario.• No deben quedar líneas de flujo sin conectar.• Se deben trazar los símbolos de manera que se puedan leer

de arriba hacia abajo y de izquierda a derecha.• Todo texto escrito dentro de un símbolo deberá ser escrito

claramente, evitando el uso de muchas palabras.

Pseudocódigo

• Mezcla de lenguaje de programación que se emplea, dentro de laprogramación estructurada, para realizar el diseño de un programa.

• Se considera un primer borrador, dado que el pseudocódigo tiene quetraducirse posteriormente a un lenguaje de programación. Cabe señalarque el pseudocódigo no puede ser ejecutado por un procesador.

• En esencial, el pseudocódigo se puede definir como un lenguaje deespecificaciones de algoritmos.

• Es la representación narrativa de los pasos que debe seguir un algoritmopara dar solución a un problema determinado.

• El pseudocódigo utiliza palabras que indican el proceso a realizar.

Ventajas de utilizar un Pseudocódigo a un Diagrama de Flujo

• Ocupa menos espacio en una hoja de papel

• Permite representar en forma fácil operaciones repetitivas complejas

• Es muy fácil pasar de pseudocódigo a un programa en algún lenguaje de programación.

• Si se siguen las reglas se puede observar claramente los niveles que tiene cada operación.

Representación El pseudocódigo utiliza para representar las accionessucesivas palabras reservadas en inglés (similares asus homónimos en los lenguajes de programación),tales como start, begin, end, stop, if-then-else, while,repeat-until….etc

Secuencia

Inicio

acción1

acción2

acción n

Fin

• CUERPO DEL PROGRAMA •LÍNEAS CONECTORAS •TOP-DOWN LEFT-RIGHT

COMENTARIOS

CONECTORES CAMBIO DE PÁGINA

ERRORES COMUNES

ERRORES COMUNES

ERRORES COMUNES

EJEMPLOS DE ALGORITMOS

DIAGRAMAS DE FLUJO

• Realizar un diagrama de flujo que permita mostrar enpantalla un mensaje de mayoría o minoría de edadsegún sea el caso para un nombre específico.

INICIO

‘Nombre:’

nom

‘Edad:’

ed

Ed>=18

nom,’Eres mayor de

edad’

nom,’Eres menor de

edad’

FIN

Pseudocódigo

• Se requiere preguntar dos valores, y acontinuación ofrecer un menú con lasoperaciones básicas (+, -, *, /). Después depresentar el resultado se ofrecerá laposibilidad de una nueva operación.

Pseudocódigo

Real : X, Y, RESPUESTAEntero : OPCIONCarácter : OP

InicioRepetir

escribir(‘Primer valor : ’ )leer(X)escribir(‘Segundo valor : ‘)leer(Y)escribir(‘1) Suma ‘)escribir(‘2) Resta ‘)escribir(‘3) Multiplicación ‘)escribir(‘4) División ‘)escribir(‘Qué operación deseas realizar ? :

‘)leer(OPCION)

casos OPCION de1 : RESULTADO

X+Y2 : RESULTADO

X-Y3 : RESULTADO

X*Y4 : si Y=0 entonces

escribir(‘ Error ‘)RESULTADO 0

en caso contrario RESULTADO X/Y

escribir (‘Resultado :‘,RESULTADO)escribir(‘Deseas otro cálculo : *S/N+ ‘)leer(OP)Hasta que RES = ‘N’Fin

MÁQUINAS DE ESTADO FINITO

Máquinas de Estados Finitos

Las máquinas de estado finito (SFM) son sistemas digitales donde las salidas dependen de las entradas y de los estados previos almacenados.

De manera mas clara, una máquina de estados finitos, es una forma gráfica de expresar un proceso secuencial.

Ejemplo

Retiro en un cajero.

1. Insertar la tarjeta.

2. Digitar la clave.

3. Digitar el monto.

4. Retirar el dinero.

Si no se sigue este estricto proceso no se puede llegar al punto 4 y obtener el dinero.

Representación

• Las máquinas de estado finito estánconformadas por entradas, salidas, estados ytransiciones, que se representan de lasiguiente manera:

ESTADO

Al siguiente

estado

Del estado

previo

X/R

X: Entrada que provoca una transición.

R: Salida.

http://www.youtube.com/watch?v=5AzRuYnCuhE&feature=related

EJEMPLO

• Encender un LED con un pulsador

Otro ejemplo

Un hombre desea cruzar un río con unLeón, una bolsa de Trigo y una Vaca. Elproblema es que sólo puede cruzar él y dos delos elementos si permitir que la vaca devore eltrigo o que el león devore a la vaca. Pararesolver el problema hay que seguir unasecuencia estricta.

Para el ejemplo del hombre

• Los estados se definen en cada una de las situaciones.– El estado inicial es cuando está con todos los elementos a

un lado del río (Lado A).– El hombre pasa al lado B del río con la vaca.– Se devuelve al lado A solo.– Pasa al lado B con el león.– Se devuelve al lado A con la vaca.– Pasa al lado B con el trigo.– Se devuelve al lado A solo.– Pasa al lado B con la vaca.

La Representación.

HLTV-E

LT-HV

HLT-V T-HLV

HTV-L

V-HTL

HV-TLE-HVTL

HT-LV

LV-HT

TV-HL

ERROR

ERROR

ERROR

H-B

H-A

H-BH-A

H-B

H-B

H-B

H-B

H-B

H-A

EJEMPLO (Clave electrónica)• CLAVE (UUDR)

DISEÑO

• Diseñar un circuito que controle el siguiente sistema.

SI SDM

ON

DISEÑO (Explicación)

El sistema se activa una vez se hunde el botón “ON”.

El motor empieza a girar a la derecha hasta que la placa negra llega al sensor “SD”.

Cuando llega al sensor “SD”, la polaridad del motor se invierte y la placa avanza hacia el lado izquierdo.

Cuando llega al sensor “SI” el motor se detiene.

PASOS

1. Se identifican las entradas y las salidas.

Entradas:

– Botón START: BS.

– Sensor Derecha: SD.

– Sensor Izquiereda: SI.

Salidas:

– X: Entrada al puente “H”.

– Y: Entrada al puente “H”.

X Y DESCRIPCIÓN

0 0 MOTOR OFF

0 1 DERECHA

1 0 IZQUIERDA

1 1 FRENO

PASOS

2. Descripción del problema (seudo código).– Inicialmente el motor se encuentra apagado, en un

estado de reposo donde el BS está desactivado, el sensor SI está activado y el SD está desactivado. Esta es la posición inicial o estado de repos del sistema.

– Cuando se da un START (BS=1) y el SI está activado, el motor se enciende ala derecha (XY=01), hasta que el sensor SI se activa.

– En ese momento el motor se activa a la izquierda (XY=10), hasta que el sensor derecha se active.

– Una vez el sensor SI se activa el sistema queda en espera para ser activado nuevamente (XY=00).

La máquina de estados

• CÓDIGO= BS SI SD / XY

00 01

10

REPOSO

IZQUIERDADERECHA

110/01

001/10010/10

000/10

110/01

000/01

010/01

100/01

010/00

Tabla de estados

VALORES PRESENTES SIGUIENTES

ESTADOS ENTRADAS SALIDAS ESTADOS

A1 A2 BS SI SD X Y A1’ A2’

0 0 0 1 0 0 0 0 0

0 0 1 1 0 0 1 0 1

0 1 1 1 0 0 1 0 1

0 1 0 1 0 0 1 0 1

0 1 1 0 0 0 1 0 1

0 1 0 0 0 0 1 0 1

0 1 0 0 1 1 0 1 0

1 0 0 0 1 1 0 1 0

1 0 0 0 0 1 0 1 0

1 0 0 1 0 0 0 0 0