Fundamentos de ProgramaciónUnidad 2: ALGORITMOS

2.1 Análisis de problemas

Problema: es la diferencia entre una situación actual y una

situación deseada, ésta última puede surgir como producto

de una necesidad, una deficiencia o una oportunidad de

mejora de los negocios.

Problema = situación actual – situación deseada

¿Dónde se esta?

¿Qué se tiene?

¿Dónde se desea estar?

¿Qué se desea tener?

¿Es realmente necesario hacerlo?

2.1.1 Características de un problema Definir y entender el problema e Identificar las

siguientes características:

◦ Entrada: información dada del problema.

¿Qué datos se necesitan para resolver el problema?

◦ Proceso: operaciones o cálculos necesarios para encontrar la

solución del problema.

◦ Salida: respuestas dadas por el proceso resultados finales de

los cálculos.

¿Qué información debe proporcionar la solución del

problema?

PROCESO

Datos

Entrada

Resultados

Salidas

Ejemplo: calcular el área de un rectángulo

Análisis del problema:

El cálculo del área del rectángulo se puede

dividir en:

◦ Entrada de datos (altura, base)

◦ Proceso: Cálculo del área (= base x altura)

◦ Salida de datos (base, altura, área)

Area=Base x Altura

Base

Altura

2.1.2 Fases de resolución de un problema

Definición de Problema

Análisis de los Datos

Diseño de la Solución (Algoritmo)

Codificación (Programa)

Prueba y Depuración

Documentación

Mantenimiento

2.1.2.1 Definición del problema

Está dada en sí por el enunciado del

problema, el cual debe ser claro y completo.

Es importante que conozcamos

exactamente "que se desea obtener al

final del proceso" ; mientras esto no se

comprenda no puede pasarse a la siguiente

etapa.

2.1.2.2 Análisis de los datos

Para poder definir con precisión el problema se

requiere que las especificaciones de entrada y

salida sean descritas con detalle ya que esto es un

requisito para lograr una solución eficaz.

Analizar los siguientes aspectos:

◦ Los resultados esperados.

◦ Los datos de entrada disponibles.

◦ Herramientas a nuestro alcance para manipular

los datos y alcanzar un resultado (fórmulas,

tablas, accesorios diversos).

2.1.2.3 Diseño de la solución (Algoritmo)

Proporcionar los sucesivos pasos a realizar, esto se

refiere a la obtención de un algoritmo que

resuelva adecuadamente el problema.

En caso de obtenerse varios algoritmos,

seleccionar uno de ellos utilizando criterios que

consideren la eficiencia del mismo.

Esta etapa incluye la descripción del algoritmo

resultante en un lenguaje natural, de diagrama de

flujo o natural de programación.

Los problemas complejos se pueden resolver más

eficazmente por la computadora cuando se dividen

en subproblemas que sean más fácil de solucionar.

2.1.2. 4 Codificación (Programa)

Se refiere a la escritura y representación en un

lenguaje de programación de un algoritmo.

Para transcribir el algoritmo al lenguaje se debe

considerar:

◦ Usar solo el conjunto de palabras e instrucciones que

conforman el lenguaje de programación.

◦ Respetar las reglas de sintaxis y semántica del lenguaje.

2.1.2.5 Prueba y depuración

Se realiza una prueba del programa ejecutable, afin de determinar si resuelve o no el problemaplanteado en forma satisfactoria.

Comúnmente se inicia la prueba de un programaintroduciendo datos válidos, inválidos eincongruentes y observando como reacciona encada ocasión.

La depuración consiste en localizar los errores ycorregirlos en caso de que estos existan.

Si no existen errores, puede entenderse ladepuración como una etapa de refinamiento enla que se ajustan detalles para optimizar eldesempeño del programa.

2.1.2.6 Documentación

Debido a que el programa resultante en esta etapa

se encuentra totalmente depurado (sin errores), se

procede a la utilización para resolver problemas

del tipo que dio origen a su diseño.

En vista de que esta utilización no podrá ser

supervisada en todas las ocasiones por el

programador, debe crearse un manual o guía de

operación que indique los pasos a seguir para

utilizar el programa.

2.1.2.7 Mantenimiento

