Ultimamente me encuentro que ando muy liado como para escribir posts ‘originales’ en el blog pero, al mismo tiempo, ultimamente hay gente que me está pidiendo dos cosas: a ver si publico más recetas en el blog y a ver si doy más detalles sobre la asignatura de complejidad computacional. Pues me veo que voy a poder matar dos pajaros de un tiro… durante las próximas semanas, voy a ir publicando poco a poco mis recetas y también contando, de manera sencilla, lo que estoy aprendiendo sobre complejidad computacional.
En lo referente a las recetas, en el blog sólo he publicado un par de recetas (mi ‘famoso’ chili con carne, y un pastel de almendras que llevamos comiendo en mi casa desde tiempos inmemoriables). Como a lo largo de este último año he ido acumulando bastantes recetas (casi todas sencillas pero sabrosas), pues no me cuesta nada ir pasandolas a limpio poco a poco para publicarlas en el blog. Os puedo adelantar que estas recetas no son nada finolis, pero seguro que le vienen bien a cualquier persona que, al igual que yo, se ha emancipado recientemente. Son recetas ‘de toda la vida’ que, de momento, yo no consigo encontrar en los libros de cocina, que suelen centrarse en recetas como “Morritos de nutria en una salsa de frutas tropicales con sugerencia de comino”. Joder, a veces me apetece un plato de lentejas y nada más.
Y en cuanto a la complejidad computacional, voy a empezar por exponer los contenidos de mi charla Limites Computacionales (que impartí en los Cursillos de Julio 2005 de la Facultad de Ingeniería de la Universidad de Deusto), para establecer una buena base de Teoría de la Computación, para que luego pueda centrarme en las jartadas de complejidad computacional que nos están contando este trimestre :-)
En fin… para empezar, una receta para hacer magdalenas que publicaré en breves instantes.
Comentar que hay una web que puede ser interesante para el tema de recetas que es:
http://www.cookingforengineers.com/
que incluye una lista larga de recetas:
http://www.cookingforengineers.com/toc.php
con screenshots y demás :)
“Inmemorable” o “inmemorial”.
Inmemoriable, simplemente, no existe ;D(para que veas que no sólo leemos tus POSTs, además los procesamos y todo)
Un abrazo, y no te tomes en serio el tirón de orejas. Ya sabes que soy un puñetero con esas cosas ;-)
Hola,
otro posible “modelo computacional” que lleva 10 años ya en danza es el que presentó el Sr. Adleman aplicado al “prolema del viajante”, y que se denomina DNA computing (http://www.rsasecurity.com/rsalabs/node.asp?id=2355):
http://genome.imim.es/courses/BioinformaticaUPF/T25/adleman1994a.pdf
Al final, las hebras de DNA son máquinas masivamente paralelas aunque se ha criticado el algoritmo de Adleman porque aunque el tiempo de ejecucion del algoritmo es lineal para cualquier instancia del problema del viajante, para cumplir con el primer paso del algoritmo la cantidad de masa necesaria crece exponencialmente (problema técnico de las PCRs).
Actualmente se está trabajando para mejorar este algoritmo:
http://www.isys.dia.fi.upm.es/~gblasco/TallerADN/LCS.pdf
Un saludo.
Uhm, eso del DNA Computing suena interesante. Me pregunto si hay algun paper donde discutan ese modelo de computación desde el punto de vista de la complejidad. En mi presentación, por ejemplo, discuto la computación cuantica cómo modelo alternativo. Aunque es un modelo equivalente a la máquina de Turing (es decir, no permite resolver problemas indecidibles), sí que permite resolver ciertos problemas más eficientemente que un ordenador ‘tradicional’ (p.ej. el problema de la factorización se puede resolver en tiempo polinómico con un ordenador cuantico). Eso sí, se conjetura que los ordenadores cuanticos no pueden resolver eficientemente problemas NP-completos, con lo cual la computación cuantica no supondría algo revolucionario desde el punto de vista de la complejidad. Pero si el DNA Computing puede resolver un problema NP-completo como el Traveling Salesman Problem en tiempo polinómico, pues eso sí que sería un pelín acojonante.
Lo dicho: ¿Alguien se sabe algun paper o web que discuta las “complexity classes” que surgen con el DNA Computing?
Bueno, pues googleando un poco aquí te paso un par de links que parecen interesantes:
http://www.cs.virginia.edu/~rcs5y/dna/narayanan98dna.pdf
y
http://www.csc.liv.ac.uk/~ctag/archive/t/CTAG-97001.ps
ya nos contarás qué te parecen (o si encuentras otras cosillas) que aunque estas cosas se ven en la carrera de refilón (un par de horitas de clase para la teoría de complejidad y el amigo Turing) la verdad es que no estoy nada puesto en el tema…
Un saludo!