• Matemáticos reconocidos poco conocidos

    Karl Weierstraß
    (1815 - 1897)

    Maestro de Cantor, Runge,  Schwarz  y de toda una generación de matemáticos alemanes, Weierstrass es el responsable de uno de los métodos más efectivos en Cálculo: el método épsilon (nombrado así pues su notación utiliza la letra griega ε). Gracias a este método se pudieron probar varios teoremas fundamentales para el fundamento de la matemática infinitesimal lo que a la postre permitió varios de los desarrollos tecnológicos de la actualidad.

    Nacido en Ostenfelde, Westphalia (ahora parte de Alemania) , en 1828, al establecerse su familia en Paderborn, ingresó al Gimnasio Católico (institución equivalente a la educación media superior) y paso mucho de su tiempo leyendo el Journal of Pure and Applied Mathematics,  que era la revista matemática líder en Europa.  

    Mientras era profesor en el Instituto Industrial de Berlín, Weierstrass desarrollo una de las más grandes ideas matemáticas hasta el momento.  En su “Introducción al Análisis” druante los años 1859-1860, dio al mundo una rigurosa metodología para que los matemáticos trabajaran con la noción de secuencias infinitas o series que alcanzaban un límite. 

    Hasta ese momento, mucho del desarrollo del cálculo Newtoniano se basaba en ideas, nociones que se sabían verdad pero no se habían demostrado rigurosamente. El concepto de “límite infinito” aplicado a variables fijas, como en la expresión “n tiende a infinito” no se sabía realmente su significado formal.  El método épsilon resolvió esto.

    Weierstrass razonó: En lugar de que el límite estuviera definido para n como el proceso de alcanzar el infinito, por qué no definimos una secuencia infinita que tenga un límite si para cualquier épsilon  ε, siempre puedes encontrar un entero n tal que para todos los enteros m>=n, el emésimo término de la secuencia siempre estuviera a ε del límite.

    Entre los conceptos que gracias al método épsilon se pudieron formalizar se encuentran:
    + El concepto de continuidad , pieza clave para el desarrollo de la ciencia
    + El teorema de Weierstraß que trata sobre máximos y mínimos locales, y
    + Teorema de Bolzano-Weierstrass , otra pieza fundamental en la construcción de los ladrillos fundamentales del cálculo: los números Reales.

    Mucho le debe la humanidad a este gigante Alemán de las matemáticas.

  • ¿Van a poder las máquinas resolver todos los problemas que los humanos no podemos? Parte I

    You say you got a real solution
    Well, you know
    We'd all love to see the plan
    Lenon-McCartney


    El título de este escrito bien podría haber sido "¿Es todo computable?", sin embargo, no sé que tan común es el término. Además, es parte de lo que quiero explicar aquí: el concepto de computabilidad.

    Pero antes de comenzar, una pequeña advertencia. Esta plática no tendrá nada que ver, por lo menos no de manera explícita, con la idea de si las máquinas son "inteligentes" o no; de si pueden "pensar" o no. De tal forma que tómenlo con calma todos los defensores a ultranza del homo sapiens sapiens como único poseedor de capacidades cognitivas.

    De manera muy informal, podemos decir que los problemas que una máquina puede resolver, son aquellos problemas que son computables. Y un problema computable, es aquel para el cual podemos dar su solución en forma de una receta para resolverlo. A estas recetas, en matemáticas y cómputo, se les conoce como algoritmos.

    Dentro del universo de problemas, existen problemas fáciles y problemas difíciles de resolver. Existen problemas para los cuales sabemos su solución, pero no sabemos si es la mejor de todas. Y existen problemas para los cuales no sabemos si tienen o no solución. Y existen problemas para los cuales sabemos su solución, pero no conocemos su receta, es decir, su algoritmo.

    Definiciones de algoritmo hay muchas. No hay un consenso general sobre una definición única en la actualidad. De manera general, una algoritmo es una secuencia de pasos, bien definidos en cuanto a contenido y orden, que nos dicen como resolver un problema, e implícitamente, el tiempo que nos llevará resolver. Se da por sentado que el procedimiento expuesto en la receta termina. Si el tiempo para resolver el problema es infinito, entonces la receta no se considera algoritmo.

    Por ejemplo, el algoritmo para conectarse a un foro de Internet, digamos La Trinchera, desde una computadora, podría ser más o menos así:

    Algoritmo Conectarse_Trinchera

    1. Prender computadora
    2. Activar una conexión a Internet
    3. Abrir un navegador
    4. Escribir la dirección www.latrinchera.org en la barra de direcciones y dar click en la tecla enter
    5. Se ve el sitio de la trinchera en el navegador?
    5.1 Si. Pasar al punto 6.
    5.2 No. Repetir desde el punto 4.
    6. Fin


    Es una secuencia de pasos, claros cada uno de ellos, uno sigue después de otro y la receta acaba. Podemos decir que el Algoritmo Conectarse_Trinchera es válido dentro de los parámetros actuales.

    Como se podrán imaginar, para que un algoritmo tenga sentido, debe de recibir cosas -entradas- y producir otras cosas -salidas. En nuestro ejemplo, la entrada podría ser el teclear la dirección, y la salida, ver el sitio en el navegador.

    A menera de breviaro cultural, la palabra algoritmo deriva en buena medida de un buen colega árabe llamado, Muhammad ibn Musa abu Abdallah al-Jwarizmi al-Madjusi al-Qutrubulli. En realidad el no invento ni el nombre ni el concepto, pero en la edad media se mezclaron varios cuestiones para que su nombre más el de sus escritos asociaran la palabra algoritmo con el concepto de procedimientos claros y precisos para resolver problemas o construir soluciones.


    Entonces, si las máquinas van a poder "hacer" sólo los problemas para los cuales exista un algoritmo para resolverlos, debemos platicar un poco más acerca de los algoritmos, antes de adentrarnos de lleno en los límites de la computabilidad.


    Una forma de clasificar a los algoritmos, es viendo que tan eficientes son. Y un modo de medir su eficiencia es midiendo el tiempo que les toma resolver el problema, en relación a sus entradas. Claro, un mismo algoritmo para sumar números enteros no tardará lo mismo en sumar 2 números que 2 billones. En 1965, J. Edmonds y A. Cobham propusieron que los dos casos fundamentales, correspondientes a lo que en la práctica llamaríamos malos y buenos algoritmos, fueran el tiempo polinómico y el tiempo exponencial que les tomara ejecutarse.

    Rapidamente, un tiempo polinómico es aquel que toma la forma tn, mientras que un tiempo exponencial toma la forma nt. La letra n representa el número de entradas y la letra t el tiempo que tardó en resolverse el problema. De manera general, al aumentar el valor de n, el exponencial tarda mucho más tiempo en resolver un problema que el polinómico. Simplemente hagan las cuentas con n=2 y t=5.


    En computación teórica, que en ciertos niveles no es otra cosas que matemáticas, se le llama P a la clase de problemas que se resuelven en tiempo polinómico: son los fáciles. Y a los algoritmos que tardan un tiempo exponencial, se les conoce como NP. Formalmente se les como problemas que no se pueden resolver en un tiempo polinómico no determinista.

    Muchos de los algoritmos con los cuales resolvemos nuestra vida diaria, son tipo del polinómico. Algunos terriblemente complicados, si, pero con la computación moderna los tiempos de solución son cada vez más rápidos. No se diga la mayor parte de los problemas clásicos de la matemática, como la geometría, pueden ser más que resueltos por máquinas, pues tenemos los algoritmos precisos para resolverlos.

    Ahora bien, los problemas NP no son necesariamente complejos en su planteamiento. Ni se imaginen que tiene que ver sólo con cuestiones científicas oscuras y entendibles por unos cuantos. No. Pueden ser tan mundanas como el siguiente ejemplo.


    El problema del Vendedor viajero1 o TSP por sus siglas en inglés.
    El problema del TSP dice:
    "Se le encarga a un vendedor que vaya a ofrecer su producto a las n ciudades principales de su país. Pero su presupuesto de viaje no es ilimitado, por lo que debe planear muy bien su ruta, de tal forma que visite cada una de las n ciudades sólo una vez, debe de regresar a la misma ciudad de la que parta, y su ruta deberá de ser la ruta más corta de todas las posibles".

    Este problema, que lleva con nosotros ya más de 100 años, resulta que para sorpresa de muchos, es NP, conforme se aumenta el número de ciudades. Y peor aún, las soluciones que existen para n grandes (85,900 es el record mundial) no se saben si son óptimas, es decir, no existe una demostración formal de que el algoritmo que resuelve el problema sea el mejor.

    Y así como este, varios problemas no sabemos si tenemos la mejor solución en nuestras manos.

    Ahora bien, que tienen que ver todo esto de P y NP con nuestro planteamiento inicial sobre los problemas que podrán resolver la máquinas? Pues que no importa si es N o NP para la máquina. El algoritmo ya existe, entonces se lo puedo enseñar a una máquina. Y seguro lo resuelve más rápido que nosotros.

    Lo que tal vez no nos podrá decir una máquina, es si si un problema NP, podrá ser alguna vez P. Es decir, encontrar una solución en tiempo polinómico a un problema que se sabe exponencial.

    No se ha demostrado en la actualidad que P sea distinto a NP. Es obvio, pero matemáticamente no existe una demostración formal. No existe una receta para saber que esto es cierto. La frase N=NP no sabemos si es cierta o falsa. Sera cierta independientemente de la teoría formal de conjuntos? Nadie tiene ni la más remota idea. Es un problema no computable actualmente.


    Para la próxima entrega platicaremos de manera un poco más formal de que es computable y que no. Y de cómo las máquinas si pueden resolver problemas que para nosotros no son obvios, pero como también hay problemas que no van a poder resolver, y un humano si.


    1 Wiki TSP
    Comments 5 Comments
    1. Sirius2b's Avatar
      Sirius2b -
      Hola, @Orkcloud... me gustó tu artículo...

      Ciertamente Algoritmia es una de las materias que quisiera estudiar algún dia... todo esto es bellisimo.

      Por cierto, la imagen que pusiste, me recordó un documental "Kasparov vs. la Máquina"... que voy a poner en el foro libre, saludos.
    1. Mobit's Avatar
      Mobit -
      Orkcloud:

      No se leíste hace algunos años un reportaje despachado en San Antonio Texas? el cual hablaba acerca de un algoritmo desarrollado en la Universidad de Texas, mismo que permitía a una computadora resolver un problema sin almacenar pasos intermedios, lo cual implica que la computadora aprendía y tomaba decisiones, en estricto sentido una fase inicial del pensamiento.
      Me gustaria tu coimentario ya que eres de los pocos junto con nuestro amigo Sirio, leidos y escribeidos.
    1. Lagos's Avatar
      Lagos -
      no
    1. orkcloud's Avatar
      orkcloud -
      Estimado Sirius, análisis de algoritmos, en serio, es muy divertido. Son álgebras sobre todo, con su buena dosis de cálculo.


      No me suena mi Mobit, pero por supuesto que hay software que toma decisiones "por si sólo" de la misma manera en que suponemos ciertos procesos cerebrales lo hacen. Hay todo un avance en sistemas que se auto-organizan al respecto. Este es el primero de 2 o tres artículos sobre el tema, así que a ver si puedes seguir los demás.

      Lagos, lo interesante, según yo, es decir por qué no.
    1. Lagos's Avatar
      Lagos -
      Porque no?...

      Luego lo escribo.
    Comments Leave Comment

    Click here to log in

    ¿Cuál es la quinta palabra de ésta pregunta? Escribe en minúsculas.