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.

El gráfico puede ayudarnos a resolver el problema de diseño del semáforo. La coloración de un gráfico es una asignación de un color a cada vértice del gráfico, de modo que no haya dos vértices conectados por un borde que tengan el mismo color. No es difícil ver que nuestro problema consiste en colorear la gráfica de giros incompatibles utilizando la menor cantidad de colores posible.

El problema de los gráficos para colorear se ha estudiado durante muchas décadas, y la teoría de los algoritmos nos dice mucho sobre este problema. Desafortunadamente, colorear un gráfico arbitrario con la menor cantidad de colores posible es uno de una gran clase de problemas llamados "problemas NP-completos", para los cuales todas las soluciones conocidas son esencialmente del tipo "pruebe todas las posibilidades". En el caso del problema de la coloración, "intente todas las posibilidades" significa probar todas las asignaciones de colores a vértices usando primero un color, luego dos colores, luego tres, y así sucesivamente, hasta que se encuentre una coloración legal. Con cuidado, podemos ser un poco más rápidos que esto, pero en general se cree que ningún algoritmo para resolver este problema puede ser sustancialmente más eficiente que este enfoque más obvio.

Ahora nos enfrentamos a la posibilidad de que encontrar una solución óptima para el problema en cuestión es computacionalmente muy costoso. Podemos adoptar

[pic 3]

Fig. 1.2. Graph showing incompatible turns.

[pic 4]

Fig. 1.3. Table of incompatible turns.

Uno de los tres enfoques. Si el gráfico es pequeño, podríamos intentar encontrar una solución óptima de manera exhaustiva, probando todas las posibilidades. Sin embargo, este enfoque se vuelve prohibitivamente costoso para los gráficos grandes, sin importar qué tan eficiente sea el intento del programa. Un segundo enfoque sería buscar información adicional sobre el problema en cuestión. Puede resultar que el gráfico tenga algunas propiedades especiales, lo que hace innecesario intentar todas las posibilidades para encontrar una solución óptima. El tercer enfoque es cambiar un poco el problema y buscar una solución buena pero no necesariamente óptima. Es posible que estemos contentos con una solución que se acerque al número mínimo de colores en los gráficos pequeños y que funcione rápidamente, ya que la mayoría de las intersecciones no son tan complejas como la Fig. 1.1. Un algoritmo que produce rápidamente soluciones buenas pero no necesariamente óptimas se denomina heurístico.

...