Memoria, estructuras y algoritmos: RAM, recursividad, pilas, buses, ordenamiento, árboles y grafos

Memoria RAM (Random Access Memory)

RAM (Random Access Memory). Es un tipo de memoria a la que se puede acceder de forma directa; es decir, se puede acceder a cualquier byte de la memoria sin pasar por los bytes precedentes. La RAM es el tipo más común de memoria en las computadoras y en otros dispositivos, tales como impresoras.

Tipos básicos de RAM

Hay dos tipos básicos de RAM:

• DRAM (Dynamic RAM), RAM dinámica.
• SRAM (Static RAM), RAM estática.

Los dos tipos difieren en la tecnología que usan para almacenar los datos. La RAM dinámica necesita ser refrescada cientos de veces por segundo, mientras que la RAM estática no necesita ser refrescada tan frecuentemente, lo que la hace más rápida pero también más cara que la RAM dinámica.

Tipos de memoria y encapsulados

• VRAM (Video RAM): Memoria de propósito especial usada por los adaptadores de vídeo. A diferencia de la memoria convencional RAM, la VRAM puede ser accedida por dos dispositivos de forma simultánea.
• SIMM (Single In-line Memory Module): Tipo de encapsulado consistente en una pequeña placa de circuito impreso que almacena chips de memoria y que se inserta en un zócalo SIMM en la placa madre o en la placa de memoria.
• DIMM (Dual In-line Memory Module): Tipo de encapsulado consistente en una pequeña placa de circuito impreso que almacena chips de memoria, que se inserta en un zócalo DIMM en la placa madre y usa generalmente un conector de 168 contactos (en versiones antiguas).
• DIP (Dual In-line Package): Tipo de encapsulado que consiste en almacenar un chip de memoria en una caja rectangular con dos filas de pines de conexión en cada lado.
• RAM Disk: Se refiere a la RAM que ha sido configurada para simular un disco duro. Se puede acceder a los ficheros de un RAM disk de la misma forma en la que se accede a los de un disco duro. VDISK (Virtual DISK) es otro nombre para los RAM Disks.
• Memoria caché o RAM Caché: Un caché es un sistema especial de almacenamiento de alta velocidad. Puede ser tanto un área reservada de la memoria principal como un dispositivo de almacenamiento de alta velocidad independiente. Hay dos tipos de caché frecuentemente usados en las computadoras personales: memoria caché (del procesador) y caché de disco.

Tecnologías y variantes de RAM

• SRAM (Static Random Access Memory): Es un tipo de memoria que es más rápida y fiable que la más común DRAM (Dynamic RAM). El término "estática" viene del hecho de que necesita ser refrescada menos frecuentemente que la RAM dinámica. La SRAM, debido a su alta velocidad, es usada como memoria caché.
• DRAM (Dynamic RAM): Tipo de memoria de gran capacidad pero que precisa ser constantemente refrescada (re-energizada) o perdería su contenido. Generalmente usa un transistor y un condensador para representar un bit. Los condensadores deben ser energizados cientos de veces por segundo para mantener las cargas.
• SDRAM (Synchronous DRAM): DRAM síncrona, un tipo de memoria RAM dinámica que suele ser más rápida que la RAM EDO. SDRAM entrelaza dos o más matrices de memoria interna de tal forma que, mientras se está accediendo a una matriz, la siguiente se está preparando para el acceso.
• FPM (Fast Page Mode): Memoria en modo paginado; el diseño más común de chips de RAM dinámica. El acceso a los bits de memoria se realiza por medio de coordenadas: fila y columna.
• EDO (Extended Data Output): Tipo de chip de RAM dinámica que mejora el rendimiento del modo de memoria Fast Page alrededor de un 10%.
• PB SRAM (Pipeline Burst SRAM): "Pipeline" es una categoría de técnicas que proporcionan un proceso simultáneo o en paralelo dentro de la computadora y se refiere a las operaciones de solapamiento moviendo datos o instrucciones en una tubería conceptual con todas las fases procesando simultáneamente. Por ejemplo, mientras una instrucción se está ejecutando, la computadora está decodificando la siguiente instrucción.
• SDR SDRAM: Memoria síncrona con tiempos de acceso de entre 25 y 10 ns que se presenta en módulos DIMM de 168 contactos (en especificaciones antiguas).
• DDR SDRAM: Memoria síncrona que envía los datos dos veces por cada ciclo de reloj (Double Data Rate). De este modo trabaja al doble de velocidad del bus del sistema sin necesidad de aumentar la frecuencia de reloj. Se presenta en módulos DIMM de 184 contactos (especificaciones antiguas).
• DDR2 SDRAM: Mejora de las memorias DDR, que permite que los búferes de entrada/salida trabajen al doble de la frecuencia del núcleo, permitiendo que durante cada ciclo de reloj se realicen cuatro transferencias. Se presenta en módulos DIMM de 240 contactos.
• DDR3 SDRAM: Considerada sucesora de DDR2; proporciona mejoras en el rendimiento, incluyendo funcionamiento a niveles de bajo voltaje, lo que reduce el consumo energético.
• RDRAM (Rambus DRAM): Competidora de la DDR. Funciona de modo distinto: la DDR utiliza los flancos de subida y bajada del reloj para duplicar su frecuencia efectiva (por ejemplo, hasta DDR-400) con un bus de datos de 64 bits, mientras que la RDRAM eleva la frecuencia de los chips para evitar cuellos de botella (ej. PC800) con un bus de datos más estrecho (por ejemplo, 16 bits).

