lunes, 29 de agosto de 2011

P ≠ NP

P ≠ NP

Al parecer un científico de HP acaba de presentar a revisión la demostración de la proposición 'P no es igual a NP', que viene a decir que la clase de complejidad de la resolución de problemas Polinomiales es distinta de la de los No Polinomiales.

Su nombre es Deolalikar Vinay, un investigador de HP, y podría tornarse un millón de dólares más rico si es verdad lo que escribió en su último artículo científico: P ≠ NP!

Ya le han incluso creado una página en Wikipedia, y los wikipedistas están ya, como de costumbre, ferozmente debatiendo si su notabilidad es o no (todavía) suficiente como para estar en la enciclopedia en línea.

Será otro que se equivoca? ¿O esta vez vamos a tener una respuesta definitiva a la pregunta del millón de la Ciencia de la Computación?

En realidad, NP no significa "No Polinomial", sino, "No-determinista Polinomial". Los problemas de la clase NP pueden ser resueltos en tiempo polinomial por una máquina de Turing No-Determinista.

Este tipo de máquina es una construcción mental, y puedes pensar en ella como un tipo de máquina que "magicamente" sabe cuál es la ruta más corta de entre todas sus posibles rutas de ejecución, y esa es la que sigue. O también puedes pensar en ella como una máquina masivamente paralela que puede ejectuar simultáneamente todas sus posibles rutas de ejecución, y detenerse cuando una de ellas finaliza.

El que un problema sea resoluble en tiempo polinomial por una máquina así, a primera vista, no parece gran cosa, ya que la máquina "hace trampa" al seguir siempre la vía más corta. ¡Pero es que hay problemas que ni con una máquina mágica como esa podrían resolverse en tiempo polinomial!

Los problemas tipo P son los que se pueden resolver en tiempo polinomial con una máquina de Turing determinista, o lo que es lo mismo, con cualquier ordenador convencional.

El que P sea diferente de NP significa que los problemas de la categoría NP, no se pueden resolver en tiempo polinomial en una máquina determinista, requieren una no-determinista para ello. Podría parecer que esto pone a salvo los algoritmos criptográficos (que se basan en que los tiempos necesarios para "romper" el código en un computador determinista son prohibitivamente grandes). Sin embargo, no está demostrado que una máquina no-determinista no pueda ser construida. Algunos piensan que la computación cuántica podría crear una máquina así. Si se pudiera construir una máquina así, los problemas NP (entre ellos el "romper" un código criptográfico) podría ser resuelto en tiempo polinomial.


Clases de complejidad P y NP


Diagrama de clases de complejidad para el caso en que P ≠ NP. La existencia de problemas fuera tanto de P como de NP-completos en este caso fue determinada por Ladner.
La relación entre las clases de complejidad P y NP es una pregunta que aún no ha podido ser respondida por la teoría de la complejidad computacional. En esencia, la pregunta ¿es P = NP ? significa: si es posible "verificar" rápidamente soluciones positivas a un problema del tipo SI/NO (donde "rápidamente" significa "en tiempo polinómico"), ¿es que entonces también se pueden "obtener" las respuestas rápidamente?
Los recursos comúnmente estudiados en complejidad computacional son:
– El tiempo: mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolver un problema.
– El espacio: mediante una aproximación a la cantidad de memoria utilizada para resolver el problema.
Los problemas se clasifican en conjuntos o clases de complejidad (L, NL, P, PCompleto, NP, NP Completo, NP Duro...).Nosotros nos vamos a centrar en las clases P y NP.
Se lo considera el problema más importante en este campo--el Clay Mathematics Institute ha ofrecido un premio de $1 millón de dólares norteamericanos para quién desarrolle la primera demostración correcta.

domingo, 28 de agosto de 2011

funcion

Función

Una funcion la denotamos por “f” es una relación entre un conjunto dado X (el dominio) y otro conjunto de elementos Y (el codominio) de forma que a cada elemento x del dominio le corresponde un único elemento del codominio f(x). Se denota por: f: X—-> Y

