M

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

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 ram

VRAM: (Vídeo RAM) una memoria de propósito especial usada por los adaptadores de vídeo. A diferencia de la convencional memoria RAM, la VRAM puede ser accedida por dos diferentes dispositivos de forma simultánea

SIMM : (Single In line Memory Module) un 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) un 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.

DIP : (Dual In line Package) un tipo de encapsulado consistente 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 acceden a los de un disco duro. VDISK, siglas de Virtual DISK, otro nombre de los RAM Disks.

Memoria Caché ó 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é y caché de disco.

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 derivado del hecho que necesita ser refrescada menos veces que la RAM dinámica.  La SRAM, debido a su alta velocidad, es usada como memoria caché.

DRAM: (Dynamic RAM) un 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 de 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 es casi un 20% más rápida que la RAM EDO. SDRAM entrelaza dos o más matrices de memoria interna de tal forma que mientras que 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) un 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) Se llama 'pipeline' a 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 'tuberia' conceptual con todas las fases del 'pipe' 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 y que se presentan en módulos DIMM de 168 contactos.

DDR SDRAM: Memoria síncrona, envía los datos dos veces por cada ciclo de reloj. 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

DDR2 SDRAM: Las memorias DDR 2 son una mejora de las memorias DDR (Double Data Rate), que permiten 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 presentan en módulos DIMM de 240 contactos.

DDR3 SDRAM: Considerado el sucesor de la actual memoria estándar DDR 2, DDR 3 promete proporcionar significantes mejoras en el rendimiento en niveles de bajo voltaje, lo que lleva consigo una disminución del gasto global de consumo.

