UPV



Resultados de la búsqueda By Etiquetas: ordenador


Diferencias entre un cerebro humano y un ordenador

Os dejo unos vídeos “Brain Quiz”, que es una serie de microespacios de divulgación científica sobre nuestro cerebro, producido por la UCC+i de la Universitat Politècnica de València y Medianomedia. Puedes ver todas los Brain Quiz en la lista de reproducción http://bit.ly/BrainQuiz y en el Canal Youtube de UPV Televisión: http:// youtube.com/UPVTV. También puedes seguirnos en http://facebook.com/UPVTV y http://twitter.com/UPVTV.

Espero que os gusten.

18 abril, 2015
 
|   Etiquetas: ,  ,  |  

¿Qué es un algoritmo?

Algoritmo de Euclides

Un algoritmo es un conjunto prescrito de reglas o instrucciones bien definidas para la resolución de un problema. En general, se trata de encontrar el método más “eficiente”, no siendo baladí el modo de medir dicha eficiencia. Para resolver esta circunstancia, en la década de los 70 numerosos científicos se interesaron por la complejidad computacional de los problemas y los algoritmos. En muchos casos se asimila el rendimiento algorítmico a la medida del tiempo medio de ejecución empleado por un procedimiento para completar su operación con un conjunto de datos. Además, es posible relacionar el esfuerzo de cálculo con la dimensión del problema a resolver.

Un algoritmo muestra una complejidad polinómica si necesita un tiempo O(nk), donde n muestra la dimensión de entrada y k es una constante independiente de n. Si la función que denota la complejidad no está acotada por un polinomio, el algoritmo presenta una complejidad en tiempo exponencial.

 Un problema de decisión es aquel que puede ser contestado con una afirmación o una negación. Llamemos P a la clase de problemas de decisión que pueden ser resueltos en tiempo cálculo que crece de forma polinomial ante incrementos lineales del número de elementos que intervienen, y NP aquellos solubles en un tiempo polinomial indeterminado, es decir, que se puede resolver en tiempo polinomial con una máquina Turing no determinística (ordenador). Un ordenador no determinístico puede ser contemplado como un autómata capaz de ejecutar un número ilimitado (pero finito) de ejecuciones en paralelo. Sólo los problemas en P son resolubles eficientemente mediante algoritmos, no conociéndose un procedimiento polinomial de resolución para los NP, siendo obvio que P pertenezca NP. Si lo contrario también ocurriera, P pertenecería a NP, querría decir que para la mayoría de los problemas de interés existen algoritmos eficientes que los resolvieran. Sin embargo, no se conoce la forma de demostrar que la igualdad P=NP sea cierta, ni tampoco que haya problemas en NP que no estén en P, es decir, la existencia de algún problema en NP que no se pueda resolver en tiempo polinómico (ver Díaz et al., 1996).

Un problema X se dice que es NP-completo (NPC) si (más…)

Universidad Politécnica de Valencia