La notacin polaca es una manera de definir expresiones en las que el orden en la que aparecern l...

Page 1 of 6

Anuncios Google

VIDRASA Vuelos baratos

Suministramos niveles de burbuja (circulares, tubulares, etc) Seleccione entre varias compaias Busque el vuelo ms
www.vidrasa.com econmico
www.portalviajar.com

INSTITUTO TECNOLGICO DE MEXICALI

MATERIA:
PROGRAMACIN DE SISTEMAS II

TRABAJO:
REPORTE DE EXPOSICIN

TEMA:

http://usuarios.lycos.es/adaneliros/ 10/11/2006
La notacin polaca es una manera de definir expresiones en las que el orden en la que aparecern l... Page 2 of 6

NOTACIN POLACA Y PROCESOS RECURSIVOS

ALUMNOS:
ADAN ELIZARRARAZ ROSAS
EFRAIN BAUELOS

NOTACIN POLACA

La notacin polaca es una manera de definir expresiones en las que el orden en la que aparecern los operadores trae impl cita la prioridad.
Expresiones sin parntesis
Algoritmo:

1. Si es operando, PUSH(VP)
2. Si es operador,
2.1 Mientras prioridad(TOP(AUX))>=prioridad(operador)
POP(AUX) y PUSH(VP)
2.2 PUSH(AUX) del operador

http://usuarios.lycos.es/adaneliros/ 10/11/2006
La notacin polaca es una manera de definir expresiones en las que el orden en la que aparecern l... Page 3 of 6

3. Si es fin de expresion,
3.1 Mientras AUX no est vaca,
POP(AUX) y PUSH(VP)

Expresiones con parntesis

Algoritmo:

1. Si es operando, PUSH(VP)
2. Si es operador,
2.1 Mientras prioridad(TOP(AUX))>=prioridad(operador)
POP(AUX) y PUSH(VP)
2.2 PUSH(AUX) del operador
3. Si es (, PUSH(AUX) una marca
4. Si es ),
4.1 Mientras TOP(AUX) < > marca
POP(AUX) y PUSH(VP)
4.2 POP(AUX) para quitar la marca
5. Si es fin de expresion,
5.1 Mientras AUX no est vaca,
POP(AUX) y PUSH(VP)
Ejemplos:
Pascal Notacin Polaca
a+b-c ab+c-
a+b*c abc*+
a+b*c+d abc*+d+
(a+b)*c ab+c*
a+(b-c) abc-+
a*b+c ab*c+
a+b/c abc/+
(a+b)/c ab+c/

RECURSIVIDAD

http://usuarios.lycos.es/adaneliros/ 10/11/2006
La notacin polaca es una manera de definir expresiones en las que el orden en la que aparecern l... Page 4 of 6

La recursividad es algo bastante simple. Es un concepto en algn sentido parecido al de induccin. Los procesos
recursivos son los que se definen en funcin de s mismos. La idea es que muy frecuentemente, cuando tenemos que
resolver un problema, es bastante fcil mediante alguna operacin llevarlo a un caso ms simple de l mismo.

Por ejemplo, supongamos que tenemos que calcular n! ( n factorial, tpico ejemplo de recursividad). Para los que no
saben, n! es el producto 1.2.3...n. Una manera de hacerlo es con un bucle del tipo:

Function Factorial(n:LongInt):LongInt;
Var
k,P:LongInt;
Begin
P:=1;
For k:=1 To n do
P:=P*k;
Factorial:=P;
End;
A esto se le llama un proceso iterativo.
Una soluci n recursiva del mismo problema sera:
Function Factorial(n:LongInt):LongInt;
Begin
If n=0 Then Factorial:=1
Else Factorial:=n*Factorial(n-1);
End;

Esta solucin se basa en el hecho de que n! = n*(n-1)! Cuando n>0.

