"Arboles y Grafos"
Referencias:
http://es.wikipedia.org/wiki/%C3%81rbol_%28inform%C3%A1tica%29
http://es.wikipedia.org/wiki/Grafo
http://elisa.dyndns-web.com/~elisa/teaching/comp/alg/pdf/arboles.pdf
http://elisa.dyndns-web.com/~elisa/teaching/comp/alg/pdf/grafos.pdf
jueves, 14 de julio de 2011
Quicksort
Este video es un ejemplo del metodo de Ordenamiento "Quicksort" que vimos en clase.
Referencias: No pongo referencias de ninguna pagina porque este ejemplo lo vimos en clase.
Referencias: No pongo referencias de ninguna pagina porque este ejemplo lo vimos en clase.
Busqueda Tabú
Búsqueda Tabú
La búsqueda tabú es un método de optimización matemática, perteneciente a la clase de técnicas de búsqueda local. La búsqueda tabú aumenta el rendimiento del método de búsqueda local mediante el uso de estructuras de memoria: una vez que una potencial solución es determinada, se la marca como "tabú" de modo que el algoritmo no vuelva a visitar esa posible solución.
Vimos en clase un ejemplo "El problema del Viajante", aqui les dejo la definicion y la explicacion de este problema que se puede resolver con busqueda Tabú.
Problema del Viajante
El problema del viajante (TSP), es comúnmente utilizado para mostrar la funcionalidad de la búsqueda tabú.
El TSP requiere buscar un orden en el cual viajar entre ciudades, tal que la distancia recorrida sea minimizada.
Por ejemplo, si las ciudades A y B están una al lado de la otra, mientras que la ciudad C está más lejos, la distancia total recorrida será más corta si las ciudades A y B son visitadas una después de la otra, antes de visitar C.
Como encontrar un orden óptimo para visitar las ciudades en el TSP es un problema NP-difícil. los métodos de aproximación basados en heurísticas son útiles para lograr la optimalidad.
La búsqueda tabú puede utilizarse para encontrar una solución satisfactoria para el TSP. Primero, la búsqueda tabú comienza con una solución inicial, que puede ser generada con el algoritmo del vecino más cercano.
Para crear nuevas soluciones, el orden en que dos ciudades son visitadas es intercambiado. La distancia total recorrida entre todas las ciudades es utilizada para juzgar cuanto mejor es una solución de otra. Para prevenir ciclos y para salir de los óptimos locales, una solución es agregada a la lista tabú si es que es aceptada en N*(x), el vecindario de soluciones.
Se continúan creando nuevas soluciones hasta que algún criterio de parada, como por ejemplo un número arbitrario de iteraciones, es encontrado.
Una vez que la búsqueda tabú se detiene, la mejor solución es aquella que cuya distancia total a recorrer entre las ciudades es la menor.
La búsqueda tabú es un método de optimización matemática, perteneciente a la clase de técnicas de búsqueda local. La búsqueda tabú aumenta el rendimiento del método de búsqueda local mediante el uso de estructuras de memoria: una vez que una potencial solución es determinada, se la marca como "tabú" de modo que el algoritmo no vuelva a visitar esa posible solución.
Vimos en clase un ejemplo "El problema del Viajante", aqui les dejo la definicion y la explicacion de este problema que se puede resolver con busqueda Tabú.
Problema del Viajante
El problema del viajante (TSP), es comúnmente utilizado para mostrar la funcionalidad de la búsqueda tabú.
El TSP requiere buscar un orden en el cual viajar entre ciudades, tal que la distancia recorrida sea minimizada.
Por ejemplo, si las ciudades A y B están una al lado de la otra, mientras que la ciudad C está más lejos, la distancia total recorrida será más corta si las ciudades A y B son visitadas una después de la otra, antes de visitar C.
Como encontrar un orden óptimo para visitar las ciudades en el TSP es un problema NP-difícil. los métodos de aproximación basados en heurísticas son útiles para lograr la optimalidad.
La búsqueda tabú puede utilizarse para encontrar una solución satisfactoria para el TSP. Primero, la búsqueda tabú comienza con una solución inicial, que puede ser generada con el algoritmo del vecino más cercano.
Para crear nuevas soluciones, el orden en que dos ciudades son visitadas es intercambiado. La distancia total recorrida entre todas las ciudades es utilizada para juzgar cuanto mejor es una solución de otra. Para prevenir ciclos y para salir de los óptimos locales, una solución es agregada a la lista tabú si es que es aceptada en N*(x), el vecindario de soluciones.
Se continúan creando nuevas soluciones hasta que algún criterio de parada, como por ejemplo un número arbitrario de iteraciones, es encontrado.
Una vez que la búsqueda tabú se detiene, la mejor solución es aquella que cuya distancia total a recorrer entre las ciudades es la menor.
miércoles, 13 de julio de 2011
Algoritmo de Prim
El Algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.
En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.
Pseudocódigo de Algoritmo
// Inicializamos todos los nodos del grafo. La distancia la ponemos a infinito y el padre de cada nodo a NULL
// Encolamos, en una cola de prioridad donde la prioridad es la distancia, todas las parejas del grafo
por cada u en V[G] hacer
distancia[u] = INFINITO
padre[u] = NULL
Añadir(cola,)
distancia[u]=0
mientras cola != 0 hacer
// OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es menor.
u = extraer_minimo(cola) //devuelve el minimo y lo elimina de la cola.
por cada v adyacente a 'u' hacer
si ((v ∈ cola) && (distancia[v] > peso(u, v)) entonces
padre[v] = u
distancia[v] = peso(u, v)
Actualizar(cola,)
Pasos para realizar el Algoritmo
1. Se marca un nodo cualquiera, este será el nodo de partida.
2. Seleccionamos la arista de menor valor incidente en el nodo marcado anteriormente (nodo de partida), y marcamos el otro nodo en el que índice.
3. Repetir el paso 2 siempre que la arista elegida enlace un nodo marcado y otro que no lo esté.
4. El proceso termina cuando tenemos todos los nodos del grafo marcados
Codigo en C++
for(int i = 0; i < cn; i++) adyacencia[i][padre] = INF; // Encuentro la menor distancia entre las filas marcadas. // El nodo padre es la linea marcada y el nodo hijo es la columna del minimo. int min = INF; for(itVec = markedLines.begin(); itVec != markedLines.end(); itVec++) for(int i = 0; i < cn; i++) if(min > adyacencia[*itVec][i]){
min = adyacencia[*itVec][i];
padre = *itVec;
hijo = i;
}
arbol[padre][hijo] = min;
arbol[hijo][padre] = min;
} return arbol;
}
Referencias:
http://www.wikipedia.com
En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.
Pseudocódigo de Algoritmo
// Inicializamos todos los nodos del grafo. La distancia la ponemos a infinito y el padre de cada nodo a NULL
// Encolamos, en una cola de prioridad donde la prioridad es la distancia, todas las parejas
por cada u en V[G] hacer
distancia[u] = INFINITO
padre[u] = NULL
Añadir(cola,
distancia[u]=0
mientras cola != 0 hacer
// OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es menor.
u = extraer_minimo(cola) //devuelve el minimo y lo elimina de la cola.
por cada v adyacente a 'u' hacer
si ((v ∈ cola) && (distancia[v] > peso(u, v)) entonces
padre[v] = u
distancia[v] = peso(u, v)
Actualizar(cola,
Pasos para realizar el Algoritmo
1. Se marca un nodo cualquiera, este será el nodo de partida.
2. Seleccionamos la arista de menor valor incidente en el nodo marcado anteriormente (nodo de partida), y marcamos el otro nodo en el que índice.
3. Repetir el paso 2 siempre que la arista elegida enlace un nodo marcado y otro que no lo esté.
4. El proceso termina cuando tenemos todos los nodos del grafo marcados
Codigo en C++
// Declaraciones en el archivo .h
const int INF = 1000000;
int cn; //cantidad de nodos
vector< vector > ady; //matriz de adyacencia
// Devuelve la matriz de adyacencia del arbol minimo.
vector< vector > Grafo :: prim(){
// uso una copia de ady porque necesito eliminar columnas
vector< vector > adyacencia = this->ady;
vector< vector > arbol(cn);
vector markedLines;
vector :: iterator itVec;
// Inicializo las distancias del arbol en INF.
for(int i = 0; i < cn; i++) arbol[i] = vector (cn, INF);
int padre = 0;
int hijo = 0;
while(markedLines.size() + 1 < cn){ padre = hijo;
// Marco la fila y elimino la columna del nodo padre. markedLines.push_back(padre);
const int INF = 1000000;
int cn; //cantidad de nodos
vector< vector
// Marco la fila y elimino la columna del nodo padre. markedLines.push_back(padre);
}
Referencias:
http://www.wikipedia.com
Algoritmo Euclidiano
Hoy en clase vimos lo que es un Algoritmo euclideano, y la maestra nos dio una brebe explicacion de como este funciona.
Definicion:
Método para encontrar el máximo factor común de dos enteros. Se divide el número mayor entre el número menor. Se repite la división, utilizando el residuo como divisor, hasta que el residuo se convierte en cero. El último residuo diferente a cero es el máximo factor común de los dos enteros
La explicacion es asi:
A % B = c
56 % 35 = 21 -->56 - 1X35 (56/35)
35 % 21 = 14 -->35 - 1X21 (35/21)
21 % 14 = 7 -->21 - 1X14 (21/14)
14 % 7 = 0
Ahora en Codigo.
Consola
Definicion:
Método para encontrar el máximo factor común de dos enteros. Se divide el número mayor entre el número menor. Se repite la división, utilizando el residuo como divisor, hasta que el residuo se convierte en cero. El último residuo diferente a cero es el máximo factor común de los dos enteros
La explicacion es asi:
A % B = c
56 % 35 = 21 -->56 - 1X35 (56/35)
35 % 21 = 14 -->35 - 1X21 (35/21)
21 % 14 = 7 -->21 - 1X14 (21/14)
14 % 7 = 0
Ahora en Codigo.
using namespace std;
int mcd(int x , int y){
int t;
x = (x < 0) ? -x:x;
int t;
x = (x < 0) ? -x:x;
y = (y < 0) ? -y:y;
t = (x < y) ? x : y;
while ( (x % t) || (y % t))
--t;
return t;
}
int euc(int x,int y){
return (!y) ? x : euc(y,x%y);
}
int main()
{
int x,y;
cout << "x: ";
cin >> x;
cout << "y: ";
cout << "y: ";
cin >> y;
cout << "MCD: " << mcd(x,y) << endl;
cout << "MCD: " << mcd(x,y) << endl;
cout << "MCD (euclides): " << euc(x,y) << endl;
system("PAUSE");
}
Consola
martes, 12 de julio de 2011
Tarea N°4
Arreglos, tablas y listas
Tarea 4
referencias:
http://elisa.dyndns-web.com/~elisa/teaching/comp/alg/pdf/arreglos.pdf
http://elisa.dyndns-web.com/~elisa/teaching/comp/alg/pdf/lindin.pdf
Tarea 4
referencias:
http://elisa.dyndns-web.com/~elisa/teaching/comp/alg/pdf/arreglos.pdf
http://elisa.dyndns-web.com/~elisa/teaching/comp/alg/pdf/lindin.pdf
lunes, 11 de julio de 2011
Isomorfio de Grafos
Hoy en clase vimos lo que era “Isomorfia”, esto quiere decir que grafos son iguales pero con distinta forma, que al vernos nosotros percibimos figuras diferentes pero al comprobarlas nos dimos cuenta que estas son iguales.
Aquí les dejo la definición y un ejemplo.
Definición:
Dos grafos K1 y K2 son isomorfos si existe una función biyectiva f entre los vértices de K1 y K2, y una función biyectiva g entre lados de K1 y K2 tales que un lado e es incidente a v y w en K1 si solo si el lado g(e) es incidente a los vértices f (v) y f (w) en K2. Al par de funciones f y g se le denomina isomorfismo.
Ejemplo:
Un isomorfismo para los grafos anteriores K1 y K2 esta definido por:
f (a) = A
f (b) = B
f (c) = C
f (d) = D
f (e) = E
y g(Xi) = Yi, i = 1, ... , 5
http://mate.cucei.udg.mx/matdis/5gra/5gra6.htm
Aquí les dejo la definición y un ejemplo.
Definición:
Dos grafos K1 y K2 son isomorfos si existe una función biyectiva f entre los vértices de K1 y K2, y una función biyectiva g entre lados de K1 y K2 tales que un lado e es incidente a v y w en K1 si solo si el lado g(e) es incidente a los vértices f (v) y f (w) en K2. Al par de funciones f y g se le denomina isomorfismo.
Ejemplo:
Un isomorfismo para los grafos anteriores K1 y K2 esta definido por:
f (a) = A
f (b) = B
f (c) = C
f (d) = D
f (e) = E
y g(Xi) = Yi, i = 1, ... , 5
http://mate.cucei.udg.mx/matdis/5gra/5gra6.htm
Grafos
Un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
Un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).
Un grafo G es un par ordenado G = (V,E), donde:
•V es un conjunto de vértices o nodos, y
•E es un conjunto de aristas o arcos, que relacionan estos nodos.
Dentro de esta teoría se encuentran varios tipos de grafos pero en este texto nombraremos los mas básicos.
Grafo no dirigido
Está conformado por un conjunto de aristas las cuales no cuentan con una dirección específica.
Un grafo no dirigido o grafo propiamente dicho es un grafo G = (V, E) donde:
• V ≠ Ø
•
es un conjunto de pares no ordenados de elementos de V.
Grafo dirigido
Es el que posee una dirección específica entre vértices.
Un grafo dirigido o dígrafo es un grafo G = (V,E) donde:
• V ≠ Ø
•
es un conjunto de pares ordenados de elementos de .
Dada una arista (a, b), a es su nodo inicial y b su nodo final.
Por definición, los grafos dirigidos no contienen bucles.
Grafos Simples
Un grafo es simple si sólo 1 arista QUE une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.
Un grafo que no es simple se denomina Multigráfica o Gráfo múltiple
Karla Garcia
Un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).
Un grafo G es un par ordenado G = (V,E), donde:
•V es un conjunto de vértices o nodos, y
•E es un conjunto de aristas o arcos, que relacionan estos nodos.
Dentro de esta teoría se encuentran varios tipos de grafos pero en este texto nombraremos los mas básicos.
Grafo no dirigido
Está conformado por un conjunto de aristas las cuales no cuentan con una dirección específica.
Un grafo no dirigido o grafo propiamente dicho es un grafo G = (V, E) donde:
• V ≠ Ø
•
Grafo dirigido
Es el que posee una dirección específica entre vértices.
Un grafo dirigido o dígrafo es un grafo G = (V,E) donde:
• V ≠ Ø
•
Dada una arista (a, b), a es su nodo inicial y b su nodo final.
Por definición, los grafos dirigidos no contienen bucles.
Grafos Simples
Un grafo es simple si sólo 1 arista QUE une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.
Un grafo que no es simple se denomina Multigráfica o Gráfo múltiple
Karla Garcia
viernes, 8 de julio de 2011
Arboles Binarios
Arbol binario
En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho.
No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo.
En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.
Aqui les muestro un arbol en dibujo, ubicando la Raiz y los nodos.
Existen diferentes tipos de arboles binarios, aqui les dejo la definicion.
*Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
*Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
*Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura).
Recorridos sobre los arboles binarios.
Existen distintos recorridos los cuales vimos hoy en clase.
Explicare cada uno de ellos dando un ejemplo.
Preorden
Este tipo de recorrido se realiza, primeri se imprmi la Raiz, depues el hijo izquierdo(subarbol izquierdo), y por ultimo hijo derecho(subarbol derecho).
Lo correspondiente al recorrido preorden de la imagen anterior sería:
2, 6, 5, 2, 9,11,7, 8, 3.
Postorden
Este tipo de recorrido se realiza, prmiero el hijo izquierdo, hijo derecho y al final la raiz.
Lo correspondiente al recorrido Postorden de la imagen sería:
5, 9, 11, 2, 6, 3, 8, 7, 2.
Inorden.
Este tipo de recorrido se realiza primero hijo izquierdo, raiz, y al final hijo derecho.
Lo correspondiente al recorrido Inorden de la imagen sería:
5, 6, 9, 2, 11, 2, 7, 8, 3.
Amplitud o por niveles.
En este caso se realiza en orden por los distintos niveles del arbol, se comenzara con el nivel 1, que solo es la raiz, seguidamente el nivel 2, el 3 y así sucesivamente.
2, 6, 7, 5, 2, 8, 9, 11, 3.
Karla Garcia
En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho.
No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo.
En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.
Aqui les muestro un arbol en dibujo, ubicando la Raiz y los nodos.
Existen diferentes tipos de arboles binarios, aqui les dejo la definicion.
*Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
*Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
*Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura).
Recorridos sobre los arboles binarios.
Existen distintos recorridos los cuales vimos hoy en clase.
Explicare cada uno de ellos dando un ejemplo.
Preorden
Este tipo de recorrido se realiza, primeri se imprmi la Raiz, depues el hijo izquierdo(subarbol izquierdo), y por ultimo hijo derecho(subarbol derecho).
Lo correspondiente al recorrido preorden de la imagen anterior sería:
2, 6, 5, 2, 9,11,7, 8, 3.
Postorden
Este tipo de recorrido se realiza, prmiero el hijo izquierdo, hijo derecho y al final la raiz.
Lo correspondiente al recorrido Postorden de la imagen sería:
5, 9, 11, 2, 6, 3, 8, 7, 2.
Inorden.
Este tipo de recorrido se realiza primero hijo izquierdo, raiz, y al final hijo derecho.
Lo correspondiente al recorrido Inorden de la imagen sería:
5, 6, 9, 2, 11, 2, 7, 8, 3.
Amplitud o por niveles.
En este caso se realiza en orden por los distintos niveles del arbol, se comenzara con el nivel 1, que solo es la raiz, seguidamente el nivel 2, el 3 y así sucesivamente.
2, 6, 7, 5, 2, 8, 9, 11, 3.
Karla Garcia
jueves, 7 de julio de 2011
Algoritmo Recursivo
Algoritmo Recursivo
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.
Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N.
De esta forma, al ir reduciendo progresivamente la complejidad del problema que resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante un caso base de la recursividad.
Las claves para construir un subprograma recurrente son:
-Cada llamada recurrente se debería definir sobre un problema de menor complejidad (algo más fácil de resolver).
-Ha de existir al menos un caso base para evitar que la recurrencia sea infinita.
Es frecuente que los algoritmos recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser mucho más breves en espacio.
Ejemplos de Algoritmos recursivos.
Factorial
Torres de Hanói
Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero.
Encontre informacion en:
http://www.wikipedia.com
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.
Generalmente, si la primera llamada al subprograma se plantea sobre un problema de tamaño u orden N, cada nueva ejecución recurrente del mismo se planteará sobre problemas, de igual naturaleza que el original, pero de un tamaño menor que N.
De esta forma, al ir reduciendo progresivamente la complejidad del problema que resolver, llegará un momento en que su resolución sea más o menos trivial (o, al menos, suficientemente manejable como para resolverlo de forma no recursiva). En esa situación diremos que estamos ante un caso base de la recursividad.
Las claves para construir un subprograma recurrente son:
-Cada llamada recurrente se debería definir sobre un problema de menor complejidad (algo más fácil de resolver).
-Ha de existir al menos un caso base para evitar que la recurrencia sea infinita.
Es frecuente que los algoritmos recurrentes sean más ineficientes en tiempo que los iterativos aunque suelen ser mucho más breves en espacio.
Ejemplos de Algoritmos recursivos.
Factorial
Torres de Hanói
Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero.
Encontre informacion en:
http://www.wikipedia.com
Algoritmo Iterativo
Los algoritmos iterativos son algoritmos que se caracterizan por ejecutarse mediante ciclos. Estos algoritmos son muy útiles al momento de realizar tareas repetitivas (como recorrer un arreglo de datos). Casi todos los lenguajes de programación modernos tienen palabras reservadas para la realización de iteraciones.
La opción al uso de algoritmos iterativos es el uso de la recursividad en funciones. Estas implican una escritura más sencilla (corta), tanto para su implementación como para su entendimiento, pero en contraparte, utilizan mucho más recursos de sistema que una iteración debido a que necesitan, además del uso del procesador, la pila del sistema para "apilar" los diversos ámbitos de cada función.
Este es un ejemplo de algoritmo iterativo que nos puso la maestra en la clase.
Lo realice en C y le di la opción al usuario que introdujera el numero de las potencias que desee imprimir.
Potencias
Diagrama de Flujo
Otro ejemplo..
Factorial
Diagrama de flujo
Comentarios: La definicion de Algoritmo iterativo la encontre en
http://www.wikipedia.com
La opción al uso de algoritmos iterativos es el uso de la recursividad en funciones. Estas implican una escritura más sencilla (corta), tanto para su implementación como para su entendimiento, pero en contraparte, utilizan mucho más recursos de sistema que una iteración debido a que necesitan, además del uso del procesador, la pila del sistema para "apilar" los diversos ámbitos de cada función.
Este es un ejemplo de algoritmo iterativo que nos puso la maestra en la clase.
Lo realice en C y le di la opción al usuario que introdujera el numero de las potencias que desee imprimir.
Potencias
Diagrama de Flujo
Otro ejemplo..
Factorial
Diagrama de flujo
Comentarios: La definicion de Algoritmo iterativo la encontre en
http://www.wikipedia.com
martes, 5 de julio de 2011
Radiosity
Tarea No.2
Problema
Crear una imagen por computadora que se asemeje lo suficiente a la vida real mediante sombras.
Radiosity
El término radiosity se refiere a una medida de energía radiante, en particular, la energía que deja una superficie por unidad de tiempo. Con el tiempo, radiosity ha venido también a significar un conjunto de técnicas computacionales para calcular por medio de las computadoras la iluminación global de un ambiente.
El método radiosity emerge recientemente en el desarrollo de la sintetización de imágenes. Este método representa el desarrollo de varias tendencias: el desarrollo de modelos basados en propiedades físicas, el uso de métodos computacionales más rigurosos la continúa tensión entre la interactividad y el realismo computacional.
Radiosidad es una aplicación del método de elementos finitos para resolver la ecuación de la representación de escenas con superficies puramente difusas.
A diferencia de algoritmos de Monte Carlo (como el trazado de trayectorias) que manejan todos los tipos de haces de luz, los métodos típicos de radiosidad sólo cuenta para las rutas que salen de una fuente de luz y se reflejan de forma difusa un cierto número de veces (posiblemente cero) antes de golpear el ojo. Estos trayectos son representados como "LD * E". Cálculos de radiosidad son independientes el punto de vista lo que aumenta los cálculos involucrados, pero hace que sean útiles para todos los puntos de vista.
Historia
Métodos de radiosidad se desarrollaron por primera vez en cerca de 1950 en el campo de la ingeniería de transferencia de calor. Fueron refinados más tarde específicamente para su aplicación al problema de la representación de gráficos por ordenador en 1984 por investigadores de la Universidad de Cornell.
Notable motores radiosidad comerciales Ilumina por Geomerics, como se ha visto en títulos como Battlefield 3, Need for Speed y otros, Lightscape (ahora incorporada en la Autodesk 3D Studio Max motor de render interno), la forma RenderZone Plus AutoDesSys, Inc.), y ELAS (Electric Image Animation System).
Características visuales
La inclusión de los cálculos de radiosidad en el proceso de presentación a menudo da un elemento adicional de realismo a la escena terminada, debido a la forma que imita fenómenos del mundo real. Considere la posibilidad de una escena de la habitación simple.
La imagen se representa con un algoritmo de radiosidad.
Hay tres tipos de iluminación en esta escena que han sido específicamente elegidos y colocados por el artista en un intento de crear una iluminación realista: una iluminación puntual con sombras (que se encuentra fuera de la ventana para crear la luz que brilla en el suelo), iluminación ambiental (sin que cualquier parte de la habitación no se enciende directamente por una fuente de luz sería totalmente oscura), y la iluminación omnidireccional sin sombras (para reducir la monotonía de la iluminación ambiental).
Blender Radiosity Animation
Descripción del algoritmo de radiosidad
Las superficies de la escena que se hizo cada uno dividido en una o más superficies más pequeñas (parches). Un factor de vista se calcula para cada par de parches. Factores de visión (también conocida como factores de forma) son los coeficientes de describir lo bien que los parches se pueden ver unos a otros.
Los parches que están muy lejos unos de otros, u orientados en ángulos oblicuos con respecto a otros, tendrán menores factores de vista. Si los otros parches se encuentran en el camino, el factor de vista será reducido o nulo, dependiendo de si la obstrucción es parcial o total.
Los factores de vista se utilizan como coeficientes de una forma lineal de la ecuación de la prestación, lo que produce un sistema de ecuaciones lineales. Al resolver este sistema se obtiene la radiosidad, o el brillo de cada parche, teniendo reflexiones difusas y sombras suaves.
Radiosidad progresiva resuelve el sistema de forma iterativa, de tal manera que después de cada iteración tenemos valores intermedios de radiosidad para el parche. Estos valores intermedios se corresponden con los niveles de rebote. Es decir, después de una iteración, sabemos cómo se ve la escena después de un rebote de la luz, después de dos pases, rebotes dos, y así sucesivamente. Radiosidad progresiva es útil para obtener una vista previa interactiva de la escena. Además, el usuario puede detener las iteraciones una vez que la imagen se ve bastante bueno, en lugar de esperar a que el cálculo de la convergencia numérica
Formulación matemática
El método de radiosidad básica tiene su base en la teoría de la radiación térmica, ya que radiosidad se basa en calcular la cantidad de energía de la luz entre las superficies transferidas. Con el fin de simplificar los cálculos, el método supone que todos los de dispersión es perfectamente difuso. Las superficies son típicamente discretizado en elementos cuadrilátero o triangular sobre el que se define una función polinómica a trozos.
Después de este fracaso, el monto de la transferencia de energía de la luz puede ser calculada mediante el uso de la reflectividad conocida del parche que reflejan, en combinación con el factor de vista de los dos parches. Esta cantidad sin dimensiones se calcula a partir de la orientación geométrica de dos parches, y se puede considerar como la fracción de la superficie emisora total posible de la primera revisión que está cubierto por el segundo parche.
Más bien, radiosidad es la energía dejando la superficie de parches por intervalo de tiempo discreto y es la combinación de la energía emitida y la reflejada:
Donde:
• Bi radiosidad es el parche de i.
• Ei se emite energía.
• Ri es la reflectividad del parche, lo que refleja la energía multiplicando la energía incidente (la energía que llega de otros parches).
• Todos los j () en el medio ambiente que se prestan, integrada por BjFji daj, para determinar la energía que sale cada j parche que llega al parche i.
• Fij es el factor de vista constante de valor de la radiación i salir y golpear el parche j.
La reciprocidad:
da:
Para facilitar el uso de la integral se sustituye y radiosidad uniforme se asume sobre el parche, la creación de la más simple
Esta ecuación se puede aplicar a cada parche. La ecuación es monocromática, por lo que una reproducción de color de radiosidad requiere de cálculo para cada uno de los colores necesarios.
Optimización
Aunque en su forma básica de radiosidad se supone que un aumento de segundo grado en el tiempo de cálculo con geometría añadido (superficies y parches), esto no es necesariamente el caso. El problema de radiosidad puede ser reformulada como un problema de representar una escena de la textura asignada. En este caso, el tiempo de cálculo aumenta sólo linealmente con el número de parches (haciendo caso omiso de cuestiones complejas como el uso de memoria caché).
Tras el entusiasmo comercial de radiosidad-mejor imagen, pero antes de la estandarización de cálculo de radiosidad rápida, muchos arquitectos y artistas gráficos que se utilizan una técnica conocida en términos generales como radiosidad falsa. Oscureciendo las áreas de mapas de texturas correspondientes a las esquinas, juntas y huecos, y su aplicación a través de la auto-iluminación o la asignación difusa, un efecto de radiosidad-como de la interacción parche podría ser creado con un procesador estándar de línea de exploración (cf. oclusión de ambiente).
Soluciones de radiosidad se puede mostrar en tiempo real a través de mapas de luz en computadoras de escritorio actual con el hardware estándar de la aceleración de gráficos
Complejidad.
Un asunto importante práctica implica O (N log n) tiempo de complejidad es que una progresiva re-
programa de refinamiento de radiosidad no debe buscar el más brillante parche para disparar el poder. Tal de búsqueda es O (N), por lo que se convertiría en la complejidad (O2) en el mejor. En cambio, los parches pueden disparar en orden aleatorio, o una especie de O (N log n) se podría realizar una o varias veces durante el ejecución del programa.
Con esto se puede concluir que la complejidad del algoritmo está representada con un NP-Completo.
Aplicación en la vida real
En la vida real este algoritmo se utiliza para la creación de imágenes ó espacios en 3D, tales como simulaciones por computadora de escenarios, edificios, mundos. Así como también en el mundo de los videojuegos, en el área de la ciencia e investigación.
Referencias:
http://en.wikipedia.org/wiki/Radiosity_%283D_computer_graphics%29
href=http://scholar.google.com.mx/scholar?q=radiosity+algorithm+complexity&hl=es&as_sdt=0&as_vis=1&oi=scholart
Problema
Crear una imagen por computadora que se asemeje lo suficiente a la vida real mediante sombras.
Radiosity
El término radiosity se refiere a una medida de energía radiante, en particular, la energía que deja una superficie por unidad de tiempo. Con el tiempo, radiosity ha venido también a significar un conjunto de técnicas computacionales para calcular por medio de las computadoras la iluminación global de un ambiente.
El método radiosity emerge recientemente en el desarrollo de la sintetización de imágenes. Este método representa el desarrollo de varias tendencias: el desarrollo de modelos basados en propiedades físicas, el uso de métodos computacionales más rigurosos la continúa tensión entre la interactividad y el realismo computacional.
Radiosidad es una aplicación del método de elementos finitos para resolver la ecuación de la representación de escenas con superficies puramente difusas.
A diferencia de algoritmos de Monte Carlo (como el trazado de trayectorias) que manejan todos los tipos de haces de luz, los métodos típicos de radiosidad sólo cuenta para las rutas que salen de una fuente de luz y se reflejan de forma difusa un cierto número de veces (posiblemente cero) antes de golpear el ojo. Estos trayectos son representados como "LD * E". Cálculos de radiosidad son independientes el punto de vista lo que aumenta los cálculos involucrados, pero hace que sean útiles para todos los puntos de vista.
Historia
Métodos de radiosidad se desarrollaron por primera vez en cerca de 1950 en el campo de la ingeniería de transferencia de calor. Fueron refinados más tarde específicamente para su aplicación al problema de la representación de gráficos por ordenador en 1984 por investigadores de la Universidad de Cornell.
Notable motores radiosidad comerciales Ilumina por Geomerics, como se ha visto en títulos como Battlefield 3, Need for Speed y otros, Lightscape (ahora incorporada en la Autodesk 3D Studio Max motor de render interno), la forma RenderZone Plus AutoDesSys, Inc.), y ELAS (Electric Image Animation System).
Características visuales
La inclusión de los cálculos de radiosidad en el proceso de presentación a menudo da un elemento adicional de realismo a la escena terminada, debido a la forma que imita fenómenos del mundo real. Considere la posibilidad de una escena de la habitación simple.
Hay tres tipos de iluminación en esta escena que han sido específicamente elegidos y colocados por el artista en un intento de crear una iluminación realista: una iluminación puntual con sombras (que se encuentra fuera de la ventana para crear la luz que brilla en el suelo), iluminación ambiental (sin que cualquier parte de la habitación no se enciende directamente por una fuente de luz sería totalmente oscura), y la iluminación omnidireccional sin sombras (para reducir la monotonía de la iluminación ambiental).
Blender Radiosity Animation
Descripción del algoritmo de radiosidad
Las superficies de la escena que se hizo cada uno dividido en una o más superficies más pequeñas (parches). Un factor de vista se calcula para cada par de parches. Factores de visión (también conocida como factores de forma) son los coeficientes de describir lo bien que los parches se pueden ver unos a otros.
Los parches que están muy lejos unos de otros, u orientados en ángulos oblicuos con respecto a otros, tendrán menores factores de vista. Si los otros parches se encuentran en el camino, el factor de vista será reducido o nulo, dependiendo de si la obstrucción es parcial o total.
Los factores de vista se utilizan como coeficientes de una forma lineal de la ecuación de la prestación, lo que produce un sistema de ecuaciones lineales. Al resolver este sistema se obtiene la radiosidad, o el brillo de cada parche, teniendo reflexiones difusas y sombras suaves.
Radiosidad progresiva resuelve el sistema de forma iterativa, de tal manera que después de cada iteración tenemos valores intermedios de radiosidad para el parche. Estos valores intermedios se corresponden con los niveles de rebote. Es decir, después de una iteración, sabemos cómo se ve la escena después de un rebote de la luz, después de dos pases, rebotes dos, y así sucesivamente. Radiosidad progresiva es útil para obtener una vista previa interactiva de la escena. Además, el usuario puede detener las iteraciones una vez que la imagen se ve bastante bueno, en lugar de esperar a que el cálculo de la convergencia numérica
Formulación matemática
El método de radiosidad básica tiene su base en la teoría de la radiación térmica, ya que radiosidad se basa en calcular la cantidad de energía de la luz entre las superficies transferidas. Con el fin de simplificar los cálculos, el método supone que todos los de dispersión es perfectamente difuso. Las superficies son típicamente discretizado en elementos cuadrilátero o triangular sobre el que se define una función polinómica a trozos.
Después de este fracaso, el monto de la transferencia de energía de la luz puede ser calculada mediante el uso de la reflectividad conocida del parche que reflejan, en combinación con el factor de vista de los dos parches. Esta cantidad sin dimensiones se calcula a partir de la orientación geométrica de dos parches, y se puede considerar como la fracción de la superficie emisora total posible de la primera revisión que está cubierto por el segundo parche.
Más bien, radiosidad es la energía dejando la superficie de parches por intervalo de tiempo discreto y es la combinación de la energía emitida y la reflejada:
Donde:
• Bi radiosidad es el parche de i.
• Ei se emite energía.
• Ri es la reflectividad del parche, lo que refleja la energía multiplicando la energía incidente (la energía que llega de otros parches).
• Todos los j () en el medio ambiente que se prestan, integrada por BjFji daj, para determinar la energía que sale cada j parche que llega al parche i.
• Fij es el factor de vista constante de valor de la radiación i salir y golpear el parche j.
La reciprocidad:
Para facilitar el uso de la integral se sustituye y radiosidad uniforme se asume sobre el parche, la creación de la más simple
Optimización
Aunque en su forma básica de radiosidad se supone que un aumento de segundo grado en el tiempo de cálculo con geometría añadido (superficies y parches), esto no es necesariamente el caso. El problema de radiosidad puede ser reformulada como un problema de representar una escena de la textura asignada. En este caso, el tiempo de cálculo aumenta sólo linealmente con el número de parches (haciendo caso omiso de cuestiones complejas como el uso de memoria caché).
Tras el entusiasmo comercial de radiosidad-mejor imagen, pero antes de la estandarización de cálculo de radiosidad rápida, muchos arquitectos y artistas gráficos que se utilizan una técnica conocida en términos generales como radiosidad falsa. Oscureciendo las áreas de mapas de texturas correspondientes a las esquinas, juntas y huecos, y su aplicación a través de la auto-iluminación o la asignación difusa, un efecto de radiosidad-como de la interacción parche podría ser creado con un procesador estándar de línea de exploración (cf. oclusión de ambiente).
Soluciones de radiosidad se puede mostrar en tiempo real a través de mapas de luz en computadoras de escritorio actual con el hardware estándar de la aceleración de gráficos
Complejidad.
Un asunto importante práctica implica O (N log n) tiempo de complejidad es que una progresiva re-
programa de refinamiento de radiosidad no debe buscar el más brillante parche para disparar el poder. Tal de búsqueda es O (N), por lo que se convertiría en la complejidad (O2) en el mejor. En cambio, los parches pueden disparar en orden aleatorio, o una especie de O (N log n) se podría realizar una o varias veces durante el ejecución del programa.
Con esto se puede concluir que la complejidad del algoritmo está representada con un NP-Completo.
Aplicación en la vida real
En la vida real este algoritmo se utiliza para la creación de imágenes ó espacios en 3D, tales como simulaciones por computadora de escenarios, edificios, mundos. Así como también en el mundo de los videojuegos, en el área de la ciencia e investigación.
Referencias:
http://en.wikipedia.org/wiki/Radiosity_%283D_computer_graphics%29
href=http://scholar.google.com.mx/scholar?q=radiosity+algorithm+complexity&hl=es&as_sdt=0&as_vis=1&oi=scholart
sábado, 2 de julio de 2011
Serie Fibonacci
SERIE FIBONACCI
1, 1, 2, 3, 5, 8, 13, 21, 34 . . . . . .N
¿Qué relación tiene la serie fibonacci?
Esta serie tiene como relación la suma de 2 números, la cual comienza con una suma simple de c=a+b(1+0=1) después se toma el elemento b (0) y se suma con el resultado (1) y así sucesivamente, ejemplo:
Aqui les muestro el diagrama de flujo que elabore en Raptor.
Le di la opcion al usuario de introducir la cantidad de numeros que desea imprmir.
INICIA
A=1 B=0 C=0 I=0 N;
SOLICITAMOS AL USUARIO LA CANTIDAD DE NUMEROS QUE DESEA IMPRMIR..
ALMACENAMOS EL NUMERO DADO POR EL USUARIO EN "N"
SUMA A+B
RESULTADO = C
IMPRIMIMOS "C"
DECLARAMOS QUE AHORA A TOME EL VALOR DE B
DEPUES NUEVAMENTE DECLARAMOS QUE C TOME EL VALOR DE B
Y SE REPITE EL CICLO HASTA EL NUMERO DADO POR EL USUARIO (N).
Tambien el codigo que realize en Dev-C++.
Y ya por ultimo la consola.
Karla Garcia
1, 1, 2, 3, 5, 8, 13, 21, 34 . . . . . .N
¿Qué relación tiene la serie fibonacci?
Esta serie tiene como relación la suma de 2 números, la cual comienza con una suma simple de c=a+b(1+0=1) después se toma el elemento b (0) y se suma con el resultado (1) y así sucesivamente, ejemplo:
Aqui les muestro el diagrama de flujo que elabore en Raptor.
Le di la opcion al usuario de introducir la cantidad de numeros que desea imprmir.
INICIA
A=1 B=0 C=0 I=0 N;
SOLICITAMOS AL USUARIO LA CANTIDAD DE NUMEROS QUE DESEA IMPRMIR..
ALMACENAMOS EL NUMERO DADO POR EL USUARIO EN "N"
SUMA A+B
RESULTADO = C
IMPRIMIMOS "C"
DECLARAMOS QUE AHORA A TOME EL VALOR DE B
DEPUES NUEVAMENTE DECLARAMOS QUE C TOME EL VALOR DE B
Y SE REPITE EL CICLO HASTA EL NUMERO DADO POR EL USUARIO (N).
Tambien el codigo que realize en Dev-C++.
Y ya por ultimo la consola.
Karla Garcia
jueves, 30 de junio de 2011
Tarea No.1
Convertidor de Hexadecimal a Decimal y de Decimal a Hexadecimal
Este algoritmo sirve para convertir una cantidad de números en hexadecimal a decimal o también sirve para convertir de decimal a hexadecimal.
Algoritmo.
1. INCIO
2. Se despliega en pantalla un menú para el usuario, en donde la opción 1 es: convertir de hexadecimal a decimal y la opción 2 es: convertir de decimal a hexadecimal.
3. El usuario escoge cualquiera de las 2 opciones anteriores.
a. (En dado caso en que el usuario selecciono la 1era opción)
4. Aparece una nueva instrucción.
5. Pedir un número al usuario en hexadecimal.
6. Se obtiene cada carácter del número hexadecimal dado por el usuario, comenzando de derecha a izquierda y almacenando ese valor en un arreglo de números enteros (este arreglo se utiliza para convertir las letras en números).
7. Se toma cada elemento del arreglo en posición ascendente (de 0 a n) y este se multiplica por 16 elevado a su posición (potencia) correspondiente, es decir el 1er elemento es 10x16^0, el 2do elemento es 10x16^1 y así sucesivamente.
8. Se suman todos los resultados de las operaciones de cada elemento del arreglo.
9. Como resultado final se despliega en pantalla al usuario el resultado de la conversión de un número hexadecimal a decimal.
b. (En dado caso en que el usuario seleccionó la 2da opción)
10. Aparece una nueva instrucción.
11. Pedir un número al usuario en decimal.
12. Dividir ese número entre 16 y almacenar el residuo hasta que el resultado de la división entera sea menor que 16.
13. Si existe algún valor mayor que 9 en el arreglo de enteros se cambia por la letra correspondiente, es decir el 10 por el A, el 11 por la B y así sucesivamente hasta llegar al número 16.
14. Como resultado final se despliega en pantalla al usuario el resultado de la conversión de un número decimal a hexadecimal.
15. FIN.
Aquí les muestro las pantallas del código que realice de acuerdo al algoritmo explicado anteriormente, realize el codigo con lenguaje C++, en Dev-C++.
Y tambien les agrego la Consola.
Opcion 1.
Opcion 2.
Comentarios: Para realizar el codigo me apoye con esta pagina:
http://www.cplusplus.com/
Karla Garcia
Convertidor de Hexadecimal a Decimal y de Decimal a Hexadecimal
Este algoritmo sirve para convertir una cantidad de números en hexadecimal a decimal o también sirve para convertir de decimal a hexadecimal.
Algoritmo.
1. INCIO
2. Se despliega en pantalla un menú para el usuario, en donde la opción 1 es: convertir de hexadecimal a decimal y la opción 2 es: convertir de decimal a hexadecimal.
3. El usuario escoge cualquiera de las 2 opciones anteriores.
a. (En dado caso en que el usuario selecciono la 1era opción)
4. Aparece una nueva instrucción.
5. Pedir un número al usuario en hexadecimal.
6. Se obtiene cada carácter del número hexadecimal dado por el usuario, comenzando de derecha a izquierda y almacenando ese valor en un arreglo de números enteros (este arreglo se utiliza para convertir las letras en números).
7. Se toma cada elemento del arreglo en posición ascendente (de 0 a n) y este se multiplica por 16 elevado a su posición (potencia) correspondiente, es decir el 1er elemento es 10x16^0, el 2do elemento es 10x16^1 y así sucesivamente.
8. Se suman todos los resultados de las operaciones de cada elemento del arreglo.
9. Como resultado final se despliega en pantalla al usuario el resultado de la conversión de un número hexadecimal a decimal.
b. (En dado caso en que el usuario seleccionó la 2da opción)
10. Aparece una nueva instrucción.
11. Pedir un número al usuario en decimal.
12. Dividir ese número entre 16 y almacenar el residuo hasta que el resultado de la división entera sea menor que 16.
13. Si existe algún valor mayor que 9 en el arreglo de enteros se cambia por la letra correspondiente, es decir el 10 por el A, el 11 por la B y así sucesivamente hasta llegar al número 16.
14. Como resultado final se despliega en pantalla al usuario el resultado de la conversión de un número decimal a hexadecimal.
15. FIN.
Aquí les muestro las pantallas del código que realice de acuerdo al algoritmo explicado anteriormente, realize el codigo con lenguaje C++, en Dev-C++.
Y tambien les agrego la Consola.
Opcion 1.
Opcion 2.
Comentarios: Para realizar el codigo me apoye con esta pagina:
http://www.cplusplus.com/
Karla Garcia
miércoles, 29 de junio de 2011
Maquina de Turing
Esta es la funcion que vimos en clase solo le modifique algunos pasos para que reste 1 unidad en vez de sumar (en binario). 
Suscribirse a:
Entradas (Atom)