jueves, 14 de julio de 2011

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

miércoles, 13 de julio de 2011


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(2p(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(2p(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(n2) 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

martes, 12 de julio de 2011

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.