Grafos dirigidos y Matrices Adyacentes

¿Qué tiempo O(n) nos lleva representar un grafo
dirigido con matrices de adyacencia? ¿ es ventajoso
o no? ¿Qué otro método podemos usar?

La desventaja principal de utilizar una matriz de adyacencias para representar
un grafo (digrafo) es que la matriz requiere un espacio (n^2) incluso si
el grafo (digrafo) es esparso, es decir, si tiene bastante menos de n^2 aristas
(arcos). Sólo leer o examinar la matriz requerirá tiempo O(n^2), en perjuicio de
posibles algoritmos de tiempo O(n) para manipular grafos (digrafos) con O(n)
aristas (arcos). Una alternativa para evitar esta desventaja es utilizar listas para
representar un grafo.

Función de los Arboles Binarios de Búsqueda

La búsqueda en árboles binarios es un método de búsqueda simple, dinámico y eficiente considerado como uno de los fundamentales en Ciencia de la Computación. De toda la terminología sobre árboles, tan sólo recordar que la propiedad que define un árbol binario es que cada nodo tiene a lo más un hijo a la izquierda y uno a la derecha. Para construir los algoritmos consideraremos que cada nodo contiene un registro con un valor clave a través del cual efectuaremos las búsquedas. En las implementaciones que presentaremos sólo se considerará en cada nodo del árbol un valor del tipo tElemento aunque en un caso general ese tipo estará compuesto por dos: una clave indicando el campo por el cual se realiza la ordenación y una información asociada a dicha clave o visto de otra forma, una información que puede ser compuesta en la cual existe definido un orden.


OPERACIONES
Todas las operaciones realizadas sobre árboles binarios de búsqueda están basadas en la comparación de los elementos o clave de los mismos, por lo que es necesaria una subrutina, que puede estar predefinida en el lenguaje de programación, que los compare y pueda establecer una relación de orden entre ellos, es decir, que dados dos elementos sea capaz de reconocer cual es mayor y cual menor. Se habla de clave de un elemento porque en la mayoría de los casos el contenido de los nodos será otro tipo de estructura y es necesario que la comparación se haga sobre algún campo al que se denomina clave.

Árboles de expresiones en C#

Características de C# 3.0 – Expresiones Lambda

En C# 3.0 la gente de Microsoft añadió muchas mejoras en el lenguaje, la mayoría inspirada en los lenguajes funcionales como Lisp, OCaml,… En particular hay dos que van de la mano: las expresiones lambda y los árboles de expresiones. Este primer artículo va a tratar de las expresiones lambda, así que recordemos que era un delegado y poco a poco veremos el porqué se añadieron todas estas nuevas características a C#.

Por ejemplo, queremos filtrar una lista de elementos T en base a un criterio pero queremos que el criterio sea modificable. Este “criterio” es una función que recibirá un T y devolverá un booleano indicando si el elemento cumple el criterio o no. En código tradicional de C# esto sería un delegado y sería algo como lo que sigue:

delegate bool Criteria(T element);



class Program