Se refiere a las actualizaciones que deban aplicarse

al programa cuando las circunstancias así lo

requieran.

Este programa deberá ser susceptible de ser

modificado para adecuarlo a nuevas condiciones

de operación.

Cualquier actualización o cambio en el programa

deberá reflejarse en su documentación.

2.2 Entidades Primitivas

Tipos de Datos

◦ Numéricos

◦ Lógicos

◦ Carácter y cadena

Operadores y Operandos

◦ Operadores aritméticos

◦ Operadores relacionales

◦ Operadores lógicos

Expresiones y su representación algorítmica

◦ Aritméticas

◦ Relacionales

◦ Lógicas

◦ Carácter y cadena

2.2.1 Tipos de datos1

Un dato se define como la expresión general que describe losobjetos con los cuales opera una computadora. Los datos deentrada se transforman por el programa, después de las etapasintermedias, en datos de salida.

Datos Numéricos: Son aquéllos que representan una cantidado valor determinado. Su representación se lleva a cabo en losformatos ya conocidos (enteros, punto y fracciones decimales siestas existen). Estos pueden representarse en dos formasdistintas :

◦ Tipo Numérico Entero (integer): Es un conjunto finito de losnúmeros enteros. Los enteros son números completos, no tienen componentesfraccionarios o decimales y pueden ser negativos y positivos.

Ejemplo: 108 20 50 2015

◦ Tipo Numérico Real (real): Consiste en un subconjunto de los númerosreales. Estos números siempre tienen un punto decimal y pueden ser positivoso negativos. Un número real consiste de un número entero y una partedecimal.También son representados como punto flotante.

Ejemplo: 3.1416 314.16 x 10-2 31416. x 10-4 78.375

2.2.1 Tipos de datos2

Carácter o Cadenas: Son los datos que representaninformación textual (palabras, frases, símbolos, etc). Norepresentan valor alguno para efectos numéricos. Puedendistinguirse porque son delimitados por apóstrofes ocomillas. Se clasifica en dos categorías :

◦ Datos tipo carácter (char) : Es un conjunto finito y ordenado decaracteres que la computadora reconoce. Un dato de este tipocontiene solo un carácter. Utiliza tablas de código como el ASCIIpara su representación.Reconoce los siguientes caracteres : Caracteres Alfabéticos (A,B,C,…Z,a,b,c…z)

Caracteres Numéricos (0,1,2,…9)

Caracteres Especiales (+, -, *, /, ^, . , ;, <, >, $,…….)

◦ Datos tipo Cadena (string): Es un sucesión de caracteres que seencuentran delimitados por una comilla (apóstrofe) o doblescomillas, según el tipo de lenguaje de programación. La longitud deuna cadena de caracteres es el número de ellos comprendidos entrelos separadores o delimitadores. Ejemplos :

„Hola Mundo‟ ‟16 de septiembre, viva bicentenario‟

2.2.1 Tipos de datos3

Lógicos: también se le denomina Booleano, es aquél dato que solo

puede tomar uno de dos valores : Falso y verdadero. Se utiliza para

representar las alternativas (si/no) a determinadas condiciones. Por

ejemplo, cuando se pide si un valor entero sea primo, la respuesta será

verdadera o falsa, según sea.

Tipos Enumerados:

◦ SUBRANGO : Son aquéllos en los que se especifica con precisión el

intervalo de valores válidos para un dato. Ejemplos:

0..100 (son enumerativos de tipo entero)

'A'..'Z' (son enumerativos de tipo cadena)

Los Reales no son válidos para crear enumerativos, ya que su intervalo no

está definido.

◦ ENUMERATIVOS : Son aquéllos en los que se definen individualmente

los valores para un dato. Ejemplos:

(0,25,40,52) Siempre deben ponerse entre paréntesis.

◦ DEFINIDOS POR EL USUARIO : Son aquéllos que el programador

crea para satisfacer las necesidades del programa en diseño.

2.2.2 Identificador, constantes y variables

Un identificador es un nombre que se le da un

elemento de programa, ya sea una constante, variable,

un procedimiento o una función.

Una Constante es aquélla que no cambia de valor

durante la ejecución de un programa (o comprobación

de un algoritmo).

Las Variables son aquéllas que pueden modificar su

