Analisis de algoritmos
Páginas: 6 (1378 palabras)
Publicado: 24 de marzo de 2010
18-03-2010
Análisis de Algoritmos
Unidad I Eficiencia de Algoritmos
Objetivos y Alcances
• Ser capaz de analizar, comprender y resolver una amplia variedad de problemas de programación, diseñando soluciones eficientes y de calidad. – Conocer el concepto de Algorítmica elemental: nociones de problema, instancia, operación básica. – Proveer al alumno de las técnicas algorítmicas básicas quele permitirán abordar el desarrollo de programas correctos y eficientes para resolver problemas no triviales. Las técnicas básicas mencionadas incluyen conocimientos teóricos y prácticos, habilidades, experiencias y sentido crítico, todas ellas fundamentadas en teorías y técnicas sólidas, comprobadas y bien establecidas.
1
18-03-2010
Justificación
• El Desarrollo de programas deaplicación en los ambientes tecnológicos, requiere que los elementos de software sean más seguros y eficientes a medida que el uso del computador invade áreas de mayor complejidad. Esto hace que los programadores requieran, cada vez más, conocimientos formales sobre el diseño de datos, y el análisis de correctitud y eficiencia de algoritmos.
•
Introducción
• En el curso de Análisis de Algoritmosse tratará de responder dos preguntas: – ¿Cuáles son las propiedades de un algoritmo dado? – ¿Qué propiedades debe tener cualquier algoritmo que resuelve un algoritmo dado?
Problema
INPUT
- Representación de datos - Tamaño del problema
Algoritmo
Propiedades -Número de operaciones -Memoria -Correctitud
OUTPUT
- Solución Algorítmica
2
18-03-2010
Problemas y Soluciones
• • •Etimológicamente, la palabra problema se deriva del griego proballein y significa “algo lanzado hacia delante”. Un problema es un asunto o conjunto de cuestiones que se plantean para ser resueltas. La naturaleza de los problemas varía con el ámbito o con el contexto donde estén planteados (ejemplo, matemáticos, químicos, filosóficos, etc.). En general, conviene expresar un problema utilizando algúnmodelo formal (por ejemplo, modelo aritmético o con grafos). Para la mayoría de los problemas puede haber muchas soluciones (maneras de resolverlos).
• •
¿Por qué analizar algoritmos?
• Evitar probar y ver que sucede (medir tiempo de ejecución) – Problemas: • Las pruebas podrían no ser representativas de todas las entradas. • Las pruebas no nos dicen si hay otras soluciones. INICIO –Ventajas: • Sirve para predecir si el algoritmo es utilizable. A (análisis independiente de la máquina) • Permite compararlo con otros algoritmos. ((A%2)==0) • Ayuda a entender mejor el algoritmo. – Efectos: A es par A es impar • Hacer mejoras en la eficiencia. • Ayuda en la correctitud. FIN • Permite definir nuevas estructuras de datos
3
18-03-2010
Estructuras de Datos y Algoritmos
•Problema: – Conjunto de hechos o circunstancias que dificultan la consecución de algún fin. Algoritmo: – Conjunto de reglas o instrucciones paso a paso para resolver un problema. Programa: – Implementación de un algoritmo en algún lenguaje de programación. Estructura de Datos: – Organización de los datos necesaria para resolver un problema.
•
•
•
Algoritmos + Estructura de Datos = ProgramasNiklaus Wirth
Visión General
Metas Estructuras y Diseño de Algoritmos
Correctitud Adaptabilidad
Metas de Implementación
Robustez
Eficiencia Reusabilidad
4
18-03-2010
Visión General
• Este curso no es sobre: – Lenguaje de programación. – Arquitectura de Computadores. – Arquitectura de Software. – Diseño de Software y principios de implementación. Sólo se tratará sobre teoríade complejidad y eficiencia de algoritmos.
•
Reseña Histórica
• Término Algoritmo: Matemático persa Mohammned al-Khowarizmi, en Latín Algorismus. Primer algoritmo: Algoritmo de Euclides, greatest common divisor, 400-300 D.C. Siglo 19 – Charles Baddage, Ada Byron. Siglo 20 – Alan Turing, Alonzo Church, John Von Neumann. Siglo 21 – Claude Shannon, Noam Chomsky, Edsger Wyde Dijkstra,...
Análisis de Algoritmos
Unidad I Eficiencia de Algoritmos
Objetivos y Alcances
• Ser capaz de analizar, comprender y resolver una amplia variedad de problemas de programación, diseñando soluciones eficientes y de calidad. – Conocer el concepto de Algorítmica elemental: nociones de problema, instancia, operación básica. – Proveer al alumno de las técnicas algorítmicas básicas quele permitirán abordar el desarrollo de programas correctos y eficientes para resolver problemas no triviales. Las técnicas básicas mencionadas incluyen conocimientos teóricos y prácticos, habilidades, experiencias y sentido crítico, todas ellas fundamentadas en teorías y técnicas sólidas, comprobadas y bien establecidas.
1
18-03-2010
Justificación
• El Desarrollo de programas deaplicación en los ambientes tecnológicos, requiere que los elementos de software sean más seguros y eficientes a medida que el uso del computador invade áreas de mayor complejidad. Esto hace que los programadores requieran, cada vez más, conocimientos formales sobre el diseño de datos, y el análisis de correctitud y eficiencia de algoritmos.
•
Introducción
• En el curso de Análisis de Algoritmosse tratará de responder dos preguntas: – ¿Cuáles son las propiedades de un algoritmo dado? – ¿Qué propiedades debe tener cualquier algoritmo que resuelve un algoritmo dado?
Problema
INPUT
- Representación de datos - Tamaño del problema
Algoritmo
Propiedades -Número de operaciones -Memoria -Correctitud
OUTPUT
- Solución Algorítmica
2
18-03-2010
Problemas y Soluciones
• • •Etimológicamente, la palabra problema se deriva del griego proballein y significa “algo lanzado hacia delante”. Un problema es un asunto o conjunto de cuestiones que se plantean para ser resueltas. La naturaleza de los problemas varía con el ámbito o con el contexto donde estén planteados (ejemplo, matemáticos, químicos, filosóficos, etc.). En general, conviene expresar un problema utilizando algúnmodelo formal (por ejemplo, modelo aritmético o con grafos). Para la mayoría de los problemas puede haber muchas soluciones (maneras de resolverlos).
• •
¿Por qué analizar algoritmos?
• Evitar probar y ver que sucede (medir tiempo de ejecución) – Problemas: • Las pruebas podrían no ser representativas de todas las entradas. • Las pruebas no nos dicen si hay otras soluciones. INICIO –Ventajas: • Sirve para predecir si el algoritmo es utilizable. A (análisis independiente de la máquina) • Permite compararlo con otros algoritmos. ((A%2)==0) • Ayuda a entender mejor el algoritmo. – Efectos: A es par A es impar • Hacer mejoras en la eficiencia. • Ayuda en la correctitud. FIN • Permite definir nuevas estructuras de datos
3
18-03-2010
Estructuras de Datos y Algoritmos
•Problema: – Conjunto de hechos o circunstancias que dificultan la consecución de algún fin. Algoritmo: – Conjunto de reglas o instrucciones paso a paso para resolver un problema. Programa: – Implementación de un algoritmo en algún lenguaje de programación. Estructura de Datos: – Organización de los datos necesaria para resolver un problema.
•
•
•
Algoritmos + Estructura de Datos = ProgramasNiklaus Wirth
Visión General
Metas Estructuras y Diseño de Algoritmos
Correctitud Adaptabilidad
Metas de Implementación
Robustez
Eficiencia Reusabilidad
4
18-03-2010
Visión General
• Este curso no es sobre: – Lenguaje de programación. – Arquitectura de Computadores. – Arquitectura de Software. – Diseño de Software y principios de implementación. Sólo se tratará sobre teoríade complejidad y eficiencia de algoritmos.
•
Reseña Histórica
• Término Algoritmo: Matemático persa Mohammned al-Khowarizmi, en Latín Algorismus. Primer algoritmo: Algoritmo de Euclides, greatest common divisor, 400-300 D.C. Siglo 19 – Charles Baddage, Ada Byron. Siglo 20 – Alan Turing, Alonzo Church, John Von Neumann. Siglo 21 – Claude Shannon, Noam Chomsky, Edsger Wyde Dijkstra,...
Leer documento completo
Regístrate para leer el documento completo.