Algoritmos

UNIDAD 2 ALGORITMOS

2.1 ANÁLISIS DE PROBLEMAS

La primera fase de la resolución de un problema con computadora es el análisis del problema. Esta fase requiere una clara definición donde se contemple exactamente lo que debe hacer el programa y el resultado o solución deseado.

Dado que se busca una solución por computadora, se precisa especificaciones detalladas de entrada y salida.

2.2 REPRESENTACIÓN DE ALGORITMOS: GRÁFICA Y SEUDOCÓDIGO.

Las dos herramientas usadas comúnmente para diseñar algoritmos son: Diagrama de flujo y Seudocódigos. Un diagrama de flujo (flowchart) es una representación gráfica de un algoritmo.

Para representar un algoritmo se debe utilizar algún método que permita independizar dicho algoritmo del lenguaje de programación elegido, ello permitirá que pueda ser codificado indistintamente en cualquier lenguaje. Se precisa que el algoritmo sea representado grafica o numéricamente.

Los métodos usuales para representar un algoritmo son:

1. Diagrama de flujo.

2. Diagrama N-S (Nassi-Schneiderman).

3. Lenguaje de especificación de algoritmos: seudocódigos.

4. Lenguaje español, inglés.

5. Formulas.

DIAGRAMA DE FLUJO.

Es una de las técnicas de representación de algoritmos más antigua y a la vez más utilizada. Es un diagrama que utiliza símbolos estándar y que tiene los pasos de algoritmos escritos en esas cajas unidas por flechas, denominadas líneas de flujo, que indican la secuencia en que se debe ejecutar.

En los diagramas de flujo existe:

 Una caja etiquetada “inicio”, que es de tipo elíptico.

 Existe una caja etiquetada “fin” de igual informa que la anterior.

 Existen otras cajas, normalmente rectangulares, tipo rombo o paralelogramo.

El uso de las fichas significa que la caja no necesita ser escrita debajo de su predecesora. Abusar demasiado de esta flexibilidad conduce a diagramas de flujo complicado e ininteligible.

SEUDOCÓDIGO.

Es una herramienta de programación en las que las instrucciones se escriben en palabras similares al inglés o español, que facilitan tanto como la escritura como la lectura de programas. El seudocódigo se puede definir como un lenguaje de especificaciones de algoritmos.

TIPO DE DATOS BÁSICOS.

 Entero: subconjunto finito de los números enteros cuyo rango dependerá del lenguaje en el que posteriormente codifiquemos el algoritmo y del ordenador.

 Real: subconjunto de los números reales limitado no solo en cuanto al tamaño, sino también en cuanto a la precisión.

 Lógico: conjunto formado por los valores cierto y falso “1 y 0”.

 Operaciones: todas las lógicas y relacionales, AND, OR.

 Carácter: conjunto finito y ordenado de los caracteres que el ordenador reconoce, se almacena en un byte. Con 8 Bits se podrán almacenar 28=256 valores diferentes.

Un carácter (letra) se guarda en un solo Byte como un número entero, correspondiente en el código ASCII.

 Cadena: los datos de este tipo contendrán una serie finita de caracteres.

Entero, real, carácter, cadena y lógico son tipos predefinidos en la mayoría de los lenguajes de programación.

VARIABLES.

Es un dato representado por una posición determinada de memoria cuyo valor puede cambiar durante el desarrollo del algoritmo.

Se identifica por su nombre y por su tipo, es el que determina el conjunto de valores que podrá tomar la variable. El nombre asignado a la variable se denomina identificador y tiene las siguientes reglas:

1. Un identificador se forma como una secuencia de letras.

2. El carácter subrayado se considera como una letra más.

3. Un identificador no puede contener espacios en blanco, ni otros caracteres distintos de los citados.

4. El primer carácter de un identificador debe ser siempre una letra o un (_), no puede ser un digito.

5. Se hace distinción entre letras mayúsculas y minúsculas.

6. ANSI C permite definir identificadores de hasta 31 caracteres de longitud.

OPERADORES.

Un operador es un carácter o grupo de caracteres que actúa sobre una, dos o más variables para realizar una determinada operación con un determinado resultado. Los operadores pueden ser unarios, binarios y ternarios, según actúen sobre una, dos o tres operaciones, respectivamente.

