Unidad: 2
Construcción a Estándares de Calidad
En el Diseño de Algoritmos y Construcción de Programas. Sin importar cualquiera que sea el tipo de software a ser desarrollado sea de sistemas (Son programas que sirven a otros programas en el trabajo de desarrollo como compiladores, editores, ..), tiempo real (Software encargado de analizar datos del mundo en forma real tales como análisis de datos, control automatizado, monitoreo de datos), gestión (a esta categoría se incluye el software comercial a nivel empresarial nóminas, inventarios), ingeniería y científico (es software que posee un amplio manejo numérico usado en biología, astronomía, CAD, …), empotrado (software que se encuentra residente en memoria, tales como : controles automáticos en los vehículos, sistemas de background, partes del sistema operativo, …), computación personal (software comercial de uso local como procesadores de texto, hojas electrónicas, navegadores web, calendarios, agendas, recetarios, …), inteligencia artificial (software de procesamiento especial sistemas expertos, sistemas basados en el conocimiento, generalmente no usan algoritmos numéricos). Todos los tipos de software mencionados requieren que los analistas, diseñadores y desarrolladores apliquen características y elementos de calidad para que se logren productos a las necesidades del usuario, estas necesidades se comienzan a encontrar un camino de solución a través de la aplicación de elementos de calidad, así se presentan dos de los más valiosos como son la eficiencia y la eficacia .
El uso eficiente y eficaz de la tecnología de los computadores es un objetivo que aún está distante. Para representar lo anterior, sólo basta señalar los reportes de fracasos y dificultades de muchos proyectos en los que se pretende involucrar a la tecnología de los computadores.
La ingeniería del software pretende utilizar los recursos computacionales de tal manera que se produzcan soluciones eficientes y eficaces a los problemas informáticos, el éxito de un proyecto...
Ejemplos de Algoritmos:
Podemos idear un algoritmo para un determinado proceso, así como también hacerlo en diferentes formas.
Por ejemplo: Cómo podríamos encontrar el promedio de un conjunto de números?
Una posible solución sería:
1.- Sumar los números dados.
2.- Contar dichos números.
3.- Dividir el resultado obtenido en el punto 1 entre el resultado obtenido en el punto 2.
Otra clase de ejemplo de Algoritmos, sería el de una llamada telefónica, o el proceso para efectuar un viaje en el Metro de Caracas, o la obtención de la licencia para conducir o el cambio de un caucho que esté bajo de aire, etc.; en fin, hay muchas formas de aplicar los algoritmos en cuestiones cotidianas descomponiendo la acción en pasos lógicos, como es el caso de una llamada desde una cabina de un teléfono público:
1.- Inicio
2.- Descolgar el teléfono
3.- Esperar la señal digital.
4.- Preguntamos si está dañado. Si lo está: Vamos al paso 5.
Si no lo está: Vamos al paso 8.
5.- Vociferar una palabra de mal gusto y fruncir el ceño.
6.- Colgar.
7.- Fin.
8.- Digitar los números.
9.- Verificamos si suena ocupado. Si suena ocupado: Vamos al paso 11.
Si no lo está: Vamos al paso 13.
10.-Insistir digitando los números.
11.- Ir al paso 8.
12.- Verificamos si contestan. Si contestan: Vamos al paso 14
Si no contestan: Vamos al paso 21.
13.- Preguntamos si se encuentra la persona.
Si se encuentra: Vamos al paso 14.
Si no se encuentra: Vamos al paso 17.
14.- Hablar lo deseado.
15.- Colgar.
16.- Fin.
17.- Pensar algo malo.
18.- Tomar un café y tranquilizarse.
19.- Ir al paso 15.
Forma de realizar un algoritmo
Los algoritmos pueden ser realizados de muchas formas o maneras, incluyendo al lenguaje natural, pseudocódigo, diagramas de flujo y lenguajes de programación entre otros. Las descripciones en lenguaje natural tienden a ser ambiguas y extensas. El usar pseudocódigo y diagramas de flujo evita muchas ambigüedades del lenguaje natural. Dichas expresiones son formas más estructuradas para representar algoritmos; no obstante, se mantienen independientes de un lenguaje de programación específico.
La descripción de un algoritmo usualmente se hace en tres niveles:
1. Descripción de alto nivel. Se establece el problema, se selecciona un modelo matemático y se explica el algoritmo de manera verbal, posiblemente con ilustraciones y omitiendo detalles.
2. Descripción formal. Se usa pseudocódigo para describir la secuencia de pasos que encuentran la solución.
3. Implementación. Se muestra el algoritmo expresado en un lenguaje de programación específico o algún objeto capaz de llevar a cabo instrucciones.
Diagrama de flujo
Los diagramas de flujo son descripciones gráficas de algoritmos; usan símbolos conectados con flechas para indicar la secuencia de instrucciones y están regidos por ISO.
Los diagramas de flujo son usados para representar algoritmos pequeños, ya que abarcan mucho espacio y su construcción es laboriosa. Por su facilidad de lectura son usados como introducción a los algoritmos, descripción de un lenguaje y descripción de procesos a personas ajenas a la computación.
El pseudocódigo está pensado para facilitar a las personas el entendimiento de un algoritmo, y por lo tanto puede omitir detalles irrelevantes que son necesarios en una implementación. Programadores diferentes suelen utilizar convenciones distintas, que pueden estar basadas en la sintaxis de lenguajes de programación concretos. Sin embargo, el pseudocódigo, en general, es comprensible sin necesidad de conocer o utilizar un entorno de programación específico, y es a la vez suficientemente estructurado para que su implementación se pueda hacer directamente a partir de él.
: Pseudocódigo
El pseudocódigo (falso lenguaje, el prefijo pseudo significa falso) es una descripción de alto nivel de un algoritmo que emplea una mezcla de lenguaje natural con algunas convenciones sintácticas propias de lenguajes de programación, como asignaciones, ciclos y condicionales, aunque no está regido por ningún estándar. Es utilizado para describir algoritmos en libros y publicaciones científicas, y como producto intermedio durante el desarrollo de un algoritmo, como los |diagramas de flujo, aunque presentan una ventaja importante sobre estos, y es que los algoritmos descritos en pseudocódigo requieren menos espacio para representar instrucciones complejas.
El pseudocódigo está pensado para facilitar a las personas el entendimiento de un algoritmo, y por lo tanto puede omitir detalles irrelevantes que son necesarios en una implementación. Programadores diferentes suelen utilizar convenciones distintas, que pueden estar basadas en la sintaxis de lenguajes de programación concretos. Sin embargo, el pseudocódigo, en general, es comprensible sin necesidad de conocer o utilizar un entorno de programación específico, y es a la vez suficientemente estructurado para que su implementación se pueda hacer directamente a partir de él.
Así el pseudodocódigo cumple con las funciones antes mencionadas para representar algo abstracto los protocolos son los lenguajes para la programación. Busque fuentes más precisas para tener mayor comprensión del tema.
Sistemas formales
La teoría de autómatas y la teoría de funciones recursivas proveen modelos matemáticos que formalizan el concepto de algoritmo. Los modelos más comunes son la máquina de Turing, máquina de registro y funciones μ-recursivas. Estos modelos son tan precisos como un lenguaje máquina, careciendo de expresiones coloquiales o ambigüedad, sin embargo se mantienen independientes de cualquier computadora y de cualquier implementación.
Implementación
Muchos algoritmos son ideados para implementarse en un programa. Sin embargo, los algoritmos pueden ser implementados en otros medios, como una red neuronal, un circuito eléctrico o un aparato mecánico y eléctrico. Algunos algoritmos inclusive se diseñan especialmente para implementarse usando lápiz y papel. El algoritmo de multiplicación tradicional, el algoritmo de Euclides, la criba de Eratóstenes y muchas formas de resolver la raíz cuadrada son sólo algunos ejemplos.
Variables
Son elementos que toman valores específicos de un tipo de datos concreto. La declaración de una variable puede realizarse comenzando con var. Principalmente, existen dos maneras de otorgar valores iniciales a variables:
1. Mediante una sentencia de asignación.
2. Mediante un procedimiento de entrada de datos (por ejemplo: 'read').
Ejemplo:
...
i:=1;
read(n);
while i < n do begin
(* cuerpo del bucle *)
i := i + 1
end;
...
Estructuras secuenciales
La estructura secuencial es aquella en la que una acción sigue a otra en secuencia. Las operaciones se suceden de tal modo que la salida de una es la entrada de la siguiente y así sucesivamente hasta el fin del proceso. La asignación de esto consiste, en el paso de valores o resultados a una zona de la memoria. Dicha zona será reconocida con el nombre de la variable que recibe el valor. La asignación se puede clasificar de la siguiente forma:
1. Simples: Consiste en pasar un valor constante a una variable (a ← 15)
2. Contador: Consiste en usarla como un verificador del número de veces que se realiza un proceso (a ← a + 1)
3. Acumulador: Consiste en usarla como un sumador en un proceso (a ← a + b)
4. De trabajo: Donde puede recibir el resultado de una operación matemática que involucre muchas variables (a ← c + b*2/4).
Un ejemplo de estructura secuencial, como obtener la área de un triángulo:
Inicio
...
float b, h, a;
printf("Diga la base");
scanf("%f", &b);
printf("Diga la altura");
scanf("%f", &h);
a = (b*h)/2;
printf("El área del triángulo es %f", a)
Fin
Forma y Técnica de documentación de algoritmos y programa
Diseño de Algoritmos:
Hasta ahora se han realizado algunos comentarios respecto a la necesidad de diseñar algoritmos correctos y eficientes utilizando los elementos de un lenguaje de programación .Es necesario en este momento mencionar algo sobre como hacerlo. El acto de diseñar un algoritmo puede considerarse como una tarea que difícilmente podrá ser del todo automatizada.
Todo problema algorítmico es un reto para su diseñador, algunos resultan inmediatos de resolver, otros son bastante complejos. La investigación en esta área ha permitido descubrir un conjunto de métodos o esquemas de diseño hacia los cuales puede orientarse la realización de muchos algoritmos.
No obstante, y a pesar de que resulta mas adecuado en bastantes casos utilizar alguno de estos esquemas que realizar un diseño desde cero, idear un algoritmo continua siendo una labor bastante creativa donde los conocimientos y la experiencia del propio diseñador tiene un papel fundamental.
El diseño de un algoritmo que resuelva un problema es, en general, una tarea difícil. Una forma de facilitar esta labor consiste en recurrir a técnicas conocidas de diseño de algoritmos, se decir, a esquemas muy generales que pueden adaptarse a un problema particular al detallar las partes generales del esquema.
Muchos problemas pueden resolverse buscando una solución fácil y directa pero, a la vez bastante ineficiente. Este método, llamado de fuerza bruta, puede ser muy directo, pero con un poco de análisis puede encontrarse algoritmos más eficientes. El esquema mas sencillo quizás sea el llamado divide y vencerás, basado en la descomposición de un problema en sus problemas. Otros esquemas requieren un análisis minucioso del problema de forma que la solución se vaya construyendo en etapas. Si puede preverse que decisión conviene en cada etapa para producir cierto tipo de mejor resultado, tenemos una solución voraz, si la decisión en una etapa, solo puede tomarse tras considerar varias soluciones de otras etapas más simples, la solución es dinámica. Aun así, hay problemas cuya solución no puede hallarse sino mediante un proceso de búsqueda, a pesar de lo complejas que son las operaciones de búsqueda, su uso adecuado mediante el esquema de búsqueda con retroceso (o backtracking) permite ganar gran eficiencia respecto a soluciones de fuerza bruta. Por último, conviene conocer otros métodos de diseño de algoritmos que también resultan de utilidad práctica.
Nos estamos refiriendo a métodos basados en la mejora de la eficiencia (por ejemplo, el uso de parámetros de acumulación al resolver problemas utilizando divide y vencerás, y el empleo de tablas como estructura auxiliar para la resolución eficiente de problemas donde se aplica programación dinámica), y a métodos basados en transformaciones del dominio para encontrar una solución más fácilmente a un problema en un dominio transformado, siendo dicha solución finalmente adaptada al dominio original.
Consideraciones generales
Si el hábil programador dispone de un recetario de algoritmos de donde poder seleccionar el más adecuado para cada problema, su tarea se simplifica.
Supongamos que disponemos de una especificación precisa, completa y consistente del problema a resolver y queremos obtener un algoritmo en el que, dados uno datos de entrada valido, se produzca cierto resultado. Si no nos importa la eficiencia del algoritmo, podríamos utilizar un algoritmo general llamado algoritmo del museo británico. Se programa un computador de manera que parta de un conjunto de axioma matemáticos y los que use para reducir aleatoriamente teoremas válidos.
Aprender los principios básicos del diseño de algoritmos podemos preguntarnos por un método aceptable. El mas entendido, y quizás el mejor, es organizar el diseño sobre un esquema de algoritmo o una técnica de diseño que haya demostrado su utilidad para otros problemas. Este método de trabajo es practicable, puesto que existe un número reducido de esquema y técnicas de diseño.
El conocimiento de técnicas de diseño es solo un primer paso para el diseñador, que debe completarse con otros
conocimientos y, sobre todo, con la experiencia.
Método de fuerza bruta
Comenzamos el estudio de esquemas algorítmicos con un método sencillo, pero que debe evitarse siempre que se pueda, dad su ineficacia; la fuerza bruta. En realidad, no es un esquema algorítmico, si no mas bien calificativo
Para una forma de diseñar algoritmos: tomar una solución directa, poco reflexionada. En principio, esto no es malo, pero dado que no se ha analizado apenas el problema, es muy probable que no se hayan aprovechado propiedades deducibles del problema y que la solución sea terriblemente ineficiente.
Una solución por fuerza bruta también puede resultar adecuada como primera aproximación a la solución final, porque su desarrollo puede permitir profundizar más sobre el problema y conocer propiedades que sean utilizadas para obtener otra versión más eficiente.
Por ejemplos:
Algunos algoritmos de búsqueda de un elemento en un vector. Uno de ellos realizaba una búsqueda secuencial con complejidad lineal sobre el tamaño del vector y podía usarse con cualquier vector. Otro algoritmo realizaba una búsqueda dicotómica o binaria, con complejidad logarítmica, y solo se podía usar cuando el vector estuviese ordenado. El algoritmo primero responde a un razonamiento más sencillo, por lo que uno puede sentirse tentado a usar siempre. Esta es la solución de fuerza bruta: una solución directa, pero poco reflexionada. Lo más razonable es comprobar si el vector esta ordenado y, en caso positivo, aprovechar esta circunstancia para usar el algoritmo más eficiente: el de búsqueda binaria.
Técnicas de los Parámetros Acumuladores y de Tabulación
La recursión es un mecanismo que permite obtener, en combinación con otras construcciones, una solución funcional a muchos problemas. Muchos algoritmos recursivos resultan eficientes, pero no todos: hay algunos fácilmente formularles, pero muy ineficientes. En estos casos, dichos algoritmos pueden servir como una primera aproximación al algoritmo definitivo, pero debe mejorar su rendimiento para que sea práctico.
Veremos dos parámetros para la mejora de eficiencia de algoritmos recursivos: el uso de parámetros acumuladores y el uso de tablas. Cada una se ilustra con un ejemplo distinto.
Parámetros Acumuladores
Veamos primero una solución ineficiente que intentaremos mejorar.
Ejemplo: Números de Fibonacci
Los números de Fibonacci suele especificarse como:
Fin(0)=1
Fib(1)1
Fib(n+2)=fib(n)+fib(n+1)
Esta especificación de los números de fibonacci tienen una formulación recursiva inmediata en estilo funcional.
Un modo de evitar problema lo proporciona la técnica de los parámetros acumuladores, cuya idea básica se expone a continuación. La función principal usa una función auxiliar que tiene los parámetros de aquellas más algunos adicionales. La función principal simplemente realiza una llamada a esta función auxiliar en los que los parámetros de aquellas se modifican y los parámetros nuevos toman un valor inicial adecuado .
Los parámetros adicionales tienen como misión ir acumulando resultados principales durante el proceso recursivo.
Tabulación
No todos los algoritmos recursivos ineficientes pueden optimizarse con la técnica de los parámetros acumuladores.
Otra técnica útil es el uso de tablas.
La intención es que la primera vez que se realiza un cálculo, se almacena en una tabla, donde puede consultarse otras veces que se necesite. Esta técnica también se suele emplear con la programación dinámica.
Ejemplo:
Sea el problema de la competición. Hay dos participantes (deportistas o equipos, no importa que), A,B, que juegan una competición que es ganada por el primero que venza en n partidos, siendo ( n ) mayor que( 0 ).
Por sencillez, se supone que ambos participantes tienen cualidades y preparación similar. De forma que cada uno tiene un 50% de posibilidades de ganar cada partido. De todas formas, la modificación para incorporar probabilidades diferentes es evidente y no complica el problema.
Divide y vencerás:
Consiste en descomponer un problema en un su problema, resolver independientemente los su problemas para luego combinar sus soluciones y obtener la solución del problema original. Esta técnica se puede aplicar con éxito a problemas como la multiplicación de matrices, la ordenación de vectores, la búsqueda en estructuras ordenadas, etc.
