Estructuras de control

ALGORITMICA III

Algorítmica III

Análisis de Estructuras de Control
Introducción
CARRERA DE

INGENIERÍA DE SISTEMAS

ALGORITMICA III

Contenido
● ● ● ●

Introducción.Principio de Invariancia. Operación Elemental. Introducción al Análisis de Eficiencia.
– – – –

Estructuras Secuenciales. Estructuras Condicionales Si. Estructuras Para ó Desde. EstructurasMientras y Repetir.

CARRERA DE

INGENIERÍA DE SISTEMAS

ALGORITMICA III

Contenido
● ●

Estructuras complejas. Conclusiones.

CARRERA DE

INGENIERÍA DE SISTEMAS

ALGORITMICAIII

Introducción
●

Existen problemas que no se conoce ningún algoritmo eficiente. El viajante de comercio, – El coloreado óptimo de grafos, – El problema de la mochila, – Los cicloshamiltoneanos, – La programación entera, – La búsqueda del camino más simple más largo de un grafo. Algoritmo que resuelva cualquiera problema anterior proporciona un algoritmo eficiente paratodas las instancias.
–

●

CARRERA DE

INGENIERÍA DE SISTEMAS

ALGORITMICA III

Introducción
●

Es sencillo verificar la validez de una supuesta solución que encontrar unasolución partiendo de cero. Un algoritmo es más eficiente si es mejor que un algoritmo evidente ó se trata del mejor algoritmo posible para resolver nuestro problema.
–

●

Un algoritmo detiempo polinomial puede no ser práctico si se considera la constante multiplicativa oculta es demasiado grande.
●

Mientras que un algoritmo que requiera un tiempo exponencial en el peorcaso puede resultar sumamente rápido en la mayoría de los casos.

CARRERA DE

INGENIERÍA DE SISTEMAS

ALGORITMICA III

Principio de la Invariancia
●

Dos implementaciones distintasde un mismo algoritmo no diferirán en su eficiencia en más de una constante multiplicativa.
–

Sean t1(n) y t2(n) tiempos de implementación del algoritmo M, c y d constantes; entonces t1(n)