Comúnmente, el término función se utiliza cuando el codominio son valores numéricos, reales o complejos. Entonces se habla de función real o función compleja mientras que a las funciones entre conjuntos cualesquiera se las denomina aplicaciones.

Una función puede considerarse como un caso particular de una relación o de correspondencia matemática. Cada relación o correspondencia de un elemento x pertenece a X con un (y sólo un) y pertenece a Y se denota f(x)= y , en lugar de

(x,y) pertenece f.

Formalmente, pedimos que se cumplan las siguientes dos condiciones:

Condición de existencia: Todos los elementos de X están relacionados con elementos de Y.

Condición de unicidad: Cada elemento de X está relacionado con un único elemento de Y.

Clasificación de las funciones:

Dados dos conjuntos X, Y, consideremos a todas las posibles aplicaciones (funciones) que pueden formarse entre estos dos conjuntos. Podemos diferenciar los siguientes casos:

Si a cada imagen le corresponde una única preimagen, inyectiva.

Si la imagen de la función es igual al codominio, sobreyectiva o suprayectiva.

Una función que sea inyectiva y sobreyectiva simultáneamente, se denomina biyectiva .

Puede haber funciones que sean biyectivas, inyectivas pero no suprayectivas, supreyectiva pero no inyectiva o que no se cumple ninguna de esas condiciones, en cuyo caso no tiene un nombre específico.

Definiciones alternas: sea f: X —> Y dada y sea b un elemento cualquiera del codominio Y. Consideremos la ecuación:

f(x)= b (*).

La función es suprayectiva o sobreyectiva si, y sólo si, la ecuación (*) siempre tiene al menos una solución.

La función es inyectiva si, y sólo si, la ecuación (*) tiene a lo más una solución.

La función es biyectiva cuando, y sólo cuando, es inyectiva y suprayectiva a la vez.


Vamos a ilustrar esos diferentes tipos de funciones (aplicaciones) en un diagrama de venn, el conjunto universal U, representado por un rectángulo, es el conjunto de todas las posibles aplicaciones, el conjunto A es aquel de las aplicaciones inyectivas, y el conjunto B aquel de las sobreyectivas, esto nos permite ver los distintos tipos de aplicaciones de un modo gráfico.

relacion

Una relación , la llamamos “R” cuando es la relación de los conjuntos A,B….etc es un subconjunto del producto cartesiano A x B x ….. Zn. Una Relación binaria es una relación entre dos conjuntos. El concepto de relación implica la idea de enumeración, de algunos de los elementos, de los conjuntos que forman tuplas.

R(a,b….zn) o bien (a,b….zn) pertenece a R.

Un caso particular es cuando todos los conjuntos de la relación son iguales: A=B….en este caso se representa como AxAxA….A como An. , pudiéndose decir que la relación pertenece a A a la n. R pertenece An.

Tipos de relaciones

En las relaciones se diferencian los tipos según el número de conjuntos en el producto cartesiano, que es el número de términos de la relación:

Relación unaria: un solo conjunto.

Relación binaria: con dos conjuntos.

Relación ternaria: con tres conjuntos.

Relación cuaternaria: con cuatro conjuntos.

Relación n-aria: caso general con n conjuntos.

Strong Induction Principle Pinohole

(Principio Básico de la Combinatoria)

Principio de Inducción Fuerte : Dejar “D” ser un subconjunto de los números enteros no negativos Z* con las propiedades :

a) El 0 entero esta en D.

b) Cada vez que el intervalo [0,n] esta contenida en D.

Se puede demostrar que n+1 también esta en D. En estas

condiciones D=Z*.