valor durante la ejecución de un programa.

El identificador que se le da a una variable o constante

suele representar un espacio de memoria donde será

almacenado su valor. Lo anterior se hace con la finalidad

de facilitar la utilización de la memoria, en lugar de

utilizar directamente direcciones de memoria.

2.2.3 Operaciones primitivas

Operando: puede ser una constante o variable

sobre la cual se realiza una determinada operación

u acción.

Operador: es el símbolo que determina el tipo

de operación o relación que habrá de establecerse

entre los operandos para alcanzar un resultado.

Los operadores se clasifican en tres grupos:

Aritméticos.

Relacionales.

Lógicos.

2.2.3.1 Operadores aritméticos

Son aquéllos que permiten la realización de cálculos

aritméticos. Utilizan operandos numéricos y proporcionan

resultados numéricos.

Operador Operación

^ Exponenciación

* Multiplicación

/ División

+ Suma

- Resta

DIV División entera (cociente)

MOD Modulo o residuo de División

2.2.3.2 Operadores relacionales

Permiten realizar comparaciones de valores de tipo

numérico o carácter. Estos operadores sirven para

expresar las condiciones en los algoritmos. Proporcionan

resultados lógicos.

Operador Significado

< Menor que

> Mayor que

<= Menor igual

>= Mayor igual

= igual

<> Diferente

2.2.3.3 Operadores lógicos

Son aquéllos que permiten la combinación de condiciones

para formar una sola expresión lógica. Utilizan operandos

lógicos y proporcionan resultados lógicos también.

Operador Significado Obtiene

verdadero si

NOT Negación (No) El operando es

falso

AND Conjunción (Y) Ambos operandos

son verdaderos

OR Disyunción (O) Al menos un

operando es

verdadero

XOR Disyunción

Exclusiva

(O/SOLO)

Solo uno de los

operandos son

verdadero

2.2.3.3.1 Tabla de verdad

X Y X

AND

Y

X

OR

Y

X

XOR

Y

NOT(X) NOT(Y)

F F F F F V V

F V F V V V F

V F F V V F V

V V V V F F F

2.2.3. 4 Prioridad de Operadores Determina el orden en que habrán de realizarse las operaciones

en una expresión determinada. Para obtener la prioridad sedeben conocer las siguientes reglas:

Las operaciones que están encerradas entre paréntesis seevalúan primero. Si existen diferentes paréntesis anidados(interiores unos a otros), las expresiones más internas seevalúan primero.

Las operaciones aritméticas dentro de una expresión suelenseguir el siguiente orden de prioridad:

En caso de coincidir varios operadores de igual prioridad en unaexpresión o subexpresión encerrada entre paréntesis, el ordende prioridad en este caso es de izquierda a derecha.

Operador Prioridad

^ Exponenciación (ALTA)

*,/,DIV,MOD multiplicación, división,

cociente , residuo

+,- suma, resta

Relacionales Baja

Lógicos

2.2.3. 5 Asignación La operación de asignación es el modo de darle valores a

una variable. La operación de asignación se representa por

el símbolo u operador :=, .

A fin de manejar datos por medio de variables, estos

pueden recibir valores determinados. El tipo de los valores

que pueden recibir dependen de la declaración previa de

tales variables.

En una asignación se resuelve, primeramente la expresión

(al lado derecho del símbolo de asignación) y se asigna el

resultado en la variable. El formato general de asignación

es: Nom_variable Expresión

Donde Expresión puede ser una variable o constante, operación,

función.

Ejemplos: A:=10*5 , B:=(5<10), palabra:=“HOLA”

2.2.3. 6 Entrada y Salida de Información Los cálculos que realizan las computadoras requieren para

ser útiles la Entrada de los datos necesarios para ejecutarlas operaciones que posteriormente se convertirán enresultados, es decir, Salida.

Las operaciones de entrada permiten leer determinadosvalores y asignarlos a determinadas variables. Esta entradase conoce como operación de Lectura (read). Los datosde entrada se introducen al procesador mediantedispositivos de entrada (teclado, unidades de disco, etc).

La salida puede aparecer en un dispositivo de salida(pantalla, impresora, etc). La operación de salida sedenomina escritura (write).

