Un algoritmo es un conjunto finito de instrucciones o pasos que sirven para ejecutar una tarea y/o resolver un problema. De un modo más formal, un algoritmo es una secuencia finita de operaciones realizables, no ambiguas, cuya ejecución da una solución de un problema en un tiempo finito.
El término algoritmo no está exclusivamente relacionado con la matemática, ciencias de la computación o informática. En realidad, en la vida cotidiana empleamos algoritmos en multitud de ocasiones para resolver diversos problemas.
Algunos ejemplos son el uso de una lavadora (se siguen las instrucciones), pero no la preparación de una comida (porque no están perfectamente definidos los pasos).
También existen ejemplos de índole matemática, como el algoritmo de la división para calcular el cociente de dos números, el algoritmo de Euclides para calcular el máximo común divisor de dos enteros positivos, o incluso el método de Gauss para resolver Sistema lineal de ecuaciones.
Un algoritmo numérico es el conjunto de instrucciones ordenadas para resolver un problema que involucra procesos matemáticos (con calculo de formulas de manera repetida).
Este tipo de algoritmos no admiten ambigüedades y debe darse cada uno de los pasos para su solución.
Se define el concepto de algoritmo numérico. Se presentan varios casos de problemas numéricos, se dan sus soluciones en forma algorítmica y se agrega en cada caso una representación en forma de diagrama de flujo.
La noción de algoritmo aparece en numerosas y disímiles situaciones de la vida cotidiana y es manejada por una gran cantidad de personas, algunas de las cuales ni tan siquiera conocen su existencia. De manera informal, un algoritmo puede definirse como una lista de instrucciones mediante las cuales puede llevarse a cabo un determinado proceso.
Los métodos numéricos permiten resolver problemas obteniendo aproximaciones para las soluciones mediante algoritmos iterativos. Estos algoritmos reciben el nombre de algoritmos numéricos.
Las aproximaciones resultan de mucha utilidad cuando las soluciones analíticas o algebraicas resultan muy difíciles o hasta imposibles de obtener empleando métodos tradicionales. Los computadores ayudan en gran manera, al facilitar la programación de los algoritmos basados en iteración. En esta sección se presentan ejemplos de estos métodos. 1.1 Ejemplo: Cálculo de e mediante serie infinita Programa que calcula el valor de la constante e, base de los logaritmos neperianos. Se hace una aproximación empleando la siguiente serie infinita: e = 1 + 1/1! + 1/2! + 1/3! + 1/4! + … El cálculo se detiene cuando el valor acumulado de e, no se logra diferenciar (por la precisión del computador), del valor calculado en la iteración anterior. Es decir, cuando el siguiente término a sumar es tan pequeño que el computador lo considera como un cero. El factorial, representado por ! en la serie, se implementa en el programa mediante una función. Una vez que se calcula la aproximación, el programa despliega el valor encontrado, así como el número de iteraciones que se emplearon para obtenerlo, es decir, la cantidad de términos de la serie que fue necesario sumar para llegar a la aproximación.
http://www.youtube.com/watch?v=FTC5wOhTuM0
ALGORITMOS NUMERICOS
El programador diseña un programa, para resolver un problema particular.
Diseñar es un proceso creativo.
El proceso de diseño de un programa consta de los siguientes pasos o etapas:
Pasos:
Pasos
Etapa
Descripción
1
Análisis del problema
Conducen al diseño detallado por medio un código escrito en forma de un algoritmo
2
Diseño de algoritmo
3
Codificación
Se implementa el algoritmo en un código escrito en un lenguaje de programación. Refleja las ideas desarrolladas en las etapas de análisis y diseño
4
Compilación y ejecución
Traduce el programa fuente a programa en código de maquina y lo ejecuta.
5
Verificación
Busca errores en las etapas anteriores y los elimina.
6
Depuración
7
Documentación
Son comentarios, etiquetas de texto, que facilitan la comprensión del programa
Concepto
Algoritmo: es un método para resolver un problema mediante una serie de pasos definidos, precisos y finitos.
Preciso: implica el orden de realización de cada uno de los pasos
Definido: si se sigue dos veces, se obtiene el mismo resultado.
Finito: Tiene un numero determinado de pasos, implica que tiene un fin,
Tipos :
Método
Descripción
Ejemplos
Algorítmico
Utiliza un algoritmo y puede ser implementado en una computadora
Instrucciones para manejar un vehículo
Instrucciones para secar grano a granel
Instrucciones para resolver ecuación de segundo grado
Heurística:
Se apoya en el resultado obtenido en un análisis de alternativas de experiencias anteriores similares. De las mismas, a se deducen una serie de reglas empíricas o heurísticas que de ser seguidas, conducen a la selección de la mejor alternativa en todas o la mayoría de las veces.
Ejemplos
Los algoritmos se pueden
expresar por:
Formulas
Diagramas de flujo
Norte-Sur,Top-Down
Pseudo código
inicio
leer a,b,c
calcular
escribir perímetro
fin
Quick Basic es un lenguaje de programación estructurado y el algoritmo se representara en seudo código y/o diagrama de flujo.
1. Análisis del problema:
Requiere la clara definición del problema donde se indique que va hacer el programa y cual ve a ser el resultado.
Debe detallarse las especificaciones de entrada y salida,
Los requisitos que definen el análisis son :
Para ver el gráfico seleccione la opción “Descargar”
La ecuación de segundo grado se define algebraicamente como :
La solución general viene dada por la expresión algebraica : (Algoritmo)
periférico
1
Análisis del problema
2
Def. del problema
Hallar raíces ecua. 2do grdo
3
Especif. de entrada
coeficientes a, b, c
Teclado
4
Especif. de salida
X1, X2
Pantalla
Impresora
Entrada: por teclado
coef
Descripción
Codificación en QBasic
a
team. cuadrático
INPUT “Coef a =”;A
b
term. lineal
INPUT “Coef b =”;B
c
term. independiente
INPUT “Coef c =”;C
Calculo
Expresión algebraica
Codificación en QBasic
X1=((-B+SQR(B^2-4*A*C))
X2=((-B-SQR(B^2-4*A*C))
Proceso:
Salida: Visualización de :Datos de entrada: A,B,C
Datos procesados: Raices: X1, X2
Variable
Significado
Codificación en QBasic
A,B,C
Coef
PRINT”A=”;A; “B=”;”C=”;C
X1
primera raíz
PRINT”X1=”;x1
X2
primera raíz
PRINT”X2=”;X2
2.Diseño del algoritmo.
Análisis de proceso implica que hace el programa.
Diseño implica como se hace o realiza la tarea (problema) solicitado
En el diseño:
El todo es la sumatoria de las partes.
Divide el todo en varias partes.
En la resolución de un problema complejo, se divide en varios sub problemas y seguidamente se vuelven a dividir los sub problemas en otros mas sencillos, hasta que puedan implementarse en el computador.
Esta característica define lo que se entiende como diseño descendente( Top-Down / Norte-Sur ) o diseño modular.
El proceso de ruptura del problema en cada etapa se llama refinamiento sucesivo.
Cada problema se resuelve mediante un modulo (subprograma) y tiene un solo punto de entrada y un solo punto de salida.
Un programa bien diseñado consta de un programa principal (modulo de nivel mas alto) que llama a subprogramas (módulos de nivel mas bajo), que a su vez pueden llamar otros sub programas.
Los programas que se estructuran de esta forma, se dicen que tienen diseño modular y el método de romper el programa en modos pequeños se llama programación modular.
Los módulos pueden ser planificados, codificados, compilados y depurados independientemente pueden ser intercambiados entre si.
Este proceso implica la ejecución de los siguientes pasos:
1
programar un modulo
2
comprobar un modulo
3
depurar el modulo
4
combinar el modulo con módulos anteriores
este proceso convierte el resultado del análisis del problema en un diseño modular con refinamientos sucesivos que permiten una traducción a un lenguaje que se denomina diseño del algoritmo.
El algoritmo se puede representar por medio de dos formas :
Pseudo código
Diagrama de flujo:
Pseudo código: es el lenguaje de especificación de algoritmos y tiene una estructura: Las instrucciones se escriben en ingles o en palabras similares al ingles o español que facilitan la escritura de programación
Para la resolución de una ecuación de segundo grado se escribiría
inicio
Introducir coeficientes a, b y c
Imprimir títulos primera raíz, segunda raíz, no tiene solución,
Calcular raíz 1 y raíz 2
Imprimir raíz 1 y raíz 2
Fin
Diagramas de flujo (flows charts): Es la representación grafica del algoritmo; según la ANSI consta de una simbologia , que tiene los siguientes significados:
Para ver el gráfico seleccione la opción “Descargar” del menú superior
Símbolos del Diagrama de flujo
Codificación :
Programación:
Windows/Dos/
Quick Basic = Editor de texto.
Programa: definición:
conjunto de datos y sentencias:
Un programa tiene la forma
Para ver el gráfico seleccione la opción “Descargar”
En el editor de Quick Basic se escribiría codificado el seudo código
que tendría la forma:
REM Programa para calcular las soluciones
REM de una ecuacion de segundo grado
PRINT “Escriba los valores de A, B y C”
C$=”Calculos”
INPUT ” A,B,C”, A, B, C
R = (B ^ 2 - 4 * A * C) ^ .5
LET X1 = (-B + R) / (2 * A)
LET X2 = (-B + R) / (2 * A)
PRINT
PRINT ” A=”; A, ” B=”; B, “C=”; C
PRINT “X1=”; X1, “X2=”; X2
PRINT
END
En el Menú
Ejecutar
En la pantalla veríamos:
Mandatos e instrucciones:
Mandato (command): es una orden aislada de efecto inmediato.
Ejemplo:
Mandato
Descripción
RUN
Ordena la ejecución de un programa.
LIST
Escribe En la pantalla el listado del programa
SAVE.
Guarda, graba el programa como un archivo de extensión BAS en el disco
Instrucción: es una orden contenida en un programa.
Ejemplo:
Instrucción
Descripción
PRINT
Escribe en pantalla.
INPUT
Introduce (entra datos)
Edición de un programa: un programa esta formado por líneas secuenciales que se ejecutan en forma descendente (Up Down)
Para dar por terminada una línea se pulsa la tecla Enter (Return) en cualquier parte de la misma. Para cambiar una línea basta volver a teclearla.
Se puede corregir una línea (borrar, rescribir ) en pantalla o bien con el mandato EDIT.
Se pueden incluir varias instrucciones en una misma línea, separándolos por dos puntos.
Una línea de pantalla (cuarenta u ochenta posiciones) es diferente de una línea de programa (doscientos cincuenta y seis posiciones).
Modo Directo:
Modo Programa
Run
Ventana activa
Ventana inmediata
mandato
Descripción
CLS
borra la pantalla
Recomendaciones:
Todo programa debe estar documentado con comentarios; la primera línea debe contener el titulo del programa. Los comentarios deben de ir precedidos de la palabra clave REM o de un apostrofo ( ‘ )
Si una línea ya tiene otras instrucciones, el comentario debe ir al final de la línea.
Los comentarios solo aparecen en el listado del programa y no aparecen escritos en la pantalla durante la ejecución.
Constantes:
QBasic, trabaja con dos tipos de datos:
Datos
Tipos
numéricos:
Enteros (INT)
Enteros largos (LNG)
de simple precisión (SGL)
de doble precisión (DBL)
alfanuméricos
hileras o cadenas (STR)
fila de caracteres en ASCII ( en parte del teclado )
Las constantes alfanuméricas pueden ser enteras o fraccionarias, se representan en forma decimal; se puede emitir el cero a la izquierda del punto decimal. Ejemplo
3452
-12.67
.23
+12345
Estos son ejemplos de valores numéricos de punto fijo; se puede emplear una notación de punto flotante.
Mantisa
letra
exponente
1,23456E+15
123456.0000000000
1.234567890789456D–10
0.000000000123456789012456
El numero máximo de cifras significativas con que se trabaja es:
6 para la precisión simple (SNG)
16 para la precisión doble (DLB)
En las constantes de punto fijo hay que añadir el carácter #
Las constantes alfanuméricas son hileras de caracteres; se escriben entre comillas, Ej. “Hola ” ; ” A47EC
Variables vectores y matrices:
Una variable es una zona de memoria que almacena un dato
X
R
A
M
DIA $
Peso
-23.5
lunes
80
Una variable se identifica mediante un nombre. El nombre de una variable numérica debe empezar por una letra y puede ir sucedido de otras letras y / o otros dígitos (X, A, B1, peso, T341)
Una variable alfanumérica debe terminar con el carácter $ (x$, a23$, dias$,)
Están terminantemente prohibidas los nombres de variables que contengan palabras claves de Basic (PRUN, LIST, NIF$,)
Las variables de precisión doble y enteros se identifican añadiendo el carácter # o el carácter % , también se pueden declarar como
DEFDBL A
7. Documentación:
Los comentarios que se incluyan deben ser significativos
Documentación interna:
Va incluida dentro del código del programa fuente, por medio de comentarios que ayudan a la comprensión del código.
Todas las sentencias comienzan con la sentencia REM o su equivalente el carácter apostrofe ( ‘).
El programa en si no los necesita y los ignora. Hace que los programas sean comprensibles.
Ense˜nanza
Los algoritmos num´ericos
Jos´e Guerrero Grajeda¤
y
Rosa Margarita ´Alvarez Gonz´alez¤¤
¤ UNAM, UAQ
¤¤ UNAM
resumen
Se define el concepto de algoritmo. Se presentan varios casos de
problemas num´ericos, se dan sus soluciones en forma algor´ıtmica y
se agrega en cada caso una representaci´on en forma de diagrama
de flujo.
I. Algoritmos y algoritmos num ericos
La noci´on de algoritmo aparece en numerosas y dis´ımiles situaciones de la
vida cotidiana y es manejada por una gran cantidad de personas, algunas de
las cuales ni tan siquiera conocen su existencia. De manera informal, un algoritmo
puede definirse como una lista de instrucciones mediante las cuales
puede llevarse a cabo un determinado proceso. Consideremos el siguiente
Ejemplo 1. Descripci´on algor´ıtmica de un conjuro con el cual se logra
perjudicar a una persona no grata
Lista de instrucciones:
1 ) Tomar una cazuela de tama˜no peque˜no.
2 ) Llenarla hasta el borde con aceite de olivas.
3 ) Coger, a la hora de Saturno, tres ramas de laurel cerezo y colocarlas
formando una Cruz de Caravaca sobre la superficie del aceite.
4 ) Pronunciar con el coraz´on henchido de odio el perjuicio que quiere
causarse, y el nombre de la persona odiada.
5 ) Esperar el cumplimiento de los efectos del conjuro antes de dos lunas. ²² ² ² ² ²
LOS ALGORITMOS NUM´ERICOS
Un diagrama que ilu straCeOl Malg#IEorNitZmOo an terior se da a continuaci´on:
Tomar una
cazuela peque˜na
#
Llenarla con
aceite de oliva
#
Coger las tres ramas
de laurel cerezo
#
Colocarlas formando
una Cruz de Caravaca
#
Pronunciar
maldici´on y nombre
#
Esperar
# FINAL.
Al igual que para este ejemplo tomado de la “bot´anica oculta”, pueden
construirse algoritmos sobre cuestiones tales como: descripci´on de un trayecto
para transportarse de Xochimilco al z´ocalo, instrucciones a seguir para
el canje de placas de un autom´ovil, el conocid´ısimo caso de la elaboraci´on
de una planilla de alta (o baja) cocina, etc´etera.
Bueno, pero ¿qu´e tiene que ver todo esto con el an´alisis num´erico? Pues
bien, resulta que s´ı tiene que ver, y mucho, dado que la noci´on de algoritmo
forma parte de la vida diaria de todo analista num´erico.
En efecto, sucede que diariamente este individuo maneja algoritmos y,
de entre ellos, algunos con caracter´ısticas especiales: algoritmos num´ericos.
Por un algoritmo relativo a un problema num´erico nosotros entendemos
una lista completa y detallada de operaciones a trav´es de las cuales una ²² ²² ² ² ²
J. GUERRERO GRAJEDA Y R. M. ´ALVAREZ GONZ´ALEZ
colecci´on de datos de entrada se transforma en una colecci´on de resultados
(datos de salida). Veamos algunos ejemplos:
Ejemplo 2. Algoritmo para el c´alculo de N!
Lista de instrucciones:
1 ) Fact à 1.
2 ) I Ã 2.
3 ) Fact à Fact ¤I.
4 ) I Ã I + 1.
5 ) Si I > N, continuar; si no ir a 3 ).
6 ) Terminar.
El diagrama asociado enC#eOsLtMeee#IcrEaNNsoZeOs com o sigue:
#
Fact à 1
#
I Ã 2
#
¡! Fact à Fact ¤I
#
I = I +1
no !!!#aaa aaIa>!N!!
# si
Escribir Fact 1A # FINAL. ²² ²² ²² ² ²
LOS ALGORITMOS NUM´ERICOS
Ejemplo 3. Algoritmo para el c´alculo del producto escalar de los vectores
x = (x1; x2; : : : ; xN); y = (y1; y2; : : : ; yN)
Lista de instrucciones:
1 ) Comienzo.
2 ) ProdXY Ã 0.
3 ) Para I = 1; 2; : : : ;N hacer
3.1 ) ProdXY Ã ProdXY + XI ¤ Y I.
4 ) Terminar.
Diagrama: C#OLMee#IrENNZO
#
ProdXY Ã 0
#
¡¡¡¡¡¡¡¡!
I Ã 1
I > N
I Ã I + 1
$%
si
#
no
#
ProdXY Ã ProdXY +XI ¤Y I
Escribir X(I) # 1A FINAL.
Los siguientes algoritmos son un poco m´as complicados.
Ejemplo 4. Algoritmo de sustituci´on hacia atr´as
Se trata de un procedimiento usado ampliamente para resolver sistemas de
ecuaciones lineales, cuando la matriz del sistema es triangular superior; esto ²² ²² ²² ²² ²
J. GUERRERO GRAJEDA Y R. M. ´ALVAREZ GONZ´ALEZ
es, cuando el sistema tiene la forma
®11×1 + ®12×2 + ¢ ¢ ¢ + ®1nxn = b1
®22×2 + ¢ ¢ ¢ + ®2nxn = b2
…
…
®n¡1;n¡1xn¡1 + ®n¡1;nxn = bn¡1
®n;nxn = bn
Es claro que en este caso, xn puede obtenerse de manera inmediata como
sigue:
xn = bn
®n;n
;
de donde resulta
xn¡1 =
bn¡1 ¡ ®n¡1;nxn
®n¡1;n¡1
:
De manera an´aloga se obtiene
xn¡2 =
bn¡2 ¡ (®n¡2;n¡1xn¡1 + ®n¡2;nxn)
®n¡2;n¡2
bn¡2 ¡ Pn
k=n¡1 ®n¡2;kxk
®n¡2;n¡2
:
En general se tiene
xi = bi ¡ Pn
k=i+1 ®ikxk
®ii
:
Con esto, nuestro algoritmo queda como sigue:
Lista de instrucciones:
1 ) xn = bn=®n;n.
2 ) Para i = n ¡ 1; n ¡ 2; : : : ; 1, hacer:
2.1 ) xi = ®¡1
ii [biPn
k=i+1 ®ikxk].
3 ) Terminar.
² ² ² ² ² Tenemos el siguiente diagrama asociado:
² ² ² ² ²
LOS ALGORITMOS NUM´ERICOS
C#OLMe#eIEr NnZO
#
xk à bn=®nn
#
¡¡¡¡¡¡¡!
i à n ¡ 1
i n
k à k + 1
$%
si
no
#
Sum à Sum+®ik ¤ xk
Escribir xi 1A # FINAL. #
xi à ®¡1
ii (bi ¡ Sum)
Ejemplo 5. Factorizaci´on de Horner
El m´etodo de Horner para la evaluaci´on de polinomios es ampliamente conocido
debido a su eficiencia, y en t´erminos generales consiste en lo siguiente:
Evaluar el polinomio
Pn(x) = anxn + an¡1xn¡1 + ¢ ¢ ¢ + a1x + a0;
de tal forma que el n´umero de multiplicaciones efectuadas sea n.
Puede checarse f´acilmente que si el polinomio anterior es evaluado en la
forma como aparece, el n´umero de multiplicaciones requeridas est´a dado
por
nX
i=1
i = n(n + 1)
2 »
n2
2 :
Para reducir el n´umero de multiplicaciones, lo que Horner propone es ²² ² ² ² ²
² ² ² ² ²
J. GUERRERO GRAJEDA Y R. M. ´ALVAREZ GONZ´ALEZ
factorizar P(x) tantas veces como sea posible, seg´un el siguiente esquema:
supongamos que:
P2(x) = ax2 + bx + c
#
P2(x) = x(ax + b) + c:
N´otese que solamente son necesarias dos multiplicaciones.
An´alogamente, si
P3(x) = ax3 + bx2 + cx + d
#
P3(x) = x(ax2 + bx + c) + d
#
P3(x) = x(x(ax + b) + c) + d:
En este caso, s´olo son necesarias tres multiplicaciones para evaluar P3(x).
En general se tiene
Pn(x) = anxn + an¡1xn¡1 + ¢ ¢ ¢ + a1x + a0
#
…
#
Pn(x) = x³x(¢ ¢ ¢ x(anx + an¡1) + an¡2) ¢ ¢ ¢ + a1´+ a0
con un total de n multiplicaciones en la evaluaci´on de Pn(x).
Obs´ervese que en la pr´actica, el m´etodo se Horner se reduce a calcular
t´erminos de la forma
bx + a;
donde a es un coeficiente de Pn(x) y b es obtenido como un t´ermino de la
misma forma anterior.
De nuestra discusi´on resulta finalmente el algoritmo para evaluar Pn(x)
con s´olo n multiplicaciones.
²² ²² ² ² ²
² ² ² ² ²
LOS ALGORITMOS NUM´ERICOS
Lista de instrucciones:
1 ) b à an.
2 ) Para i = n ¡ 1; n ¡ 2; : : : ; 1; 0, hacer:
2.1 ) b à b ¤ x + ai.
3 ) Pn(x) Ã b.
Damos en Cs#eOgLuMeide#IraENNunZOdiagr ama representativo:
#
b à an
#
¡¡¡¡!
i à n ¡ 1
i