El número de Erdős es un modo de describir la distancia colaborativa, en lo relativo a trabajos matemáticos entre un autor y Erdős. El término fue acuñado en honor al matemático húngaro Paul Erdős, uno de los escritores más prolíficos de trabajos matemáticos.
Para que a una persona se le pueda asignar un número Erdős, ésta debe de haber co-escrito un trabajo matemático con un autor con un número Erdős finito. Paul Erdős tiene un número Erdős de cero. Si el número Erdős más bajo de un coautor es X, entonces el número Erdős del autor es X+1.
Erdős escribió cerca de 1500 artículos matemáticos, la mayoría de ellos en co-autoría. Tuvo 509 colaboradores directos;1 éstas son las personas con un número Erdős de 1. La gente que hubo colaborado con ellos (pero no con Erdős mismo) tiene un número Erdős de 2 (6,984 personas), aquellas personas que han colaborado con gente que tiene un número Erdős de 2 (pero no con Erdős mismo, ni con alguien con un número Erdős de 1) tienen un número Erdős de 3, y así sucesivamente.
Una persona con ninguna conexión a la cadena de coautoría de Erdős tiene un número Erdős indefinido o infinito. Hay por supuesto, espacio para la ambigüedad acerca de lo que constituye un vínculo entre dos autores; según el sitio web del Proyecto de Número de Erdős dice: "Nuestro criterio para la inclusión de un rango entre vértices u y v es alguna investigación colaborativa entre ellos, teniendo como resultado un trabajo publicado. Cualquier número de co-autores adicionales es permitido", pero el Proyecto no incluye publicaciones cuya índole no sea de investigación, como libros de texto, obituarios y cosas por el estilo.

miércoles, 24 de agosto de 2011

Paul Erdős

Paul Erdős, nacido (26 de marzo de 1913 – 20 de septiembre de 1996), fue un matemático húngaro inmensamente prolífico y famoso por su excentricidad que, con cientos de colaboradores, trabajó en problemas sobre combinatoria, TEORIA DE GRAFOS, teoría de números, análisis clásico, teoría de aproximación, teoría de conjuntos y probabilidad.
A la edad de 3 años ya sabía sumar y para los 4 ya podía calcular cuántos segundos había vivido una persona. Al pequeño Paul le apasionaban las matemáticas tanto como a sus padres, ambos matemáticos y profesores de dicha ciencia.
Cuando tenía sólo seis años de edad, ante el aumento del antisemitismo, su madre le sugirió realizar una conversión. "Puede hacer lo que quiera", dijo el muchacho, "pero voy a seguir siendo como yo nací. (judío)".
A pesar de las restricciones a los judíos de entrar en las universidades de Hungría, a Erdös, como ganador de un examen nacional, se le permitió ingresar en 1930. Estudió para su doctorado en la Universidad Pázmány Péter de Budapest.
Obtuvo su doctorado en 1934, a la edad de 21 años, y dejó Hungría para radicarse en Mánchester, Inglaterra, debido al recrudecimiento del fascismo en su país de origen y al aumento del odio hacia los judíos.
Erdős fue uno de los publicadores de artículos matemáticos más prolíficos de todos los tiempos, únicamente superado por Leonhard Euler. Escribió aproximadamente 1.500 artículos en el transcurso de su vida, colaborando con alrededor de 500 coautores. Él creía firmemente en las matemáticas como una actividad social.
Dentro de sus aportaciones, destacan contribuciones a la teoría de Ramsey y la aplicación del método probabilista.
Debido a sus numerosos aportes, colaboradores y amigos inventaron el número de Erdős como un homenaje con tintes de humor matemático: Erdős tiene asignado el número 0, todos aquellos que colaboraron en algún artículo con él tienen el 1, alguien que haya colaborado con alguno de sus colaboradores tiene el 2, y así sucesivamente.... Sencillas estimaciones comprueban que el 90% de los matemáticos activos tienen un número de Erdős menor que 8 (parece sorprendente si uno no conoce la teoría de Seis grados de separación).

lunes, 22 de agosto de 2011

graficas bipartitas

