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

...