Instinto Lógico

Recuerda que nadie debe pensar por tí.

Etiqueta: computacional

P versus NP

P VS NPEs indudable que la complejidad computacional es una rama de las matemáticas/ informática que de suma importancia. Hay algunos problemas que son irresolubles por la gran cantidad de operaciones que se deberían realizar.

Cuando hacemos referencias a P y NP estamos haciendo referencia a la complejidad computacional.

Sin entrar engrandes disquisiciones matemáticas podemos definir varias clases de complejidad:

  • La clase P es el conjunto de todos los problemas resolubles en tiempo polinómico.
  • La clase EXP es el conjunto de todos los problemas resolubles en tiempo exponencial.
  • La clase PSPACE es el conjunto de todos los problemas resolubles en espacio polinómico.
  • La clase EXPSPACE es el conjunto de todos los problemas resolubles en espacio exponencial.

Por ejemplo el problema de determinar si un número es par o encontrar el camino más corto en un grafo se pueden resolver en tiempo y espacio polinómico, sin embargo muchos problemas sobre toma de decisiones o de combinatoria, como por ejemplo, el problema PERMUTACION: “dada una cadena de caracteres C sin caracteres repetidos, calcular todas las posibles permutaciones de los caracteres de C sólo se sabe resolver en tiempo exponencial en concreto n!

Formula de Stirling

Pero ¿a qué nos referimos cuando hablamos de NP? (más…)

Dijkstra y el camino más corto

dijkstra_edgarEdsger Dijkstra (1930 -2002 ) es uno de los padres de la informática al que poca gente ajena a la informática conoce. Éste físico teórico realizó contribuciones fundamentales al campo de la informática actual están los semáforos, el algoritmo del banquero o la notación polaca inversa.

Todas las contribuciones mencionadas anteriormente han supuesto un avance significativo en el desarrollo informático, pero en esta entrada nos vamos a centrar en una de las contribuciones de Dijkstra que más se ha popularizado en los últimos tiempos gracias al uso de los GPS. Se trata del algoritmo que lleva su nombre: “El algoritmo de Dijkstra”.

El algoritmo de Dijkstra se aplica sobre un grafo ponderado y calcula la distancia desde un vértice inicial al resto de vértices del grafo. Los GPS tratan el mapa de carreteras como un grafo ponderado (cuyos pesos son o bien la distancia o el tiempo) y utilizan este algoritmo para calcular el camino más corto entre dos puntos.

Formulación del algoritmo de Dijkstra

Como se ha dicho anteriormente, el algoritmo de Dijkstra calcula la distancia desde un vértice inicial s al resto de vértices del grafo. En cada paso etiquetaremos los vértices del grafo de la siguiente forma: (dist(u),v), dónde dist(u) es la distancia acumulada desde el vértice s al u y v es el vértice predecesor de u en el camino más corto de s a u.

Para realizar el algoritmo de Dijkstra utilizaremos las siguientes estructuras: (más…)

Complejidad computacional

complejidad computacionalEl primer paso para resolver un problema informático es encontrar un algoritmo que lo resuelva. Pero una vez resuelto el problema, nos surgen las siguientes dudas: ¿Exisiten algoritmos “mejores” para resolver el problema?

Podríamos decir que algoritmo, es una sucesión finita de operaciones elementales, que sabemos ejecutar cuando actua sobre una serie de datos. Un algoritmo, será mejor que otro en tiempo si, actuando sobre los mismos datos, el tiempo de ejecución es menor, y será mejor que otro en espacio si, actuando sobre los mismos datos, la memoria, principal o secundaria, que utilza es menor. Pero, tanto el tiempo como el espacio utilizado dependen de la máquina en la que ejecutemos el algoritmo, por tanto hay que determinar una forma para estudiar la eficiencia de los algoritmos independiente de la máquina que se utilice. (más…)

Instinto Lógico © 2014 Frontier Theme