PROGRAMACIÓN Y ESTRUCTURA DE DATOS.
Introducción.
Jerarquía de memorias.
Se tienen 2 tipos de unidades de almacenamiento.
1) Unidades operacionales. Formadas por registros y acumuladores en el procesador almacenan las
instrucciones a realizar y los datos necesarios.
2) Unidades de almacenamiento. Formada por la memoria principal y la secundaria.
La memoria principal maneja una mayor cantidad de datos, pero para su tratamiento debe ser
transferida a un registro o acumulador.
La memoria secundaria se utiliza para información más permanente, alojadas en estructuras
llamadas archivos.
Transmisión de datos entre memoria y CPU.
La memoria se encuentra formada por n localidades de memoria que guardan un número b de bits.
Además cada localidad tiene una dirección asociada de 0 a n-1 también formada por una cantidad x
de bits. Entre la memoria y el procesador existe un canal de comunicación conocido como bus de
memoria con 3 tipos de líneas:
● Líneas de dirección (Address Bus) que transportan la dirección de memoria a acceder.
● Líneas de datos (Data Bus) que transportan los bits a almacenar o que se recuperaron.
● Líneas de control (Control Bus) que indican la operación a realizar (lectura o escritura).
Transmisión de datos entre CPU y dispositivos.
La comunicación se da mediante interfaces o drivers que se encargan de enviar los datos de acuerdo
al formato que cada dispositivo requiere.
Transmisión de datos entre memoria y dispositivos.
Usualmente se da a través del procesador, pero hay dispositivos que pueden hacer acceso directo a
memoria.
Definición de algoritmos.
Es un conjunto de instrucciones lógicas y ordenadas que nos sirven para dar con la solución a un
problema. Su diseño involucra un proceso mental dividido en varias etapas.
Efectividad de algoritmos.
Para comparar la efectividad de un algoritmo con respecto a otros, se necesita conocer la
complejidad espacial (entre más estructuras de datos maneje un algoritmo mayor es su complejidad)
y su complejidad temporal (el tiempo que lleve para entregar resultados).
Se grafica el tiempo en función del tamaño n que tiene un problema para ser resuelto cuando n crece
de forma ilimitada. (Comportamiento Asintótico)
Así f(x) es un polinomio que depende de las variables y estructuras que forman el algoritmo.
Estructura de datos.
Es la armadura que sostiene los datos de un problema y define la forma en la que estarán dispuestos
en memoria principal.
Nota.
Las estructuras de datos cuando están en memoria secundaria, se conocen como estructuras de
almacenamiento, más conocidas como archivos.
Operaciones básicas a realizar sobre una estructura de datos:
Creación, destrucción, almacenamiento, recuperación.
Formas de almacenamiento.
Enteros.
Sistema decimal.
El sistema decimal es un sistema posicional. El valor de cada dígito
depende de su posición.
1 El dígito uno, el número vale uno.
10 El dígito uno, el número vale diez.
100 El dígito uno, el número vale cien.
El valor del número se obtiene con la suma de cada dígito por su valor posicional.
10n … 102 101 100 . 10-1 10-2 … 10-n
356 = 3 x 102+ 5 x 101+ 6 x 100= 3 x 100 + 5 x 10 + 6 x 1 = 300 + 50 + 6 = 356
El total de números es:
Bn=103 = 1000
Y el número más grande que se puede tener con n posiciones es:
Bn– 1 Por ejemplo, con 3 posiciones decimales se tienen 103– 1 = 999
Sistema binario.
El sistema binario es un sistema posicional. El valor de cada dígito depende de su posición.
1 El dígito uno, el número vale uno.
10 El dígito uno, el número vale dos.
100 El dígito uno, el número vale cuatro.
El valor del número se obtiene con la suma de cada dígito por su valor posicional.
2n … 22 21 20 . 2-1 2-2 … 2-n
100110 = 1 x 25 + 0 x 24 + 0 x 23 + 1 x 22 + 1 x 21 + 0 x 20= 32 + 0 + 0 + 4 + 2 + 0 = 38
El total de números es:
Bn=23 = 8
Y el número más grande que se puede tener con n posiciones es:
Bn– 1
Por ejemplo, con 3 posiciones binarias se tienen 23– 1 = 7
000
001
010
011
100
101
110
111
Conversión decimal a binario.
a) Por suma de potencias de 2
45 = 32 +8+4+1 = 101101
76 = 64+8+4 = 1001100
b) Por división repetida
Se divide el número repetidamente entre dos conservando los residuos hasta que se obtenga un cociente
cero.
El primer residuo es el LSB y el último el MSB
MSB LSB
Los números enteros se representan en la computadora usando cualquiera de los siguientes sistemas:
● Signo y magnitud
● 1er. Complemento
● 2do. Complemento
La diferencia entre los sistemas está en cómo representan a los números enteros negativos.
El bit MSB se reserva para el signo, 0 es positivo y 1 es negativo.
2do. Complemento
De manera más sencilla se complementa el equivalente positivo y se le suma 1.
Obtener -7
7 = 00111
Complemento 11000
+ 1
= 11001
Obtener -3
3 = 0011
Complemento 1100
+ 1
= 1101
Rango.
-2n-1<= X <= 2n-1 - 1
2,147,483,647
-2,147,483,648
Reales.
Punto fijo. El punto decimal está implícitamente localizado en
alguna posición predeterminada.
Ejemplos.
0110110 = 54
011011.011 = 27.375
Representación de la parte decimal.
0.1 = 0.5
0.01 = 0.25
0.001 = 0.125
0.0001 = 0.0625
La suma de los productos de los dígitos por su valor posicional.
1011.101 = 1 x 23+ 0 x 22 +1 x 21 +1 x 20 +1 x 2-1 +0 x 2-2+1 x 2-3= 8+0+2+1+0.5+0+0.125 = 11.625
+2.5 = 010.1
La parte fraccionaria se calcula partiendo de 0.5 y dividiendo entre 2
0.5, 0.25, 0.125, 0.0625, etc…
O con el factor de escala:
Positivo que representa X 2-n ,donde n es el número de bits de la representación entera.
110.11011 = 6.84375
0.11011 = 27 x 2 -5= 0.84375
10.01110 =
0.01110 = 14 x 2 -5= 0.4375
1111.00100101 =
0.00100101 = 37 x 2 -8 = 0.14453125
Fracciones decimales a binario.
a) Expresado como la suma de fracciones de las potencias negativas de 2.
b) Se duplica la parte fraccionaria de la cantidad y nos quedamos con la parte entera hasta obtener
una parte decimal igual a cero.
Ejemplos.
0.25 =
0.5
1.0
=0.012
0.125 =
0.25
0.5
1.0
=0.0012
0.84375 =
1.6875
1.375
0.75
1.5
1.0
= 0.110112
Pero 0.26 un número finito, al pasarlo a binario se hace infinito. Este se truncará y tal vez
redondeará, lo que generará aproximaciones.
0.26
0.52
1.04
0.08
0.16
0.32
0.64
1.28
0.56
1.12
0.24
0.48
0.96
1.92
1.84
1.68 =0.010000101000111 ………. truncamiento = redondeo = aproximado
Punto flotante.
Permite representar números muy grandes o muy pequeños con el sig. Formato:
MxbE, donde M es la mantisa, b es la base y E es el exponente.
bE es el factor de escala.
Se asume una base fija y un exponente que varía para distinto número. Los números representados
no siempre tienen los mismos dígitos a la derecha del punto.
Ejemplos.
3.14159
314159 x 10-5
314.159 x 10-2
3141590 x 10-6
31415.9 x 10-4
0.000314159 x 104
168x 1011 = 16800000000000
832 x 10-13 = 0.0000000000832
En la computadora exponente y mantisa se expresan en base 2.
Ejemplo
N=16 bits
El número de bits con los que se expresa la mantisa constituye la precisión y los del exponente
determinan el rango.
Representación de 4 bytes (32 bits)
Un problema es que distintos números se pueden representar de distintas formas.
Para evitar esto la convención es que el bit 23 (el bit 24), sea siempre igual a 1. Ajustando el
exponente al valor necesario, a esto se le llama representación normalizada. Y al bit 23 se le llama
bit oculto.
Dado que siempre vale uno, la máquina no lo lee. Para evitar el desperdicio de un bit este se usa
también para el exponente.
En algunos sistemas el exponente se expresa en un sistema llamado exceso de 127 (en algunos
casos 128 o 126)
La razón, es para evitar lo siguiente:
Exponente 1 = 00000001, -1= 11111111. Pues los negativos en base 2 se representan en segundo
complemento.
Los negativos parecen mayores, para evitar esto se resta para que el exponente más negativo sea
00000001 y el positivo más grande 11111110.
Donde el valor del exponente se obtiene restando al número representado por los 8 bits (7 + el signo)
00000101 = 5 – 128 = -123
11111111 = 255 – 128 = 127
00000000= 0 – 128 = -128
El rango del exponente es -128 <= E <= 127
Nota: En la representación normalizada IEEE 754, se maneja exceso de 127 en números de 32
bits.
Doble precisión.
Se pueden usar números de doble precisión 8 bytes en lugar de 4, buscando minimizar el problema
de aproximación.
IEEE 754.
La representación normalizada son en:
Bit 31 30 … 23 22 … 0
Signo Exponente Mantisa
0+ con
1- exceso 127
10.5= 0 10000010 0101000000000…0
130 – 127=3 1.3125 x 23 = 10.5
1= 0 01111111 000000000000…0
127 – 127 = 0 1.0 x 20 = 1
20.5= 0 10000011 010010000…0
131-127=4 1.28125 x 24 = 20.5
Siguen el estándar IEEE 754
float double
Bits 32 64 80 128
Precisión (Mantisa) 24 53 64 113
Bit oculto si Si no si
Exceso 127 1023 16383 16383
Bit mantisa 23 52 64 112
Bits exponente 8 11 15 15
Rango mantisa +127 a -126 +1023 a -1022 +16383 a -16383 +16383 a -16383
Precisión (mantisa 7.22 15.95 19.26 34.01
entre log2(10))
- 10000110 = 2+4+128 = 134 - 127 = 7 exponente
111100011 = 1+2+32+64+128+256 = 483 x 2^-9 = 0.943359375
1.943359375x2^7 = -248.75
Selección adecuada de la estructura de datos.
✔ Los números de punto flotante están sujetos a una gran pérdida de precisión si las
operaciones involucran cantidades que no pueden expresarse como potencias de 2.
✔ Los números de punto flotante pueden representar más valores que los de tipo
entero.
✔ Las operaciones de punto flotante son más lentas que las de tipo entero.
✔ En algunos sistemas los enteros se pueden representar sin signo lo que incrementa
el rango.
✔ Los resultados de doble precisión no se redondean, se truncan.
✔ Debe evitarse en lo posible manejar potencias reales.
✔ Al asignar una variable real a una entera algunos sistemas truncan y otros redondean.
✔ Variables de precisión sencilla afectan a las de doble precisión si se mezclan.
Caracteres.
Para representar caracteres mediante bits se utilizan códigos de representación que establecen una
relación uno a uno entre los caracteres y los números enteros.
Ejemplos.
ASCII (American Standard Code for Information Interchange)
Standard 7 bits (128 caracteres) 2^7 = 128
Extendido 8 bits (256 caracteres) 2^8 = 256
Unicode 16 bits (65536 caracteres) Consortium Unicode. Formado por IBM, Microsoft, Apple, Xerox,
Sun, Digital, Novell, Adobe.
Versión 3 actualmente asignados 49,194 caracteres.
Unicode 3.0 tiene el equivalente como ISO 10646 de 32 bits (actualmente solo se usan 16 bits).
ISO 8859 formado por alfabetos del 1 al 15. De 16 bits, 8 en equivalencia con el ascii y los otros 8
cambian dependiendo del alfabeto.
El más usado es ISO 8859-1 Latin1 es el que nos corresponde.
UTF-8 código variable de 1 a 4 bits. Unicode Transformation Format, mapea matemáticamente
ASCII de 7 bits, ISO 8859-1, y UCS (ISO/IEC 10646-1 de 8, 16, 32 bits)
Cadenas. (strings)
Los caracteres se concatenan para formar cadenas o strings. Cada carácter se almacena
internamente en la representación simbólica usada por el sistema.
Notas:
Booleanos.
Almacena valores verdaderos y falsos. En la mayoría de los sistemas se manejan como constantes
enteras donde cualquier valor distinto de cero es verdadero.