Sea r ≥ 2 un entero. Una grafica G = (V, E) es r-partita si existe una particion de V en r conjuntos independientes, que llamamos clases. En vez de decir 2-partita, decimos bipartita.
Una grafica r-partita donde cada par de vertices de distintas clases es adyacente se llama una grafica r-partita completa, o tambien multipartita completa.
Una grafica r-partita completa con clases de ni vertices se denota Kn1,...nr;cuando n1 = . . . = nr = s, la denotamos Ks,r. Entonces Ks,r es la grafica r-partita completa donde cada clase tiene exactamente s vertices. Las graficas K1,n son arboles pero se llaman estrellas por obvias azones.

Teorema 1. Una grafica es bipartita si y solo si no contiene un ciclo impar.

Demostracion. Sea G una grafica bipartita con biparticion (V1, V2), y sea x1x2 · · · xℓ un ciclo de G. Podemos suponer que x1 ∈ V1. Entonces x2 ∈ V2, x3 ∈ V1, etc.
Entonces xi ∈ V1 si y solo si i es impar. Ya que xℓ ∈ V2, ℓ es par.
Ahora supongamos que G no contiene ningun ciclo impar. Ademas, podemos suponer que G es conexa, porque una grafica es bipartita si y solo si cada componente es bipartita. Sea x ∈ V (G) y definimos V1 = {y ∈ V (G) | dist(x, y) ≡ 1 (mod 2)}, V2 = V (G) \ V1. Si existiera una arista xy ∈ E(G) tal que x, y ∈ Vi (i = 1 o 2), entonces G contendrıa un ciclo impar, lo que es mposible. Por lo tanto G es bipartita.

miércoles, 17 de agosto de 2011

Funcion Generadora

una función generadora o función generatriz es una serie formal de potencias cuyos coeficientes codifican información sobre una sucesión an cuyo índice corre sobre los enteros no negativos.
Hay varios tipos de funciones generadoras: funciones generadoras ordinarias, funciones generadoras exponenciales, la serie de Lambert, la serie de Bell y la serie de Dirichlet; de las cuales abajo se ofrecen definiciones y ejemplos. Cada sucesión tiene una función generadora de cierto tipo. El tipo de función generadora que es apropiada en un contexto dado depende de la naturaleza de la sucesión y los detalles del problema que se analiza.
Las funciones generadoras son expresiones cerradas en un argumento formal x. A veces, una función generadora se «evalúa» en un valor específico x=a pero hay que tener en cuenta que las funciones generadoras son series formales de potencias, por lo que no se considera ni se analiza el problema de la convergencia en todos los valores de x.
Por lo mismo es importante observar que las funciones generadoras no son realmente funciones en en el sentido usual de ser mapeos entre un dominio y un codominio; el nombre es únicamente el resultado del desarrollo histórico de su estudio.

La función generadora ordinaria de una sucesión (an) = a0, a1, a2, a3 ... se define como

Es común usar la expresión función generadora sin mayor calificativo, para referirse a este tipo de función.

Una función generadora es una cuerda de tender en la que colgamos una sucesión de números para mostrarla
Herbert Wilf

DONALD KNUTH


Donald Ervin Knuth, (nacido el 10 de enero de 1938 en Milwaukee, Wisconsin) es uno de los más reconocidos expertos en ciencias de la computación por su seminal investigación dentro del análisis de algoritmos y compiladores. Es Profesor Emérito de la Universidad de Stanford.
Se le conoce principalmente por ser el autor de la obra "The art of computer programming" (El arte de programar computadoras), una de las más respetadas referencias en el campo de las ciencias de la computación. Sentó las bases y dio nombre al análisis de algoritmos, y ha realizado numerosos aportes a varias ramas teóricas de la informática. Es el creador de TEX, del sistema de diseño de tipos METAFONT y del estilo de programación conocido como programación literaria (Literate programming).