Notación

Existen varias notaciones para expresar operaciones:

• Infija: El orden es primer operando, operador, segundo operando. Ej.: A + B.
• Prefija: El orden es operador, primer operando, segundo operando. Ej.: + A B.
• Postfija: El orden es primer operando, segundo operando, operador. Ej.: A B +.

Recursividad

La recursividad se puede usar en toda situación en la cual la solución pueda ser expresada como una secuencia de movimientos, pasos o transformaciones gobernadas por un conjunto de reglas no ambiguas.

Funciones recursivas

Las funciones recursivas se componen de:

• Caso base: Una solución simple para un caso particular (puede haber más de un caso base). La secuenciación, iteración condicional y selección son estructuras válidas de control que pueden ser consideradas enunciados. Nota: La regla recursiva indica que las estructuras de control que se pueden formar combinando de manera válida la secuenciación, iteración condicional y selección también son válidas.
• Caso recursivo: Una solución que involucra volver a utilizar la función original, con parámetros que se acercan más al caso base. Los pasos que sigue el caso recursivo son los siguientes:
  • El procedimiento se llama a sí mismo.
  • El problema se resuelve resolviendo el mismo problema pero de tamaño menor.
  • La manera en la cual el tamaño del problema disminuye asegura que el caso base eventualmente se alcanzará.

Factorial

Definición:

0! = 1, 1! = 1, 2! = 2 (2! = 2 * 1!), 3! = 6 (3! = 3 * 2!), 4! = 24 (4! = 4 * 3!).

Fórmula general: N! = N * (N − 1)!

¿Por qué escribir programas recursivos?

La recursividad suele ser más cercana a la descripción matemática, generalmente más fácil de analizar y se adapta mejor a las estructuras de datos recursivas. Los algoritmos recursivos ofrecen soluciones estructuradas, modulares y elegantemente simples.

¿Cuándo usar recursividad?

Para simplificar el código, especialmente cuando la estructura de datos es recursiva (por ejemplo: árboles).

¿Cuándo no usar recursividad?

No usarla cuando los métodos usan arreglos largos, cuando el método cambia de manera impredecible de campos, o cuando las iteraciones sean la mejor opción (por razones de eficiencia o uso de memoria).

Fibonacci

Caso base: Fib(0) = 0; Fib(1) = 1.

Caso recursivo: Fib(i) = Fib(i−1) + Fib(i−2).

Dividir para vencer

Muchas veces es posible dividir un problema en subproblemas más pequeños, generalmente del mismo tamaño, resolver los subproblemas y luego combinar sus soluciones para obtener la solución del problema original.

Pilas

Una pila es una lista ordinal o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO, es decir, "último en entrar, primero en salir". Permite almacenar y recuperar datos y se aplica en multitud de ocasiones en informática debido a su simplicidad y ordenación implícita en la propia estructura.

Operaciones básicas

POP / PUSH

En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, top of stack en inglés). La operación retirar (pop) permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS. La operación apilar (push) coloca un elemento en la cima de la pila.

Contextos de uso

Las pilas suelen emplearse en los siguientes contextos:

• Evaluación de expresiones en notación postfija (notación polaca inversa).
• Reconocedores sintácticos de lenguajes independientes del contexto.
• Implementación de recursividad.

Arquitectura básica de una pila

Una pila típica es un área de la memoria de los computadores con un origen fijo y un tamaño variable. Al principio, el tamaño de la pila es cero. Un puntero de pila, por lo general en forma de un registro de hardware, apunta a la localización más reciente en la pila; cuando la pila tiene un tamaño de cero, el puntero de pila apunta al origen de la pila.

Las dos operaciones aplicables a todas las pilas son:

