Jueves 26/09

Dynamic programming

Método para resolver problemas de optimización dividiéndolos en problemas más simples (como divide y vencerás). Después de resolver los problemas simples, DP combina las soluciones simples para formar una solución al problema.

Richard E. Bellman la inventó en 1957.

Características de un problema para resolverse con dynamic programming:

-Estuctura óptima: La solución de un problema dado puede ser encontrada al combinar óptimas soluciones a sus subproblemas.

-Overlapping subproblems: Hay que solucionar el subproblema una y otra vez.

Caso de fibonacci:

• Estructura óptima: Cada solución a un subproblema es óptima, tenemos dos casos base que son +optimos (exactos, como fibonacci de 0 y de 1).

• Overlapping: Si quiero calcular el fibonacci de 10 tengo que calcular el fibonacci de 7 tres veces.

En programación dinámica hay problemas que se van a repetir, esta es la diferencia con el divide y vencerás. Tiene un approach bottom-up.

Divide and Conquer: Resolver uno de los problemas no ayudará a resolver otro. Tengo un enfoque de resolución top-down.

Memorización

Después de resolver un subproblema, lo guardo en una tabla para utilizarlo después.

example: find the longest common substring.

"tofoodie" and "toody" the answer should be "ood" creo una matriz con los elementos de los strings para ver donde se están repitiendo las letras.

Tarea moral: Investigar cómo se soluciona el problema de la mochila (Knapsack problem) con algoritmos genéticos y con dynamic programming.

Algoritmos voraces (Greedy algorithms)

Un algoritmo voraz toma siempre la mejor decisión basado en la información que tiene en cada iteración. Hace una decisión local esperando que ésta ayude a tomar la mejor decisión global.

En algunas ocasiones podrían no proveer la solución óptima, pero sí la aproximan, o sea, sacrifico precisión por tiempo. No son precisos, pero son rápidos y me dan una respuesta cercana a la mejor.

Ejemplo: Dijkstra Algorithm

Partes de un algoritmo voraz:

• Conjunto de candidatos

• Función de selección, donde en cada iteración agrego un elemento a las solución global

• Feasibility function, usada para determinar si algun candidato está dentreo de la solución o no.

• Función objetivo.

• Función solución.

Algoritmo del cajero automático

if x = 0, stops.

Algoritmos Probabilísticos

Cuando un algoritmo toma una decisión, es preferible que la decisión tenga un factor random. Si queremos una decisión que no importa si es cercana a la óptima. Aun con el mismo input es muy probable que obtenga resultados diferentes.

Comparado con los algoritmos determinísticos, estos podrían fallar o incluso nunca termine de ejecutarse. Puede encontrar diferentes posibles soluciones a un mismo input.

¿Por qué aunque un algoritmo sea determinístico existen casos donde no hay respuestas correctas?

R/ Por un fallo en el hardware.

Categorías:

• Numéricos: 90% de probabilidad de dar una solución correcta, entre más tiempo se ejecute mejor será la aproximación.

-Las vegas algorithms: Decisiones completamente random, si no se puede enconrtrar una solución, el algoritmo lo dirá.

-Monte Carlo algorithms: Calcula la solución correcta con un alto porcentajde de probabilidad, longer runtime increases the probability of a right answer.

Some thoughts on web development:

Web page: documento que puede ser accesado por un buscador web y que está en la world wide web. Escrita en HTML, XML O JS.

Página estática: El contenido es estático a menos que edite la página como tal.

Página dinámica: Pueden cambiar el contenido dependiendo de la lógica. Son generadas por el servidor.

Web application: Es software que puede correrse en un web browser. Compuesto por: UI Layer, Logic Layer, Data Layer.

Se necesitan estos componentes: Browser, DB Server, Application server and optionally web server.

El web 2.o brindó la posibilidad de agregar lógica del lado del cliente. Usando, por ejemplo, JavaScript, la UI es más interactiva.

Web applications use AJAX more intensively to improve the user experience.

AJAX es Asynchronous Javascript and HTML.