PDF de programación - Tema 9 - Optimizacion

Tema 9

Optimizacion

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

9. Optimizacion

Concepto. Objetivos. Factibilidad. Reglas de Jackson. Formas de optimización. Por afinación.
Por algoritmos. Recursos. Tablas. Parámetros. Matemáticos. Modelos de clasificación. Distintos
métodos. Eficiencia de algoritmos

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

9. Optimizacion

9.1 Concepto

Optimizar un algoritmo implica construirlo lo mas correctamente posible, con
estilo, transparente, sin errores y eficiente.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

9. Optimizacion

9.2 Objetivos

Los objetivos principales son que el algoritmo debe ser construido lo más
pequeño posible o que sea lo más rápido en su ejecución, o de ser viable,
ambos a la vez.

●Lo más pequeño posible: significa que tenga la menor cantidad de
instrucciones posibles

●Lo más rápido posible: significa economizar el tiempo de ejecución del
algoritmo en máquina.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

9. Optimizacion

9.3 Factibilidad

La optimización puede provocar escribirlo incorrectamente, puede resultar
más difícil de entender y más costoso su mantenimiento, como así también
más propenso a incorporar errores.

Todo esto cuesta mucho dinero por lo que debe justificarse económicamente
la tarea de optimizar antes de emprenderla, de allí deriva la primer regla de
Jackson.

la actitud debe ser construir
En caso de justificarse económicamente,
inicialmente un algoritmo claro y transparente, para luego optimizarlo, esto da
lugar a la segunda regla de Jackson.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

9. Optimizacion

9.4 Reglas de Jackson

Regla N 1: "No lo haga"

Si no se puede justificar económicamente.

Regla N 2: "No lo haga todavía"

Si está justificada comenzar con un diseño no óptimo, esto en pro de la
claridad y simplicidad, y a posteriori optimizarlo.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

9. Optimizacion

9.5 Formas de Optimizacion

Por afinación

Por algoritmos

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

9. Optimizacion

9.5 Formas de Optimizacion

Por afinación

Por algoritmos

Esto implica no modificar la estructura del algoritmo sino utilizar factores de
bloque, segmentación de programas, asignación de memorias intermedias,
etc.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

9. Optimizacion

9.5 Formas de Optimizacion

Por afinación

Por algoritmos

La optimización por algoritmos se realiza a través de recursos como ser:

Estructuras de datos (arreglos, pilas, colas, árboles, etc).

Tablas

Matemáticos (por ejemplo para determinar pares e impares se utilizan los
recursos: parte entera, resto, potencia de menos uno (-1), etc).

Parámetros (por ejemplo para determinar la longitud de los arreglos, tope
de una pila, frente y final de una cola, tasa de interés, etc.).

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

9. Optimizacion

9.5 Formas de Optimizacion

La mayoría de los autores (Jackson, Boria, Rice y Rice) eligen los modelos
de clasificación para ilustrar la optimización por algoritmos.

Para ilustrar el objetivo más pequeño se emplea el caso de determinación
de tipos de triángulos.

Para ilustrar el objetivo más rápido se aprovechará el método de
clasificación de intercambio directo comunmente llamado "burbuja"
(desarrollado en el tema de clasificacion).

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

9. Optimizacion

9.5 Formas de Optimizacion

Optimización haciendo el algoritmo más pequeño

Dado un conjunto de tríos de valores A, B, C (mayores que cero) determinar,
de entre los que forman triángulo, los distintos tipos (escaleno, isósceles,
equilátero) y también cual de ellos es recto. Informar de acuerdo a la figura
que contiene el modelo de la salida.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

LADO 1LADO 2LADO 3TIPO------Escaleno------No triángulo------Equilátero------EscalenoRECTOSINOSI 9. Optimizacion

9.5 Formas de Optimizacion

Optimización haciendo el algoritmo más pequeño

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

PRI_PROFIN_PROEQUILATEROISOSCELESESCALENOUN TRIOU N T R I A N G U L O PRI - PRO(1 vez)UN - TRIO(t veces)FIN - PRO(1 vez) TRIANGULO(0 ó 1 vez)NO TRIANGULO(0 ó 1 vez)IMPRIMIR(1 vez) TIPO(1 vez) EquilateroIsoscelesEscalenoA)B)NIVEL 1ProgramaPrincipalNIVEL 2Un - TrioNIVEL 3TrianguloNIVEL 4TipoRECTOSRECTO(1 vez) J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

COMENZARPRI-PROEOFNOSIFIN-PROUN-TRIOPARARUN-TRIOA < B+CNOSIB < A+CNOSIC < A+BNOSINO-TRIANGULOTRIANGULOIMPRIMIRLEERFIN-PRO"A B C TIPO "PRI-PROLEERRECTOTIPOA = BB = CSISIB = CTIPO="ISOSCELES"A = CTIPO="ESCALENO"NONOSINONOTIPO="EQUILATERO"SITRIANGULORECTOTIPOLEERLEERA,B,CA, B, C, TIPOIMPRIMIRRECTONO-TRIANGULOTIPO= "NOTRIANGULO"RECTO= " "RECTOA2 = B2 + C2nosiB2 = A2 + C2nosiC2 = A2 + B2nosiRECTO = "NO"RECTO = "SI" 9. Optimizacion

