aqui les dejo un video sobre arboles binarios kon sus recorridos tales como in orden, postorden y preorden.

Algunas clases

PSPACE
En teoría de la complejidad computacional, la clase PSPACE es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio polinomial  y tiempo ilimitado.
NPSPACE
En teoría de la complejidad computacional, la clase de complejidad NPSPACE es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing no-determinista en espacio polinómico y tiempo ilimitado.
P
En teoría de la complejidad, la clase de complejidad de los problemas de decisión que pueden ser resueltos en tiempo polinómico calculado a partir de la entrada por una máquina de Turing determinista es llamada P.


EXPTIME
En teoría de la complejidad computacional, la clase de complejidad EXPTIME (también llamada EXP) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(2^p(n)), donde p(n) es una función polinomial sobre n.

Np
En teoría de la complejidad computacional, NP ("tiempo polinomial no determinista"). Es el conjunto de problemas que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinista.
NL
En teoría de la complejidad computacional, la clase de complejidad NL (espacio logarítmico no determinista) es el conjunto de los problemas de decisión que pueden ser resueltos en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada, por una máquina de Turing no determinista tal que la solución si existe es única. La clase L está contenida en NL y está contenida estrictamente en PSPACE. 
SL
La clase de complejidad SL (espacio logarítmico simétrico, del inglés Symmetric Logspace o Sym-L) es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina de Turing no determinista en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada.
EXPSPACE
La clase de complejidad EXPSPACE es el conjunto de los problemas de decisión que pueden ser resueltos con una máquina de Turing determinista en espacio O(2^p(n)), donde p(n) es una función polinomial sobre n. (Cuando se restringe p(n) como una función lineal, la clase resultante se denomina ESPACE.)

 L
La clase de complejidad L (LSPACE o espacio logarítmico determinista) es el conjunto de los problemas de decisión que pueden ser resueltos en espacio log(n) (sin contar el tamaño de la entrada), donde n es el tamaño de la entrada, por una máquina de Turing determinista tal que la solución si existe es única. La clase L está contenida en NL y está contenida estrictamente en PSPACE. 

Entre muchas clases mas.

referncias:
http://es.wikipedia.org/wiki/Anexo:Clases_de_complejidad

problemas de decision y complejidad computacional

Problemas de decisión y su complejidad computacional

En teoría de la computación, un problema es un conjunto de frases de longitud finita que tienen asociadas frases resultantes también de longitud finita. Un problema de decisión es un problema en donde las respuestas posibles son «sí» o «no».

Complejidad computacional

La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, la complejidad inherente a la resolución de un problema computable. Los recursos comúnmente estudiados son el tiempo (mediante una aproximación al número y tipo de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (mediante una aproximación a la cantidad de memoria utilizada para resolver un problema).

TIME (f(n)) = el conjunto de lenguajes para los cuales existe una máquina de Turing determinista que los decida en tiempo que crece asintóticamente como la función f(n).

NTIME (f(n)) = el conjunto de lenguajes para los cuales existe una máquina de Turing no determinista que los decida en tiempo que crece asintóticamente como la función f(n).

Hoy en día las computadoras resuelven problemas mediante algoritmos que tienen como máximo una complejidad o coste computacional polinómico, es decir, la relación entre el tamaño del problema y su tiempo de ejecución es polinómica. Éstos son problemas agrupados en la clase P.

Los problemas que no pueden ser resueltos por nuestras computadoras (las cuales son Máquinas Determinísticas), que en general poseen costes factorial o combinatorio pero que podrían ser procesados por una máquina no-determinista, están agrupados en la clase NP. Estos problemas no tienen una solución práctica, es decir, una máquina determinística (como una computadora actual) no puede resolverlos en un tiempo razonable.

Los problemas en P son en términos generales problemas fáciles, mientras los problemas en NP pero no en P son en términos generales problemas difíciles.

La pregunta P=NP

El saber si las clases P y NP son iguales es el más importante problema abierto en Computación teórica. Incluso hay un premio de un millón de dólares para quien lo resuelva.

Sat

 Problema de satisfacibilidad booleana (también llamado SAT) fue el primer problema identificado como perteneciente a la clase de complejidad NP-completo.

El SAT es el primer problema NP-completo conocido, y fue demostrado por Stephen Cooken 1971. El problema SAT se trata de un problema donde interesa saber si una expresión booleana con variables y sin cuantificadores tiene asociada una asignación de valores para sus variables que hace que la expresión sea verdadera.

http://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_complejidad_computacional

 

algoritmos de grafos

Algoritmo de Dijkstra

El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.

La idea subyacente en este algoritmo consiste en ir explorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el nodo con distancia menor, pueden quedar excluidos de la búsqueda nodos que en próximas iteraciones bajarían el costo general del camino al pasar por una arista con costo negativo).
TEOREMA: El Algoritmo de Dijkstra realiza O(n²) operaciones (sumas y comparaciones) para determinar la longitud del camino más corto entre dos vértices de un grafo ponderado simple, conexo y no dirigido con n vértices.

Pseudocódigo

función Dijkstra (Grafo G, nodo_salida s)

  //Usaremos un vector para guardar las distancias del nodo salida al resto

  entero distancia[n] //Inicializamos el vector con distancias iniciales

  booleano visto[n] //vector de boleanos para controlar los vertices de los que ya tenemos la distancia mínima

  para cada w ∈ V[G] hacer

     Si (no existe arista entre s y w) entonces

         distancia[w] = Infinito //puedes marcar la casilla con un -1 por ejemplo

     Si_no

         distancia[w] = peso (s, w)

     fin si

  fin para

  distancia[s] = 0

  visto[s] = cierto

  //n es el número de vertices que tiene el Grafo

  mientras que (no_esten_vistos_todos) hacer

     vertice = coger_el_minimo_del_vector distancia y que no este visto;

     visto[vertice] = cierto;

     para cada w ∈ sucesores (G, vertice) hacer

         si distancia[w]>distancia[vertice]+peso (vertice, w) entonces

            distancia[w] = distancia[vertice]+peso (vertice, w)

         fin si

     fin para

  fin mientras

