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).
- Burbulla.
- Rápido (quicksort).
- Por inserción.
- Por selección.
- Por montóns.
- É 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:
- secuencial
- binaria
- É 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.
- A*(pathfinder)
- Dijkstra
- BFS (busca en anchura)
- DFS (busca en profundidade)
- Moitos máis
- 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).
- 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.
Inspired in File:PageRank-hi-res.png., Dominio público, Enlace
- RLE
- Huffman
- MP3
- JPG vs PNG
- 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:
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:
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:
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.