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.