Algoritmos famosos

Unha parte importante da formación algorítmica debe ser visualizar algoritmos famosos, para que estes non sexan caixas negras nos que metes datos e obtés datos dun xeito eficaz pero oculto. Con isto damos unha Cultura Algorítmica, un contexto aos recursos mostrados, indicando que posible importancia poden ter esas técnicas lóxico-matemáticas que aprendemos en clase. Cando o alumnado de bacharelato non é capaz de responder para que serven ferramentas matemáticas como os logaritmos ou as derivadas (ás que lle teñen adicadas moitas horas da súa vida académica), temos un problema de descontextualización. O mesmo pode pasarnos coa Programación ou a Tecnoloxía se convertemos todos os procesos nunha caixa negra.

Non temos porque entender ao 100%  ou saber aplicar os algoritmos famosos (algúns utilizarán recursos matemáticos complexos), chega con mostrar o problema que pretenden resolver ou mellorar, e como abordan os seus creadores a solución a ese problema. Incluso problemas aparentemente sinxelos como ordenar N elementos, sendo N grande, poden ser moi complexos cando se pretende optimizar o proceso. Un parámetro importante á hora de falar de algoritmos e dos problemas aos que se aplican é precisamente a complexidade do problema e  a eficacia do algoritmo.

Unha boa recomendación para clase de Programación ou TIC pode ser realizar traballos expositivos, individuais ou en grupo, analizando estes algoritmos famosos e os seus problemas.

Como traballar en clase con Algoritmos famosos

 
  • Falando deles fomentas a Cultura Algorítmica.
  • Visualizando a nivel cualitativo, non é necesario programalos.
  • Dado un problema, comparar algoritmos de resolución e a súa eficacia.
  • Aptos para facer traballos de investigación e exposicións.

 

 

Nesta páxina botaremos unha visual aos algoritmos máis famosos (dende un punto de vista académico, cando menos), pero é unha seción en construcción por parte do Proxecto Algoritmia. Unha boa recomendación, se queres ver polo miúdo este tema,  é facer o curso de Algoritmos de Khan Academy (para profesorado ou alumnado de 2º Bach. con experiencia e interés).

Algoritmos de Ordenamento
Colocar elementos nunha lista secuenciada con unha relación de orde
Algoritmos famosos(algúns)
  • Burbulla.
  • Rápido (quicksort).
  • Por inserción.
  • Por selección.
  • Por montóns.
Que podemos aprender lendo sobre eles
  • É o algoritmo máis importante para quen se inicia na Programación teórica.
  • Técnicas diversas algorítmicas diversas como divide e vencerás.
  • Notación algorítmica.
  • Estruturas de datos

Destes algoritmos temos falado noutra sección de Algoritmia, en Antes de scratch, onde podes atopar diversas actividades para axudar a visualizar como ordenan os ordenadores.

Precisamente o de visualizar o funcionamento do algoritmo é unhas das mellores opcións para traballar con estes algoritmos, pois serán fáciles de entender e comparar. Por exemplo este é o de Quicksort, que utiliza un valor pivote para mellorar na rapidez de ordenamento:

Un par de vídeos interesantes para visualizar os algoritmos de ordenamento:

Algoritmos de Busca en lista
Buscar elemento con certas propiedades nunha estrutura de datos lineal.
Algoritmos famosos(algúns)
  • secuencial
  • binaria
Que podemos aprender lendo sobre eles
  • É o segundo algoritmo máis importante para quen se inicia na Programación teórica.
  • É fácil de programar.
  • Notación algorítmica.
  • Estruturas de datos lineais (arrays)

Con estes algoritmos pode introducirse a necesidade de utilizar estruturas de datos non lineais, que serán máis exitosas na resolución de moitos problemas.

Igual que os de ordenamento, temos actividades sobre eles na sección Antes de Scratch.

Dos dous algoritmos básicos, a súa utilidade é:

  • Secuencial: compara un por un todos os elementos da lista ata atopar o desexado. Só recomendado para listas desordenadas, por ser pouco eficaz.
  • Binaria: recomendado para aplicar listas ordenadas, vai dividindo a lista en subgrupos, sendo un deles onde está o dato buscado.
Algoritmos de Busca gráfica ou de grafos
Minimizar o camiño entre nodos nunha rede, nodos que adoitan ser datos con estrutura non lineal. Permiten crear navegacións automáticas en infinidade de aplicacións: coches, videoxogos, robots...
Algoritmos famosos(algúns)
  • A*(pathfinder)
  • Dijkstra
  • BFS (busca en anchura)
  • DFS (busca en profundidade)
  • Moitos máis