RDRAM (Rambus DRAM): Aunque competidora de la DDR, la RDRAM funciona de modo muy distinto: la DDR utiliza los flancos de subida y bajada del reloj para duplicar su frecuencia efectiva (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 (hasta PC800) con un bus de datos de 16 bits.

NOTACION  

()   POTENCIA         */            +   -

INFIJA El orden es primer operando, operador, segundo operando.

PREFIJA El orden es operador, primer operando, segundo operando.

POSTFIJA El orden es primer operando, segundo operando, operador.

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.

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 como enunciados. NOTA: Regla recursiva 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álidos

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  0! = 1 1! = 1          2! = 2 ? 2! = 2 * 1!       3! = 6 ? 3! = 3 * 2!            4! = 24 ? 4! = 4 * 3!    N * (N – 1) !

¿Por qué escribir programas recursivos?   Son mas cercanos a la descripción matemática.Generalmente mas fáciles de analizar Se adaptan mejor a las estructuras de datos recursivas. Los algoritmos recursivos ofrecen soluciones estructuradas, modulares y elegantemente simples.

CUANDO USAR RECURSIVIDAD? Para simplificar el código. Cuando la estructura de datos es recursiva ejemplo : árboles.

CUANDO NO USAR RECURSIVIDAD  Cuando los métodos usen arreglos largos. Cuando el método cambia de manera impredecible de campos. Cuando las iteraciones sean la mejor opción.

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 entonces 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" que permite almacenar y recuperar datos. Se aplica en multitud de ocasiones en informática debido a su simplicidad y ordenación implícita en la propia estructura.

 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 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.

 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 más reciente localización en la pila; cuando la pila tiene un tamaño de cero, el puntero de pila de puntos en el origen de la pila.

 Las dos operaciones aplicables a todas las pilas son: Una operación apilar, en el que 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 de partida. Una operación desapilar: un elemento de datos en la ubicación actual apuntado por el puntero de pila es eliminado, y el puntero de pila se ajusta por el tamaño de los datos de partida.

. Esto significa que rotar a la derecha es mover el primer elemento a la tercera posición, la segunda a la primera y la tercera a la segunda.

MANZANA                                             PLATANO

PLATANO        DERECHA                       FRESA

FRESA                                                     MANZANA

FRESA                                                    MANZANA

PLATANO               IZQUIERDA           FRESA

MANZANA                                            PLATANO

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 de la dirección actual de la "cima" de células de la pila. En la parte superior e inferior se utiliza la terminología con independencia de que la pila crece realmente a la baja de direcciones de memoria o direcciones de memoria hacia 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: Es el conjunto de conexiones utilizadas para el intercambio de información entre el procesador y la memoria RAM. Por el viajan los datos cada vez que el procesador los necesita si el dato buscado no se encuentra en la memoria cache el microprocesador lo busca en la RAM. Como esto es muy frecuente la velocidad del Bus de datos influirá en la velocidad y 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 que 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.

 Ya desde su concepción inicial, los diseñadores del PC dispusieron una arquitectura que permitiese este tipo de intercambios.  El mecanismo utilizado se conoce como acceso directo a memoria DMA ("Direct Memory Access"), e 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.

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 escriba 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

 Modos de operación

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.  Es utilizada por dispositivos que solo pueden transmitir 1 byte cada vez

Bloque ("Block") Las transferencias se realizan en bloques (un máximo de 64 KB).  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 esto retrasa mucho la velocidad y el rendimiento del microprocesador se creó la memoria cache que se comunica con el microprocesador a altísimas velocidades y que almacena los datos mas usados entonces el microprocesador los busca allí y si no los encuentra recién se los pide a la RAM esto agiliza muchísimo al microprocesador.

METODOS DE ORDENAMIENTO

ALGORITMO DE ORDENAMIENTO O SORTEO Este proceso consiste en reacomodar los elementos de la lista en un nuevo orden, de acuerdo a algún criterio.

 Los métodos de agrupación se pueden ordenar en dos categorías:

Ordenación de arrays o Interna: Cuando los datos se guardan en memoria interna.

 Ordenación de ficheros o Externa: Cuando los datos de guardan en memoria externa .

METODO DE LA BURBUJA......METODO DE 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. .

El procedimiento de la burbuja es el siguiente: Ir comparando desde la casilla 0 numero tras número 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 seguirá así hasta que halla ordenado todas las casillas del vector. Una de las deficiencias del algoritmo es que ya cuando a ordenado parte del vector vuelve a compararlo cuando esto ya no es necesario.

METODO QUICKSORT: Se toma un elemento x de una posición cualquiera del arreglo. 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 pero ahora 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.

ALGORITMO DE BUSQUEDA Es aquel que 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 éste. Este problema puede reducirse a devolver la existencia de un número en un vector.

BUSQUEDA SECUENCIAL Se utiliza cuando el contenido del vector no se encuentra 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 que el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del arreglo.

BUSQUEDA BINARIA: . Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del arreglo (normalmente el elemento central), si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del arreglo que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del arreglo que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible, con el elemento buscado como elemento central. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en el arreglo.

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., resumir o identificar un dato a través de la probabilidad, utilizando 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: numero de accesos que es necesario efectuar sobre un array para encontrar el elemento deseado.

DISTRIBUCION SIMPLE: Ordena el vector tomando cada número e insertándolo en la posición que toma su valor, es decir, tengo un cinco en el arreglo; lo pongo en la posición cinco, algo así como: "lo que valgas en esa posición te pongo".

METODO 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 especialmente formateados, radix sort no está limitado sólo a los enteros.

ARBOLES

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 numero 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.

Un árbol ordenado de define como un árbol en el que los subárboles de cada nodo forman un conjunto ordenado. En un árbol ordenado, podemos hablar del primero, segundo o último hijo de un nodo en particular. El primer hijo de un nodo en un árbol ordenado se denomina con frecuencia el hijo más viejo de este nodo y el último se denomina el hijo más joven.  (A-----B-C-D------E------F-------G-)

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 dada, es una definición recursiva, es decir, cada subárbol es un árbol binario.

 Cuando se visitan los nodos preorden, primero se visita la raíz, después el subárbol izquierdo y por ultimo 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 ultimo 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 ultimo la raíz.

FUNCIONES USADAS EN LOS ARBOLES  

 BUSQUEDA  -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!.

 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 deseamos borrar un nodo que tiene dos descendientes, ya que son con un solo puntero no puede apuntarse en dos direcciones.

GRAFOS    Conjunto de vertices o nodos V y un conjunto de arcos A. Se representan con el par G=(V, A).

La terminología que manejaremos regularmente para el uso de grafos es la siguiente:

CAMINO. Es una secuencia de vértices V1, V2, V3, ... , Vn, tal que cada uno de estos V1->V2, V2->V3, V1->V3. LONGITUD DE CAMINO. Es el número de arcos en ese camino.

CAMINO SIMPLE. Es cuando todos sus vértices, excepto tal vez el primero y el último son distintos.

CICLO SIMPLE. Es un camino simple de longitud por lo menos de uno que empieza y termina en el mismo vértice.

ARISTAS PARALELAS. Es cuando hay más de una arista con un vértice inicial y uno terminal dados.

GRAFO CICLICO. Se dice que un grafo es cíclico cuando contiene por lo menos un ciclo.

 GRAFO ACICLICO. Se dice que un grafo es aciclíco cuando no contiene ciclos.

GRAFO CONEXO. Un grafo G es conexo, si y solo si existe un camino simple en cualesquiera dos nodos de G.

GRAFO COMPLETO ó FUERTEMENTE CONEXO. Un grafo dirigido G es completo si para cada par de nodos (V,W) existe un camino de V a W y de W a V (forzosamente tendrán que cumplirse ambas condiciones), es decir que cada nodo G es adyacente a todos los demás nodos de G.

 GRAFO UNILATERALMENTE CONEXO. Un grafo G es unilateralmente conexo si para cada par de nodos (V,W) de G hay un camino de V a W o un camino de W a V.

GRAFO PESADO ó ETIQUETADO. Un grafo es pesado cuando sus aristas contienen datos (etiquetas). Una etiqueta puede ser un nombre, costo ó un valor de cualquier tipo de dato. También a este grafo se le denomina red de actividades, y el número asociado al arco se le denomina factor de peso.

VERTICE ADYACENTE. Un nodo o vértice V es adyacente al nodo W si existe un arco de m a n.

GRADO DE SALIDA. El grado de salida de un nodo V de un grafo G,es el número de arcos o aristas que empiezan en V.

GRADO DE ENTRADA. El grado de entrada de un nodo V de un grafo G, es el número de aristas que terminan en V.

NODO FUENTE. Se le llama así a los nodos que tienen grado de salida positivo y un grado de entrada nulo.

NODO SUMIDERO. Se le llama sumidero al nodo que tiene grado de salida nulo y un grado de entrada positivo.

REPRESENTACION DE GRAFOS

MATRIZ DE ADYACENCIA La matriz de adyacencia es la forma más común de representación y la más directa. Consiste en una tabla de tamaño n x n, en la que a i j tendrá como 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 hay que asegurarse de que se marca con un 1 tanto la entrada a i j como la entrada a j i, puesto que se puede recorrer en ambos sentidos.

LISTA DE ADYACENCIA Una lista de adyacencia consiste de una lista de los vértices del grafo y para cada vértice de 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 entre ambos vértices.

Las aplicaciones más importantes de grafos Rutas entre ciudades. Determinar tiempos máximos y mínimos en un proceso. Flujo y control en un programa.