Diseño y análisis de los algoritmos

Design and Analysis of Algorithms

1. Hay muchos pasos implicados en la escritura de un programa de computadora para resolver un problema dado. Los pasos van desde la formulación del problema y la especificación, diseño de la solución, implementación, prueba y documentación y finalmente a la evaluación de la solución. Este capítulo describe nuestro enfoque para estos pasos. Los capítulos siguientes discuten los algoritmos y estructuras de datos que son los pilares de la mayoría de programas de ordenador.

La mitad de la batalla es saber qué problema resolver. Cuando se aborda inicialmente, la mayoría de los problemas no tienen una especificación simple y precisa. De hecho, ciertos problemas, como crear una receta "gourmet" o preservar la paz mundial, pueden ser imposibles de formular en términos que admitan una solución informática. Incluso si sospechamos que nuestro problema se puede resolver en una computadora, generalmente hay una considerable latitud en varios parámetros del problema. A menudo es solo por experimentación que se pueden encontrar valores razonables para estos parámetros.

Si ciertos aspectos de un problema pueden expresarse en términos de un modelo formal, generalmente es beneficioso hacerlo, ya que una vez que se formaliza un problema, podemos buscar soluciones en términos de un modelo preciso y determinar si ya existe un programa para resolverlo. resuelve ese problema

Incluso si no hay un programa existente, al menos podemos descubrir qué se sabe sobre este modelo y usar las propiedades del modelo para ayudar a construir una buena solución.

Casi cualquier rama de las matemáticas o la ciencia puede ser llamado en servicio para ayudar a modelo cierto dominio del problema. Problemas esencialmente numéricas en la naturaleza se pueden modelar por tales común conceptos matemáticos como ecuaciones lineares simultáneas (por ejemplo, encontrar las corrientes en circuitos eléctricos, o encontrar tensiones en marcos de vigas conectadas) o ecuaciones diferenciales (p. ej. predicción de crecimiento de la población o la tasa a la que va a reaccionar productos químicos). Símbolo y problemas de procesamiento de texto pueden ser modelados por cadenas de caracteres y gramáticas formales. Problemas de esta naturaleza incluyen compilación (traducción de programas escritos en un lenguaje de programación en lenguaje máquina) y las tareas de recuperación de información como reconocimiento de palabras en las listas de títulos de propiedad de una biblioteca.

Algorithms

Una vez que tenemos un modelo matemático adecuado para nuestro problema, podemos intentar encontrar una solución en términos de ese modelo. Nuestro objetivo inicial es encontrar una solución en la forma de un algoritmo, que es una secuencia finita de instrucciones, cada una de ellas tiene un significado claro y puede realizarse con una cantidad finita de esfuerzo en un periodo finito de tiempo. Una instrucción de asignación de número entero como x: = y + z es un ejemplo de una instrucción que puede ejecutar

en una cantidad finita de esfuerzo. En un algoritmo, las instrucciones se pueden ejecutar cualquier número de veces, siempre que las instrucciones mismas indiquen la repetición. Sin embargo, requerimos que, sin importar cuáles sean los valores de entrada, un algoritmo termine después de ejecutar un número finito de instrucciones. Por lo tanto, un programa es un algoritmo siempre y cuando nunca entre en un bucle infinito en ninguna entrada.

Hay un aspecto de esta definición de un algoritmo que necesita alguna aclaración. Dijimos que cada instrucción de un algoritmo debe tener un "significado claro" y debe ser ejecutable con una "cantidad de esfuerzo finita". Ahora, lo que está claro para una persona puede no serlo para otra, y a menudo es difícil demostrar rigurosamente que una instrucción se puede llevar a cabo en un tiempo determinado. A menudo también es difícil probar que en cualquier entrada, una secuencia de instrucciones termina, incluso si entendemos claramente lo que significa cada instrucción. Sin embargo, por argumento y contraargumento, generalmente se puede llegar a un acuerdo sobre si una secuencia de instrucciones constituye un algoritmo. La carga de la prueba recae en la persona que afirma tener un algoritmo. En la Sección 1.5 discutimos cómo estimar el tiempo de ejecución de las construcciones de lenguajes de programación comunes que se puede mostrar que requieren una cantidad de tiempo finita para su ejecución.

Además de usar los programas de Pascal como algoritmos, a menudo presentamos algoritmos que utilizan un pseudo-lenguaje que es una combinación de las construcciones de un lenguaje de programación junto con declaraciones informales en inglés. Usaremos Pascal como lenguaje de programación, pero casi cualquier lenguaje de programación común podría usarse en lugar de Pascal para los algoritmos que discutiremos. El siguiente ejemplo ilustra muchos de los pasos en nuestro enfoque para escribir un programa de computadora.

Ejemplo 1.1. Se puede usar un modelo matemático para ayudar a diseñar un semáforo para una intersección complicada de carreteras. Para construir el patrón de luces, crearemos un programa que tome como entrada un conjunto de giros permitidos en una intersección (continuar recto en una carretera es un "giro") y se divide en la menor cantidad de grupos posible, de manera que todos los giros en un grupo se permiten simultáneamente sin colisiones. Luego, asociaremos una fase del semáforo con cada grupo en la partición. Al encontrar una partición con el menor número de grupos, podemos construir un semáforo con el menor número de fases.

Por ejemplo, la intersección que se muestra en la Fig. 1.1 ocurre en un pozo de agua llamado JoJo's cerca de la Universidad de Princeton, y se sabe que causa algunas dificultades de navegación, especialmente en el viaje de regreso. Las carreteras C y E están en camino, las otras dos. Hay 13 giros que uno podría hacer en esta intersección. Algunos pares de giros, como AB (de A a B) y EC, se pueden realizar simultáneamente, mientras que otros, como AD y EB, hacen que las líneas de tráfico se crucen y, por lo tanto, no se pueden realizar simultáneamente. La luz en la intersección debe permitir giros en un orden tal que nunca se permitan AD y EB al mismo tiempo, mientras que la luz podría permitir que AB y EC se realicen simultáneamente.

[pic 2]

Fig. 1.1. An intersection.

Podemos modelar este problema con una estructura matemática conocida como gráfico. Un gráfico consiste en un conjunto de puntos llamados vértices y líneas que conectan los puntos, llamados bordes. Para el problema de la intersección del tráfico, podemos dibujar un gráfico cuyos vértices representan giros y cuyos bordes conectan pares de vértices cuyos giros no se pueden realizar simultáneamente.

Para la intersección de la Fig. 1.1, este gráfico se muestra en la Fig. 1.2, y en la Fig. 1.3 vemos otra representación de este gráfico como una tabla con un 1 en la fila i y la columna j cuando hay un borde entre los vértices i y j.

...