Tema 23 – Diseño de algoritmos. Técnicas descriptivas.

1. Introducción. 1

1.1. Relación con los ciclos impartidos en FP. 1

1.2. Introducción a la Programación. 1

1.3. Introducción a los Algoritmos. 1

2. Diseño de Algoritmos. 1

2.1. Elementos de un algoritmo. 2

2.2. Estrategias o enfoques de diseño de algoritmos. 2

2.3. Complejidad Computacional 2

3. Técnicas Descriptivas. 2

3.1. Diagramas de flujo. 2

3.2. Diagramas de Nassi-Schneiderman. 3

3.3. Tablas de Decisión. 3

3.4. Pseudocódigo (falso lenguaje) 3

4. Técnicas de Diseño de algoritmos. 3

4.1. Recursividad. 4

4.2. Divide y Vencerás. 4

4.3. Backtraking (vuelta atrás) 4

4.4. Algoritmos Voraces. 4

5. Bibliografía. 5

1. Introducción

1.1. Relación con los ciclos impartidos en FP

Este tema está directamente relacionado con los siguientes módulos y ciclos formativos de la rama de informática:

· CFGS Administración de Sistemas Informáticos:

o Fundamentos de programación (Informática).

· CFGS Desarrollo de Aplicaciones Informáticas:

o Programación en lenguajes estructurados (Informática).

1.2. Introducción a la Programación

· Programa: Conjunto de instrucciones en algún lenguaje de programación suministradas al ordenador, ordenadas de una forma determinada, para que éste ejecute las operaciones para resolver un problema.

· Instrucción: Es una cadena de símbolos de un alfabeto, formada de acuerdo con ciertas reglas sintácticas que el procesador (o el compilador) entiende, y que finalmente serán interpretadas y ejecutadas por el procesador.

· Lenguajes de programación: Técnica estándar de comunicación que permite expresar las instrucciones que han de ser ejecutadas en una computadora. Consiste en un conjunto de reglas sintácticas y semánticas que definen un programa informático.

Un lenguaje de programación permite a un programador especificar de manera precisa: sobre qué datos una computadora debe operar, cómo deben ser estos almacenados y transmitidos y qué acciones debe tomar bajo una variada gama de circunstancias. Todo esto, a través de un lenguaje que intenta estar relativamente próximo al lenguaje humano o natural, tal como sucede con el lenguaje Léxico.

Se pueden clasificar en lenguajes de bajo nivel (lenguaje máquina), nivel medio (ensamblador) y nivel alto (C, pascal, cobol…).

1.3. Introducción a los Algoritmos

“Un algoritmo es una lista bien definida, ordenada y finita de operaciones que permite hallar la solución a un problema. Dado un estado inicial y una entrada, a través de pasos sucesivos y bien definidos se llega a un estado final obteniendo una solución”

· Debe de ser eficiente, definido, finito y preciso:

o Eficiente: Utilizará de forma óptima los recursos del ordenador.

o Definido (determinista): Ante unos mismos valores de entrada, un algoritmo debe proporcionar siempre el mismo resultado o valor de salida (a excepción de los algoritmos probabilistas o no deterministas que estarán en función de valores pseudoaleatorios).

o Finito: La mayoría de autores restringen la definición de algoritmo a procedimientos que deben acabar en algún momento, y así serán en su mayoría, aunque otros contemplan la posibilidad de que existan procedimientos que pudieran ejecutarse indefinidamente.

o Preciso: cada paso a seguir tiene un orden y las operaciones a llevar a cabo deben ser especificadas de manera rigurosa y no ambigua.

· En la mayoría de los casos su estudio es completamente abstracto sin usar ningún tipo de lenguaje de programación ni cualquier otra implementación, aunque también se puede plasmar de esa forma. Así, el análisis de los algoritmos se centra en los principios básicos del algoritmo, no en los de la implementación particular. Las formas de plasmar un algoritmo son varias: lenguaje natural, pseudocódigo, diagramas de flujo o en algún lenguaje de programación.

· Un algoritmo, estrictamente hablando, no puede ejecutarse hasta que no se implementa, ya sea en un lenguaje de programación, en un circuito eléctrico o en un aparato mecánico.

2. Diseño de Algoritmos

2.1. Elementos de un algoritmo

· Datos: Los tipos de datos más simples son los numéricos enteros o reales, los caracteres y los booleanos. Los tipos más complejos son por un lado las estructuras de datos estáticas, como registros, vectores o tablas, y por otro las dinámicas, como listas, colas, pilas o árboles.

· Expresiones: suelen estar compuestas por la unión de varios operandos: variables, constantes o literales; unidos entre sí por operadores que realizan una acción sobre ellos.

· Variables: Son zonas de memoria que contendrán un dato, al cual se le asigna un nombre para poder referenciarlo y así acceder a su valor o modificarlo.