En la escritura de algoritmos las acciones de lectura yescritura se representan por los formatos siguientes:

leer ( Nom_variable )

escribir (lista de variables de salida)

2.2.4 Expresiones Las expresiones son combinaciones de constantes,

variables, símbolos de operadores, paréntesis y nombres de

funciones especiales.

Cada expresión toma un valor que se determina tomando

los valores de las variables y constantes implicadas y la

ejecución de las operaciones indicadas.

Una expresión consta de operadores y operandos.

Según sea el tipo de objetos que manipulan, las

expresiones se clasifican en : aritméticas, relacionales,

lógicas y carácter o cadena.

El resultado de la expresión numérica es de tipo numérico ;

el resultado de una expresión relacional y de una expresión

lógica es de tipo lógico ; el resultado de una expresión

carácter es de tipo carácter.

2.3 Técnicas de Diseño

Con el objeto de facilitar el diseño de

algoritmos y la organización de los diversos

elementos de los que se componen se utilizan

algunas técnicas que muestran una metodología

a seguir para resolver los problemas.

Estas técnicas hacen que los programas sean

más fáciles de escribir, verificar, leer y mantener.

Algunas de las técnicas más conocidas son :

Top Down (diseño descendente)

Botton Up

Warnier Orr

2.3.1.1 Top Down Es una técnica para diseñar que consiste en tomar el

problema en forma inicial como una cuestión global y

descomponerlo sucesivamente en problemas más pequeños y

por lo tanto, de solución más sencilla.

La descomposición del problema original (y de las etapas

subsecuentes), puede detenerse cuando los problemas

resultantes alcanzan un nivel de detalle que el programador o

analista pueden implementar fácilmente.

El problema se descompone en etapas o estructuras

jerárquicas, de modo que se puede considerar cada estructura

como dos puntos de vista : ¿lo que hace?, y ¿cómo lo hace ?.

Si se considera un nivel n de refinamiento, las estructuras se

consideran de la siguiente forma : nivel n : Vista desde el exterior. ¿lo que hace ?

nivel n+1 : Vista desde el interior. ¿cómo lo hace ?

2.3.1.2 Ejemplo Top Down

2.3.2 Botton Up

Esta técnica consiste en partir de los detalles más

precisos del algoritmo completando sucesivamente

módulos de mayor complejidad, se recomienda cuando

ya se cuenta con experiencia y ya se sabe lo que se va

a hacer.

Conforme se va alcanzando el desarrollo de módulos

más grandes se plantea como objetivo final la

resolución global del problema.

Este método es el inverso del anterior y es

recomendable cuando se tiene un modelo a seguir o

se cuenta con amplia experiencia en la resolución de

problemas semejantes.

La técnica de Botton Up es frecuentemente utilizada

para la realización de pruebas a sistemas ya concluidos.

2.3.3.1 Warnier Orr

Es una técnica que utiliza una representación

semejante a la de cuadros sinópticos para mostrar

el funcionamiento y organización de los elementos

que conforman el algoritmo.

Básicamente, utiliza una notación de llaves para

organizar los módulos y se auxilia en la siguiente

simbología para indicar operaciones de control. + OR (uno, otro o varios)

+ XOR (uno u otro, solo uno)

(x,y) puede hacerse tantas veces desde x hasta y

Los diagramas Warnier Orr se leen de izquierda a

derecha y de arriba hacia abajo.

2.3.3.2 Ejemplo Warnier Orr

2.4 Representación de Algoritmos

Descripción narrada

Diagrama de flujo (representación gráfica)

Pseudocódigo

Diagramas estructurados(N-S)

2.4.1 Descripción narrada

Utiliza el lenguaje natural para describir la

secuencia de pasos a seguir para dar

solución a un problema especifico.

Es muy utilizada para describir algoritmos

cotidianos como recetas de cocina,

instructivos de instalación, etc.

Se debe de emplear una clara redacción con

énfasis en los detalles y sin ambigüedades.

La secuencia de pasos se debe de enumerar

de acuerdo al orden de ejecución del

algoritmo.

2.4.2 Diagrama de flujo

Se basan en la utilización de diversos

símbolos para representar operaciones

específicas.