• Apilar: Un elemento de datos se coloca en el lugar apuntado por el puntero de pila, y la dirección en el puntero de pila se ajusta por el tamaño de los datos insertados.
• Desapilar: Un elemento de datos en la ubicación actual apuntada por el puntero de pila es eliminado, y el puntero de pila se ajusta por el tamaño de los datos retirados.

Ejemplo ilustrativo (rotaciones)

En ocasiones se muestran ejemplos ilustrativos con elementos simples. Por ejemplo, rotaciones a la derecha e izquierda con elementos MANZANA, PLÁTANO, FRESA:

Rotar a la derecha: mover el primer elemento a la tercera posición, la segunda a la primera y la tercera a la segunda.

Ejemplo (posiciones antes / acción / posiciones después):

• MANZANA          PLÁTANO          FRESA
• PLÁTANO    DERECHA    FRESA
• FRESA             MANZANA
• FRESA             MANZANA
• PLÁTANO     IZQUIERDA   FRESA
• MANZANA        PLÁTANO

Una pila es normalmente representada en los ordenadores por un bloque de celdas de memoria, con los "de abajo" en una ubicación fija, y el puntero de pila indicando la dirección actual de la "cima" de células de la pila. La terminología "arriba" y "abajo" se utiliza independientemente de que la pila crezca realmente hacia direcciones de memoria menores o mayores.

Intercambio de datos entre tipos de memoria

El Registro de Intercambio de Datos es el utilizado por el bus de datos del ordenador para tomar y dejar los datos que se leen y escriben en memoria.

Bus de datos

Bus de datos: Conjunto de conexiones utilizadas para el intercambio de información entre el procesador y la memoria RAM. Por él viajan los datos cada vez que el procesador los necesita. Si el dato buscado no se encuentra en la memoria caché, el microprocesador lo busca en la RAM. Como esto es muy frecuente, la velocidad del bus de datos influirá en el rendimiento del microprocesador.

Tipos de bus

1. Bus de datos: Utilizado para que el microprocesador intercambie información con los otros elementos del sistema, y en algunos casos entre dispositivos.
2. Bus de direcciones: Usado para indicar cuál es el elemento con el que se realizará la transferencia de datos.
3. Bus de control: Indica la dirección, tipo y otras características de la operación de transferencia.

Desde su concepción inicial, los diseñadores del PC dispusieron una arquitectura que permitiese intercambios directos entre dispositivos y memoria. El mecanismo utilizado se conoce como acceso directo a memoria DMA (Direct Memory Access). Igual que ocurre con las excepciones, el sistema DMA dispone de algunos elementos hardware auxiliares que lo convierten en un subsistema autónomo dentro del bus externo.

Elementos del sistema DMA

Estos elementos son:

• Ciertas líneas dedicadas en el bus de control.
• Un procesador específico, el DMAC (DMA Controller), que permite que puedan realizarse estos intercambios sin apenas intervención del procesador.
• Pequeñas zonas auxiliares de memoria, conocidas como registros de página.

Líneas de control

El bus de control tiene líneas específicas para este tipo de intercambios, de forma que el DMA es un subsistema autónomo dentro del mecanismo general de intercambio de datos y control del bus. Son las siguientes:

• Líneas DRQ1 a DRQ3 ("DMA request"): Utilizadas por los dispositivos que necesitan efectuar un acceso directo a memoria.
• Líneas DACK1 a DACK3 ("DMA acknowledge"): Se utilizan para acusar recibo de la petición DRQ correspondiente.
• AEN ("Access Enabled"): Cuando esta señal está alta, el controlador DMA tiene control sobre ciertas líneas del bus; precisamente las que gobiernan los intercambios con memoria y puertos (MEMR, MEMW, IOR, IOW, etc.).
• MEMR ("Memory Read"): Cuando se activa, esta señal indica a la memoria conectada al bus que coloque los datos en el bus de datos.
• MEMW ("Memory Write"): Cuando se activa, indica a la memoria que almacene los datos situados en el bus de datos.

Conexiones del controlador DMA con las patillas 30 y 31 de la UCP (según especificación original).

Modos de operación del DMA

• Sencillo ("Single"): Este modo transfiere solo un byte cada vez. Después de cada transferencia el sistema cede el control del bus y debe adquirirlo de nuevo para transmitir el siguiente. Se utiliza por dispositivos que solo pueden transmitir 1 byte cada vez.
• Bloque ("Block"): Las transferencias se realizan en bloques (un máximo de 64 KB en arquitecturas clásicas). Se supone que el periférico es capaz de escribir/leer los datos a velocidad sostenida, porque una vez iniciada la transferencia continúa hasta que se completa.
• Demanda ("Demand"): Como en el caso anterior, la transferencia se realiza en bloques, pero solo tiene lugar mientras el dispositivo mantiene activada la línea de petición correspondiente (DRQ).

