#algoritmia

ALGORITMIA E LÓGICA DA PROGRAMAÇÃO

O nome pode assustar um pouquinho e parece algo difícil ou até complicado, mas pode ter certeza que não é.

Repórter: “Algoritmo é o conjunto de instruções ou ações que ao serem executadas, permitirão realizar uma determinada tarefa.” 

É isso, assim como uma receita de bolo: Você precisa preparar a massa com os ingrediente, em uma sequência lógica, quebras os ovos, bater até ficar uniforme e por…

Algoritmia – Introdução Básica II

Como Construir um Algoritmo 1. Compreender o problema. 2. Imaginar que se está a desenvolver um algoritmo para pessoas que não trabalham com informática. 3. Usar frases curtas e simples. 4. Ser objetivo 5. Procurar usar palavras que não tenham sentido duvidoso. 6. Definir os dados de entrada. 7. Determinar o necessário para transformar os dados de entrada em dados de saída: (more…)

Algoritmia – Introdução Básica I

O que é a lógica? Lógica, a ciência de raciocinar, criar e encadear pensamentos de modo a atingir um determinado objetivo. Exemplos de aplicação da lógica Todos os cães comem carne, dálmatas são cães. Logo, dálmatas comem carne. O quarto está fechado e o meu livro está lá dentro. Então, preciso abrir a porta do quarto para poder ir buscar o livro. Sequência Lógica A Sequência Lógica, são os…

Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time O(n^2.3755). Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le Gall has led to an improved algorithm running in time O(n^2.3729). These algorithms are obtained by analyzing higher and higher tensor powers of a certain identity of Coppersmith and Winograd. We show that this exact approach cannot result in an algorithm with running time O(n^2.3725), and identify a wide class of variants of this approach which cannot result in an algorithm with running time O(n^2.3078); in particular, this approach cannot prove the conjecture that for every ε > 0, two nxn matrices can be multiplied in time O(n^2+ε).

But textbook selection is a fairly ordinary challenge for me. The real question is: Which algorithms should we teach in this course, circa 2014? Surely the rise of big data, multi-core processors, mobile computing, and social networking require a fresh look at the topics we teach undergrads.

La programación dinámica es un tanto confusa, y lo sé! en las últimas semanas, estuve interrogando a muchas personas: "Qué es la programación dinámica?" muchas de ellas respondían conceptos muy confusos, por lo que llegué a concluír (erróneamente) que la programación dinámica era una especie de magia mediante la cual los algoritmos se hacen mucho más eficaces y rápidos, y que todo mago capaz de invocar el conjuro de la programación dinámica de forma exitosa, sería capaz de resolver todos los problemas de algoritmia del mundo.... no... DEL UNIVERSO!

Pero luego de un tiempo, y luego de que Jhtan me explicara varias veces el concepto (btw, gracias ^_^) por fin entendí qué es la programación dinámica:

NO ES MAGIA de hecho, nada es magia... todo tiene su explicación ;)

La programación dinámica tampoco es una forma de solucionar todos los problemas del universo y traer la felicidad y la paz mundial, de hecho, la programación dinámica también tiene sus limitaciones (como cualquier otro paradigma de algoritmia) y no funciona para cualquier problema... como ven, nada es mágico, y, en todo el conocimiento que he coleccionado a lo largo de mi vida, podría asegurarles casi con certeza: nada es mágico, no hay una receta mágica que funcione para todo y garantice perfección, si hacer algoritmos fuera algo automatizable, entonces habrían algoritmos para hacer algoritmos, y por lo tanto, programas que programen programas.  (Pero eso ya es un tema diferente...)

Si la programación dinámica no es magia, y si tampoco es una receta mágica, entonces... ¿Qué es exactamente la programación dinámica? y ¿por qué debería un informático entenderla? Vamos por pasos...

¿Qué es?

La programación dinámica es un paradigma (entre muchos) para resolver problemas. Este paradigma consiste en: utilizar resultados parciales (que el programa ha calculado y guardado en algún lugar) para dar con el resultado requerido. Un ejemplo! (bastante escueto e inútil, pero que ayudará a entender el paradigma): imagina que aún estás en colegio, y tu profesora quiere jugar un juego: ella te dirá una palabra que empieza con "a" y tú tienes que buscarla en el diccionario y leerle su significado... si tus compañeros encuentran la palabra antes que tú, ella te castigará sin recreo (digamos que está loca, y la lleva contra tí, o algo así), por suerte, tú eres más avispado que tus compañeros, y, como sabes que la profesora preguntará una palabra que comience con la letra "a", separas la sección del diccionario que contiene todas las palabras con la letra "a" y eso te da cierta ventaja.

En el ejemplo, la porción del diccionario que haz separado, constituye un conjunto de resultados parciales, y para encontrar el resultado, buscas entre los resultados parciales el resultado correcto. La programación dinámica se trata, básicamente, de eso: calcular resultados parciales, guardarlos, y luego usarlos (ya sea buscando entre ellos o realizando operaciones con ellos) para obtener el resultado deseado.

Viéndolo así, Gauss utilizó este paradigma para resolver el problema de 1 + 2 + 3 + ... + n y simplificarlo en su, tan conocida fórmula n(n+1)/2 cuando aún era niño.

Cuenta la anécdota que, el maestro de aritmética de Gauss le planteó al salón el problema de sumar los primeros 100 números de forma consecutiva (1 + 2 + 3 + ... + 100), pero Gauss se dio cuenta que  1+99 = 100 y que  2 + 98 = 100 y que r + ( 100 - r ) = 100 y por lo tanto r + (n - r) = n... y allí está de nuevo resultados parciales, Gauss encontró todos los resultados parciales, los guardó, y se dio cuenta que formaban un rectángulo, luego, se dio cuenta que el resultado deseado era uno de los triángulos contenido en el conjunto de resultados parciales, así que procesó todos estos resultados parciales para obtener el resultado deseado, y de allí viene su fórmula n(n+1)/2.

Ahora vamos a la siguiente pregunta...

¿por qué es importante?

Aunque la programación dinámica no es una receta mágica, es una de las muchas armas que todo informático debería saber empuñar. Hay una gran variedad de problemas que se pueden resolver con programación dinámica, uno de ellos es el de Longest Common Subsequence.

Y bueno, recién estoy entendiendo la programación dinámica y no tengo mucha experiencia en esto del competitive programming y por eso aún no entiendo del todo sus implicaciones...

Pero lo que sí puedo afirmarles con certeza es que, entender (al menos en parte) cómo funciona la programación dinámica, y ser capaz de identificar problemas que requieren de programación dinámica para su solución, me ha dado cierto aire de confianza, la sensación de que, todos los problemas a los que no les encuentro solución, TIENEN una solución, pero primero, necesito aprender una nueva forma de encararlos: de entenderlos.

Algoritmos voraces (Cambio de monedas, Dijkstra) en Numbers.