Se les llama diagramas de flujo porque los

símbolos utilizados se conectan por medio

de flechas para indicar la secuencia de

operación.

La simbología utilizada para la elaboración

de diagramas de flujo es variable y debe

ajustarse a un patrón definido previamente.

2.4.2.1 Simbología de Diagrama de flujo1

Símbolo Función

Terminal : representa el inicio o fin de un programa,

puede también representar una parada o interrupción

programada que sea necesario realizar en un programa

Entrada/Salida de datos

Proceso: cualquier tipo de operación que pueda originar

cambio de valor, formato o posición de la información

almacenada en memoria, operaciones aritméticas.

Descisión: indica operaciones lógicas o de comparación

entre datos.

Conector: sirve para conectar partes de un diagrama en

una misma hoja.

Indicador de dirección o línea de flujo: indica el sentido de

ejecución de las operaciones.

Línea conectora: sirve de unión entre 2 símbolos

2.4.2.1 Simbología de Diagrama de flujo2

Símbolo Función

Conector: conexión entre 2 puntos situados en páginas

diferentes.

Llamada a subrutina (proceso predeterminado) o a un

modulo independiente del programa.

Pantalla : se puede utilizar en lugar del símbolo de salida.

Impresora : se puede utilizar en lugar del símbolo de

salida.

Teclado : se puede utilizar en lugar del símbolo de

entrada.

2.4.2.2 Representación de estructuras de

control en diagrama de flujo

SECUENCIA

Acción 1

Acción 2

Acción n

SELECCIONSIMPLE

Condición

Accion(es)

NO

SI

DOBLE

Condición

Accion(es)

NO SI

Accion(es)

Selector

Accion(es)

MULTIPLE

Accion(es) Accion(es) Accion(es)…

Valor 1 Valor 2 Valor 3 Valor N

2.4.2.2 Representación de estructuras de

control de repetición diagrama de flujo

Condicionada al Inicio (While)

Condición

Accion(es)

NO

SI

PREDEFINIDA

Condicionada al Final (Repeat-Until)

Condición

Accion(es)

NO

SI

Accion(es)

SI

NOi=Val. Inicial

i=i+1

I<=Val. Final

2.4.3 Pseudocódigo

Es un lenguaje de especificación de algoritmos. El uso de tal

lenguaje hace el paso de codificación final (esto es, la

traducción a un lenguaje de programación) relativamente

fácil.

La ventaja del pseudocódigo es que en su uso en la

planificación de un programa, el programador se puede

concentrar en la lógica y en las estructuras de control y no

preocuparse de las reglas de un lenguaje específico.

Es también fácil modificar si se descubren errores o

anomalías en la lógica del programa.

utiliza para representar las acciones sucesivas palabras en

un lenguaje natural (similares a sus homónimos en los

lenguajes de programación), tales como inicio, fin, repite –

hasta, si –entonces-sino, etc.

2.4.3.1Palabras usadas en Pseudocódigo

Secuencia

Inicio

acción1

acción2

:

acción n

Fin

Decisión Simple

si condición entonces

acción1

acción2

:

acción n

Doble

si condición entonces

acción(es)

en caso contrario

acción(es)

Múltiple

casos selector de

valor1 : acción(es)

valor2 : acción(es)

:

valor n : acción(es)

2.4.3.1Palabras Iteración en Pseudocódigo

Predefinida

para var. Entera inicial hasta final hacer

acción(es)

Condicional al inicio

Haz mientras (condición)

acción(es)

Condicional al final

Repetir

acción(es)

Hasta que condición

2.4.4 Diagramas Estructurados

(nassi-schneiderman)

El diagrama N-S de Nassi-Schneiderman, también

conocido como diagrama de Caja, es como un

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.

Los Diagramas Estructurados, son una técnica que

permite formular algoritmos mediante una

representación geométrica y de asignación

de espacios de un bloque específico.

2.4.4.1 Estructuras de control diagramas N-S

Secuencia

Selección Simple

Selección DobleSelección Múltiple

2.4.4.1 Estructuras de control de repetición

diagramas N-S

Condicionada al inicio (While) Condicionada al final (Repeat-Until)

Pre-definida

2.4.4.2 Ejemplos diagrama (N-S)