{

static List FilterList(List list, Criteria criteria)

{

List newList = new List();

foreach (T element in list)

if (criteria(element))

newList.Add(element);



return newList;

}



static bool CriteriaLessThan5(int intValue)

{

return intValue <> 5;

}



static void Main(string[] args)

{

List numbers = new List() { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

List numbers2;



numbers2 = FilterList(numbers, CriteriaLessThan5);

foreach (int number in numbers2)

Console.WriteLine(number);



numbers2 = FilterList(numbers, CriteriaBiggerThan5);

foreach (int number in numbers2)

Console.WriteLine(number);



Console.ReadKey();

}

}


Árboles de Expresiones
Otra nueva característica mucho más “rara” de C# 3.0: son los árboles de expresiones. En algunos lenguajes, como Lisp, se permite manejar el código como si fueran datos y los datos como si fueran código. Los árboles de expresión son la forma que tiene C# de implementar esta funcionalidad (de forma algo limitada).

Por ejemplo, tenemos la expresión lambda:

num=> num <5;

Que devolvía si un número era menor que cinco o no. Expresado en forma de un delegado del tipo Func, el código sería:
Func(int,bool) f = num => num < 5;
Y la forma de poner lo mismo usando un árbol de expresiones es:
System.Linq.Expressions.Expression(Func(int, bool)) e = num => num < 5;
La diferencia entre Func y Expression es que f es una función que se puede ejecutar:
bool result = f(10);
Pero para ejecutar e tenemos que hacer lo siguiente:
bool result = e.Compile()(10);
Es decir: para ejecutar un árbol de expresiones primero tenemos que compilarlo (porque son datos que representan código, no código en sí) y una vez compilado ya podemos utilizar el resultado como si fuera un método normal. De forma gráfica, e internamente está representado por el árbol de este Blog

Acerca de mi

Buen día, mi nombre es Jorge, estudio Ingeniería en Informática, me encanta la música como es ejecutar la Guitarra, Batería, bajo, teclado, en fin casi todo, mi primer amor es JESUS, soy una persona dinámica accesible con la finalidad de superarme cada día más de la mano de DIOS.

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.

FUNCION Factorial (n)

VAR resultado: Entero

SI (n<2)>

resultado =1;

SINO

resultado = n * Factorial(n-1);

FSI

RETORNA resultado;
FFUNCION

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 a 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.

Ventajas:

1. Resolucion de problemas complejos

2. Eficiencia del algoritmo

3. Paralelismo

4. Acceso a memoria

5. Control de redondeo

Desventajas:

La principal desventaja de este método es su lentitud en la repetición del proceso recursivo: los gastos indirectos de las llamadas recursivas a la resolución de los subproblemas, junto con el hecho de tener que almacenar la pila de llamadas puede empeorar cualquier mejoras hasta entonces lograda. Esta tarea sin embargo, depende del estilo de la implementación: con casos base lo suficientemente grandes, se reducen los gastos indirectos de la repetición de la llamada.

Otra desventaja o inconveniente importante, es la dificultad o incluso inconveniencia de aplicar el método a situaciones en las que la solución al problema general no se deriva de la suma directa y simple de los subproblemas(partes). Esto se presenta por ejemplo cuando son relevanters las interacciones o efectos mutuos entre los subproblemas, lo que genera nuevos subproblemas, al considerar cada una de estas interacciones, incrementando exponencialmente el número de subproblemas a considerar, al incrementarse la complejidad de la situación general y de sus componentes.

De modo similar, el algoritmo puede no ser aplicable cuando las interacciones no son predecibles de preciso.

¿En que consiste el Algoritmo de Schönhage-Strassen?

El Algoritmo de Sch­onhage-Strassen consiste en la multiplicación de Matrices. Es asintóticamente más rápido que el algoritmo de multiplicación de matrices estándar, pero más lento que el algoritmo más rápido conocido, y es útil en la práctica para matrices grandes.

El método clásico requiere n²(2n-1) operaciones aritméticas para multiplicar dos matrices (n x n). Sorprendentemente Strassen (1969) publicó un método que solo requería 4.7n²·8¹ operaciones. Se ha realizado mucho trabajo para intentar reducir el exponente 2.81, actualmente el mejor tiempo conocido es O(n²·496) operaciones (Coppersmith y Wingrad, 1982). Hay todavía un largo camino por recorrer, pues la mejor cota inferior conocida es 2n²-¹.

En lo que es la multiplicación es una de las operaciones que debemos repetir varias veces en enteros grandes, por lo que no está de más comprobar que la multiplicación por el método estandar de dos enteros binarios de longitudes k y precisa un máximo k' suma de un bit(Operaciones bit), por lo tanto el producto de dos números enteros con a lo sumo r cifras decimales requiere a lo mas log² r operaciones. Es decir, es de orden O(log² r) y por lo tanto es una operación eficiente. Actualmente hay algoritmos de multiplicación mas rápidos, el más conocido es el método de Karatsuba (cuya descripción es completamente accesible) que permite multiplicar dos enteros de longitud binaria menor o igual que k en O(k¹·59) operaciones bit. El método más rápido se debe a Schonhage y Strassen y su complejidad temporal es O(k log log log k).

Utilizando el algoritmo de Strassen definimos las siguientes matrices:

M1=(A1.2 - A2,2).(B2,1 + B2,2)
M2=(A1,1 + A2,2).(B1,1 + B2,2)
M3=(A1,1 - A2,1).(B1,1 + B2,1)
M4=(A1,1 + A1,2).B2,2
M5=A1,1 .(B1,2 -B2,2)
M6=A2,2.(B2,1 - B1,1)
M7=(A2,1 + A2,2).B1,1

Biografía: http://www.algoritmia.net/articles.php?id=34
http://es.wikipedia.org/wiki/Algoritmo_de_Strassen
http://decsai.ugr.es/~castro/CA/node5.html
http://jair.lab.fi.uva.es/~fdelgado/cripto/resumen.pdf

Volker Strassen

Volker Strassen nació el 29 de Abril de 1936 en Dusseldorf-Gerresheim. Después de estudiar música, filosofía, física y matemáticas en muchas universidades alemanas, recibió su doctorado en matemáticas en 1962 en la Universidad de Gottingen bajo la supervisión de Konrad Jacobs. Entonces Ocupó un puesto en el departamento de Estadísticas de la Universidad de California. En 1968 se trasladó al instituto de Matemática Aplicada de la Universidad de Zurich, donde permaneció 20 años antes de trasladarse a la Universidad de Constanza en 1988. Se Jubiló en 1998.

Biografía: http://es.wikipedia.org/wiki/volker_strassen