• Un algoritmo es una secuencia finita de pasos que se utilizan para resolver un problema.
  • Los algoritmos no necesariamente son utilizados por computadoras, son utilizados por la gente.
  • La palabra algoritmo viene del nombre de un matemático persio autor de un libro del siglo noveno acerca de cómo hacer matemáticas a mano.
  • Los algoritmos no se limitan solo a las matemáticas, por ejemplo cuando estás cocinando y te guias por una receta estás utilizando un algoritmo.
  • Los algoritmos han sido parte de la tecnología humana desde la edad de piedra.
  • Pensar de manera algorítmica acerca del mundo, aprender acerca de las estructuras fundamentales de los problemas a los que nos enfrentamos y acerca de las soluciones nos permite saber que tan buenos somos y entender los errores que cometemos.
  • Generalmente las personas deben tomar decisiones en ambientes de incertidumbre, con tiempo limitado, información incompleta y un mundo cambiante. En este caso los algoritmos no son muy eficientes incluso pueden ser inexistentes.
  • No siempre consideres todas las opciones, no siempre persigas el resultado que parece el mejor,viaja ligero, ten paciencia, confía en tus instintos y no pienses demasiado. Relájate. Tira una moneda, perdona pero no olvides.

Cuando detenerse:

  • La naturaleza de la monogamia es que los que la practican se enfrentan a un problema fundamental e inevitable. Cuando se debe considerar que has conocido suficientes personas para saber cual es la mejor elección. Este problema es lo que los matemáticos llaman la parada óptima y tiene una respuesta: 37%
  • El problema de la secretaría: en cualquier problema de este tipo el dilema más importante no es cuál opción escoger sino cuantas opciones considerar.
  • La regla del 37%: se conoce también como el problema de la secretaria. Imagínese que está entrevistando a un grupo de personas para el cargo de secretarias y tu objetivo es maximizar el chance de contratar la mejor del grupo. Tienes el chance segun los matematicos de acceder a los números ordinales (rangos relativos de las aplicaciones comparadas con cada uno) y no a numeros cardinales (rango de acuerdo a una escala general). Se entrevista a las candidatas en orden aleatorio, una a la vez.Puedes decidir dar el trabajo a una persona en particular en cualquier momento sin terminar de entrevistar a todas, pero si tu pasas un aspirante y no decides contratarla no lo puedes hacer de nuevo, pierdes el chance. Hay dos maneras en que se puede fallar: detenerse muy rápido o detenerse muy tarde. Si nos detenemos muy rápido se deja el mejor candidato por fuera. Si nos detenemos muy tarde podemos buscar una candidato que ya no existe. La estrategia adecuada consiste en conseguir el mejor balance entre las dos opciones. Si nuestro objetivo es conseguir el mejor candidato está claro que en la entrevista se supone que debes contratar al mejor candidato que se ha presentado delante de ti. El primer candidato puede ser el mejor por definición, por lo tanto para encontrar los mejores candidatos las posibilidades disminuyen en la medida que avanzamos en las entrevistas. De hecho el segundo aspirante tiene la posibilidad 50/50 de ser el mejor que veamos, el quinto candidato tiene solo un chance de 1 en 5 y el sexto tiene un chance de 1 en 6 y así de manera sucesiva. Como resultado los mejores candidatos aparecen en la medida que la búsqueda continua pero ello ocurrirá cada vez con menos frecuencia. La solución óptima se plantea en base a la regla de mirar y luego saltar. Se establece una cantidad determinada de tiempo para mirar (explorar tus opciones y reunir datos) en lo que categóricamente no se escoge a nadie, no importa que tan bueno sea su currículo. Después de eso se entra a la fase de saltar y nos preparamos para escoger a el aspirante que supere al mejor que observamos en la fase de mirar. Esto se aplica cuando los aspirantes son pocos, con solo un aspirante el problema es sencillo de resolver, hay que contratarla. Con dos aspirantes tenemos una posibilidad de fallar de 50/50 independientemente de lo que se haga. Si agregamos un tercer aspirante las cosas se ponen interesantes, el porcentaje al azar de lograr una buena contratación es del 33%. En este caso cuando hacemos la entrevista al primer aspirante no tenemos información, aparece como la mejor opción. Cuando entrevistamos al tercer aspirante no tenemos opción, tenemos que hacerle una oferta obligatoria porque ya descartamos a los otros dos. Pero cuando entrevistamos al segundo aspirante tenemos un poco de ambos, sabemos si es mejor o peor que el primero y tenemos la posibilidad de contratarla o descartarla. Qué sucede si la contratamos si es mejor que la primera aspirante o la descartamos si no lo es. Pareciera que esta es la mejor estrategia cuando tenemos tres aspirantes, si hacemos esto es posible que con tres aspirantes al igual que con dos podemos escoger al mejor la mitad de las veces. A medida que la lista de aspirantes aumenta para determinar la línea entre mirar y saltar nos lleva a la regla del 37%, mirar primero el 37% de los aspirantes sin escoger a ninguno, luego escoger al mejor que aparezca cuando se compara con los que ya evaluamos.