fin función

http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra

algoritmos de grafos

Algoritmo de Bellman-Ford

El algoritmo de Bellman-Ford (algoritmo de Bell-End-Ford), genera el camino más corto en un Grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo). El algoritmo de Dijkstra resuelve este mismo problema en un tiempo menor, pero requiere que los pesos de las aristas no sean negativos. Por lo que el Algoritmo Bellman-Ford normalmente se utiliza cuando hay aristas con peso negativo. Este algoritmo fue desarrollado por Richard Bellman, Samuel End y Lester Ford.

Algoritmo

El Algoritmo de Bellman-Ford es, en su estructura básica, muy parecido al algoritmo de Dijkstra, pero en vez de seleccionar vorazmente el nodo de peso mínimo aun sin procesar para relajarlo, simplemente relaja todas las aristas, y lo hace |V|-1 veces, siendo |V| el número de vértices en el grafo. Las repeticiones permiten a las distancias mínimas recorrer el árbol, ya que en la ausencia de ciclos negativos, el camino más corto solo visita cada vértice una vez. A diferencia de la solución voraz, la cual depende de la suposición de que los pesos sean positivos, esta solución se aproxima más al caso general
Pseudocódigo

BellmanFord(Grafo G, nodo_origen s)

      // inicializamos el grafo. Ponemos distancias a INFINITO menos el nodo origen que 

      // tiene distancia 0

       for v ∈ V[G] do

           distancia[v]=INFINITO

           predecesor[v]=NIL

       distancia[s]=0

       // relajamos cada arista del grafo tantas veces como número de nodos -1 haya en el grafo

       for i=1 to |V[G]-1| do

           for (u, v) ∈ E[G] do

               if distancia[v]>distancia[u] + peso(u, v) then

                   distancia[v] = distancia[u] + peso (u, v)

                   predecesor[v] = u

       // comprobamos si hay ciclos negativo

       for (u, v) ∈ E[G] do

           if distancia[v] > distancia[u] + peso(u, v) then

               print ("Hay ciclo negativo")

               return FALSE

       return TRUE

http://es.wikipedia.org/wiki/Algoritmo_de_Bellman-Ford

Representación y manipulación de grafos

Caracterización de grafos

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.

Grafos conexos

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.

Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos.

En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer con base en él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes (fuertemente) conexas", es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teorías de grafos.

 La teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos(también llamadas gráficas). 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 .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).

Estructuras de datos en la representación de grafo

Existen diferentes formas de almacenar grafos en una computadora. La estructura de datos usada depende de las características del grafo y el algoritmo usado para manipularlo. Entre las estructuras más sencillas y usadas se encuentran las listas y las matrices, aunque frecuentemente se usa una combinación de ambas. Las listas son preferidas en grafos dispersos porque tienen un eficiente uso de la memoria. Por otro lado, las matrices proveen acceso rápido, pero pueden consumir grandes cantidades de memoria.

Estructura de lista

Lista de incidencia - Las aristas son representadas con un vector de pares (ordenados, si el grafo es dirigido), donde cada par representa una de las aristas.

  Lista de adyacencia - Cada vértice tiene una lista de vértices los cuales son adyacentes a él. Esto causa redundancia en un grafo no dirigido (ya que A existe en la lista de adyacencia de B y viceversa), pero las búsquedas son más rápidas, al costo de almacenamiento extra.

En esta estructura de datos la idea es asociar a cada vértice i del grafo una lista que contenga todos aquellos vértices j que sean adyacentes a él. De esta forma sólo reservará memoria para los arcos adyacentes a i y no para todos los posibles arcos que pudieran tener como origen i.

Adyacencia Vecinos

v y w son adyacentes si una arista los une:

{v,w} ! E.

Vértices adyacentes son llamados vecinos.

El conjunto de vecinos de v es su vecindario, ! (v).

Definición

El complemento de G = (V,E) es un grafo ¯G = (V, ¯E) donde

!v "= u : !{v, u} # ¯E $ {v, u} /# E".

Grafos especiales

Un grafo es plano si se puede dibujar en dos dimensiones así que ninguna arista cruza a otra arista.

En un grafo no dirigido, los vértices v y w tienen un papel igual en la arista {v, u}.

Si las aristas tienen dirección, G es dirigido (también digrafo).

En una arista dirigida !v,w": v es el origen (o inicio) de la arista w es el destino (o fin) de la arista

Grafos reflexivos

Un bucle es una arista reflexiva, donde coinciden el vértice de origen y el vértice de destino: {v, v} o !v, v".

Si un grafo G no cuente con ningún bucle, el grafo es no reflexivo.

Aristas

Las aristas son típicamente pares de vértices, {u, v} ! E

                               E " V × V

También se puede definir grafos donde el producto es entre más de dos “copias” del conjunto V , el cual caso se habla de hipergrafos.

Grafo

Un grafo es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v) tal que , tal que . Para simplificar, notaremos la arista (a,b)como ab.

En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.

Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red de carreteras que conecta ciudades, una red eléctrica o la red de drenaje de una ciudad.

Subgrafo

Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G. Se dice que un grafo G contiene a otro grafo H si algún subgrafo de G es H o es isomorfo a H(dependiendo de las necesidades de la situación).

El subgrafo inducido de G es un subgrafo G' de G tal que contiene todas las aristas adyacentes al subconjunto de vértices de G.

biliografia: http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos