Este blog es creado para agregarse las actividades, tareas e investigaciones a lo largo del curso, haciendo la función de un portafolio de evidencias.
Tarea 2 - Unidad 1
Manejo
de memoria estática y dinámica
·
Memoria Estática:
Desde
la compilación reservan un espacio fijo de elementos, se guarda en el disco
duro de una forma adyacente.
·
Memoria Dinámica:
En
la ejecución varia el número de elementos y uso de memoria a lo largo del
programa.
Esta
memoria se puede pedir en cualquier momento de la ejecución con una llamada a
malloc Memory Allocation
La
memoria dinámica es el que se puede modificar o hacer cambios en el tiempo en
que se está ejecutando el programa
La
memoria dinámica se guarda en el disco duro donde puede encontrar espacio o
donde se pueda ubicar.
Características:
·
Memoria Estática:
Se
define explícitamente al declarar una variable, ya sea global o local
El
compilador genera automáticamente el espacio de memoria
-Se
mantiene fija durante toda la vida de la variable (independientemente de que se
utilice o no)
·
Memoria Dinámica:
-Utiliza
una parte de la memoria principal denominada heap
-Apoya
el uso eficiente de la memoria durante la ejecución
-Requiere
apuntadores que almacenen direcciones de memoria real, dado que estas se
asignan dinámicamente.
Estructura
de Datos
Hay
sólo unos pocos tipos básicos de estructuras de datos: arrays, listas y
árboles. Todo lo demás puede estar compuesto mediante el uso de tipos diferentes
de estas dos estructuras (por ejemplo, una tabla hash se puede implementar con
una matriz de los valores de hash y una lista para cada valor de hash para
manejar colisiones).
De
estas estructuras, las matrices son estáticas (es decir, su huella de memoria
no varía con el tiempo a medida que las operaciones se realizan sobre ellos) y
todo lo demás es dinámico (es decir, en el caso general los cambios de consumo
de memoria).
Ventajas
y Desventajas
·
Memoria Estática:
Ventajas:
-
la memoria estática tiene las siguientes ventajas:
-
Tiene una lógica simple
-
Es óptima para resolver pequeños y medianos problemas
Desventajas:
-
No se puede cambiar en ejecución
-
No es óptima
-
Se hace desperdicio de memoria cuando no se guarda el tamaño determinado
·
Memoria Dinámica:
Ventajas:
-
El tamaño de la estructura no interfiere en el tamaño
-
Se guarda donde encuentra espacio
-
No hace falta darle el tamaño
Desventajas:
No
se conoce con anticipación el espacio que memoria que se va ocupar
Bibliografía
Estructuras
de datos: Referencia practica con orientación a objetos
Autores:
Román Martínez, Elda Quiroga
Editorial:
Cengage Learning Editores
Differences
between Static & Dynamic data structures
www.Stackoverflow.com
UNAM
http://www.google.com.mx/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CCAQFjAA&url=http%3A%2F%2Faprender.fca.unam.mx%2F~rcastro%2Fprogmemoria.ppt&ei=qtw2UJzfIMjsrQHNtYF4&usg=AFQjCNG0UCsiml7okE7xChB4vsRrjPUxKg&sig2=RFuVHbUisq12UgrnwZ7Wcg
http://www.programacionfacil.com/estructura_de_datos:manejo_de_memoria
Tarea 3 - Unidad 1
TIPO DE DATOS ABSTRACTO –TDA
Una función es una
generalización del concepto operador para ser aplicado a operaciones generales
definidas por un programador. Una función puede ser aplicada a diferentes
datos. Con funciones se logra una ocultación de información, denominado encapsulación. Un concepto similar
es la abstracción de datos. Un tipo
de datos abstracto – TDA define una nueva clase de objeto o concepto
que puede manejarse con independencia de la estructura de datos para
representarlo.
Para ello es necesario
especificar:
Las operaciones que se
puede realizar con los objetos.
El efecto que se
produce al actuar con las operaciones sobre los mismos.
Así un TDA es una
generalización de los tipos de datos primitivos de un lenguaje de programación.
Un TDA encapsula la definición del tipo y todas las operaciones con este tipo.
Los lenguajes de
programación entregan al programador ciertos tipos de datos básicos o primitivos,
especificando el conjunto de valores que una variable de uno de esos tipos
puede tomar y el conjunto de operaciones realizables sobre los mismos.
El número de tipo de
datos varía de un lenguaje de programación a otro. Por ejemplo, LISP puro tiene
sólo la expresión simbólica como tipo de dato, en cambio ADA tiene seis tipos
de datos básicos: enumeration, integer, real, array, record, y acces.
Los lenguajes de
programación tienen sus propias reglas para sus tipos de datos. Por ejemplo, si
se declara en C/C++
unsigned int x, y;
indica que las dos
variables son del tipo int y
el rango de valores que pueden tomar es 0 a 65.535. Si se realiza la operación
x/y su resultado será de tipo int.
En cambio si una de las variables fuese de punto flotante el resultado será de
punto flotante.
En el caso de FORTRAN77
las variables de tipo entero no se declaran, se usan las letras I, J, K, L, M o
N como inicial del nombre de la variable para indicar que una variable es del
tipo entero.
Además, los tipos de datos
básicos o primitivos que entregan los lenguajes de programación, también
proporcionan algún soporte para combinar datos entre sí de diferentes formas.
Esto se realiza por medio de estructuras de datos. De esta forma, los
programadores son capaces de definir sus propios tipos de datos combinando
varios tipos básicos para crear tipos agregados o compuestos, como son los
arreglos y las estructuras (registros).
La instrucción n = 5+3 de un programa donde = es el operador de asignación, el
contenido de la localidad de almacenamiento dado por n será el valor 8. En cambio, si n = ’O’ + ’K’, n contendrá la cadena OK. Cada tipo de datos no
solamente es reconocido por los elementos de datos que puede tomar, sino por
las operaciones asociadas a él. A un conjunto de elementos de datos se le
conoce como dominio de datos.
Por ejemplo, en PASCAL el
dominio entero se describe como: D = {0, 1, 2, ....., max}. Con el
identificador constante max, que corresponde al entero más grande. Las
operaciones para este dominio son:
Operadores unarios: {+,
-}
Operadores binarios:
{+, -, /,* ,div, mod}.
Esto es una abstracción
matemática que define los números enteros y sus propiedades. De esta forma
definido se espera que los números enteros asociados a sus operaciones se
comporten de manera apropiada en cualquier computador en la que se ejecute un
programa.
Los TDAs son
generalizaciones de los tipos de datos básicos y de las operaciones primitivas.
Además, un TDA encapsula cierto tipo de datos en el sentido que es posible
poner la definición del tipo y todas las operaciones con ese tipo en una
sección de un programa.
Cada conjunto de
operaciones define un TDA distinto. Por ejemplo, se puede definir un tipo de
datos abstracto CONJUNTO [Aho1988] con el cual se pueden definir las siguientes
operaciones:
ANULA(A) Hace vacío al
conjunto A
UNION(A, B, C)
Construye el conjunto C a partir de la unión de los conjuntos A y B.
TAMAÑO(A) Entrega la
cantidad de elementos del conjunto A.
Existen muchas
estructuras de datos que se pueden utilizar para implantar eficientemente un
conjunto. Por ejemplo, mediante arreglos. Las operaciones sobre conjuntos se
pueden implantar mediante funciones.
El componente básico de
una estructura de dato es la celda, la cual almacena un valor tomado de algún
tipo de dato básico o compuesto. Las estructuras de datos se crean dando un
nombre a agregados de celdas e interpretando (algunas veces) los valores de
algunas celdas como representantes de conexiones entre las celdas.
La mayoría de los
lenguajes de programación utilizan el mecanismo de agregación de celdas llamado
arreglo que es una colección de elementos de tipo homogéneo. Generalmente, está
ligado de manera estática con información proporcionada en la declaración de
una variable del tipo arreglo.
Ejemplo: Arreglo
bidimensional en C/C++
int a[5][3]
Aunque el programador
declara un arreglo de dos dimensiones, el computador tiene sólo una memoria de
una dimensión, lo que muestra en la figura. En el arreglo bidimensional se
quiere tener acceso al elemento marcado utilizando dos índices i y j, a[i][j].
En este caso con i=2 y j=0. La transformación de estos índices es realizada
aplicando la fórmula:
a[i][j] = b[i * n + j]
n es la cantidad de
columnas del arreglo bidimensional. La aplicación de esta fórmula entrega el
siguiente resultado:
a[2][0] = b[6]
Este resultado
corresponde al caso que los datos de un arreglo bidimensional están almacenados
por filas. Una fórmula similar se obtiene si los datos están almacenados por
columnas.
Otro ejemplo para un tipo
de dato abstracto es un objeto círculo para el cual es necesario especificar
que operaciones puede realizarse con él y el efecto que se produce al actuar
sobre él, por ejemplo:
float entrega Radio(circulo:
c)
{Necesita: un circulo c
Entrega: el radio del
círculo c}
La estructura de datos lista
también puede ser tratada como un TDA. Los detalles de la implantación de la
estructura de datos lista no le interesan al programador que utiliza esta
estructura. El término tipo de datos abstracto se refiere al hecho que se
acentúan las operaciones permitidas y no los detalles de la representación de
los datos en el programa, es decir se conocen solamente las propiedades
funcionales incluyendo los casos de error.
La abstracción permite
simplificar el análisis y resolución de un problema separando las
características que son relevantes de aquellas que no lo son. La relevancia
dependerá fuertemente del contexto.
Hay muchas formas para
especificar un TDA. Una de esas formas usa la estructura de una función en
C/C++. Un ejemplo es el TDA RACIONAL [Tenenbaum1993], que corresponde al
concepto matemático de número racional. Un número racional es un número que
puede expresarse como el cociente de dos enteros. Las operaciones que se
definen con números racionales son:
La creación de un
número racional a partir de dos enteros.
La suma.
La multiplicación.
La prueba de igualdad.
La especificación de este
TDA en un lenguaje formal de especificación es la siguiente:
/* Definición de valores
*/
abstract typedef <int,
int> RACIONAL;
condición RACIONAL[1] !=
0;
/* Definición de
operadores */
abstract RACIONAL
crearRacional(a, b)
int a, b;
precondición b != 0;
postcondición
crearRacional[0] == a;
crearRacional[1] == b;
abstract RACIONAL
sumaRacional(a, b)
int a, b;
postcondición suma[1] ==
a[1]*b[1];
suma[0] == a[0]*b[1] +
b[0]*a[1];
abstract RACIONAL
multRacional(a, b)
int a, b;
postcondición
multRacional[0] == a[0]*b[0];
multRacional[1] ==
a[1]*b[1];
abstract igualRacional(a,
b)
int a, b;
postcondición
igualRacional == (a[0]*b[1] == b[0]*a[1]);
El concepto TDA se puede
resumir con la siguiente figura, en la cual se muestra como un TDA especifica
el QUÉ pero no el CÓMO. El CÓMO está encapsulado.
Suscribirse a:
Entradas (Atom)