Algoritmo

Ejemplos de algoritmos relevantes
Ricardo Peña Marí
Departamento de Sistemas Informáticos y Computación Universidad Complutense de Madrid

Master en formación de profesorado de Secundaria – Informática curso 2009-2010

R. Peña (SIC-UCM)

Ejemplos de algoritmos

Master Secundaria 09-10

1 / 13

Lecturas recomendadas

• “De Euclides a Java: Historia de los algoritmos y de loslenguajes de programación”. Ricardo Peña. Cap. 5. Ed. Nivola (Colección Ciencia Abierta), 2006. • “Computer Algorithms”. E. Horowitz, S. Sahni, S. Rajasekaram. Computer Science Press 1998. • “Introduction to Algorithms”. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Partes I, II, IV, VI y VII. MIT Press 2001.

R. Peña (SIC-UCM)

Ejemplos de algoritmos

Master Secundaria 09-10

2 / 13La programación lineal
• Suponga que es usted el director de la cocina de un cuartel y que tiene que planificar la dieta de los soldados, sujeta a las siguientes restricciones.
1

2

3

Ha de conseguir al menos un cierto número C de calorías diarias suficiente para que los soldados soporten el entrenamiento. Ha de alcanzar un mínimo P de proteínas y V de vitaminas que cubran susnecesidades diarias. Ha de obtener el menor coste posible para el ejército.

• Puede confeccionar la dieta eligiendo entre n alimentos. Son conocidas las cantidades p1 , . . . , pn de proteínas, v1 , . . . , vn de vitaminas y c1 , . . . , cn de calorías contenidas en un gramo de cada alimento, así como sus precios e1 , . . . , en , en euros por gramo. Su problema se puede expresar así: minimizar e1 x1 +· · · + en xn sujeto a p1 x1 + · · · + pn xn ≥ P v1 x1 + · · · + vn xn ≥ V c1 x1 + · · · + cn xn ≥ C x1 ≥ 0, . . . , xn ≥ 0
R. Peña (SIC-UCM) Ejemplos de algoritmos Master Secundaria 09-10 3 / 13

La programación lineal (2)
• Este problema se le planteó al matemático George Dantzig (1914-2005) cuando, en 1946, aceptó un empleo como consultor del departamento de planificación de las FuerzasAéreas de Estados Unidos. • Su aportación a resolver este problema, y muchos otros expresables en términos semejantes, fue el algoritmo llamado método del simplex (1947). • Resolver un conjunto de inecuaciones lineales sujetas a maximizar o minimizar una función objetivo, también lineal, se conoce como un problema de programación lineal. • En términos geométricos, un simplex es un poliedro convexo enun espacio n-dimensional. Si n = 2, hablamos de un polígono convexo en el plano. • El conjunto de inecuaciones determinan un simplex llamado región factible. • La ecuación e1 x1 + · · · + en xn = K , formada a partir de la función objetivo, determina un hiperplano para cada valor de K . El mayor valor de K (o el menor, si se trata de un problema de minimización) se alcanza en el vértice delpoliedro más alejado en la dirección en que crece (o decrece) K .
R. Peña (SIC-UCM) Ejemplos de algoritmos Master Secundaria 09-10 4 / 13

La programación lineal (y 3)
• El método del simplex comienza con cualquier punto factible y luego se desplaza a lo largo de las aristas del poliedro buscando que crezca la función objetivo. Cuando esta no puede crecer más, se ha alcanzado el valor óptimo. • Elcoste asintótico del método del simplex es exponencial en el caso peor. • No obstante ese coste se manifiesta solo en casos patológicos. La mayor parte de los problemas se resuelven con costes polinomiales. • En 1979, el matemático soviético L. Khachiyan diseñó otro algoritmo cuyo caso peor era polinomial (O(n4 L), para n variables y números con L dígitos). Sin embargo, el método del simplex en lapráctica era más eficiente. • Hubo que esperar hasta 1984 para encontrar un algoritmo polinomial O(n3,5 L) que en la práctica compitiera con el de Dantzig. Se llama método proyectivo y se debe a N. Karmarcar. A diferencia del de Dantzig, no recorre las aristas del poliedro sino sus puntos interiores. • Una variante de la programación lineal consiste en exigir que las incógnitas tengan valores...