Objetivo: Aplicar las principales estructuras de datos no lineales.
Subtemas:
3.1. Recursividad.
3.2. Árboles.
3.3. Grafos.
Subtemas:
3.1. Recursividad.
3.2. Árboles.
3.3. Grafos.
Mostrando entradas con la etiqueta III UNIDAD. Mostrar todas las entradas
Mostrando entradas con la etiqueta III UNIDAD. Mostrar todas las entradas
sábado, 11 de octubre de 2014
viernes, 10 de octubre de 2014
Introducción
Las estructuras dinámicas
lineales de datos tienen grandes ventajas de flexibilidad sobre las
representaciones contiguas; sin embargo, tienen un punto débil: son listas
secuenciales, es decir, están dispuestas de modo que es necesario moverse a
través de ellas una posición a la vez (cada elemento tiene un siguiente elemento).
Esta linealidad es típica de cadenas, de elementos que pertenecen a una sola
dimensión: campos en un registro, entradas en una pila, entradas en una cola y
de nodos en una lista enlazada simple. Las estructuras de datos no lineales
resuelven los problemas que plantean las listas lineales y en las que cada elemento
puede tener diferentes siguientes elementos.
Terminología
RECURSIVIDAD
La
recursividad (recursión) es aquella propiedad que posee un método por la
cual puede llamarse a sí mismo. Aunque se puede utilizar la recursividad como
una alternativa a la iteración, una solución recursiva es, normalmente, menos
eficiente en términos de tiempo de computadora que una solución iterativa,
debido a las operaciones auxiliares que llevan consigo las invocaciones
suplementarias a los métodos; sin embargo, en muchas circunstancias, el uso de
la recursión permite a los programadores especificar soluciones naturales,
sencillas, que serían, en caso contrario, difíciles de resolver. Por esta
causa, la recursión es una herramienta poderosa e importante en la resolución
de problemas y en la programación. Diversas técnicas algorítmicas utilizan la
recursión, como los algoritmos divide y vence y los algoritmos de vuelta
atrás.
ÁRBOLES
Intuitivamente, el concepto
de árbol implica una estructura en la que los datos se organizan de modo que
los elementos de información están relacionados entre sí a través de ramas. El
árbol genealógico es el ejemplo típico más representativo del concepto de árbol
general.
Un árbol consta de un
conjunto finito de elementos, denominados nodos y de un conjunto finito
de líneas dirigidas, denominadas ramas, que conectan los nodos. El
número de ramas asociado con un nodo es el grado del nodo.
Un árbol es un conjunto de
uno o más nodos tales que:
1.
Hay un nodo diseñado especialmente llamado raíz.
2.
Los nodos restantes se dividen en n ≥ 0 conjuntos disjuntos, T1 ... Tn, tal que
cada uno de estos conjuntos es un árbol. A T1 ... Tn se les denomina subárboles
del raíz.
Si
un árbol no está vacío, entonces el primer nodo se llama raíz.
Además
del nodo raíz, existen muchos términos utilizados en la descripción de los
atributos de un árbol. En la Figura 13.3, el nodo A es el raíz. Utilizando el
concepto de árboles genealógicos, un nodo puede ser considerado como padre si
tiene nodos sucesores.
Estos
nodos sucesores se llaman hijos. Por ejemplo, el nodo B es el padre de
los hijos E y F. El padre de H es el nodo D. Un árbol puede representar
diversas generaciones en la familia. Los hijos de un nodo y los hijos de estos
hijos se llaman descendientes, y el padre y los abuelos de un nodo son
sus ascendientes. Por ejemplo, los nodos E, F, I y J son descendientes
de B. Cada nodo no raíz tiene un único padre y cada padre tiene cero o más
nodos hijos. Dos o más nodos con el mismo padre se llaman hermanos. Un
nodo sin hijos, tal como E, I, J, G y H se llama nodo hoja.
El
nivel de un nodo es su distancia al nodo raíz. La raíz tiene una distancia
cero de sí misma, por ello se dice que está en el nivel 0. Los hijos del nodo
raíz están en el nivel 1, sus hijos están en el nivel 2, y así sucesivamente.
Una cosa importante que se aprecia entre los niveles de nodos es la relación
entre niveles y hermanos. Los hermanos están siempre al mismo nivel,
pero no todos los nodos de un mismo nivel son necesariamente hermanos.
Los
árboles se utilizan para representar fórmulas algebraicas, para organizar
objetos en orden de tal forma que las búsquedas sean muy eficientes y en
aplicaciones diversas tales como inteligencia artificial o algoritmos de
cifrado. Casi todos los sistemas operativos almacenan sus archivos en árboles o
estructuras similares a árboles. Además de las aplicaciones citadas, los
árboles se utilizan en diseño de compiladores, procesado de texto y algoritmos
de búsqueda.
GRAFOS
Un
grafo es un conjunto de puntos (una estructura de datos) y un conjunto de
líneas, cada una de las cuales une un punto a otro. Los puntos se llaman nodos
o vértices y las líneas se llaman aristas o arcos. Se representa con el par G = (V, A).
Un
arco o arista representa una relación entre dos nodos, se representa por (u, v)
siendo u, v el par de nodos.
§ Lazo:
arista que une a un nodo(vértice) consigo mismo.
§ camino:
secuencia de uno o mas aristas que conectan dos nodos.
§ La
longitud de un camino es el número de aristas que comprende.
§ Se
dice que dos vértices son adyacentes si hay una arista que los une.
Un
grafo permite modelar relaciones arbitrarias entre objetos. Un grafo G = (V,A)
es un par formado por un conjunto de vértices o nodos, V, y un conjunto de
arcos o aristas, A.
Cada
arco es el par (u,w), siendo u, w dos vértices relacionados.
jueves, 9 de octubre de 2014
Mapa conceptual de recursividad
El siguiente mapa conceptual corresponde al tema de recursividad, esta actividad fue realizada en equipo y en el salón de clases.
miércoles, 8 de octubre de 2014
Reporte de investigación de recursividad
El siguiente enlace corresponde a la investigación del tema "Recursividad". Contiene la definición, los tipos, las características y ejemplos del tema.
clic aqui
clic aqui
martes, 7 de octubre de 2014
Práctica 1
Crear un programa que calcule el factorial de un número:
a) De forma recursiva
b) De forma iterativa
clic aqui
a) De forma recursiva
b) De forma iterativa
clic aqui
lunes, 6 de octubre de 2014
Práctica 2
Crear un programa que determine el producto de dos números naturales:
a) De forma recursiva
b) De forma iterativa
a) De forma recursiva
b) De forma iterativa
domingo, 5 de octubre de 2014
Práctica 3
Crear un programa que implemente la serie de Fibonacci:
a) De forma recursiva
b) De forma iterativa
clic aqui
a) De forma recursiva
b) De forma iterativa
clic aqui
sábado, 4 de octubre de 2014
Práctica 4
Esta práctica fue realizada en el salón de clases, y consistió en crear un método recursivo para determinar el mínimo común divisor de dos números.
viernes, 3 de octubre de 2014
Práctica 5
Crear un programa que implemente las Torres de Hanoi.
Nota: Las Torres de Hanoi es un juego oriental que consta de tres columnas o varillas llamadas origen, destino y auxiliar y una serie de discos de distintos tamaños.
Los discos están colocados de mayor a menor tamaño en la columna origen. El juego consiste en pasar todos los discos a la columna destino y dejarlos como estaban de mayor a menor. (el más grande en la base, el más pequeño arriba)
Las reglas del juego son las siguientes:
Sólo se puede mover un disco cada vez.
Para cambiar los discos de lugar se pueden usar las tres columnas.
Nunca deberá quedar un disco grande sobre un disco pequeño.
clic aqui
Nota: Las Torres de Hanoi es un juego oriental que consta de tres columnas o varillas llamadas origen, destino y auxiliar y una serie de discos de distintos tamaños.
Los discos están colocados de mayor a menor tamaño en la columna origen. El juego consiste en pasar todos los discos a la columna destino y dejarlos como estaban de mayor a menor. (el más grande en la base, el más pequeño arriba)
Las reglas del juego son las siguientes:
Sólo se puede mover un disco cada vez.
Para cambiar los discos de lugar se pueden usar las tres columnas.
Nunca deberá quedar un disco grande sobre un disco pequeño.
clic aqui
jueves, 2 de octubre de 2014
Práctica 6
Crear un programa que implemente las operaciones aritméticas básicas (haciendo uso de la recursividad):
a) Suma
b) Resta
c) Multiplicación
d) División
clic aqui
a) Suma
b) Resta
c) Multiplicación
d) División
clic aqui
miércoles, 1 de octubre de 2014
Práctica 7
Crear un programa que implemente un menú con las siguientes opciones:
a) Potencia n de un número x.
b) Factorial de un número.
c) Serie de Fibonacci.
d) Producto de dos números naturales.
clic aqui
a) Potencia n de un número x.
b) Factorial de un número.
c) Serie de Fibonacci.
d) Producto de dos números naturales.
clic aqui
martes, 30 de septiembre de 2014
domingo, 28 de septiembre de 2014
Crucigrama de la terminología de árboles
La siguientes imágenes corresponden al crucigrama del tema de árboles, el cual contiene los conceptos básicos del tema.
sábado, 27 de septiembre de 2014
Cuestionario de árboles
Este cuestionario fue realizado en clase, y consistió en contestar un cuestionario de árboles.
viernes, 26 de septiembre de 2014
Actividad de árboles
En esta actividad realizada en el salón de clases, pusimos en práctica los recorridos en un árbol, y un ejercicio acerca de la teoría de conjuntos, la cual es muy utilizada en árboles y grafos.
jueves, 25 de septiembre de 2014
Árbol binario ordenado
Esta actividad consistió en crear un árbol binario ordenado a partir de una lista de números dados.
miércoles, 24 de septiembre de 2014
Práctica 9
Crear un programa en java que cumpla con los siguiente:
a) Crear un árbol binario de letras.
b) Explicar el método implementado
clic aqui
a) Crear un árbol binario de letras.
b) Explicar el método implementado
clic aqui
martes, 23 de septiembre de 2014
Práctica 10
Crear un árbol binario a partir de la expresión (a+b)/(c-d), e imprimir cualquiera de los tres recorridos.
clic aqui
clic aqui
lunes, 22 de septiembre de 2014
Práctica 11
Crear un árbol binario:
a) Los datos de cada nodo deben ser números
b) Numeración aleatoria
c) Ordenar los nodos (de forma ascendente o descendente)
clic aqui
a) Los datos de cada nodo deben ser números
b) Numeración aleatoria
c) Ordenar los nodos (de forma ascendente o descendente)
clic aqui
Suscribirse a:
Entradas (Atom)