Regla 37
Regla 37

Siguiendo la estrategia óptima nos permite tener el 37% de chance escoger el mejor aspirante, esto es una simetría matemática que nos permite escoger de una manera adecuada. Una tasa de fracaso del 63% cuando se sigue la mejor estrategia es un porcentaje no despreciable. Esto quiere decir que fallamos en gran porcentaje de los casos, la intuición también nos dice que nuestros chance de escoger el mejor aspirante disminuye a medida que la cifra aumenta. La regla del 37 puede ser aplicada a un número de aspirantes o al tiempo durante el cual uno está haciendo la búsqueda. Si buscamos por ejemplo entre los 18 y los 40 años la regla del 37% nos da como resultado 26.1 años como el punto en el cual hay que comenzar la decisión. Si en cualquier caso disponemos de toda la información porque si el primer aspirante se encuentra en el percentil 95 podemos saber y contratarlo de manera confiable, si no hay nadie por encima del percentil 96.

Cuando vender: imaginemos que queremos vender una casa. Después de consultar varios agentes inmobiliarios, publicas tu oferta, en la medida que cada oferta aparece debes decidir si aceptarla o rechazarla. Si la rechazamos esto tiene un costo. Vender una casa es muy similar a un juego del que dispondremos de toda la información. Sabemos el valor de la oferta, tenemos información del mercado inmobiliario por lo que podemos predecir qué rango de oferta debemos esperar (parecido a los percentiles). La diferencia es que nuestro objetivo no es asegurar la mejor oferta sino obtener la mayor cantidad de dinero. Si asumimos el costo de la espera una buena oferta hoy supera a una mejor en los próximos meses. Podemos ignorar cualquier precio por debajo del rango y tomar la primera opción que exceda la oferta.

Dónde estacionar: el conductor debe considerar que el area de estacionamiento mas demandada es tambien el area mas grande, el estacionar tiene un componente teórico de juego en la medida de que tratas de superar a los otros conductores. Esto está relacionado con la tasa de ocupación (proporción de todos los lugares disponibles que están ocupados en este momento). Si la tasa de ocupación es baja es fácil conseguir un ¿buen puesto Si es alta el estacionarse representa un desafío. Donald Shoup es autor del libro EL Alto Costo de Estacionarse Gratis dice que mucho de los dolores de cabeza al momento de estacionarse son consecuencia de las políticas adoptadas por las ciudades que resultan en altas tasas de ocupación. Si el costo para estacionarse es demasiado bajo en un sitio en particular hay un gran incentivo para estacionarse ahí, lo que hace que la mayoría de las veces no se consigan puestos y la peersona pierda tiempo.La solucion segun Shoup es instalar parquimetros que sean capaces de cambiar los precios en la medida que la demanda aumente. El estacionarse es un típico problema de cuando parar. Si vas manejando en una calle cada vez que observas un sitio vacío debes tomar la decisión de estacionarse. Si quieres conseguir un sitio de estacionar cercano para reducir la distancia a tu destino la solucion esta en la regla de mirar y luego saltar. Lo recomendado es pasar todos los puestos vacantes que aparecen a cierta distancia y después tomar el primero que aparezca. El momento de cambiar de mirar a saltar depende de la proporción de puestos que tienen probabilidad de ocuparse (tasa de ocupación).

Estacionarse
Estacionarse

Supongamos una calle infinita con una tasa de ocupación del 99%, con 1% de puestos vacantes, entonces debes tomar el primer puesto que veas comenzando a casi 70 puestos de tu destino (mas de un cuarto de milla) de tu destino. Pero si Shoup tiene su estrategia y la tasa de ocupación cae a 85% se debe comenzar a buscar seriamente a media cuadra del destino. La mayor disponibilidad de puestos siempre hace la vida más fácil. el estacionar es un proceso (un proceso de detenerse óptimamente) y consume atención, tiempo y combustible.

