PDF de programación - Tema 2 - Algoritmos

2



Algoritmos



ALGORITMOS


Dpl. Ing. Carlos Balderrama Vásquez

43

Tema 2

2.1 Introducción

El objetivo principal de la materia es el de enseñar a resolver problemas mediante una
computadora. Un programador de computadoras antes de nada es un resolvedor de
problemas.

Por lo que para llegar a ser un programador eficaz se necesita aprender a resolver
problemas de un modo riguroso y sistemático.

Por esto la materia tiene como nombre Metodología de la programación.

Antes de comenzar con el tema vamos a considerar el significado de la palabra
ALGORITMO esta palabra se deriva de la traducción al latín de la palabra árabe
ALKHÔWARÎZMI, nombre de un matemático y astrónomo árabe que escribió un tratado
sobre la manipulación de números y ecuaciones en el siglo IX, titulado KITAB AL-JABR
W’ALMUGALABA, la palabra álgebra se derivó por su semejanza sonora de AL-JABR.

Etimológicamente la palabra problema deriva del griego PROBALLEIN y significa “algo
lanzado hacia delante”. Un problema es un asunto o conjunto de cuestiones que se
plantean para ser resueltas, la naturaleza de los problemas varia con el ámbito o con el
contexto donde están planteados: así existen problemas matemáticos, físicos, filosóficos,
etc.,



Programa de
computadora

Problema

Diseño del
algoritmo



Fig.2 .1 Esquema del desarrollo de algoritmos

2.2 Definición

“Un Algoritmo es una secuencia de operaciones detalladas y no ambiguas, que al ejecutarse
paso a paso, conducen a la solución de un problema”. En otras palabras es un conjunto de
reglas para resolver una cierta clase de problema.

“Algoritmo es un conjunto de instrucciones que especifican la secuencia de operaciones a
realizar, en orden, para resolver un sistema específico o clase de problema”.

“Un Algoritmo es la aplicación de pasos lógicos, secuenciales y metódicamente aplicados
para dar solución a un problema en cuestión.” En otras palabras un algoritmo es una
formula para resolver problemas.


“En otras palabras un algoritmo es una formula para la solución de un problema.”

“Todo problema se puede describir por medio de un algoritmo “

44

Metodología de la Programación I



Algoritmos



“ Todo algoritmo es independiente del lenguaje”


2.3 Características De Los Algoritmos.

Las propiedades de un algoritmo son las siguientes:

a) El algoritmo debe ser preciso e indicar el orden de realización de cada paso.
b) El algoritmo debe ser definido, si se sigue un algoritmo dos veces, se debe obtener el

mismo resultado cada vez.

c) El algoritmo debe ser finito, si se sigue un algoritmo se debe terminar en algún

momento; o sea debe tener un número finito de pasos.



Salida

Resultados



Entrada

Proceso


El algoritmo debe ser planteado como un sistema de información.



Análisis

Modelo



2.4 Clasificación De Los Algoritmos

Se puede clasificar tomando en cuenta dos aspectos.


Fig. 2.2 Representación de un algoritmo como un sistema de Información

• Secuenciales
• Condicionales
• Repetitivos



Dpl. Ing. Carlos Balderrama Vásquez

45

Tema 2

2.5 Tipos De Algoritmos


palabras.

Cualitativos: Son aquellos en los que se describen los pasos utilizando

Cuantitativos: Son aquellos en los que se utilizan cálculos numéricos para
definir los pasos del proceso.

2.6 Lenguajes Algoritmicos

Es una serie de símbolos y reglas que se utilizan para describir de manera explícita un
proceso.

2.7 Tipos De Lenguajes Algoritmicos


• Gráficos: Es la representación gráfica de las operaciones que realiza un

algoritmo (diagrama de flujo).

• No Gráficos: Representa en forma descriptiva las operaciones que debe

realizar un algoritmo (pseudocodigo).


Un algoritmo puede ser expresado de las siguientes formas.


a) Lenguaje Natural : el uso de términos del lenguaje natural, es una forma

de representar un algoritmo.

b) Lenguaje Simbólico: es otra forma de representación de un algoritmo,

que además permite una introducción a la programación estructural.

c) Lenguaje Gráfico : es una forma de escribir una secuencia de pasos en

forma de diagrama, en la practica se denomina Diagramas de Flujo.


Una receta de un plato de cocina se puede expresar en español, ingles o francés pero
cualquiera sea el lenguaje los pasos para la elaboración del plato se realizarán sin importar
el cocinero.


2.8 Las Tecnicas De Diseño De Algoritmos


El diseño de la mayoría de los algoritmos requiere creatividad y conocimientos de la
metodología de programación, esto significa que debe desarrollar una lógica computacional
a través de la resolución de programas.

Y principalmente en diseño de un algoritmo debe realizarse apartir de un análisis del
problema.