OPERADORES ARITMÉTICOS.

Son los más sencillos de entender y de utilizar. Todos ellos son operadores binarios se utilizan los cinco operadores siguientes:

• Suma +

• Resta –

• Multiplicación *

• División /

• Resto %

OPERADOR DE ASIGNACIÓN.

Atribuye a una variable, -depositan en su zona de memoria correspondiente- el resultado de una expresión o el valor. El operador de asignación más utilizado es el de igualdad (=), que no debe de ser confundido con la igualdad lógica (==).

DIAGRAMA DE NASSI-SCHNEIDERMAN (N-S)

También conocido como diagrama de Chapin; es como un diagrama de flujo en el que se omite las flechas de unión y las cajas son contiguas. Una lógica se representa con un rectángulo en el que cada banda es una acción a realizar.

2.3 DISEÑO DE ALGORITMOS APLICADOS A PROBLEMAS.

Para llegar a la realización de un programa es necesario el diseño previo de algoritmo de modo que sin algoritmo no puede existir un programa. En cada problema el algoritmo se puede expresar en un lenguaje diferente de programación y ejecutarse en una computadora distinta; sin embargo, el algoritmo será siempre el mismo.

Un aspecto muy importante será el diseño de algoritmos. El diseño de la mayoría de los algoritmos requiere creatividad y conocimientos profundos de la técnica de la programación.

TÉCNICAS DE DISEÑOS DE ALGORITMOS.

Algoritmos voraces (greedy): seleccionan los elementos más prometedores del conjunto de cantidades hasta encontrar una solución.

Algoritmo paralelo: permiten la división de un problema en subprogramas de forma que se puedan ejecutar de forma simultánea en varios procesadores.

Algoritmos probabilísticos: alguno de los pasos de este tipo están en función de valores seudoaleatorios.

Algoritmos determinísticos: el comportamiento del algoritmo es lineal; cada paso del algoritmo tiene únicamente un paso sucesor y otro antecesor.

Divide y vencerás: divide el problema en sus conjuntos disjuntos obteniendo una solución de cada uno de ellos para después unirlas, logrando así la solución al problema compuesto.

Metaheuristicas: encuentran soluciones aproximadas a problemas basándose en un conocimiento anterior de los mismos.

Programación dinámica: intenta resolver problemas disminuyendo su costo computacional aumentando el coste especial.

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 constantes.

CARACTERÍSTICAS DE ALGORITMO.

La resolución de un problema exige el diseño de un algoritmo que resuelve el problema. Pasos para la resolución de un problema:

1. Diseño del algoritmo que describe la secuencia ordenada de pasos sin ambigüedades.

2. Expresar el algoritmo como un programa en lenguaje adecuado.

3. Ejecución y validación del programa por la computadora.

CARACTERÍSTICAS DE LOS ALGORITMOS.

Un algoritmo debe:

 Ser preciso e indicar el orden de realización de cada paso.

 Estar definido. Si se sigue un algoritmo dos veces, se debe obtener el mismo resultado cada vez.

 Ser finito. Si se sigue un algoritmo, se debe terminar en algún momento; o se debe tener un número finito de paso.

2.4 DISEÑO ALGORÍTMICO DE FUNCIONES.

Nosotros podemos realizar cualquier algoritmo y representarlo en cualquiera de las formas anteriores dichas pero a su vez dividiéndolas en módulos, funciones, procedimientos subalgoritmos, etc. Los subprogramas pueden ser de dos tipos funciones y procedimientos. Una función va a ser un subprograma que pueda devolver además datos de tipo estructurado.

PROGRAMA MODULAR.

Es uno de los métodos de diseño más flexible y potentes para mejorar la productividad de un programa. En programación modular el programa se divide en módulos, cada uno de los cuales ejecutan una única actividad o tarea y se codifica independientemente de los otros módulos. Cada uno de estos módulos se analiza, codifican y ponen a punto por separado.

Cada programa contiene un módulo denominado programa principal, que controla todo lo que sucede; se transfiere en control a submodulos cada submodulo devuelve el módulo principal cuando se haya completado

...