Cuando detenerse: analizemos el problema del ladron, en este problema el ladrón tiene la oportunidad de llevar a cabo una secuencia de robos, cada robo le aporta una recompensa y hay una posibilidad de huir cada vez, pero si el ladrón lo atrapan pierde todas las ganancias acumuladas. Se plantea que algoritmo debe seguir: el número de robos que debes ejecutar es igual al chance de escapar dividido entre el chance que tienes de ser atrapado. Si eres un ladrón profesional y tienes el 90$ de ejecutar el robo (y el 19% de posibilidad de ser atrapado) entonces te puedes retirar después de 9 robos (90/10: 9). Si eres un principiante con una posibilidad de éxito de 50/50 la primera vez no tienes nada que perder pero solo debes intentarlo una vez (con suerte).

Existen problemas de decisiones secuenciales en que no existe una regla óptima para detenerse. Un ejemplo es el juego triple o nada: tienes 1$ y puedes jugar el siguiente juego las veces que quieras, apuesta todo tu dinero y tienes el 50% de posibilidad de recibir el triple de esa cantidad y el 50% de posibilidad de perderlo todo. Cuántas veces debes jugar: a pesar de su simplicidad no hay un momento óptimo para detenerse porque cada vez que se juega tus ganancias son un poco más elevadas. Si comienzas con 1$, puedes conseguir 3$ la mitad de las veces y 0$ la otra mitad por lo que en promedio puedes esperar terminar la primera partida con 1.50$ en tu bolsillo. La matemática demuestra que debes seguir jugando pero si sigues esta estrategia siempre terminaras perdiendo todo.

  • Sin embargo al momento de detenerse y aplicar la regla del 37% tiene un costo para la gente: el tiempo. Si se investiga por un tiempo el ser humano se aburre lo cual no es irracional pero es difícil de seguir rigurosamente.

