viernes, 30 de noviembre de 2012
jueves, 29 de noviembre de 2012
Unidad
III. Relaciones y grafos.
|
EJERCICIO 4.1
Considerando las
tres familias dado en la figura 4.1
Fred y Mavis
John y Mar
Alice
Ken y
Sue Mike
Penny
Jane Fiona Alan
Figura 4.1
Escribe abajo el
orden de las parejas correspondientes de la siguiente relación en la serie P de
las personas de estas tres familias.
(a) R = {(x, y): x
es un abuelo de y}
(b) S= {(x, y): x
es una hermana de y}
SOLUCION
(a) R
contenido del orden de las parejas:
(Fred, Jane),(Fred,Fiona),(Fred,Alan),(John,Jane),(John,Fiona)
y (John,Alan).
(b) S contenido
del orden de las parejas:
(Sue,Penny),(Penny,Sue),(Jane,Fiona),
(Fiona,Jane ), (Alice,Ken),(Sue,Mike), (Penny,Mike),(Jane,Alan) y (Fiona,Alan).
EJERCICIO 4.2
Escribe el orden
de las parejas correspondientes de las siguientes relaciones binarias entre A=
{1, 3, 5, 7} y B= {2, 4, 6}:
(a) U = {(x, y): x
+ y = 9}
(b) V = {(x, y):
x < y}
SOLUCIÓN
(a) U contenido
del orden de las parejas (3,6), (5,4) y (7,2).
(b) V contenido
del orden de las parejas (1,2), (1,4), (1,6), (3,4), (3,6) y (5,6).
EJERCICIO 4.3
De la
siguiente relación definida en A= {1, 2, 3, 4, 5,6}:
R= {(x, y): x es
un divisor de y}
Escribe abajo el
orden de las parejas correspondientes de R.
SOLUCION
R contenido de
parejas:
(1,1),(1,2),(1,3),(1,4),(1,5)(1,6),(2,2),(2,4),(2,6),(3,3),(3,6),(4,4),(5,5)
y (6,6).
EJERCICIO 4.4
Hallar la relación
de la dirección en la representación grafica de R en el ejemplo
4.3.
SOLUCION
Entonces la
relación de las parejas de R es. {1, 2, 3, 4, 5,6} y la dirección de la
grafica tiene seis vértices. Dado el diagrama correspondiente que está en la
figura 4.3.
La relación de las
parejas son los números y las vértices el total de las flechas.
EJERCICIO 4.5
La relación R en
las parejas de A= {a, b, c,d) tiene la siguiente representación matriz donde
las filas y las columnas deben de poner el nombre de los elementos de A en el
orden dado.
F T
T F
F F
T
martes, 27 de noviembre de 2012
UNIDAD III. RELACIONES Y GRAFOS.
USO DE RELACIONES.
USO DE RELACIONES.
PRODUCTO CARTESIANO
PARES
ORDENADOS: intuitivamente un par ordenado (a,b) es un par de objetos en el cual
el orden en el que estos se consideran debe ser: primero a y después b . Las
letras a y b se llaman la primera y la segunda componentes, respectivamente, de
la pareja ordenada.
Dos pares
ordenados (a, b) y (c, d) son iguales si solo si
a = c y b =
d
PRODUCTO
CARTECIANO: dados dos conjuntos A y B se llama producto cartesiano (o conjunto
producto) de A y B, al conjunto de todos los pares ordenados (a, b) de tal
forma que la primera componente a pertenece al conjunto A y la segunda
componente b es elemento del conjunto B. Este conjunto se denota por A × B y se
lee “A producto cartesiano de B”
Simbólicamente
A × B = {(a,
b) | a ? A ? b ? B}
Ejemplos
a) Si A =
{a, b, c} ; B = {x, y}
A × B = =
{(a, x), (a, y), (b, x), (b, y), (c, x), (c, y)}
Nótese que
el conjunto tiene seis elementos
b) Si A =
{1, 2, 3} ; B = {4, 5, 6}
A × B = =
{(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6)}
B × A = =
{(4, 1), (4, 2), (4, 3), (5, 1), (5, 2), (5, 3), (6, 1), (6, 2), (6, 2)}
Nótese que
en este ejercicio cada conjunto tiene nueve elementos, y que A × B ? B × A
En general,
si n(A) = p y n(B) = q entonces, n(A × B) = n(B × A) = pq
Además, el
producto cartesiano No es conmutativo, es decir A x B ? B x A a menos que A = B
o que uno de los conjuntos sea vacío.
Si A y B son
conjuntos finitos su producto puede ser representado en el plano cartesiano
colocando el conjunto A en el eje horizontal, y B en el eje vertical. A cada
par ordenado (a,b) le corresponde un punto del plano.
Por ejemplo,
Si A = {a1, a2, a3, a4} y B = {b1, b2, b3} , el conjunto producto consta de 12
elementos o parejas, y en su representación gráfica deben aparecer 12 puntos
que forman un red, así:
Otra forma
de representar el producto A × B es mediante un diagrama de árbol.
Por ejemplo,
si A = {1, 2 ,3} y B = {a, b}, la gráfica arborescente correspondiente a A × B,
es:
Relacion binaria
Una relación
(binaria) R de un conjunto X a un conjunto Y es un subconjunto del producto
cartesiano X × Y. si (x, y) ? R escribimos xRy y decimos que x esta relacionado
con y.
Una relación
que es reflexiva, simétrica y transitiva en un conjunto X se llama relación de
equivalencia sobre X.
Ejemplos
a) Sean los
conjuntos X = {a, b, c, d} y Y = {1, 2, 3, 4}, definir una relación R de X en Y
y determinar el dominio de R y lel rango de R.
R = {(a, 1),
(b, 2), (c, 3), (d, 4)}
El dominio
se define por el conjunto {x ? X/(x, y) ? R para algún y ? Y}
dominio de R
es el conjunto {a, b, c, d}
b) La
relación R sobre X = {1, 2, 3, 4} esta definida por “(x, y) ? R si x = y“ es:
R = {(1, 1),
(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
el dominio
de R es el conjunto {1, 2, 3, 4}
el rango de
R es el conjunto {1, 2, 3, 4}
se concluye
que: el dominio y el rango son iguales porque la relación está definida sobre
el mismo conjunto X.
La digráfica
de la relación R es la siguiente:
Matrices de relaciones
Este tema lo
encontramos en la página 132, sección 3.3. Se describirá brevemente como formar
una matriz de relación y se realizara ejemplos. Una matriz es una manera
conveniente de representar una relación R de X a Y. Se etiquetan los renglones
con elementos de X (en algún orden arbitrario), y se etiquetan las columnas con
elementos de Y (orden arbitrario). Luego el elemento en el renglón x y la
columna y se hace igual a 1 si xRy, y 0 de otra manera. Esta matriz se llama
matriz de la relación R.
Ejemplos:
Formar la
matriz de relación de los siguientes conjuntos:
a)
R = {(1, b),
(1, d), (2, c), (3, c), (3, b), (4, a)}
Donde X =
{1, 2, 3,4} y Y = {a, b, c, d}
Considerando
los ordenes: 1, 2, 3,4 y a, b, c, d tenemos la matriz:
b)
X = {2, 3,
4} Y = {5, 6, 7, 8}
Considerando
las ordenes: 2, 3, 4 y 5, 6, 7,8; definida por xRy si x divide a y
GRAFOS
Existen
varios tipos de grafos:
a) Un GRAFO
NO DIRIGIDO G consiste en un conjunto V de vértices (o nodos) y un conjunto E
de aristas (o arcos) tal que cada arista e ? E se asocia con un par no ordenado
de vértices. Entonces se puede decir que si existe una arista e entre un par de
vértices v y w, esta puede ser igual a: e = ( v, w) o e = ( w, v)
Un grafo
esta formado de vértices y aristas (lados), por lo tanto G = {V, E}
Los vértices
del grafo G son: V_1, V_2, V_3, V_4 entonces V = {V_1, V_2, V_3, V_4}
Las aristas
del grafo son: e_1, e_2, e_3, e_4 entonces E = {e_1, e_2, e_3, e_4}
Entonces
podemos decir que G = {{V_1, V_2, V_3, V_4}, {e_1, e_2, e_3, e_4}}
Como el
grafo G no tiene lazos ni lados paralelos entonces es un grafo simple.
Otro ejemplo
de grafo no dirigido es el siguiente:
Clasificacion ce tipos de relaciones
a) Reflexiva
La relación
R del ejemplo anterior dada por:
R = {(1, 1),
(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
se dice que
es reflexiva por que cada elemento x ? X, (x, x) ? R; los pares ordenados (1,
1), (2, 2), (3, 3) y (4, 4) están en R. Si observamos la digráfica de la
relación reflexiva, encontramos que tiene un lazo sobre cada vértice.
b) Simétrica
Tomando la
relación R del ejemplo anterior dada por:
R = {(1, 1),
(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
“no es
simétrica”, por cuanto no cumple la definición que dice: “si para cada x, y ?
X, si (x, y) ? R, entonces (y, x) ? R”.
c)
Transitiva
Tomando la
relación R del ejemplo anterior dada por:
R = {(1, 1),
(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
“es una
relación transitiva R sobre el cojunto X”, por cuanto cumple la definición que
dice: “x, y, z ? X, si (x, y) y (y, z) ? R, entonces (x, z) ? R”.
Específicamente
tenemos (1, 2), (2, 3) se tiene (1, 3); (1, 3), (3, 4) se tiene (1, 4); (2, 3),
(3, 4) se tiene (2, 4) todos pertenecen a R.
d)
Antisimétrica
Tomando la
relación R del ejemplo anterior dada por:
R = {(1, 1),
(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
“la relación
R sobre el cojunto X es antisimétrica”, por cuanto cumple la definición que
dice para toda: “x, y X, si (x, y) ? R y x ? y, entonces (x, y) ? R”.
Específicamente tenemos (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)
pertenecen a R, pero (2, 1), (3, 1), (4, 1), (3, 2), (4, 2), (4, 3) no
pertenecen a R.
e) Inversa
Tomando la
relación R del ejemplo anterior dada por:
R =
{(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}
La relación
inversa de R que se denota por R-1, esta dada por:
R - 1 = {(1,
1), (2, 1), (3, 1), (4, 1), (2, 2), (3, 2), (4, 2), (3, 3), (4, 3), (4, 4)}
Ejercicio 1
A partir del
siguiente dígrafo, resuelva las siguientes instrucciones:
1. Escriba R
como un conjunto de pares ordenados
R ={(3, 5),
(4, 4), (5, 5), (3, 5), (3, 4), (4, 5)}
2. Escriba
una relación reflexiva sobre G1
R = {(3,3),
(4,4), (5,5)}
3. Escriba
una relación simétrica sobre G1
R = {(3,3),
(4,4), (5,5)}
4. Escriba
una relación antisimétrica sobre G1
R = {(3, 5),
(3, 4), (4, 5)}
5. Escriba
una relación transitiva sobre G1
R ={(3, 4),
(4, 5), (3, 5)}
6. Escriba
R-1 como un conjunto de pares ordenados
R-1 = {(3,
3), (4, 3), (4, 4), (5, 4), (5, 5), (5, 3)}
EMPLEO DE GRAFOS
Podemos clasificar los grafos en dos grupos: dirigidos y no dirigidos.
En un grafo no dirigido el par de vértices que representa un arco no está
ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo
arco. En un grafo dirigido cada arco está representado por un par ordenado de
vértices, de forma que y representan dos arcos diferentes.
Ejemplos
G1 = (V1, A1)
V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}
G2 = (V2, A2)
V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)}
G3 = (V3, A3)
V3 = {1, 2, 3} A3 = { <1, 2>, <2, 1>, <2, 3> }
Gráficamente estas tres estructuras de vértices y arcos se pueden
representar de la siguiente manera:
Algunos de los principales tipos de grafos son los que se muestran a
continuación:
Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese
grado es k lo llamaremos k-regular.
Por ejemplo, el primero de los siguientes grafos es 3-regular, el
segundo es 2-regular y el tercero no es regular
Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos
conjuntos disjuntos de modo que no haya adyacencias entre vértices
pertenecientes al mismo conjunto
Ejemplo.- de los dos grafos siguientes el primero es bipartito y el
segundo no lo es
Grafo completo: Aquel con una arista entre cada par de vértices. Un
grafo completo con n vértices se denota Kn.
A continuación pueden verse los dibujos de K3, K4, K5 y K6
Un grafo bipartito regular: se denota Km,n donde m, n es el grado de
cada conjunto disjunto de vértices.
A continuación ponemos los dibujos de K1,2, K3,3, y K2,5
Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo
componen no están conectados, esto es, que son vértices aislados.
Grafos Isomorfos: Dos grafos son isomorfos cuando existe una
correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos
de estos quedan unidos por una arista en común.
Caminos
Sean x, y " V, se dice que hay un camino en G de x a y si existe
una sucesión finita no vacía de aristas {x,v1}, {v1,v2},..., {vn,y}. En este
caso
x e y se llaman los extremos del camino
El número de aristas del camino se llama la longitud del camino.
Si los vértices no se repiten el camino se dice propio o simple.
Si hay un camino no simple entre 2 vértices, también habrá un camino
simple entre ellos.
Cuando los dos extremos de un camino son iguales, el camino se llama
circuito o camino cerrado.
Llamaremos ciclo a un circuito simple
Un vértice a se dice accesible desde el vértice b si existe un camino
entre ellos. Todo vértice es accesible respecto a si mismo
Camino.
Es un conjunto de vértices y aristas que llevan a un punto del grafo.
Clasificación de grafos.
Podemos clasificar los grafos en dos grupos: dirigidos y no dirigidos.
Grafo regular: Aquel con el mismo grado en todos los vértices
Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos
conjuntos disjuntos de modo que no haya adyacencias entre vértices
pertenecientes al mismo conjunto.
Grafo completo: Aquel con una arista entre cada par de vértices.
Un grafo bipartito regular: se denota Km,n donde m, n es el grado de
cada conjunto disjunto de vértices.
Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo
componen no están conectados, esto es, que son vértices aislados.
Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia
biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan
unidos por una arista en común.
Grafos Platónicos: Son los Grafos formados por los vértices y aristas de
los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el
cubo, el octaedro, el dodecaedro y el icosaedro.
GRAFOS EULERIANOS.
Aquellos que contienen un camino euleriano.
GRAFOS CONEXOS
Un grafo se puede definir como conexo si cualquier vértice V pertenece
al conjunto de vértices y es alcanzable por algún otro.
ÁRBOLES
Un árbol se define como un tipo de grafo que no contiene ciclos, es
decir es un grafo también acíclico, pero a su vez es conexo.
BOSQUES DE ÁRBOLES.
Los bosques de árboles son un caso similar a los árboles, son acíclicos,
pero no son conexos.
RECORRIDO DE UN GRAFO.
Recorrer un grafo significa tratar de alcanzar todos los nodos que estén
relacionados con uno que llamaremos nodo de salida. Las dos principales
técnicas para recorrerlo son: recorrido en anchura y recorrido en profundidad.
GRAFO
Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (arcs en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole. Un grafo simple está formado por dos conjuntos:
Un conjunto V de puntos llamados vértices o nodos.
‘’‘Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados. De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos.’‘’
GRAFOS DIRIGIDOS
Un grafo en el cual toda arista es dirigida se denominará "digrafo" o bien "grafo dirigido". Un grafo dirigido o dígrafo consiste de un conjunto de vértices V y un conjunto de arcos A.
Los vértices se denominan nodos o puntos; los arcos también se conocen como aristas o líneas dirigidas que representan que entre un par de vértices existe una relación univoca.
GRAFOS NO DIRIGIDOS:
Un grafo en el cual todas las aristas son no dirigidas se denominará "grafo no dirigido". El grafo no dirigido es aquel que no tiene sentido su arista. Un grafo no dirigido G representa elementos, y una arista (v, w) representa una incompatibilidad entre los elementos v y w.
Si en un Grafo hay aristas dirigidas y aristas no dirigidas, entonces el grafo se denomina "mixto".
NODO
Nodos (también llamados vértices) se representan con puntos en el grafo.
Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (arcs en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
Los grafos son artefactos matemáticos que permiten expresar de una forma visualmente muy sencilla y efectiva las relaciones que se dan entre elementos de muy diversa índole. Un grafo simple está formado por dos conjuntos:
Un conjunto V de puntos llamados vértices o nodos.
‘’‘Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados. De una manera más informal podemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, denominados aristas o arcos.’‘’
GRAFOS DIRIGIDOS
Un grafo en el cual toda arista es dirigida se denominará "digrafo" o bien "grafo dirigido". Un grafo dirigido o dígrafo consiste de un conjunto de vértices V y un conjunto de arcos A.
Los vértices se denominan nodos o puntos; los arcos también se conocen como aristas o líneas dirigidas que representan que entre un par de vértices existe una relación univoca.
GRAFOS NO DIRIGIDOS:
Un grafo en el cual todas las aristas son no dirigidas se denominará "grafo no dirigido". El grafo no dirigido es aquel que no tiene sentido su arista. Un grafo no dirigido G representa elementos, y una arista (v, w) representa una incompatibilidad entre los elementos v y w.
Si en un Grafo hay aristas dirigidas y aristas no dirigidas, entonces el grafo se denomina "mixto".
NODO
Nodos (también llamados vértices) se representan con puntos en el grafo.
RECURSIVIDAD
La recursividad
forma parte del repertorio para resolver problemas en Computación y es de los
métodos más poderosos y usados. Los algoritmos recursivos ofrecen soluciones
estructuradas, modulares y elegantemente simples. La recursividad es un
concepto fundamental en matemáticas y en computación. Una definición recursiva
dice cómo obtener conceptos nuevos empleando el mismo concepto que intenta
describir.
En toda situación
en la cual la respuesta pueda ser expresada como una secuencia de movimientos,
pasos o transformaciones gobernadas por un conjunto de reglas no ambiguas, la
fórmula recursiva es un buen candidato para resolver el problema. Los
razonamientos recursivos se encuentran en la base misma de las matemáticas
porque son necesarios para describir conceptos centrales como el de número:
Ejemplo:
1. Factorial
Definición:
factorial (n) = n! si n > 0
factorial (n) = n*n-1*n-2* ... * 1 si n > 0
el valor de 0! se define como
factorial (0) = 1
Su definición
recursiva es:
factorial (n) = 1 si n = 0
factorial (n) = n* factorial (n-1) si n > 0
así para calcular
el factorial de 4:
factorial (4) = 4 * factorial (3) =
4 * 6 = 24
factorial (3) = 3 * factorial (2) =
3 *2 = 6
factorial (2) = 2 * factorial (1) =
2 * 1 = 2
factorial (1) = 1 * factorial (0) =
1 * 1 = 1
estática int
factorial (int n)
comienza
si n = 0 entonces
regresa 1
otro
regresa factorial (n-1)
* n
termina
Las definiciones
recursivas de funciones en matemáticas que tienen como argumentos números
enteros, se llaman relaciones de recurrencia. Forma de una ecuación de recurrencia:
coar
+c1ar-1 + c2ar-2 + ....+ ckar-k
= f(r) función matemática discreta
donde ci
son constantes, es llamada una ecuación de recurrencia de coeficientes
constantes de orden k, condicionada a que c0 y ck = 0.
Una definición
recursiva dice cómo obtener conceptos nuevos empleando el mismo concepto que
intenta definir.
El poder de la
recursividad es que los procedimientos o conceptos complejos pueden expresarse
de una forma simple.
Un razonamiento
recursivo tiene dos partes: la base y la regla recursiva de construcción. La
base no es recursiva y es el punto tanto de partida como de terminación de la
definición.
Ejemplo:
Base: La secuenciación, iteración condicional y selección son estructuras
válidas de control que pueden ser consideradas como enunciados.
Regla
recursiva: Las estructuras de control que se pueden formar combinando de
manera válida la secuenciación iteración condicional y selección también son
válidos.
Un conjunto de
objetos está definido recursivamente siempre que:
(B) algunos elementos del conjunto
se especifican explícitamente
(R) el resto de los elementos del
conjunto se definen en términos de los elementos ya definidos donde
(B) se llama base
(R) se llama cláusula recursiva
Observaciones:
1. El procedimiento
se llama a si mismo
2. El problema se
resuelve, resolviendo el mismo problema pero de tamaño menor
3. La manera en la
cual el tamaño del problema disminuye asegura que el caso base eventualmente se
alcanzará
La recursividad es
un método poderoso usado en inteligencia artificial, su poder es que algunos
conceptos complejos pueden expresarse en una forma simple. Una definición
recursiva difiere de una definición circular en que tiene una forma de escapar
de su expansión infinita. Este escape se encuentra en la definición o porción
no recursiva o terminal de la definición.
Las fórmulas
recursivas pueden aplicarse a situaciones tales como prueba de teoremas,
solución de problemas combinatorios, algunos acertijos, etc.
4. Definición recursiva para elevar un número a
una potencia: Un número elevado a la potencia cero produce la unidad; la
potencia de un número se obtiene multiplicándolo por sí mismo elevando a la
potencia menos uno. Por ejemplo:
32 = 3*(31) =
3*(3*30) = 3*(3*1)= 3*(3) = 9
estática int
potencia (int n, int k)
comienza
si k=0 entonces
regresa 1
otro
regresa n * potencia
(n,k-1
termina
5. Número de
Combinaciones
Recursivamente,
podemos definir el número de combinaciones de m objetos tomados de n, denotado
(n,m) para n> 1 y 0 < m < n por:
(n,m) = 1 si
m = 0 ó m = n ó n = 1
(n,m) = (n-1, m) +
(n-1,m-1) en otro
caso
estática int combinaciones (int n, int m)
comienza
si m = 0 o m = n o n = 1 entonces
regresa 1
otro
regresa combinaciones
(n-1,m) + combinaciones (n-1,m-1)
termina
Definición: Cuando una llamada
recursiva es la última posición ejecutada del procedimiento se llama
recursividad de cola, recursividad de extremo final o recursión de extremo de
cola.
Definición: Cuando un
procedimiento incluye una llamada a si mismo se conoce como recursión directa.
Definición: Cuando un
procedimiento llama a otro procedimiento y este causa que el procedimiento
original sea invocado, se conoce como recursión indirecta.
Al principio
algunas personas se sienten un poco incómodas con la recursividad, tal vez
porque da la impresión de ser un ciclo infinito, pero en realidad es menos
peligrosa una recursión infinita que un ciclo infinito, ya que una recursividad
infinita pronto se queda sin espacio y termina el programa, mientras que la
iteración infinita puede continuar mientras no se termine en forma manual.
Cuando un
procedimiento recursivo se llama recursivamente a si mismo varias veces, para
cada llamada se crean copias independientes de las variables declaradas en el
procedimiento.
ALGORITMOS RECURSIVOS
Un algoritmo recursivo es un algoritmo que expresa
la solución de un problema en términos de una llamada a sí mismo. La llamada a
sí mismo se conoce como llamada recursiva o recurrente.
Recursividad indirecta
Cuando en una subrutina hay llamadas a ella misma
se habla de recursividad directa, en contraposición, cuando se tienen varias
subrutinas y estas se llaman unas a otras formando ciclos se dice que la
recursión es indirecta.
Ejemplo:
1.-Da un algoritmo
recursivo para hallar an, donde a es el número real distinto de cero y n un
entero no negativo.
Solución:Podemos construir un
algoritmo recursivo basándonos en la definición recursiva de an.
Esta definición afirma que an+1 = a.an para n >
0 con la condición inicial a0 =
1. Para calcular an podemos usar sucesivamente la
regla recursiva para reducir el exponente hasta que se haga cero
|
Algoritmo 1 un algoritmo recursivo para hallar an
|
|
Procedure potencia (a número
real no nulo, n: entero no negativo)
If n = 0 the potencia (a,n):=1 Else potencia (a,n):=a.potencia (a,n-1) |
2.-Da un algoritmo
recursivo para calcular el máximo común divisor de dos enteros no negativos a y
b, a > b.
Solución: nos podemos basar en la
reducción mcd(a, b) = mcd (b mod a, a) y la condición mcd (0,b) = b cuando b
> 0.
|
Algoritmo 2 un algoritmo recursivo para hallar el
mcd (a, b)
|
|
Procedure mcd(a, b: entero no negativo, a<b)
If a = 0 the mcd (a,b):=b Else mcd (a, b):=mcd (b mod a,a) |
3.- Expresa el algoritmo de
búsqueda lineal como procedimiento recursivo
Solución: para buscar x en la sucesión a1, a2 …an
en el paso decimo comparamos x y ai. Si x = a entonces i es la posición de x.
es el caso contrario la búsqueda de x se reduce a buscar en la sucesión con un
elemento menos es decir la sucesión ai + 1, …..an.
|
Algoritmo 3 un algoritmo recursivo de búsqueda
lineal |
|
Procedure búsqueda (i, j, x)
If ai = x the Posicion :=i Else if i = j the Posicion :=0 Else busqueda (i+ 1, j, x |
4.- El procedimiento
recursivo del algoritmo 4 de el valor de n! cuando la entrada en un entero
positivo n
|
Algoritmo 4 un algoritmo recursivo para la
función factorial
|
|
Procedure factorial (n: entero
positivo)
If n= 1 the Factorial (n) :=1 Else factorial (n) :n. factorial (n-1) |
5.-
|
Algoritmo 5 un algoritmo recursivo para los
números de fibonacci
|
|
Procedure fibonacci (n entero
no negativo)
If n= 0 the Fibonacci (0) = 0 Else if n = 1 the Fibonacci(1) = 1 Else Fibonacci (n) = Fibonacci (n-1)+ Fibonacci (n-2) |
Un algoritmo se llama recursivo si resuelve un
problema reduciéndolo a un caso del mismo problema con cada dato de entrada más
pequeño
Funciones
Los números de fabanacci, f0, f1, f2…. De definen a
partir de las ecuaciones f0 = 0, f1 = 1 y fn = fn-1 + f n-2
Para n = 2, 3, 4, ….
Suscribirse a:
Entradas (Atom)