Variedad solución (I)

Durante este curso de máster que estoy haciendo me he ido empapando de una idea, todavía expresada de manera bastante vaga en mi cabeza, pero que me parece interesante. La idea consiste en que a muchos problemas se les puede asociar un objeto geométrico llamado comúnmente variedad solución. Esto permite, de manera bastante sistemática, aplicar técnicas geométricas al estudio de problemas en los que, en principio, no era completamente evidente cómo hacerlo. El otro día tuve una clase de la que disfruté mucho y que me dejó pensando durante un buen rato, uno de esos momentos en los que tu cerebro hace click y tienes la sensación de entenderlo todo mejor. Queriendo dejar constancia de esto en mi diario, tengo previsto escribir dos entradas: la de hoy, contando lo que entendí de la clase del otro día, y otra aplicándolas a un problema concreto: la demostración de una versión generalizada del Teorema Fundamental del Álgebra.

Libros 01/03/2014

He subido a Netkups unos pocos libros, sobre todo de matemáticas, por si alguien (o yo mismo, supuesto que mi ordenador sufriera un accidente) los necesita en algún momento.

Link

La gran mayoría de ellos los he usado en el pasado para hacer algún trabajo y otros los he consultado para otras cosas, así que los temas que tratan son muy variados. En el futuro, si amplío la colección, subiré la correspondiente actualización. Aquí dejo la lista:

Fernando, J. F.; Gamboa, J. M.;  "Estructuras Algebraicas: Divisibilidad en Anillos Conmutativos".
Fernando, J. F.; Gamboa, J. M.; "Ecuaciones Algebraicas: Extensiones de Cuerpos y Teoría de Galois".
Atiyah, M. F.; Macdonald, I. G.; "Introduction to Commutative Algebra".
Eisenbud, D.; "Commutative Algebra with a View Toward Algebraic Geometry".
Kreuzer, M.; Robbiano, L.; "Computational Commutative Algebra 1".
Kreuzer, M.; Robbiano, L.; "Computational Commutative Algebra 2".
Iserles, A.; A First Course in the Numerical Analysis of Differential Equations".
Li, M.; Vitány, P.; "An Introduction to Kolmogorov Complexity and its Applications".
Gathen, J.; Gerhard, J.; "Modern Computer Algebra".
Walker, R. J.; "Algebraic Curves".
Boyce, W. E.; DiPrima, R. C.; "Ecuaciones Diferenciales y Problemas con Valores en la Frontera".
DeGroot, M. H.; Schervish, M. J.; "Probability and Statistics".
Lehmann, E. L.; Romano, J. P.; "Testing Statistical Hypotheses".
Von Neumann, J.; "Mathematical Foundations of Quantum Mechanics".
Eisenbud, D.; "The Geometry of Syzygies".
Hulek, K.; "Elementary Algebraic Geometry".
Lang, S.; "Introduction to Algebraic Geometry".
Perrin, D.; "Algebraic Geometry".
Smith, K. E.; Kahanpää, L.; Kekäläinen, P.; Traves, W.; "An Invitation to Algebraic Geomerty".
Lee, J. M.; "Introduction to Smooth Manifolds".
Do Carmo, M. P.; "Geometría Diferencial de Curvas y Superficies".
Do Carmo, M. P.; "Riemannian Geometry".
O Neill, B.; "Semi-Riemannian Geometry with Applications to Relativity".
Kline, M.; "Mathematical Thought from Ancient to Modern Times (Vol 1)".
Kline, M.; "Mathematical Thought from Ancient to Modern Times (Vol 2)".
Kline, M.; "Mathematical Thought from Ancient to Modern Times (Vol 3)".
Munkres, J.; "Topology".
Hatcher, A.; "Algebraic Topology".
Lee, J. M.; "Introduction to Topological Manifolds".
Guillemin, V.; Pollack, A.; "Differential Topology".
Hirsch, M. W.; "Differential Topology".
Milnor, J. W.; "Topology from the Differentiable Viewpoint".
Tu, L. W.; "Introduction to Manifolds".

Matriz de incidencia de un grafo y su homología

Muchas veces cuando se da un curso de Teoría de Grafos se introduce el concepto de matriz de incidencia, una matriz cuyas filas representan las aristas del grafo y cuyas columnas representan los vértices, de tal modo que la posición $(i,j)$ de la matriz es un $1$ si la arista $i$ es incidente a vértice $j$, y un $0$ si no lo es. Existe una generalización más o menos natural de esta matriz para grafos dirigidos: la matriz de incidencia dirigida, que en la posición $(i,j)$ tiene un $1$ si la arista $i$ "sale" del vértice $j$, un $-1$ si la arista $i$ "entra" al vértice $j$, y un $0$ si la arista $i$ no es incidente a vértice $j$.

Dataset: Menéame

Me he bajado Menéame para un proyecto de minería de datos y pongo aquí el dataset que tanto esfuerzo me ha costado conseguir por si alguien lo quiere. El formato de los datos es texto plano. Consiste en 53.088 filas, cada una de ellas conteniendo información de una noticia publicada en la portada de Menéame entre septiembre de 2010 y hoy. Por algún motivo he tenido problemas para parsear las noticias más antiguas, así que hasta esa fecha he podido llegar. Contiene algunos fallos, pero son despreciables dado el volumen de datos.

La primera fila contiene los nombres de las columnas. A partir de la segunda, cada fila contiene 7 campos separados por la secuencia de caracteres ' ;; ' (espacio, punto y coma, punto y coma, espacio). Los campos son

1. Cabecera de la entrada (titular) [texto]
2. Entradilla [texto]
3. Número de meneos de la noticia [entero]
4. Número de clics de la noticia [entero]
5. Url de la noticia en Menéame [texto]
6. Url de la página a la que dirige la noticia [texto]
7. Nombre del usuario que publicó la noticia [texto]

El dataset se puede descargar aquí:

http://netkups.com/?d=5c60398812ce3

P, NP, NP-completo: aclaración para profanos

A mucha gente le suena el problema P vs. NP porque ha salido en Futurama, porque ha salido en Los Simpson, o porque ha leído algo sobre ello en una entrada de Menéame. Como todo concepto científico más o menos avanzado que se hace popular, mucha gente lo ha entendido mal y va por ahí diciendo burradas como que NP significa No Polinomial, y cosas así. Aunque entender con algo de profundidad el problema requeriría un curso entero dedicado a ello, sí que creo que se puede intentar explicar el asunto de manera rápida, sin reparar en las sutilezas pero también sin llevar a engaños.

Qué pequeño es Q y qué raros son los abiertos

Me he encontrado con un problema que me ha parecido curioso: si un conjunto abierto $E$ verifica $\mathbb{Q} \subsetneq E \subsetneq \mathbb{R}$, ¿es verdad que $E$ debe ser igual a $\mathbb{R}$ salvo, a lo sumo, un conjunto de medida cero? Sabiendo que $\mathbb{Q}$ es un conjunto denso en $\mathbb{R}$ con la topología usual, y que un abierto es algo "gordito" en el sentido de que ningún abierto mide $0$, la existencia de un abierto que recubra todos los naturales y que mida menos que $\mathbb{R}$ es algo contraintuitiva.

Tests de primalidad

Para mi asignatura de Complejidad Computacional he hecho un trabajo más o menos bibliográfico, más o menos divulgativo, sobre tests de primalidad. La estrella, digamos, del trabajo, es la demostración desmenuzada, en términos algo más elementales que los del paper original, del test AKS. Aparecen también, sin tanto detalle, los tests probabilistas de Fermat, Miller-Rabin y Solovay-Strassen. Aquí lo dejo.

Link