Explorar/Aprovechar:

  • Cada dia que pasa estamos forzados a tomar decisiones entre varias opciones que difieren en una dimensión específica: hacemos cosas nuevas o las que son nuestras favoritas. Se entiende que la vida es un balance entre la novedad y la tradición, entre lo más nuevo y lo mejor,entre tomar riesgos o disfrutar lo que conocemos y amamos.
  • Exploración es reunir información y Explotación es usar la información que disponemos para obtener un buen resultado. Es intuitivo que no se puede vivir sin explorar pero también si no se utiliza la información es igual de malo. En la definición en el lenguaje computacional la explotación caracteriza lo que consideramos los mejores momentos de la vida, por ejemplo una reunión familiar. Por ejemplo lo bueno de la música es que existe siempre algo nuevo que escuchar.
  • En computación puede existir conflictos entre explorar y explotar. Existe un escenario que se llama el problema del bandido multi-armado. El nombre viene del termino coloquial para las maquinas de casino (el bandido armado). Si nos imaginamos caminando en una casino lleno de máquinas, cada una de las cuales tiene su manera de ganar, no conocemos cómo funcionan, si no juegas no tienes idea de cuáles máquinas dan más ganancia y en cuales se pierde más. Por supuesto lo que aspiramos es a maximizar nuestras ganancias y esto implica explorar diferentes máquinas y probarlas (explorar) y utilizar las que consideras mejor (explotar). Si por ejemplo tenemos solo 2 maquinas, en una jugaste 15 veces de las cuales 9 veces ganaste y 6 perdiste. En la otra sólo has jugado 2 veces, en 1 ganaste y en otra perdiste. Cual representa la mejor: simplemente dividiendo las veces que ganas entre el número total de intentos te dará el valor esperado de la máquina y de esta manera la primera máquina tiene la delantera porque el record es 9-6 con un valor esperado del 60% y la segunda 1-1 tiene un valor esperado de 50%. Pero en la segunda solo intentaste 2 veces por lo que no sabemos cual es la mejor en este momento. Igual ocurre al seleccionar un restaurante o un CD, es cuestión de decidir qué máquina escoger. Pero entender el balance entre explorar/explotar no es la mejor manera de mejorar las decisiones de donde comer o que musica escuchar. También nos permite determinar como nuestros objetivos deben cambiar en la medida que envejecemos y cual es la manera más racional de actuar no siempre implica escoger la mejor. la gente tiende a tomar decisiones aisladas, siempre focalizando el mejor valor esperado, pero las decisiones casi nunca se encuentran aisladas y el valor esperado no es el final de la historia. Si no solo estas pensando en la próxima decisión sino en todas las decisiones que debes tomar en el futuro el explorar/explotar es crucial en el proceso. en relación a qué máquina utilizar esto depende de algo que no se a discutido: por cuanto tiempo vas a estar en el casino. Debemos medir el intervalo. Cuando se intenta balancear las experiencias favoritas y las nuevas nada importa más que el intervalo en el que planeamos disfrutar las cosas. Según explica Chris Stucchio es mejor probar un restaurante nuevo cuando uno recién se muda a una ciudad que cuando se piensa mudar. Lo que pasa cuando hacemos cosas nuevas es que el valor de explorar para conseguirlo sólo puede disminuir en el tiempo. El valor de la explotación puede solo aumentar en el tiempo. De manera que debes explorar solo cuando tengas tiempo de utilizar el conocimiento obtenido, explotalo cuando estés listo para canjearlo. Este intervalo hace la diferencia. En el caso de las máquinas en el casino el matemático Herbert Robbins propuso un algoritmo: gana-quedate, pierde-retírate. A pesar de que es una estrategia simple el matemático demostró en 1952 que se obtienen mejores resultados que al azar (balance exploración-explotación). Pero si cambias de máquina cada vez que pierdes es incomodo, como el hecho de visitar un restaurante 100 veces comienzo platos excelentes y en una ocasión la comida no es buena y descartarlo. Las buenas opciones no deben ser descartadas por ser imperfectas. De acuerdo al algoritmo gana-quedate, pierde-retírate debes cambiar de restaurante asi sea el ultimo dia en la ciudad. Por ahora el problema del bandido no ha sido resuelto.
  • Índice Gittins: En 1970 la corporación Unilever le pregunto a un joven matemático llamado John Gittins los siguiente: si tenemos varios compuestos químicos diferentes, cual es la mejor manera de determinar que compuesto es mas efectivo contra una enfermedad. Gittins concibió el objetivo de obtener recompensa no por un intervalo de tiempo fijo sino por un futuro descontado. El asume que el valor de la recompensa disminuye geometricamente, por ejemplo hay una posibilidad del 1% de que seas atropellado por un bus, entonces se debe evaular el cenar mañana como el 99% del valor de cenar hoy, solo porque es posible que nunca llegues a cenar. Por ejemplo en el caso de las maquinas del casino según este índice seria jugar la maquina con el índice mas alto. La tensión que se genera entre explorar y explotar se resuelve con la tarea de maximizar una cantidad sencilla que cuenta para ambos. Si vemos la tabla del índice podemos apreciar que la estrategia de ganar es ir de izquierda a derecha porque el índice se incrementa. Lo mas interesante es que un récord 0-0 (completamente desconocido) tiene un índice de Gittins de 0.709 en lugar del valor esperado de 0.5000, en otras palabras algo que nunca has experimentado es mucho mas atractivo que una maquina que paga 7 veces de 10.
Índice de Gittins
Índice de Gittins
Índice de Gittins
Índice de Gittins

El índice de Gittins justifica preferir los desconocido, de manera que tenemos la posibilidad de explotar los resultados de lo que exploramos. Existe un aviejo adagio que dice que el pasto es siempre mas verde del otro lado de la cerca, las matemáticas nos dicen porque: lo desconocido tiene el chance de ser mejor incluso si nosotros actualmente esperamos que no sea diferente, o esta muy cercano de ser peor. Explorar tiene un gran valor porque se hacemos cosas nuevas se incrementa la posibilidad de encontrar lo mejor. Se basa en el descuento geométrico de una recompensa en el futuro, dando a cada intento una fracción constante de la anterior, o que se ha corroborado por una serie de experimentos de económica conductual y psicología en la cual se demuestra que las personas no siguen estos principios.

Arrepentimiento y Optimismo:

Tratar y fallar nos genera aprendizaje; pero si no se trata sufrimos la inestimable perdida de lo que pudo haber sido. Chester Barnard

