Unidad 1: Fácil y difícil. Dos tipos de trayectorias. Bienvenidos/as a Computación en Sistemas Complejos. Prácticamente, cada sistema complejo se compone de flujos, no solo de energía y recursos, sino también de información. La información se almacena, transmite, transforma, y de eso trata la computación. Los cerebros computan, las células computan, las computadoras computan, algunas personas dicen que las ciudades computan. Entonces, vamos a estar examinando tanto el poder como las limitaciones de la computación, por qué ciertos problemas son cualitativamente fáciles o difíciles de resolver que otros, por qué algunos son completamente imposibles y qué tipos de computación vemos tanto en aparatos tecnológicos como en el entorno natural. Entonces, comenzaremos viendo dos tipos de trayectorias. Dos problemas que son superficialmente muy similares, y sin embargo, uno resultará ser mucho más difícil que el otro y trataremos de averiguar por qué. De acuerdo, este es un viejo mapa de los puentes de Königsberg, quizás antes hayas visto este problema -Königsberg ahora se llama Kaliningrado- y tenemos aquí el río Pregolia, y hay dos islas en el río, y muchos puentes entre ellas que las conectan con las dos orillas del río. Entonces, los ciudadanos de Königsberg, aparentemente, solían pasar las tardes de los domingos, entre otras cosas, queriendo saber si es posible cruzar cada uno de estos puentes una sola vez. Entonces, tratemos de ver si podemos encontrar una forma de hacer esto. Podemos ir hacia arriba, después por abajo y luego por allá. Ahora nos atoramos. De acuerdo, retrocedamos y tratemos algo distinto. Podemos ir arriba -nos atoramos de nuevo. De acuerdo. Entonces, una forma de resolver este problema para saber si hay una manera de cruzar cada puente una sola vez, es a través de la búsqueda. Podríamos seguir buscando entre todas las posibilidades. Pero, de hecho, Euler -Leonhard Euler-, uno de los grandes matemáticos que básicamente inventó lo que llamamos Teoría de Grafos, para resolver este problema nos mostró que no necesitamos buscar en absoluto. Lo que vamos a hacer es abstraer cada uno de los cuatro lugares, ambos lados del río y las dos islas, en un nodo y una red, convirtiéndose los puentes en enlaces o aristas de esta red. Entonces, Euler señaló que, de acuerdo con las reglas del juego, dado que solo se puede cruzar cada puente una sola vez, cada vez que entres en un lugar a través de un puente, debes dejarlo por otro, lo cual significa que los puentes en cada lugar deben venir en pares. Eso significa que, con excepción, tal vez, de donde comenzamos y terminamos, cada nodo debe tener un número par de aristas tocándolo, lo que llamamos un grado par en Teoría de Grafos. Bueno, solo míralos y verás que todos tienen grado impar. Tres, tres, tres y cinco. Entonces, inmediatamente sabemos que ningún recorrido es posible. No necesitamos buscar en absoluto, nos hemos saltado el proceso de búsqueda completamente. Ahora, eso es útil, ya que si se tratara de los puentes de Venecia o -de hecho, Pittsburgh tiene muchos puentes-, el buscar entre todas estas posibilidades tomaría una enorme cantidad de tiempo. La idea de Euler sobre este problema permite saltarnos ese proceso de búsqueda.