· Operadores: Elementos que se aplican a uno o varios operadores, realizando algún tipo de operación. Los básicos son los Aritméticos (+,-,*,/,^), Condicionales (=,<,>,<>), Lógicos (AND, NOT, OR) y de Asignación (:=, <-), etc.

· Instrucciones: Primitivas de Entrada, Salida y Asignación, y De control Alternavitas y repetitivas.

2.2. Estrategias o enfoques de diseño de algoritmos

· Top-down: Se define el sistema como una caja negra en la que lo que importa son las entradas y las salidas y no su funcionamiento interno. Después se descompone en cajas negras más pequeñas o subsistemas y se definen con más detalle. De forma recursiva, hasta que el sistema queda talmente especificado.

· Bottom-up: En contraste, en el diseño Bottom-up las partes individuales se diseñan con detalle y luego se enlazan para formar componentes más grandes, que a su vez se enlazan hasta que se forma el sistema completo.

· El desarrollo de software moderno usualmente combina tanto Top-down como Bottom-up. Aunque un conocimiento completo del sistema se considera usualmente necesario para un buen diseño, la mayoría de proyectos de desarrollo de software tratan de reutilizar componentes software desarrollados y probados previamente.

2.3. Complejidad Computacional

· Todo algoritmo tiene una serie de características, entre otras que requiere una serie de recursos, algo que es fundamental considerar, a la hora de implementarlos en una máquina. Estos recursos son principalmente:

o El tiempo: período transcurrido entre el inicio y la finalización del algoritmo.

o La memoria: la cantidad que necesita el algoritmo para su ejecución.

· Notación O-grande:

o En general, la mayoría de los problemas tienen un parámetro de entrada que es el número de datos que hay que tratar, esto es, N. La cantidad de recursos del algoritmo es tratada como una función de N. f(N). De esta manera puede establecerse un tiempo de ejecución del algoritmo que suele ser proporcional a una de las siguientes funciones: 1, logN, N, NlogN, N2, N3, 2N,…

o En general, el tiempo de ejecución es proporcional a alguno de los tiempos de ejecución anteriormente propuestos, además de la suma de algunos términos más pequeños. Así, un algoritmo cuyo tiempo de ejecución sea T = 3N2 + 6N se puede considerar proporcional a N2. En este caso se diría que el algoritmo es del orden de N2, y se escribe O(N2). Conviene diferenciar entre el peor caso y el esperado. Por ejemplo, el tiempo de ejecución del algoritmo Quick Sort es de O(N2). Sin embargo, en la práctica este caso no se da casi nunca y la mayoría de los casos son O(N·logN.)

3. clip_image002Técnicas Descriptivas

3.1. Diagramas de flujo

· Representan gráficamente la secuencia lógica de las operaciones en la resolución de un problema. Debe reflejar el comienzo del programa, las operaciones, la secuencia en la que se realizan y el final del programa.

· Usan símbolos conectados con flechas para indicar la secuencia de instrucciones. Principalmente rectángulos para procesos o instrucciones, rombos para condiciones, círculos para conexión entre procesos y “cuadrados tumbados” para las E/S.

· Son usados para representar algoritmos pequeños, ya que abarcan mucho espacio y su construcción es laboriosa.

3.2. Diagramas de Nassi-Schneiderman

clip_image004

· Son parecidos a los diagramas de flujo, pero omitiendo las flechas, y con las cajas o bloques contiguos. Se lee de arriba abajo y cada bloque ejecuta una operación específica que puede ser descrita con la precisión que se desee.

3.3. Tablas de Decisión

Condición 1

Condición 2

Condición 3

S S S N N N

S N N N N S

– S N S N –

Acción 1

Acción 2

X X X X

X X X

· Herramienta que permite presentar de forma concisa las reglas de lógica que hay que utilizar para decidir acciones a ejecutar, teniendo en cuenta las condiciones y la lógica de decisión de un problema dato. Son utilizadas para traducir los textos administrativos, legislativos, etc., que describen las reglas de gestión de procedimientos a automatizar, permitiendo esclarecer textos difíciles de comprender y descubrir las anomalías y los olvidos. Asimismo, son utilizadas para definir y precisar una lógica de decisión compleja.

3.4. Pseudocódigo (falso lenguaje)

· Técnica para expresar un algoritmo de forma similar a como se haría en un lenguaje de programación, pero utilizando convenciones del lenguaje natural y la lógica del flujo de control. En general, la especificación de un algoritmo constará de los siguientes elementos:

o Declaración de variables

o Precondición

o Nombre del algoritmo.

o Postcondición

