Sesión 6

INICIAR

Lic. Ingeniería en Sistemas y Tecnologías de la InformaciónSesión 6

Fundamentos de programación

Fundamentos de programación. SESIÓN 6

Bienvenidos a la sesión 6 de nuestra materia Fundamentos de programación.

Para comprender con más detalle los conceptos generales de (FUNDAMENTOS DE PROGRAMACIÓN) es necesario revisar los siguientes temas:6. Algoritmos y resolución de problemas 6.1 Definición de algoritmo6.2 Estrategias de resolución de problemas: división y conquista, fuerza bruta, algoritmos voraces, programación dinámica6.3 Estrategias de diseño algorítmico: fuerza bruta, divide y vencerás, programación dinámica6.4 Análisis de la complejidad de algoritmos

Fundamentos de programación. SESIÓN 6

2

Fundamentos de programación. SESIÓN 6

Es una secuencia de pasos finitos, claros y definidos que se siguen para resolver un problema o realizar una tarea. En programación, los algoritmos son esenciales para desarrollar soluciones eficientes y efectivas.

Algoritmos y Resolución de Problemas

Características

Algoritmos

1

Claridad

Los pasos deben estar claramente definidos y ser comprensibles.

Eficiencia

El algoritmo debe utilizar los recursos (tiempo y memoria) de manera óptima.

3

Finitud

Debe terminar después de un número finito de pasos.

4

Entrada

Debe aceptar entradas bien definidas.

5

Salida

Debe producir una salida o resultado claro.

Fundamentos de programación. SESIÓN 6

1

2

3

4

5

6

Definir el Problema

Evaluación y Optimización

Prueba y Depuración

Implementación del Algoritmo

Especificación del Algoritmo

Planificación del Algoritmo

Estrategias de resolución de problemas: división y conquista, fuerza bruta, algoritmos voraces, programación dinámica

Fundamentos de programación. SESIÓN 6

+

Fundamentos de programación. SESIÓN 6

+

En la programación, existen varias estrategias para resolver problemas de manera eficiente. A continuación, se describen cuatro de las estrategias más comunes:

Estrategias de Resolución de Problemas en Fundamentos de la Programación

+

+

Algoritmos Voraces

Fuerza Bruta

División y Conquista

Programación Dinámica

Fundamentos de programación. SESIÓN 6

Análisis de la complejidad de algoritmos

El análisis de la complejidad de algoritmos es una técnica fundamental para evaluar la eficiencia de un algoritmo en términos de tiempo de ejecución y uso de recursos, como la memoria. Su propósito es determinar cuántos recursos consumirá un algoritmo a medida que crecen los datos de entrada. Para realizar este análisis, se utilizan notaciones como la O-Notación o "Big O", que describe el peor caso de un algoritmo, es decir, la cantidad máxima de operaciones necesarias en función del tamaño de los datos. Este análisis permite predecir el comportamiento del algoritmo bajo diferentes circunstancias y ayuda a los programadores a elegir la solución más eficiente para un problema dado.El análisis de la complejidad se enfoca en dos aspectos principales: complejidad temporal, que mide cuánto tiempo tomará ejecutar un algoritmo, y complejidad espacial, que mide cuánta memoria adicional se requiere. Por ejemplo, algunos algoritmos pueden tener una complejidad temporal de O(n), lo que significa que el tiempo de ejecución crecerá linealmente con el tamaño de los datos, mientras que otros pueden tener una complejidad de O(n²), lo que indica que el tiempo de ejecución crecerá exponencialmente. Este análisis es crucial para optimizar programas, especialmente en aplicaciones que manejan grandes cantidades de datos o en sistemas donde el rendimiento es una prioridad.

Recursos bibliográficos

• Gabelas-Barroso, J. A. (Coord.), García-Marín, D. (Coord.) & Aparici, R. (Coord.). (2023). La invasión del algoritmo: (1 ed.). Editorial Gedisa.

Consulta el tema 1 La invasión del algoritmo. Página 13-22

Fundamentos de programación. SESIÓN 6

Recuperado de: https://elibro.net/es/ereader/udibiblioteca/230062

Recursos bibliográficos

• Mañas, J. (2017) Análisis de Algoritmos – Complejidad. ADSW.

Recuperado de: https://www.dit.upm.es/~pepe/doc/adsw/tema1/Complejidad.pdf

Fundamentos de programación. SESIÓN 6

Consutla todo el documento.

Sambol (2021) Notación Big O | Explicación y Análisis de la complejidad de un Algoritmo. [Video]. YouTube.

Recuperado de:https://www.youtube.com/watch?v=zbrXClNX0Yg

Fundamentos de programación. SESIÓN 6

1

Comprender el problema-Identificar los datos de entrada y salida

5

-Usar pseudocódigo o diagramas de flujo para especificar el algoritmo.-Asegurarse de que cada paso sea claro y preciso.

6

-Dividir el problema en subproblemas manejables.-Diseñar un algoritmo paso a paso.

4

-Traducir el algoritmo a un lenguaje de programación.-Escribir el código correspondiente.

2

-Evaluar la eficiencia del algoritmo.-Optimizar para mejorar rendimiento si es necesario

3

-Probar el algoritmo con diferentes casos de prueba.-Corregir cualquier error o defecto encontrado.

Consiste en dividir el problema original en subproblemas más pequeños, resolver cada uno de estos subproblemas de manera independiente y luego combinar las soluciones para obtener la solución del problema original.

Concepto

• Permite manejar problemas grandes y complejos.
• Facilita la paralelización.

Ventajas

Consiste en probar todas las posibles soluciones y seleccionar la mejor. Es una estrategia simple y directa, aunque no siempre eficiente.

Concepto

• Fácil de implementar.
• Garantiza encontrar la solución óptima si existe.

Ventajas

Esta estrategia toma decisiones en cada paso basándose en la mejor opción local, con la esperanza de encontrar una solución global óptima.

Concepto

• Sencillos y rápidos de implementar.
• Eficientes en tiempo de ejecución para ciertos problemas.

Ventajas

Resuelve problemas dividiéndolos en subproblemas superpuestos y almacenando las soluciones de estos subproblemas para evitar cálculos redundantes. Utiliza una tabla para registrar las soluciones de subproblemas ya resueltos.

Concepto

• Eficiente en términos de tiempo al evitar recalcular soluciones de subproblemas.
• Garantiza encontrar la solución óptima.

Ventajas