Que podemos aprender lendo sobre eles
  • Un tipo de algoritmo moi presente nas nosas vidas.
  • De uso importante na Intelixencia Artificial.
  • Gran cantidade de problemas necesitan unha solución algorítmica por busca, non alxebraica.
  • Os grafos son unha parte importante das Matemáticas.
  • Estruturas de datos non lineais (árbore e grafos).

Estes algoritmos son moi interesantes polo tipo de problemas que afrontan. Un dos máis famosos, que deu orixe á teoría de grafos, é o das pontes de Könisberg, que resolveu o matemático Euler.

Como noutros casos, en Secundaria-Bacharelato pode chegar con ver o algoritmo en funcionamento, non é necesario entrar nas súas mateméticas, que pode ser complexa

Para cousas prácticas, como programar o movemento optimizado dun robot (por exemplo, o robot aspiradora nas casas) ou deseñar-resolver un labirinto (por exemplo, nun videoxogo) temos diversos algoritmos:

  • Un moi importante, o de Dijkstra, minimiza os camiños nunha rede (entre outras, é  moi usado en telemática para desenvolver redes de comunicación).

 

Dijkstra Animation.gif

De Ibmua - Work by uploader., Dominio público, Enlace

  • Outro importante, o de A*, minimiza o custe para ir dun punto a outro nunha rede, se asociamos pesos (valores) a cada nodo. Poderiamos utilizalo para resolver un labirinto:

Se xa traballas con clases e obxectos en Python podes ver un bó titorial de programación en Python do algoritmo pathfinder.

Relacionado cos grafos temos famosos algoritmos privados como Page Rank, o algoritmo (hoxe en día falariamos mellor dun conxunto de algoritmos) de Google que usamos todos os días no seu navegador: a cada páxina da busca se lle asocia un número en función das ligazóns e outros factores (algúns segredos); con eses número se crea unha rede ordenada.

Algoritmos de compresión de datos e codificación
Como converter un tipo de datos noutros (codificar)  e como gardalos utilizando menos espazo de memoria (comprimir)
Algoritmos famosos(algúns)
  • RLE
  • Huffman
  • MP3
  • JPG vs PNG
Que podemos aprender lendo sobre eles
  • Como funciona unha parte fundamental da tecnoloxía dixital (codificar-decodificar)
  • Cibernética (teoría da información)
  • Códecs

Todos os codecs que usamos (ou sexa, os formatos dos ficheiros) son algoritmos que resolven de distintas maneiras o problema básico da codificación (converter datos dun tipo) e da compresión.

A matemática pode ser complexa, pero o funcionamento cualitativo do algoritmo pode ser sinxelo de explicar. Para os estudantes o importante será visualizar que detrás de cada códec se atopan unhas fórmula mátemáticas e un algoritmo, co cal rompemos coa caixa negra que pode ser o formato. Explicar a diferenza entre un códec e outro (por exemplo, se é con perdas e ou sen perdas) axuda a esta visualización.

Por exemplo esta imaxe axuda a enteder o que ten detrás o famoso formato JPG, e como fai para enganar ao ollo humano:

Dctjpeg.png

De No machine-readable author provided. FelixH~commonswiki assumed (based on copyright claims)
Dominio público, Enlace

JPG dividide a foto en cadros de 8x8 e logo garda os datos de cada un dos 64 cadriños como números, que nalgúns casos poderá obviar, aforrando espazo de memoria (e perdendo información polo camiño). MP3 fai algo similar coas frecuencias.

Exercicio simple para clase sobre codificación

 

Un exercicio interesante para clase sobre codificación e compresión (no que de paso podemos explicar os pasos na dixitalización de información) consiste en pedir un debuxo pixelado en branco e negro (con unha folla de cadriños) dunha resolución determinada (como moito 15x15, para que non leve tempo), e logo crear un ficheiro tipo mapa de bits no que solicitaremos aplicar un códec de comprensión en pseudocódigo, ou sexa, unhas normas cualitativas para reducir o tamaño do ficheiro. Podemos pedir por exemplo un space invader:


By Peter Astbury [CC0], from Wikimedia Commons

 

O curioso do exercicio anterior é que moito alumnado acaba descubrindo, sen sabelo, un algoritmo de compresión de datos moi famoso, o RLE (run-lenght encoding): se temos unha cadea de caracteres (por exemplos os 0 e 1 do debuxo en mapa de bits) cando se repiten datos gardamos só o valor e o número de repetición. Por exemplo, no noso debuxo escollemos unha liña:


A codificación da liña subliñada sería: 01111111110

Temos 11 bits (caracteres) que almacenar; entón gardaríamos co algoritmo RLE os seguinte datos: 011901 que veñen sendo 6 caracteres, co que aforramos case a metade do espazo.

 

 

Criptografía e seguridade Algoritmos cuánticos