Knuth es un programador conocido por su humor geek: ofrece una recompensa de 2,56 dólares a quien encuentre errores conceptuales o tipográficos en sus libros ( «256 centavos son 1 dólar hexadecimal»), y por otro lado ofrecía 3,16 por errores en 3:16 Bible Texts Illuminated. Numeró las distintas versiones de TEX de manera que se aproximaran al número π (3, 3.1, 3.14, etc.), al igual que los números de versión de MetaFont se van aproximando a e. Su cita más célebre, al enviarle sus comentarios a un colega autor de un algoritmo, es: «Cuidado con los errores en el código anterior; sólo he demostrado que es correcto, no lo he probado».
Knuth es el autor de 3:16 Bible Texts Illuminated (1991, ISBN 0-89579-252-4), libro en el que intenta examinar la Biblia por un proceso de «muestreo estratificado aleatorio», es decir, un análisis del capítulo 3, versículo 16 de cada libro. Cada versículo se acompaña de un renderizado en arte caligráfico, realizado por un grupo de calígrafos capitaneado por Hermann Zapf.
Está casado con Jill Carter Knuth. Tienen dos hijos.

Funcion Sobreyectiva

una función es sobreyectiva (epiyectiva, suprayectiva, suryectiva, exhaustiva o subyectiva), si está aplicada sobre todo el codominio, cuando cada elemento de "Y" es la imagen de como mínimo un elemento de "X".
Los siguientes diagramas corresponden a función sobreyectiva:


Funcion Biyectiva

una función es biyectiva si es al mismo tiempo inyectiva y sobreyectiva; es decir, si todos los elementos del conjunto de salida tienen una imagen distinta en el conjunto de llegada, y a cada elemento del conjunto de llegada le corresponde un elemento del conjunto de salida.

Una implicación directa es que en una función biyectiva la cardinalidad del conjunto de salida o dominio, y el de llegada o codominio, son iguales. Esto también se puede ver en el ejemplo, donde |X|=|Y|=4.

Funcion Inyectiva

De manera más precisa, una función es inyectiva cuando se cumple alguna de las dos afirmaciones equivalentes:
Si x1,x2 son elementos de tales que f(x1) = f(x2), necesariamente se cumple x1 = x2.
Si x1,x2 son elementos diferentes de , necesariamente se cumple
Los siguientes diagramas corresponden a función inyectiva:


domingo, 14 de agosto de 2011

graficas


Un grafo o gráfica es el principal objeto de estudio de la teoría de graficas.
Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).
Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras. Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).
Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias exactas y las ciencias sociales.
"Definiciones"
Un grafo G es un par ordenado G = (V,E), donde:
V es un conjunto de vértices o nodos, y
E es un conjunto de aristas o arcos, que relacionan estos nodos.
Normalmente V suele ser finito. Muchos resultados importantes sobre grafos no son aplicables para grafos infinitos.
Se llama orden del grafo G a su número de vértices, | V | .
El grado de un vértice o nodo V es igual al número de arcos E que se encuentran en él.
Un bucle es una arista que relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final coinciden.


vertices


En teoría de grafos, un vértice o nodo es la unidad fundamental de la que están formados los grafos. Un grafo no dirigido está formado por un conjunto de vértices y un conjunto de aristas (pares no ordenados de vértices), mientras que un grafo dirigido está compuesto por un conjunto de vértices y un conjunto de arcos (pares ordenados de vértices). En este contexto, los vértices son tratados como objetos indivisibles y sin propiedades, aunque puedan tener una estructura adicional dependiendo de la aplicación por la cual se usa el grafo; por ejemplo, una red semántica es un grafo en donde los vértices representan conceptos o clases de objetos.
Los dos vértices que conforman una arista se llaman puntos finales ("endpoints", en inglés), y esa arista se dice que es incidente a los vértices. Un vértice w es adyacente a otro vértice v si el grafo contiene una arista (v,w) que los une. La vecindad de un vértice v es un grafo inducido del grafo, formado por todos los vértices adyacentes a v.


sábado, 13 de agosto de 2011

problema de la pelicula "UNA MENTE INDOMABLE"





el ejercicio dice:

de la grafica
encontrar:
1) la matriz de adyacencia A
2) la matriz, dando el numero de 3 pasos
3) la funcion generadora de paseo desde los puntos i al j
4) la funcion generadora de paseo desde los puntos 1 al 3