El acto de diseñar un algoritmo puede considerarse como una tarea que difícilmente podrá
ser del todo automatizada, todo problema algoítmico es un reto para su diseñador. Algunos

46

Metodología de la Programación I



Algoritmos



resultan inmediatos de resolver, otros son bastante complejos. la investigación en esta área
ha permitido descubrir un conjunto de métodos y esquemas de diseño hacia los cuales
puede orientarse la realización de muchos algoritmos. Idear un algoritmo continua siendo
una labor bastante creativa donde los conocimientos y las experiencias del propio diseñador
tiene un papel fundamental.


2.8.1 Divide y vencerás

Consiste en descomponer un problema en subproblemas, resolver independientemente los
subproblemas para luego combinar sus soluciones y obtener una solución del problema
original.

Esta técnica puede ser utilizada con éxito en problemas como multiplicación de matrices,
ordenación de vectores, etc.

Ejemplo. Encontrar el ángulo entre dos vectores A(x,y,z) y B(x,y,x).



A

B
→
B
B

α = ?



Determinar la ecuación del ángulo entre dos vectores. del producto escalar se tiene
)

COS

α

→
A

→
B

B

=

A

*

*

*

(

→
A
A
Determinar las operaciones intermedias

cos

α

=

*
*

A
B

N
D

=

=

=
=



2

2

Ax
Bx

=

Ax

+

+

*

2

2

Ay
By

+

+

2

2

Az
Bz

Bx

+

Ay

*

By

+

Az

*

Bz

=

A
B
=
→→
BA
A
B

*
*

Dpl. Ing. Carlos Balderrama Vásquez

47

Tema 2

Determinar la solución general.


ANG

=

cos 1
−

(

DN

/

)

=

ARCCOS

(

DN

/

)


2.8.2 Método voraz

Este método trata de producir algún tipo de mejor resultado a partir de un conjunto de
opciones candidatas. Par ello se va procediendo paso a paso realizándose la mejor
elección(utilizando un función objetivo que respeta un conjunto de restricciones) de entre
las posibles. Puede emplearse en problemas de optimización, como el conocido de la
mochila, en la búsqueda de caminos mínimos sobre grafos, la planificación en la ejecución
de programas en un computador, etc.


Ejemplo Dar cambio utilizando el menor número de billetes.

Conjunto
{"doscientos","cien","cincuenta","veinte","diez","cinco","dos","uno"};
Conjunto de cantidades ={200,100,50,20,10,5,2,1};
Cambiar (dato, posición)

billetes

de

=

cuantos = dato DIV cantidades[posición];
si (cuantos es distinto de 0) entonces

fin_si
Cambiar (dato MOD cantidades[posición], posición+1);

si (dato es distinto de 0) entonces



Fin_si
Fin_cambiar
inicio

imprimir ("hay ”, cuantos, “billetes de “, billetes [ posición]);

cambiar(1388,0);

fin

El estilo y calidad de los algoritmos van fuertemente unidos, ante la pregunta “Cuales son
las características de un buen algoritmo?” la respuesta identifica los factores de calidad de
los algoritmos.


• Corrección: el algoritmo debe funcionar.
• Eficiencia : el algoritmo no debe desaprovechar recursos.
• Claridad : el algoritmo debe estar bien documentado.


2.8.3 Top Down

También conocida como de arriba-abajo (diseño descendente) y consiste en establecer una
serie de niveles de mayor a menor complejidad (arriba-abajo) que den solución al

48

Metodología de la Programación I



Algoritmos



problema. Consiste en efectuar una relación entre las etapas de la estructuración de forma
que una etapa jerárquica y su inmediato inferior se relacionen mediante entradas y salidas
de información.

Este diseño consiste en una serie de descomposiciones sucesivas del problema inicial, que
recibe el refinamiento progresivo del repertorio de instrucciones que van a formar parte del
programa.

La utilización de la técnica de diseño Top-Down tiene los siguientes objetivos básicos:

Simplificación del problema y de los subprogramas de cada descomposición.

Las diferentes partes del problema pueden ser programadas de modo independiente e
incluso por diferentes personas.

El programa final queda estructurado en forma de bloque o módulos lo que hace mas
sencilla su lectura y mantenimiento.


SEGUNDO
REFINAMIENTO



PRIMER
REFINAMIENTO



ULTIMO


REFINAMIENTO



Problema
Inicial



Sub Problema

1



Sub Problema

M


Sub problema


1.1


Sub problema


1.2


Sub problema


M.1


Sub problema


M.2

Modulo 1

Modulo 2

Modulo 3

Modulo 4

Modulo N-3

Modulo N-2

Modulo N-1

Modulo N



Fig. 2.3 Diseño Top Down

Dpl. Ing. Carlos Balderrama Vásquez

49

Tema 2

2.8.4 Bottom Up

El diseño ascendente se refiere a la identificación de aquellos