Si el índice de Gittins es muy complicado nos podemos focalizar en el arrepentimiento. El arrepentimiento puede ser motivador. El arrepentimiento es el resultado de comparar lo que hicimos con lo que hubiera sido mejor de hacer. El arrepentimiento puede ser muy motivante. Jeff Bezos tenía una posición segura y bien remunerada en Nueva York, comenzar una tienda on line de libro era riesgoso, sin embargo si me ubico en mis 80 años quiero tener un número minimizado de arrepentimientos. Estoy seguro que si no tengo éxito no me arrepentiré de ello, solo me arrepentiría de no haberlo tratado. Nuestro arrepentimiento no para de crecer incluso si escogemos la mejor estrategia porque incluso la mejor estrategia no es perfecta todo el tiempo. El arrepentimiento no crecerá tanto si escogemos la mejor estrategia que si escogemos otra.El arrepentimiento mínimo es el arrepentimiento que se incrementa de forma logarítmica (de manera que cometemos tantos errores en los primeros intentos como en los siguiente 90, como en los siguientes intentos en un año).

El límite de confianza superior es un algoritmo que garantiza el mínimo arrepentimiento. Las representaciones visuales de la estadística incluye barra de error que se extienden por arriba y por abajo y muestran un rango de posibles valores que cuantifican lo que esta siendo medido. Este rango se conoce como intervalo de confianza y con esta medida se gana confianza en lo que estamos haciendo. Un algoritmo de este tipo escoge la posibilidad que de manera razonable lo haga mejor en el futuro, es siempre mayor que el valor esperado. Este tipo de algoritmo es muy similar al índice Gittins pero es más fácil de calcular y no requiere la presunción del descuento geométrico. El límite de confianza superior implementa optimismo en presencia de incertidumbre. El optimismo puede ser perfectamente racional, se debe focalizar en lo mejor que una opción puede ser, basado en la evidencia, aumenta las posibilidades que menos conocemos. El optimismo es la mejor manera de prevenir el arrepentimiento.

En 1969 Marvin Zelen, estadístico de la Universidad de Harvard propuso el algoritmo de Zelen (Trials adaptativos) por la controversia generada por los clinical trials que se realizan en la práctica médica. Propuso una versión en la que la posibilidad de utilizar un tratamiento determinado aumenta con cada ganancia y disminuye con cada perdida.

Una de las cosas más curiosas acerca del ser humano es que nos toma muchos años para ser competente y autónomos. Alison Gopnik, profesor de psicología de la Universidad de California, plantea de que este periodo prolongado de dependencia nos permite desarrollar la idea de el papel de la exploración/explotación. Generalmente nos enfocamos en los resultados de nuestras decisiones, como si cada decisión fuese la última, pero debemos entender que la exploración tiene sentido. Durante toda la vida se debe tomar una gran cantidad de decisiones y natural enfatizar la idea de explorar (lo actual a lo mejor, lo excitante a lo seguro,etc) como los niños. En la vejez existe la tendencia a disminuir nuestra relación con los demás, esto es el resultado de procesos de selección a lo largo de la vida que hace que la gente estratégicamente y adaptativamente maximice sus círculos sociales y emocionales para minimizar los riesgos.

Clasificación:

Organizar es lo que las computadoras hacen, fue la necesidad de organizar lo que hizo que las computadoras se desarrollaran. El primer programa almacenado en una computadora fue un programa de clasificación. Clasificar es una parte esencial para trabajar con cualquier tipo de información. Nuestro correo electrónico nos muestra los 50 mensajes organizados por el tiempor en que fueron recibidos, los blog nos muestran los artículos clasificados por la fecha de publicación,etc. Lo que diferencia a Google de otros buscadores es la manera en que se organiza la información y nos muestra por ejemplo las 10 cosas más relevantes. Organizar no solo es algo que hacemos con la información, lo hacemos con las personas.

la agonía de organizar: para disminuir los costos por unidad la gente usualmente aumenta el tamaño de sus operaciones escribió J.C. Hosken en 1955 en el primer artículo publicado sobre organizar. Una de las cosas mas fundamentales de la teoría de la organización es que el tamaño duele. Por eso una de las claves consiste en minimizar el número de cosas que tenemos que organizar. Una de las maneras de prevenir esta dificultad computacional es lavar la ropa mes frecuentemente. Si lavamos 3 veces más frecuentemente podemos reducir la dificultad de organizar en un facto de nueve. La computación ha desarrollado un atajo específico para medir los peores casos algorítmicamente: se llama la notación Big-O la cual es inexacta en su diseño. La notación Big-O nos permite hablar sobre el tipo de relación que se establece entre el tamaño del problema y el tiempo de ejecución.

El ordenamiento de burbuja es un algoritmo simple, intuitivo y extremadamente ineficiente.