Unidad 4 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 deseada.

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

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

Las dos herramientas más utilizadas comúnmente para diseñar algoritmos son: diagramas de flujo yPseudocó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 un algoritmo pueda ser codificado indistintamente en cualquier lenguaje. Para conseguir este objetivo se precisa que el algoritmo sea representado gráfica o numéricamente, de modo que las sucesivas acciones no dependan de la sintaxis de ningún lenguaje de programación, sino que la descripción pueda servir fácilmente para su transformación en un programa, es decir, su codificación.

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: pseudocódigo,

4. lenguaje español, ingles

5.- fórmulas

Los métodos 4 y 5 no suelen ser fáciles de transformar en programas. Una descripción en españolnarrativo no es satisfactoria, ya que es demasiado prolija y generalmente ambigua. Una fórmula, sin embargo, es buen sistema de representación.

Diagramas de flujo

Un diagrama de flujo (flowchart) es una de las técnicas de representación de algoritmos más antiguay a la vez más utilizada, aunque su empleo ha disminuido considerablemente, sobro todo, desde la aparición de lenguajes de programación estructurados. Un diagrama de flujo es un diagrama que utiliza símbolos (cajas) estándar y que tiene los pasos de algoritmo escritos en esas cajas unidas por flechas, denominadas líneas deflujo, 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 forma que la anterior,

• existen otras cajas, normalmente son rectangulares, tipo rombo o paralelogramo (el resto de las figuras se utilizan sólo en diagramas de flujo generales o de detalle y no siempre son imprescindibles).

Se puede escribir más de un paso del algoritmo en una sola caja rectangular. El uso de flechas significaque la caja no necesita ser escrita debajo de su predecesora. Sin embargo, abusar demasiado de esta flexibilidad conduce a diagramas de flujos complicados e ininteligibles.

Pseudocódigo

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

Tipos 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. El rango depende de cuantos bits utilice para codificar el número.

Real: Subconjunto de los números reales limitado no sólo en cuanto al tamaño, sino también en cuanto a la precisión. Suelen ocupar 4, 6 ó 10 bytes. Se representan por medio de la mantisa, y un exponente

Lógico: Conjunto formado por los valores Cierto y Falso. ‘1’ y ‘0’.

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

> , <

== (igual), >= , <= , ¹ …

Carácter: Conjunto finito y ordenado de los caracteres que el ordenador reconoce. se almacenan en un byte. Con 8 bits se podrán almacenar 28= 256 valores diferentes (normalmente entre 0 y 255; con ciertos compiladores entre-128 y 127).

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

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

Podrán representarse de estas dos formas:

‘H’ ’O’ ’L’ ’A’ == “HOLA”,

No es lo mismo “H” que ‘H’, ya que el primero es una cadena y el segundo un carácter.

Entero, Real, Carácter, Cadena y Lógico son tipos predefinidos en la mayoría de los lenguajes de programación. Además el usuario podrá definir sus propios tipos de datos, si estos facilitan de alguna manera la resolución del problema.

Variables

Una variable 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, que podrá ser cualquiera, y es el que determina el conjunto de valores que podrá tomar la variable. En los programas la declaración de cada una de las variables origina que se reserve un determinado espacio en memoria etiquetado con el correspondiente identificador. El nombre asignado a la variable se denomina identificador y tiene las siguientes reglas:

1.Un identificador se forma con una secuencia de letras (minúsculas de la aala z; mayúsculas de la A a la Z; y dígitos

del 0 al 9).

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, como por ejemplo (*,;.:-+, etc.).

4. El primer carácter de un identificador debe ser siempre una letra o un (_), es decir, no puede ser un dígito.

5. Se hace distinción entre letras mayúsculas y minúsculas. Así, Masa es considerado como un identificador distinto de masa y de MASA.

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

Operadores, Expresiones y Sentencias

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. Ejemplos típicos de operadores son la suma (+), la diferencia (-), el producto (*), etc. Los operadores pueden ser unarios, binarios y ternarios, según actúen sobre uno, dos o tres operandos, respectivamente.

OPERADORES ARITMÉTICOS

Los 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: % ( resto de la división entera. Este operador se aplica solamente a constantes, variables o expresiones de tipo entero).

OPERADORES DE ASIGNACIÓN

Los operadores de asignación atribuyen a una variable –es decir, depositan en su zona de memoria correspondiente– el resultado de una expresión o el valor.

Variable (en realidad, una variable es un caso particular de una expresión).

El operador de asignación más utilizado es el operador de igualdad (=), que no debe ser confundido con la igualdad lógica (==). Su forma general es: nombre_variable = expresión.

DIAGRAMAS DE NASSI-SCHNEIDERMAN (N-S)

El diagrama N-S de NassiSchneiderman -también conocido como diagrama de Chapin- es comoun diagrama de flujo en el que se omiten las flechas de unión y las cajas son contiguas. Las acciones sucesivas se escriben en cajas sucesivas y, como en los diagramas de flujo, se pueden escribir diferentes acciones en una caja. Un algoritmo 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.

Los algoritmos son independientes tanto del lenguaje de programación en que se expresan como de la computadora que lo ejecuta. 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.

Dada la importancia del algoritmo en la ciencia de la computación, un aspecto muy importante será el diseño de algoritmos. El diseño de la mayoría de los algoritmos requiere creatividady conocimientos profundos de la técnica de la programación.

Técnicas de diseño de algoritmos

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

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

...