Noten que si no chequeara inicialmente si n=0, la funcin se invocara a s misma infinitas veces y nunca terminara de
ejecutarse (en realidad en poco tiempo dara error). Por eso, siempre una funcin recursiva tiene una condicin inicial en
la que no debe llamarse a s misma. Esta situacin es similar al primer caso de la induccin.
El propsito de la recursin es hacer cdigos ms simples y fciles de programar. Con un poco de prctica les aseguro
que adems son mucho ms fciles de entender.
En el caso del factorial, los dos mtodos no consumirn tiempos muy diferentes. Los procesos recursivos suelen ocupar
ms memoria y tardar un poquito ms que los iterativos porque cuando el compilador llama a una subrutina guarda
todas las variables locales en una zona de memora llamada "stack".
De todas maneras, los dos procedimientos de arriba se toman un tiempo proporcional a n para ejecutarse. La constante
de proporcionalidad es menor en el primero, pero eso no es algo de lo que debamos preocuparnos demasiado porque
depende tambin de la versin de nuestro compilador, de la computadora que usamos, etc.
Veamos otro ejemplo. La famosa sucesin de Fibonacci se define de la siguiente manera:

http://usuarios.lycos.es/adaneliros/ 10/11/2006
La notacin polaca es una manera de definir expresiones en las que el orden en la que aparecern l... Page 5 of 6

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2) cuando n>2

En este caso, la misma definicin del problema es recursiva. Es claro que la forma m s fcil de programarlo es
recursivamente.
La solucin recursiva sera:
Function Fibonacci(n:LongInt):LongInt;
Begin
if (n=1) or (n=2) Then Fibonacci:=1
else Fibonacci:=Fibonacci(n-1)+Fibonacci(n-2);
end;
Una soluci n iterativa se vera de la siguiente manera:
Function Fibonacci(n:LongInt):LongInt;
Var
a,b,aux,k:LongInt;
Begin
a:=1;
b:=1;
For k:=2 To n do
begin
aux:=b;
b:=a+b;
a:=aux;
end;
Fibonacci:=a;
end;

Este es un mejor ejemplo de cuanto ms simple puede ser el uso de tcnicas recursivas. En problemas ms
complicados la diferencia puede ser a n mayor.
Claro que esto tambin tiene su contracara. La implementacin recursiva de la sucesin de Fibonacci es mucho ms
lenta que la iterativa. Esta vez la diferencia va ms all de la forma en que acta el compilador. En realidad son dos
algoritmos totalmente diferentes.
La solucin iterativa simplemente hace lo que cualquier ser humano hara si tuviera que calcular el nmero n de la
sucesin de Fibonacci. Calcula uno por uno todos los nmeros hasta llegar al nmero n. El tiempo de ejecucin es
proporcional a n.
El orden en que se calculan las cosas en la solucin recursiva es muy distinta. Pensemos por ejemplo que hara si le
pedimos que calcule Fibonacci(5):

http://usuarios.lycos.es/adaneliros/ 10/11/2006
La notacin polaca es una manera de definir expresiones en las que el orden en la que aparecern l... Page 6 of 6

Al llamar a la funcin Fibonacci(5), esta llama a Fibonacci(4) y a Fibonacci(3) y suma sus resultados.
Fibonacci(4) llama a Fibonacci(3) nuevamente y a Fibonacci(2).
Fibonacci(3) se ejecutar entonces dos veces. Cada vez llamar a Fibonacci(2) y a Fibonacci(1).
Entonces Fibonacci(2) se ejecuta tres veces, y Fibonacci(1) se ejecuta dos.
Como se ve, algunos valores de la sucesin se calculan varias veces. No necesita ser mucho ms grande n para que las
repeticiones sean tantas que el algoritmo sea impracticable debido al tiempo que tarda y la memoria que consume.
Les recomiendo que implementen estos dos algoritmos y vean la diferencia. Cuando n>46 el resultado no entra en un
LongInt, si se quiere calcular Fibonacci(n) para n>46 se deben usar las tcnicas explicadas en la leccin sobre sumas
de enteros largos.
Como conclusin, los mtodos recursivos suelen ser muy buenos para simplificar la programacin. La pregunta que
debemos hacernos es si el tiempo que vamos a ahorrar programando es mayor al que vamos a perder en la ejecucin
del programa. Generalmente la respuesta es afirmativa.
Como ltimo ejemplo aqu hay uno que calcula la suma de las cifras de n:
Function SumDig(N:LongInt):LongInt;
begin
if N=0 Then SumDig:=0
else SumDig:=SumDig(N div 10) + (N mod 10);
end;

http://usuarios.lycos.es/adaneliros/ 10/11/2006