Please enable JavaScript.
Coggle requires JavaScript to display documents.
TEMA 23 - Coggle Diagram
TEMA 23
INTRODUCCIÓN
Resolver problema vida cotidiana -> Metodología
Trasladar al mundo Computación -> Algoritmos.
Elemento central del código, plasmar ideas programador.
-
DISEÑO DE ALGORITMOS
Concepto de algoritmo
Pasos -> ordenados + finitos
Estado Inicial + pasos -> Estado final + resultados
Pasar lenguaje programación
Requisitos:
- Pasos no ambiguos + bien definidos
- Secuencia finita + ordenada
- Procedimiento tiempo finito + delimitado
-
-
Eficiencia Algorítmica
Varias formas de resolver problema
Idoneidad:
Tiempo de ejecución + Cantidad de Recursos
Ejemplo: par - impar
Técnicas de Diseño
-
Recursividad
Resolver versión reducida del problema
Código finito -> resultados infinitos
Instancias del problema pero menor tamaño
Caso base
Tipos:
- Simple -> Factorial
- Múltiple -> Fibonacci
- Indirecta
Divide y vencerás
Dividir conjunto de datos del problema -> subconjuntos + pequeños
obtener solución -> instrucción sencilla
combinar soluciones de cada subconjunto -> solución global
Programación Dinámica
Dividir problema -> demasiados subproblemas
= Tiempo ejecución -> orden exponencial
Subproblemas se resuleven + veces -> guardamos solución
= Tiempo ejecución polinomial + eficiente
Ejemplo ->Triangulo de Pascal
Algoritmos Voraces
Elegir opción optima a cada paso -> solución global óptima
Casa paso -> mejor elemento posible -> elemento + prometedor
No replantea decisión
Esquema algorítmico -> Fácil diseño + comprobación funcionamiento
No asegura la solución + óptima
Uso-> sistema devolución de cambio -> maquinas expendedoras
Vuelta atrás
Recorrer todos los caminos posibles -> solución
Fuerza bruta
Espacio posibles soluciones -> árbol de exploración
- Expandir árbol de exploración
- Recorrer árbol -> hasta solución o soluciones alternativas (mejor o todas)
Sudoku
Ramificación y Poda
Versión + sofisticada
Eliminar caminos inviables -> sin solución o no es mejor
Ejemplo Sudoku:
- Ramificación -> expandir árbol de exploración
- Poda -> descartar caminos inviables -> 3 en la misma fila
TECNICAS DESCRIPTIVAS
-
Pseudocódigo
Representar algoritmo -> lenguaje cercano natural
Eliminar sintaxis rígida de un LP -> frases + flexibles -> mejor comprensión
Ejemplo Área Rectángulo
Ventaja Lenguaje natural -> menos ambiguo + fácil traducir LP
Diagramas de Flujo
Representar secuencia de pasos -> símbolos entrelazados.
Ejemplo numero par o impar
Acciones -> Rectángulos
Operaciones E/S -> romboides
Decisiones -> Rombos
-
BIBLIOGRFÍA
- Amonorma Martínez, F. A. (2018). Fundamentos de la Programación. Madrid: Editorial Centro de Estudios Financieros.
- Bhargava, A. Y. (2019). Algoritmos: Guía ilustrada para programadores y curiosos. Madrid. ANAYA multimedia.
- Dorrego Martín, M. (2019). Módulo Profesional Programación. Madrid: Editorial Síntesis.
- Repositorio de problemas de programación. Link: https://www.aceptaelreto.com
- Web sobre estructuras típicas de distintos lenguajes de programación: http://lenguaj.es/
- W3schools, el sitio web de Desarrollo más grande del mundo. Link: https://www.w3schools.com