Ediciones ENI Editorial | líder en informática
Programación de algoritmos en C++
Introducción
Este capítulo presenta algoritmos aplicados en C++ que abordan problemas actuales en tres áreas: reconocimiento de patrones, búsqueda del camino más corto y compresión de datos.
Reconocimiento de patrones de texto
Para un problema determinado, no existe un algoritmo universal. Algunos algoritmos sólo son eficaces en una situación concreta.
Aquí nos interesa la búsqueda de patrones textuales, es decir, la búsqueda de una subcadena en una cadena y presentaremos varias formas de algoritmo.
La librería STL, al igual que boost, ofrece naturalmente funciones para conseguirlo, pero la lógica utilizada para la implementación no se indica en el archivo de cabecera. Es útil conocer algunos algoritmos de referencia para poder aplicarlos sabiamente.
1. Enfoque directo
El enfoque ingenuo consiste en comparar el patrón de búsqueda carácter por carácter con el texto de entrada. Si todas las comparaciones tienen éxito, desde el primer hasta el último carácter del patrón, se dice que el patrón se ha agotado y la búsqueda ha terminado.
Si la comparación difiere antes de llegar al final del patrón, no tiene sentido continuar las comparaciones para los caracteres siguientes. Se desplaza el patrón un carácter y comience de nuevo la comparación.
La implementación en C++ de este algoritmo no presenta ninguna dificultad. Tenemos que comprobar los caracteres uno a uno sin sobrepasar el tamaño del patrón o del texto a analizar:
int busqueda_patron_simple(string s, string m)
{
int pos = 0;
int p = 0;
while (pos < s.length())
{
if (s.at(pos) == m.at(0))
{
// primer carácter idéntico
p = 1;
// comparar uno por uno los siguientes caracteres del patrón
while (
p + pos < s.length() &&
p <...Encontrar el camino más corto
Hay muchas situaciones en las que es necesario encontrar el camino más corto: en logística, en conducción asistida por ordenador, en planificación y programación, en motores de escenarios de videojuegos, etc.
Antes de presentar tres algoritmos esenciales, he aquí una breve introducción a los grafos.
1. Presentación de los grafos
En el capítulo de la librería estándar STL, vimos una estructura dinámica llamada lista. Una lista está formada por un elemento cabeza (un valor) unido a una lista llamada continuación. Para recorrer la lista, nos gusta utilizar una función recursiva que recuerde hasta llegar a la lista vacía.
Dado que un elemento puede tener varios sucesores, obtenemos un árbol formado por nodos. Los nodos tienen un único antepasado, llamado padre y un número múltiple de descendientes, llamados hijos. Los nodos terminales que no tienen hijos se llaman hojas, mientras que el elemento situado en la parte superior del árbol se denomina raíz. Hay casos especiales de árboles, como los que tienen como máximo dos hijos, llamados árboles B o árboles B, donde B significa binario 2.
Un grafo generaliza la construcción del árbol admitiendo que un nodo (llamado vértice) tenga varios antepasados.
Los grafos están formados por dos tipos de elementos: los vértices y los arcos. Los vértices representan objetos y los arcos establecen relaciones entre ellos. Los arcos pueden llevar valores (o pesos), pero esto no es determinante en el estudio de un grafo como tal.
Los grafos pueden ser dirigidos o no dirigidos. En el primer caso, los arcos son dirigidos y se representan mediante flechas. Si es necesario, un arco puede ser bidireccional dividiéndose para representar cada dirección. La numeración o identificación de los vértices tampoco es una característica determinante, aunque sea habitual, al menos en las fases de estudio de un algoritmo.
Matemáticamente, un grafo está formado por un conjunto S y una relación A sobre S. Tomamos nota G=(S,A). En el caso de un arco dirigido, si un arco va del vértice a al vértice b, tenemos:
a A b (a en relación con b). Esta relación no es simétrica y no hay ninguna...
Comprimir archivos
La cuestión de ahorrar espacio para representar la información surgió muy pronto. Aunque la tecnología ha hecho fantásticos progresos, la necesidad de comunicación y almacenamiento también ha aumentado en las mismas proporciones. En consecuencia, buscamos constantemente reducir el tamaño de los archivos y el ancho de banda consumido.
Presentamos dos algoritmos bien conocidos y aún ampliamente utilizados, en particular en los programas de archivado del mercado o en los módulos de compresión utilizados para Internet y la nube.
1. Enfoque estadístico: algoritmo Huffman
También se conoce como codificación Huffman, en honor a su inventor. El principio de este algoritmo es reducir el número de bits utilizados para codificar caracteres frecuentes (bytes) en el archivo a comprimir y alargar los demás.
En español, la letra E es muy frecuente, mientras que las letras K y Z lo son mucho menos. Como regla general, codificar la E en 7 bits en lugar de 8 ahorrará 1 bit por cada aparición.
Como siempre se necesitan 256 códigos diferentes para representar cada carácter ASCII (1 byte), aceptaremos que las letras menos frecuentes tengan códigos más largos, por ejemplo de 9 bits.
El algoritmo de Huffman construye una codificación binaria (un B tree) a partir de las estadísticas de caracteres. Dependiendo de la implementación, las estadísticas se predefinen en función del tipo de archivo o se calculan dinámicamente a partir del archivo que se va a comprimir. Las implementaciones más sofisticadas modifican la codificación actualizando las estadísticas a medida que se procesa el archivo.
a. Aplicación de la codificación
La codificación comienza contando las apariciones de cada carácter (representado en un byte) en el archivo fuente. Para ello, utilizamos una matriz de clase Nodo, que se utilizará para construir el árbol para la codificación:
class Nodo
{
public:
int code, lcode;
int frec, guarda;
int fils1, fils2;
Nodo()
{
code = lcode = frec = guarda = 0;
fils1...Implementación de una red neuronal en C++
Se trata de técnicas algorítmicas ligeramente diferentes, ya que pertenecen a la familia de la metaheurística, que reúne enfoques no deterministas para resolver problemas informáticos complejos como la optimización (búsqueda de valores mínimos o máximos, determinación de rutas, etc.) o la lógica difusa. Un algoritmo clásico es un método determinista que realiza una secuencia de operaciones para alcanzar un resultado en un tiempo conocido de antemano.
Los algoritmos con metaheurística persiguen un objetivo que alcanzarán con un cierto grado de precisión, en un determinado periodo de tiempo y trabajan con modelos de datos que generalmente están evolucionando. Las metaheurísticas actúan como catalizadores de los resultados; son una especie de "receta" que acelerará la consecución de un objetivo. En esta categoría se incluyen los algoritmos de templado simulado, los algoritmos genéticos y las redes neuronales.
1. ¿Una red neuronal para algoritmos?
Una red neuronal se puede concebir como una función que recibe argumentos y calcula un conjunto de resultados. Los argumentos de entrada pueden ser muchos y variados, incluidos símbolos, valores numéricos, letras, etc. Estas cantidades se representan en forma de valores numéricos continuos o discretos, digamos del tipo float, y cada ejemplo desarrolla su propia interpretación (o modelización), asimilando el valor a un booleano, una cantidad numérica o un símbolo.
La red neuronal reacciona a los argumentos de la función aplicada a su capa de entrada; las neuronas intermedias se activan en función de las interconexiones y acaban activando a su vez determinadas neuronas de la capa de salida.
La activación es una función de transferencia que produce un valor de cierta intensidad. Es importante entender que los valores de salida no son booleanos (1 o 0), sino valores que pueden estar "cerca" de los valores objetivo que intentamos alcanzar.
Una red neuronal se implementa en dos fases. La primera es la fase de aprendizaje, en la que se presentan a la red ejemplos de situaciones, en forma de referencias de entrada y salida. Durante esta fase, la red se adapta para que las neuronas de salida se activen...