9.5 Formas de Optimizacion

Optimización haciendo el algoritmo más pequeño

Seguidamente se procede a optimizar el algoritmo desarrollado en el ejemplo anterior para tratar
de hacerlo más pequeño (menor cantidad de instrucciones), teniendo en cuenta lo siguiente:

1) En la rutina un-trío se observa que la condición matemática de triángulo
(un lado sea menor que la suma de los otros dos) se transforma en suficiente
si el lado que se compara es el mayor de todos.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

9. Optimizacion

9.5 Formas de Optimizacion

Optimización haciendo el algoritmo más pequeño

2) En la rutina de recto también la condición necesaria basada en Pitágoras
(A2= B2+ C2) se transforma en suficiente si se sabe con anticipación cual es
la hipotenusa, o sea el lado mayor.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

RECTOA2 = B2 + C2nosiB2 = A2 + C2nosiC2 = A2 + B2nosiRECTO = "NO"RECTO = "SI" 9. Optimizacion

9.5 Formas de Optimizacion

Optimización haciendo el algoritmo más pequeño

3) En la rutina tipo se advierte que deben compararse todos contra todos los
lados para determinar el tipo de triángulo. Probablemente el tener juntos los
posibles lados iguales, implique una simplificación del algoritmo.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

TIPOA = BB = CSISIB = CTIPO="ISOSCELES"A = CTIPO="ESCALENO"NONOSINONOSITIPO="EQUILATERO" 9. Optimizacion

9.5 Formas de Optimizacion

Optimización haciendo el algoritmo más pequeño

las

condiciones necesarias

Transformar
con que fueron definidas
inicialmente, en dos condiciones suficientes (puntos 1 y 2) y simplificar el
análisis de tipo en el punto 3, se logra si
los lados están clasificados en
orden descendente.

Aprovechando una rutina desarrollada que ordena en forma descendente un
conjunto de números, se invoca a la misma al comienzo de la rutina un_trío
y a partir de allí se optimiza el algoritmo con los lados ordenados, quedando
como se indica a continuación las rutinas un-trío , tipo y recto.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

9. Optimizacion

9.5 Formas de Optimizacion

Optimización haciendo el algoritmo más pequeño

Un_trío: Se suprimen las condiciones de B<A+C y C<A+B.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

UN-TRIOA < B+CNoSiNOTRIANGULOTRIANGULOIMPRIMIRLEERORDENAR 9. Optimizacion

9.5 Formas de Optimizacion

Optimización haciendo el algoritmo más pequeño

Tipo: En el caso de triángulos isósceles, al ordenar los lados, los que son
iguales están contiguos, por lo que la condición A = C es innecesaria.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

TIPOA = BB = CSISIB = CTIPO="ISOSCELES"TIPO="ESCALENO"NONOSINOTIPO="EQUILATERO"TIPOA = BB = CSISIB = CTIPO="ISOSCELES"A = CTIPO="ESCALENO"NONOSINONOSITIPO="EQUILATERO" 9. Optimizacion

9.5 Formas de Optimizacion

Optimización haciendo el algoritmo más pequeño

Recto: Se suprimen las condiciones B2= A2+ C2 y C2= A2+ B2

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

RECTOA2 = B2+C2SINORECTO = "SI"RECTO = "NO"RECTOA2 = B2 + C2nosiB2 = A2 + C2nosiC2 = A2 + B2nosiRECTO = "NO"RECTO = "SI" 9. Optimizacion

9.5 Formas de Optimizacion

Optimización haciendo el algoritmo más rápido.

Aprovechando la utilización de la rutina de ordenación de los lados del
ejemplo anterior (ORDENAR), a los efectos de introducir otros recursos de
optimización que no hagan a la reducción del programa - lo más pequeño
posible - , sino a la reducción de los tiempos de ejecución - lo más rápido
posible - .

A continuación se desarrolla uno de los métodos de clasificación más
conocido: intercambio directo o burbuja.

Recordemos que este algoritmo se basa en recorrer la lista (arreglo), de derecha a izquierda o
de izquierda a derecha, examinando pares sucesivos de elementos adyacentes, permutándose
los pares desordenados. Así el desarrollo del algoritmo tal cual se mostró en el
tema
correspondiente.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

9. Optimizacion

9.5 Formas de Optimizacion

Optimización haciendo el algoritmo más rápido.

Aprovechando la utilización de la rutina de ordenación de los lados del
ejemplo anterior (ORDENAR), a los efectos de introducir otros recursos de
optimización que no hagan a la reducción del programa - lo más pequeño
posible - , sino a la reducción de los tiempos de ejecución - lo más rápido
posible - .

A continuación se desarrolla uno de los métodos de clasificación más
conocido: intercambio directo o burbuja.

Recordemos que este algoritmo se basa en recorrer la lista (arreglo), de derecha a izquierda o
de izquierda a derecha, examinando pares sucesivos de elementos adyacentes, permutándose
los pares desordenados. Así el desarrollo del algoritmo tal cual se mostró en el
tema
correspondiente.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

154233710154233