Técnicas de Diseño de algoritmos
Existen varias técnicas de diseño de algoritmos que permiten desarollar la solución al problema planteado, algunas de ellas son:
- Algoritmos voraces (greedy): seleccionan los elementos más prometedores del conjunto de candidatos hasta encontrar una solución. En la mayoría de los casos la solución no es óptima.
- Algoritmos paralelos: permiten la división de un problema en subproblemas de forma que se puedan ejecutar de forma simultánea en varios procesadores.
- Algoritmos probabilísticos: algunos de los pasos de este tipo de algoritmos están en función de valores pseudoaleatorios
- Algoritmos determinísticos: El comportamiento del algoritmo es lineal: cada paso del algoritmo tiene únicamente un paso sucesor y otro ancesor.
- Algoritmos no determinísticos: El comportamiento del algoritmo tiene forma de árbol y a cada paso del algoritmo puede bifurcarse a cualquier número de pasos inmediatamente posteriores, además todas las ramas se ejecutan simultáneamente.
- Divide y vencerás: dividen el problema en subconjuntos disjuntos obteniendo una solución de cada uno de ellos para después unirlas, logrando así la solución al problema completo.
- Metaheurísticas: encuentran soluciones aproximadas (no óptimas) a problemas basándose en un conocimiento anterior (a veces llamado experiencia) de los mismos.
- Programación dinámica: intenta resolver problemas disminuyendo su coste computacional aumentando el coste espacial.
- Ramificación y acotación: se basa en la construcción de las soluciones al problema mediante un árbol implícito que se recorre de forma controlada encontrando las mejores soluciones.
- Vuelta Atrás (Backtracking): se construye el espacio de soluciones del problema en un árbol que se examina completamente, almacenando las soluciones menos costosas.
Diseño del algoritmo.
Análisis de proceso implica que hace el programa.
Diseño implica como se hace o realiza la tarea (problema) solicitado
En el diseño:
- El todo es la sumatoria de las partes.
- Divide el todo en varias partes.
Esta característica define lo que se entiende como diseño descendente( Top-Down / Norte-Sur ) o diseño modular.
El proceso de ruptura del problema en cada etapa se llama refinamiento sucesivo.
- Cada problema se resuelve mediante un modulo (subprograma) y tiene un solo punto de entrada y un solo punto de salida.
- Un programa bien diseñado consta de un programa principal (modulo de nivel mas alto) que llama a subprogramas (módulos de nivel mas bajo), que a su vez pueden llamar otros sub programas.
Los módulos pueden ser planificados, codificados, compilados y depurados independientemente pueden ser intercambiados entre si.
Este proceso implica la ejecución de los siguientes pasos:
| 1 | programar un modulo |
| 2 | comprobar un modulo |
| 3 | depurar el modulo |
| 4 | combinar el modulo con módulos anteriores |
este proceso convierte el resultado del análisis del problema en un diseño modular con refinamientos sucesivos que permiten una traducción a un lenguaje que se denomina diseño del algoritmo.
El algoritmo se puede representar por medio de dos formas :Pseudo código
Diagrama de flujo:
Pseudo código: es el lenguaje de especificación de algoritmos y tiene una estructura: Las instrucciones se escriben en ingles o en palabras similares al ingles o español que facilitan la escritura de programación
Para la resolución de una ecuación de segundo grado se escribiría
inicio
Introducir coeficientes a, b y c
Imprimir títulos primera raíz, segunda raíz, no tiene solución,
Calcular raíz 1 y raíz 2
Imprimir raíz 1 y raíz 2
Fin
Diagramas de flujo (flows charts): Es la representación grafica del algoritmo; según la ANSI consta de una simbologia , que tiene los siguientes significados:
Para ver el gráfico seleccione la opción "Descargar" del menú superior
Símbolos del Diagrama de flujo
Codificación :
Programación:
Windows/Dos/
Quick Basic = Editor de texto.
Programa: definición:
conjunto de datos y sentencias:
Un programa tiene la forma
Para ver el gráfico seleccione la opción "Descargar"
En el editor de Quick Basic se escribiría codificado el seudo código
que tendría la forma:
REM Programa para calcular las soluciones
REM de una ecuacion de segundo grado
PRINT "Escriba los valores de A, B y C"
C$="Calculos"
INPUT " A,B,C", A, B, C
R = (B ^ 2 - 4 * A * C) ^ .5
LET X1 = (-B + R) / (2 * A)
LET X2 = (-B + R) / (2 * A)
PRINT " A="; A, " B="; B, "C="; C
PRINT "X1="; X1, "X2="; X2
END
En el Menú
| Ejecutar |
Mandatos e instrucciones:
Mandato (command): es una orden aislada de efecto inmediato.
Ejemplo:
| Mandato | Descripción |
| RUN | Ordena la ejecución de un programa. |
| LIST | Escribe En la pantalla el listado del programa |
| SAVE. | Guarda, graba el programa como un archivo de extensión BAS en el disco |
Ejemplo:
Instrucción | Descripción |
| Escribe en pantalla. | |
| INPUT | Introduce (entra datos) |
Para dar por terminada una línea se pulsa la tecla Enter (Return) en cualquier parte de la misma. Para cambiar una línea basta volver a teclearla.
- Se puede corregir una línea (borrar, rescribir ) en pantalla o bien con el mandato EDIT.
- Se pueden incluir varias instrucciones en una misma línea, separándolos por dos puntos.
- Una línea de pantalla (cuarenta u ochenta posiciones) es diferente de una línea de programa (doscientos cincuenta y seis posiciones).
Modo Programa
Run
Ventana activa
Ventana inmediata
mandato | Descripción |
| CLS | borra la pantalla |
- Todo programa debe estar documentado con comentarios; la primera línea debe contener el titulo del programa. Los comentarios deben de ir precedidos de la palabra clave REM o de un apostrofo ( ‘ )
- Si una línea ya tiene otras instrucciones, el comentario debe ir al final de la línea.
- Los comentarios solo aparecen en el listado del programa y no aparecen escritos en la pantalla durante la ejecución.
QBasic, trabaja con dos tipos de datos:
Datos | Tipos |
| numéricos: | Enteros (INT) Enteros largos (LNG) de simple precisión (SGL) de doble precisión (DBL) |
| alfanuméricos | hileras o cadenas (STR) fila de caracteres en ASCII ( en parte del teclado ) |
- Las constantes alfanuméricas pueden ser enteras o fraccionarias, se representan en forma decimal; se puede emitir el cero a la izquierda del punto decimal. Ejemplo
| 3452 | -12.67 | .23 | +12345 |
| Mantisa | letra | exponente |
| 1,23456E+15 | |
| 123456.0000000000 | |
| 1.234567890789456D–10 | 0.000000000123456789012456 |
- El numero máximo de cifras significativas con que se trabaja es:
16 para la precisión doble (DLB)
- En las constantes de punto fijo hay que añadir el carácter #
- Las constantes alfanuméricas son hileras de caracteres; se escriben entre comillas, Ej. "Hola " ; " A47EC