Como las transferencias directas con RAM pueden retrasar mucho al microprocesador, se creó la memoria caché que se comunica con el microprocesador a altísimas velocidades y que almacena los datos más usados. Entonces el microprocesador los busca primero en la caché y, si no los encuentra, recién se los pide a la RAM; esto agiliza muchísimo el rendimiento del microprocesador.

Métodos de ordenamiento

Algoritmo de ordenamiento o de ordenación: Este proceso consiste en reacomodar los elementos de una lista en un nuevo orden, de acuerdo a algún criterio.

Los métodos de ordenación se pueden agrupar en dos categorías:

• Ordenación interna (o de arrays): Cuando los datos se guardan en memoria interna.
• Ordenación externa (o de ficheros): Cuando los datos se guardan en memoria externa.

Método de la burbuja (intercambio directo)

Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios.

Procedimiento: Ir comparando desde la casilla 0 elemento tras elemento hasta encontrar uno mayor; si este es realmente el mayor de todo el vector se llevará hasta la última casilla; si no es así, será reemplazado por uno mayor que él. Este procedimiento continúa hasta que haya ordenado todas las casillas del vector. Una de las deficiencias del algoritmo es que, cuando ya ha ordenado parte del vector, vuelve a compararlo cuando esto ya no es necesario.

Método Quicksort

Se toma un elemento x de una posición cualquiera del arreglo (el pivote). Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x. Se repiten los pasos anteriores para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de x en el arreglo (recursión).

Algoritmos de búsqueda

Un algoritmo de búsqueda está diseñado para localizar un elemento concreto dentro de una estructura de datos. Consiste en solucionar un problema de existencia o no de un elemento determinado en un conjunto finito de elementos, es decir, si el elemento en cuestión pertenece o no a dicho conjunto, además de su localización dentro de este.

Búsqueda secuencial

Se utiliza cuando el contenido del vector no está ordenado o no puede ser ordenado. Consiste en buscar el elemento comparándolo secuencialmente con cada elemento del arreglo hasta que éste se encuentre, o hasta que se llegue al final del arreglo. La existencia se puede asegurar desde el momento en que el elemento es localizado, pero no se puede asegurar la no existencia hasta no haber analizado todos los elementos del arreglo.

Búsqueda binaria

Para implementar este algoritmo el arreglo debe estar ordenado. Se compara el elemento a buscar con un elemento de posición central; si el valor de éste es mayor que el del elemento buscado, se repite el procedimiento en la mitad izquierda del arreglo; en caso contrario, se toma la mitad derecha. De esta manera se obtienen intervalos cada vez más pequeños hasta que se encuentre el elemento o hasta que el intervalo sea indivisible, lo que permite deducir la ausencia del elemento.

Algoritmos Hash

Hash: Se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un documento, registro, archivo, etc. Resume o identifica un dato mediante una función hash o algoritmo hash. Los algoritmos hash son métodos de búsqueda que proporcionan una longitud de búsqueda pequeña y una flexibilidad superior a la de otros métodos.

Longitud de búsqueda: Número de accesos que es necesario efectuar sobre un array para encontrar el elemento deseado.

Distribución simple

Ordena el vector tomando cada número e insertándolo en la posición que corresponde a su valor; es decir, si tengo un cinco en el arreglo, lo pongo en la posición cinco (método aplicable cuando el universo de valores es acotado y conocido).

Método Radix

Ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante formateados, radix sort no está limitado sólo a los enteros.

Árboles

Un árbol es una estructura no lineal formada por un conjunto de nodos y un conjunto de ramas.

En un árbol existe un nodo especial denominado raíz.

Un nodo del que sale alguna rama recibe el nombre de nodo de bifurcación o nodo rama, y un nodo que no tiene ramas recibe el nombre de nodo terminal o nodo hoja.

Los nodos restantes están agrupados en n > 0 conjuntos distintos A1, … , An, cada uno de los cuales es a su vez un árbol, que recibe el nombre de subárbol de raíz.

El número de ramas de un nodo recibe el nombre de grado del nodo.

El nivel de un nodo respecto al nodo raíz se define diciendo que la raíz tiene nivel 0 y cualquier otro nodo tiene un nivel igual a la distancia de ese nodo al nodo raíz. El máximo de los niveles se denomina profundidad o altura del árbol.