· Definición de datos: En algunos casos, y si los tipos de datos son simples, la definición de datos se da por supuesta, en otros casos, sobretodo si se emplean tipos más complejos como pilas, colas, vectores o registros, se definen en la cabecera del algoritmo.

· Primitivas:

o Salida: Escribir VARIABLE

o Entrada: Leer VARIABLE

o Asignación: VARIABLE1 :=VARIABLE2 ó <-

· Estructuras de control: Cada autor utiliza sus propias convenciones del lenguaje, por lo que existen muchas y diversas. Las principales son:

o Secuencial: Instrucción 1, instrucción 2, …

o Selectiva: Si P Entonces … Sino … Fin Si

o Selección múltiple: Seleccionar P, Caso Valor1: … Caso Valor2: … En otro caso: … Fin Seleccionar

o Iterativa: Mientras P Hacer … Fin Mientras ó Hacer … Hasta P

4. Técnicas de Diseño de algoritmos

4.1. Recursividad

· Cuando un algoritmo se invoca a sí mismo o es invocado en otro algoritmo previamente llamado.

· 2 condiciones:

o Las sucesivas invocaciones deben ser efectuadas con versiones cada vez más reducidas del problema inicial

o Debe existir una condición de fin de las llamadas o fin de la recursividad.

· Ejemplos típicos de recursividad son la función Factorial de un número; el recorrido de un árbol; algoritmos “divide y vencerás” o backtracking.

4.2. Divide y Vencerás

· La técnica de diseño de algoritmos llamada “divide y vencerás” (divide and conquer) consiste en descomponer el problema original en varios sub-problemas más sencillos de forma recursiva, hasta que sean lo suficientemente sencillos como para resolverlos mediante un cálculo sencillo. Por último, se combinan los resultados de cada sub-problema para obtener la solución del problema original.

· El pseudocódigo sería:

funcion divide_y_venceras(problema)
{
   si el problema es trivial
      entonces resolver el problema;
   si no es trivial
   {
      descomponer el problema en n subproblemas más pequeños;
      para i=1 hasta n hacer
         divide_y_venceras(subproblema_k);
      combinar las n soluciones;
    }
}

· Un ejemplo de “divide y vencerás” es la ordenación rápida, o quicksort, utilizada para ordenar arrays. El ahorro de tiempo es grande: el tiempo necesario para ordenar un array de elementos mediante el método de la burbuja es cuadrático: O(N2) sin embargo, si dividimos el problema en subproblemas de forma recursiva hasta que la solución sea trivial, el tiempo disminuye hasta ser, en la mayoría de los casos, logarítmico O(NlogN)..

4.3. Backtraking (vuelta atrás)

· Son un tipo de algoritmos “Divide y Vencerás”, se utilizan para encontrar soluciones a un problema realizando una búsqueda sistemática, es decir, se prueban todas las opciones hasta encontrar la solución válida, o demostrar que no hay solución. Para conseguir este propósito, se separa la búsqueda en varias búsquedas parciales o subtareas. Asimismo, estas subtareas suelen incluir más subtareas, por lo que el tratamiento general de estos algoritmos es de naturaleza recursiva.

· Estos algoritmos se asemejan al recorrido en profundidad dentro de un grafo siendo cada subtarea un nodo del grafo. El caso es que el grafo no está definido de forma explícita, sino de forma implícita, es decir, que se irá creando según avance el recorrido.

· Ramificación y acotación: Es una variante del Backtracking mejorado sustancialmente. Se aplican restricciones de tal forma que se puedan “podar” algunas ramas para no recorrer ciertas subtareas, cuando se llegue a un punto en el que se demuestra que no es posible encontrar una solución válida o mejor que otra que ya se ha encontrado.

· Resuelve problemas clásicos como recorrer el tablero con los movimientos de un caballo, o situar 8 reinas en el tablero sin que se amenacen entre si, y se utiliza para resolver otros más actuales como los sudokus.

4.4. Algoritmos Voraces

· Funcionan en fases, en cada una de ellas se toma una decisión que parece buena, sin considerar las consecuencias futuras, por lo que no siempre se encontrará la solución óptima. Se basan en algún óptimo local (como dijkstra) esperando que también el global sea óptimo. Un ejemplo es el del camino más corto en un grafo.

5. Bibliografía

· Pressman, R.S.: Ingeniería del sofware. Un enfoque práctico. McGraw-Hill

· Alcalde, E y García, M.: Metodología de la programación. McGraw-Hill

· http://es.tldp.org Documentación libre en español de Linux/Unix

· http://www.tutorialparaprofesores.com Documentación de Microsoft para profesores.

· https://msdn.microsoft.com Centro de desarrollo de Microsoft

· http://algoritmia.com Web sobre el diseño de algoritmos –

Publicado: marzo 17, 2019 por Laura Gonzalez

Etiquetas: tema 23 informatica