Árbol ordenado, bosque y árbol binario

Un árbol ordenado se define como un árbol en el que los subárboles de cada nodo forman un conjunto ordenado. En un árbol ordenado, podemos hablar del primer, segundo o último hijo de un nodo en particular. El primer hijo se denomina con frecuencia el hijo más viejo y el último el hijo más joven.

Un bosque es un conjunto ordenado de árboles ordenados.

Un árbol binario es un conjunto finito de nodos que consta de un nodo raíz que tiene dos subárboles binarios denominados subárbol izquierdo y subárbol derecho. La definición es recursiva: cada subárbol es a su vez un árbol binario.

Recorridos

Cuando se visitan los nodos preorden, primero se visita la raíz, después el subárbol izquierdo y por último el subárbol derecho.

Cuando se visitan los nodos en inorden, primero se visita el subárbol izquierdo, después la raíz y por último el subárbol derecho.

Cuando se visitan los árboles en postorden, primero se visita el subárbol izquierdo, después el subárbol derecho y por último la raíz.

Funciones usadas en árboles

• Búsqueda: Para todo nodo a: todas las claves del subárbol izquierdo son menores que la clave de a y todas las claves del subárbol derecho de a son mayores que la clave de a (propiedad del árbol binario de búsqueda).
• Borrado: Es una tarea fácil si el nodo a borrar es un nodo terminal o tiene un único descendiente; la dificultad se presenta cuando se desea borrar un nodo que tiene dos descendientes, ya que con un solo puntero no puede apuntarse en dos direcciones. En esos casos se usan estrategias como reemplazar por el sucesor inorden o por el predecesor inorden.

Grafos

Un grafo es un conjunto de vértices o nodos V y un conjunto de arcos A. Se representa con el par G = (V, A).

La terminología habitual para grafos incluye:

Conceptos básicos

• Camino: Secuencia de vértices V1, V2, V3, ..., Vn tal que existe arco entre V1→V2, V2→V3, ..., V(n−1)→Vn.
• Longitud de camino: Número de arcos en ese camino.
• Camino simple: Camino en el que todos sus vértices, excepto tal vez el primero y el último, son distintos.
• Ciclo simple: Camino simple de longitud al menos uno que empieza y termina en el mismo vértice.
• Aristas paralelas: Cuando hay más de una arista con un vértice inicial y uno terminal dados.
• Grafo cíclico: Se dice que un grafo es cíclico cuando contiene al menos un ciclo.
• Grafo acíclico: Se dice que un grafo es acíclico cuando no contiene ciclos.
• Grafo conexo: Un grafo G es conexo si y solo si existe un camino simple entre cualesquiera dos nodos de G.
• Grafo completo o fuertemente conexo: Un grafo dirigido G es fuertemente conexo si para cada par de nodos (V, W) existe un camino de V a W y otro de W a V; es decir, cada nodo es (directamente o indirectamente) adyacente a todos los demás.
• Grafo unilateralmente conexo: Un grafo G es unilateralmente conexo si para cada par de nodos (V, W) hay un camino de V a W o un camino de W a V.
• Grafo pesado o etiquetado: Un grafo es pesado cuando sus aristas contienen datos (etiquetas), por ejemplo nombre, costo o cualquier valor. También se denomina red de actividades, y el número asociado al arco se denomina factor de peso.
• Vértice adyacente: Un vértice V es adyacente a un vértice W si existe un arco entre ellos (en la dirección considerada).
• Grado de salida: Número de arcos que empiezan en un nodo V (outdegree).
• Grado de entrada: Número de arcos que terminan en un nodo V (indegree).
• Nodo fuente: Nodo que tiene grado de salida positivo y grado de entrada nulo.
• Nodo sumidero: Nodo que tiene grado de salida nulo y grado de entrada positivo.

Representación de grafos

• Matriz de adyacencia: Forma común y directa de representación. Consiste en una tabla de tamaño n x n en la que aij tendrá valor 1 si existe una arista del vértice i al vértice j; en caso contrario, el valor será 0. Si el grafo es no dirigido, habrá que marcar con un 1 tanto la entrada aij como la entrada aji.
• Lista de adyacencia: Consiste en una lista de los vértices del grafo y, para cada vértice, una lista de sus vértices vecinos.

Camino mínimo

Se denomina camino mínimo entre dos vértices V y W al camino óptimo (de menor peso o menor número de aristas) entre ambos vértices.

Aplicaciones más importantes de grafos

Las aplicaciones incluyen rutas entre ciudades, determinación de tiempos máximos y mínimos en un proceso, flujo y control en un programa, entre otras.