Algoritmos y Estructura de

Datos I 2016
Algoritmos y Estructuras de Datos
I
Tema 1
Conceptos básicos
Objetivos del
tema:
• La informática como campo del conocimiento,
perfil de los profesionales, carreras de Informática,
estándares, acreditación
• Concepto de información e informatización
• Concepto codificación, bit y byte
• Sistemas numéricos, conversiones y operaciones.
Qué es la Informática?
Definición:
Informática abarca el “conjunto de conocimientos
científicos y técnicas que hacen posible el tratamiento
automático y racional de la información por medio de
computadoras”.

El término INFORMATICA, de origen francés, está

formado por la contracción de los vocablos:
INFORmación y autoMATICA
Qué es la Informática?
Términos significativos en la definición:

Racional

Automático

El objetivo marcado es el “tratamiento automático” de

la información y el medio utilizado “la computadora”.
 Qué es la Informática?
Para entender en qué consiste la Informática, es imprescindible
conocer:

• Características técnicas de las computadoras (hardware)

• Tipos de información y datos (sistemas de representación,
archivos y bases de datos).
• Los procesos y métodos aplicados a la información o datos
(programas).
• Los sistemas de comunicación (procesar la información a
distancia y compartirla de forma segura).
 La Informática como disciplina

Definición de la ACM y la IEEE:

La Computación como disciplina comprende el estudio
de procesos algorítmicos que describen y transforman a
la información; estudian su teoría, análisis, diseño,
eficiencia, implementación y aplicación.

La pregunta fundamental subyacente en toda la

computación es:
¿qué puede ser automatizado (en forma
eficiente)?
La Informática como disciplina

Computación? o Informática?
La Informática como disciplina

• Generalmente en países de lengua inglesa se utiliza

“Computing”, en otros países (Europa) se utiliza
“Informática”.
• Computación se relaciona con los procesos numéricos, lo
que sea computable, mediante el uso de una computadora.
• Mientras que Informática, está más relacionada con la
aplicación de las tecnologías de la computación.
• En esta asignatura ambos términos se consideran
equivalentes.
La Informática como disciplina
Dentro de la disciplina se identificas 9 subáreas de
conocimiento:
• Estructuras de Datos y Algoritmos
• Lenguajes de Programación
• Arquitectura
• Computación Numérica y Simbólica
• Sistemas Operativos
• Metodología e Ingeniería de Software
• Bases de Datos y búsqueda de Información
• Inteligencia Artificial y Robótica
• Comunicación Humano-Computadora
Conceptos importantes
Ciencia?
• Es el conocimiento que surge de la
investigación
• Se enfoca en el “por qué”
Técnica?
• Es la aplicación de los conocimientos a
productos concretos para mejorar la
calidad de vida de las personas y de la
sociedad en su conjunto
• Se enfoca en el “cómo hacer”
Algoritmos y Estructuras de Datos
I

Perfiles Profesionales en
Informática
Perfiles profesionales de la
disciplina Informática
Definición de la ACM Computing Curricula
Carreras de Informática a nivel nacional
- Acreditación
Desde el año 2009 se establecieron 5 “terminales”:
• Licenciatura en Ciencias de la Computación
• Licenciatura en Sistemas/Sistemas de Información
• Licenciatura en Informática
• Ingeniería en Computación
• Ingeniería en Sistemas de Información /Informática
• un Núcleo Curricular Básico (NCB) común a todas y
• un Núcleo Curricular Específico (NCE) propio de cada línea.
Carreras de Informática a nivel
nacional
Nuestra Licenciatura tiene:
• Núcleo Curricular Básico (NCB), los temas comunes a todas
las líneas: Ciencias Básicas; Teoría de Computación;
Algoritmos y Lenguajes; Arquitectura, Sistemas Operativos
y Redes.
• Núcleo Curricular Específico (NCE) que enfatizará los temas
de Ingeniería del Software, Bases de Datos y Sistemas de
Información.
• Para más información sobre este tema consultar la página de
la Red UNCI: http://redunci.info.unlp.edu.ar
 Esquema Plan de estudio LSI 2009
Algebra Algoritmos y Organización y Sistemas y
Estructuras de Arquitectura de Organizaciones
Lógica y datos I y II Computadoras
Matemática
Computacional Paradigmas y Sistemas Administración y
lenguajes Operativos Gestión de
Calculo Dif e Organizaciones
Integral Programación
Orientada a Comunicaciones de
Objetos Datos
Probabilidad y
Estadistica

Bases de Datos I Taller de Programación Ingeniería de

I y II Software I

Analista Programador Universitario

Bases de Datos II Redes de Datos Ingeniería de

Software II Auditoría y Seg.
Teoría de la Informática
Computación

Métodos Proyecto Final de Optativa III: Ing. Economía

Computacionales Carrera de Software II Aplicada

Optativa I Optativa II
Métodos Internetworking
Computacionales
Licenciado en Sistemas de Información
Algoritmos y Estructuras de Datos
I
Tema 1
Concepto básicos: Información, dato,
importancia de la información como
apoyo a las decisiones
A qué se llama Información?

Es un término quetiene muchos significados de

acuerdo al contexto
1. “Comunicación o adquisición de conocimientos
que permiten ampliar o precisar los que se
poseen sobre una materia determinada”.
2. ”Conjunto de símbolos con los que se
representan convencionalmente hechos, objetos
e ideas”.
 A qué se llama Información?

El resultado del procesamiento constituye una información que

aporta al conocimiento.
A qué se llama Dato?
 Dato es cualquier conjunto de caracteres que
representan hechos o cosas del mundo real.
 Carácter es cualquier símbolo numérico, alfabético o
especial que se emplea en la escritura y en el cálculo:
Ejemplo de datos: Nº celular, tamaño de una imagen, dirección
postal, fecha de nacimiento, PBI, etc.
Por qué la necesidad de
información?
Recordemos! En Informática, el término
INFORMACION tiene un significado amplio y otro más
específico.
• Conjunto de símbolos con los que se representan
hechos, objetos e ideas.

• Conocimiento derivado del análisis o tratamiento

de los datos.

Este conocimiento o información se utiliza para tomar

decisiones con vistas a un accionar concreto
 Ejemplo: Ingresantes a la UNNE 2015

Cómo aporta esta información a las decisiones que se toman

para promover la formación de determinados perfiles
profesionales?
Por qué se automatiza el tratamiento de la
información?

• Funciones que el hombre por sí solo no puede

realizar
• Funciones que demandan mucho tiempo.
• Seguridad en la ejecución
• La sustitución del hombre en tareas monótonas
Algoritmos y Estructuras de Datos
I

Tema 1
Codificación, bit, byte, unidades de
medida de la información
almacenada
 Codificación de la información
• Codificación es una transformación que representa los
elementos de un conjunto mediante los de otro, de
forma tal que a cada elemento del primer conjunto le
corresponda un elemento distinto del segundo.
• Los códigos permiten comprimir y estructurar la
información
Ejemplos:
F-Femenino M-masculino
201-Corrientes; 202-Goya…
 Concepto de bit y byte

• En el interior de las computadoras la información se

representa mediante 1 y 0.
• La computadora sólo es capaz de procesar la información
representada en bits.
• Un bit o dígito binario, es la unidad más pequeña de
información que puede procesar una computadora.
• El bit se asocia a los valores: 0 ó 1
Concepto de bit y byte

1 bit permite codificar 2 mensajes.

Por ejemplo: APAGADO o PRENDIDO

0
Concepto de bit y byte

Dos bombillas permiten representar 4 estados diferentes:

00 (las 2 apagadas),
01 (1 apagada y 1 prendida)
01 (1 prendida y 1 apagada)
11 (las 2 prendidas)
Concepto de bit y byte

3 bombillas permiten representar 8

combinaciones diferentes
Concepto de byte

Un byte es un grupo de bits que constituye una unidad

lógica.
Por ejemplo, con 8 bits se puede representar 256
caracteres diferentes (letras, números, símbolos
especiales)
Concepto de byte

Ejemplo: Representación de la letra “A” en

ASCII
 Que representan los bits?
En el interior de las computadoras, la información se almacena y se
transfiere de un sitio a otro según un código que utiliza sólo dos
valores (un código binario) representado por 0 y 1.
 Unidades de medida de la información
almacenada
MEDIDA EQUIVALENCIA EJEMPLOS

1 Byte 8 bits Una letra, un número

1 Kilobyte (KB) 1024 bytes = 210 bytes Un archivo de texto, 20 KB

1024 KB = 220 bytes = 1.048.576 Un archivo mp3, 3 MB
1 Megabyte (MB)
bytes
1024 MB = 230 bytes = una película en DivX, 1 GB
1 Gigabyte (GB)
1.073.741.824 bytes
1 Terabyte (TB) 1024 GB = 240 bytes 800 películas, 1 TB

En diciembre de 2007, YouTube tuvo

1 Petabyte (PB) 1024 TB = 250 bytes
un tráfico de 27 PB
Internet ocupa entre 100 y 300 EB
1 Exabyte (EB) 1024 PB = 2 60 bytes

1 Zettabyte (ZB) 1024 PB = 2 70 bytes Información de datacenters

1 YottaBytes 1024 PB = 2 80 bytes Información de datacenters

Unidades de medida de la información
almacenada
Conversión de unidades de medida
 Conversión de unidades de medida de
la información

Por qué 1024?

1024 = 210

Convertir:
a. 3 MB a KB A trabajar!!
b. 3500000 bytes a MB
c. 600000 bits a KB
Sistemas numéricos,
conversiones y
operaciones

42
 Sistemas de Numeración
• El estudio de las computadoras y del procesamiento de datos
requiere algún conocimiento de los sistemas numéricos, ya que
estos constituyen la base de todas las operaciones de una
computadora.
• Los sistemas numéricos difieren en cuanto a la disposición y al
tipo de los símbolos que utilizan.
• Se analizarán los sistemas:
• Decimal
• Binario
• Hexadecimal

43
Posiciones de valor relativo
Un sistema de numeración en base b utiliza para representar los
números un alfabeto compuesto por b símbolos.

Así todo número se expresa por un conjunto de cifras,

contribuyendo cada una de ellas con un valor que depende de:

• La cifra en sí  “valor absoluto”

• La posición que ocupe dentro del número  “valor posicional”

La posición del dígito del extremo derecho es la de menor valor, y

el dígito que la ocupa se denomina "dígito menos significativo".

44
 Posiciones de valor relativo
• Aunque su valor es evidente, la notación 6.954 significa en
realidad:
6000 + 900 + 50 + 4 = 6.954
• Cualquier entero positivo n que se representa en el sistema
decimal como una cadena de dígitos decimales, puede expresarse
también como una suma de potencias de diez ponderada por un
dígito.
6.954 =
6 x 103 + 9 x 102 + 5 x 101 + 4 x 100 =
6 x 1000 + 9 x 100 + 5 x 10 + 4 x 1
Notación expandida para el entero

45
 Posiciones de valor relativo

• Cualquier valor fraccionario m, representado en el sistema

decimal por una cadena de dígitos decimales junto con un punto
decimal intercalado, puede expresarse también en notación
expandida usando potencias negativas de 10.
• El valor posicional de los dígitos a la derecha del punto decimal
es, respectivamente:

1 1 2 1 1
10  10  10
3

10 100 1000

46
 Posiciones de valor relativo
Ejemplo: el número decimal 3.278,52 puede obtenerse como suma
de:
3.000
200
70
8
0,5
0,02
3.278,52
es decir, se verifica:
3.278,52 = 3x103 + 2x102 + 7x101 + 8x100 + 5x10-1 + 2x10-2

Cada posición tiene un peso y un nombre específicos.

47
Posiciones de valor relativo
• El sistema de posiciones de valor relativo no es posible
sin el 0. Su presencia en un número significa que la
potencia de la base representada por la posición del
dígito 0 no se utiliza.
• El número decimal 8.003 significa:

8 x 10 3 + 0 x 102 + 0 x 101 + 3 x 100 =

8 x 1000 + 0 x 100 + 0 x 10 + 3x1 =
8.000 + 0 + 0 + 3 = 8.003

48
Sistema Decimal
• El factor más importante en el desarrollo de la
ciencia y la matemática fue la invención del sistema
decimal.
• Este sistema utiliza diez símbolos: 0, 1, 2, 3, 4, 5, 6,
7, 8, 9, denominados generalmente "cifras
decimales".

• La base de este sistema es b = 10.

49
Sistema Binario
• Usa dos símbolos diferentes: 0 y 1 denominados bits.
• La base de este sistema es b = 2.
• El valor relativo de los dígitos binarios a la izquierda del dígito
menos significativo aumenta en una potencia de dos cada vez.
• Los valores de posición de la parte entera de un número
binario son las potencias positivas de dos:
24 23 22 21 20 (de derecha a izquierda)
• Y los valores de posición de la parte fraccionaria de un número
binario son las potencias negativas de dos:
2-1 2-2 2-3 2-4 (de izquierda a derecha)

50
Sistema Binario

Ejemplo: el número binario 101101,11 significa:

101101,11 = 1x25 + 0x24 + 1x23 + 1x22 + 0x21 +1x20 +

1x2-1 + 1x2-2 =
= 1x32 + 0 + 1x8 + 1x4 + 0 +1x1 + 1x0,5 +
1x0,25 =
= 45,75 (en el sistema decimal)

51
Sistema Hexadecimal

• Los números binarios de gran magnitud consisten en

largas series de ceros y unos, que son difíciles de
interpretar y manejar.

• Como un medio conveniente para representar esos

números binarios de gran magnitud se utiliza el sistema
numérico hexadecimal, de base b = 16.

• Utiliza 16 símbolos diferentes:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

• Cada dígito hexadecimal representa cuatro dígitos

binarios.

52
Sistema Hexadecimal

Ejemplo: el número hexadecimal 2CA

es igual a:

2CA = 2x162 + 12x161 + 10x160

= 2x256 + 12x16 + 10x1
= 512 + 192 + 10
= 714 (en el sistema decimal)
53
Tabla de equivalencia entre los sistemas numéricos
Decimal Hexadecimal Binario
0 0 0000
1 1 0001
2 2 0010
3 3 0011
4 4 0100
5 5 0101
6 6 0110
7 7 0111
8 8 1000
9 9 1001
10 A 1010
11 B 1011
12 C 1100
13 D 1101
14 E 1110
15 F 1111 54
Teorema fundamental de la Numeración
Una determinada cantidad, que denominaremos número
decimal (N en este caso), se puede expresar de la siguiente
manera:

n
N  (digito ) * (base)
i  d
i
i

Base = 10
i = posición respecto de la coma
d = nro. de dígitos a la derecha de la coma
n = nro. de dígitos a la izquierda de la coma, menos 1
dígito = cada uno de los que componen el número

55
Teorema fundamental de la Numeración

El Teorema Fundamental de la Numeración relaciona una

cantidad expresada en cualquier sistema de numeración, con la
misma cantidad expresada en el sistema decimal:
...+ X4* B4 + X3* B3 + X2* B2 + X1* B1 + X0* B0
+ X-1* B-1 + X-2* B-2 + X-3* B-3 + X-4* B-4 + .......

Ejemplo: 201,1 número en base 3.

¿Cuál será la representación de la misma cantidad en el sistema
decimal?
201,1 = 2x32 + 0x31 + 1x30 + 1x3-1
= 19,33
56
 Conversiones entre los distintos sistemas

• BINARIO a DECIMAL: Se suman los productos de todos

los valores posicionales por el número que ocupa la
posición.
Ej. Número Binario:
1 1 0 1, 0 1
1x23 + 1x22 + 0x21 + 1x20 + 0x2-1 + 1x2-2
8 4 0 1 1 0,25 =13,2510

El valor posicional es la base del sistema elevada al número

de la posición que ocupa el numero.

57
 Conversiones entre los distintos sistemas

• HEXADECIMAL a DECIMAL: Se multiplica el número

representado por el valor posicional que le corresponde, y
se suman los resultados .
Ej. Número Hexadecimal:
A E 1 B
= 10x163 + 14x162 +1 x161 + 11x160
= 40960 + 3584 + 16 + 11
= 44571 (decimal)

58
 Conversiones entre los distintos sistemas

• DECIMAL a BINARIO: Se divide el número que se quiere

convertir por la base del sistema al que se quiere cambiar.
• Los resultados que se obtengan en el cociente deben seguir
dividiéndose hasta que este resultado sea menor que la
base.
• Los restos que resulten de todas las divisiones se escribirán
de derecha a izquierda, comenzando con el ultimo cociente.
26 2
Ej. Número Decimal: 26 0 13 2
1 6 2
0 3 2
Con lo que: 26(10 = 11010(2
1 1

59
 Conversiones entre los distintos sistemas
• DECIMAL a BINARIO (cont.):
Parte fraccionaria: Algoritmo Parte Entera:
Para convertir N = (0,5821)10 en su equivalente binario multiplique N y
cada parte fraccionaria sucesiva por la base (2 en este caso), observando
la parte entera del producto, como sigue:
Multiplicaciones Partes enteras
0,5821 x 2 = 1,1642 1
0,1642 x 2 = 0,3284 0
0,3284 x 2 = 0,6568 0
0,6568 x 2 = 1,3136 1
0,3136 x 2 = 0,6272 0
La parte entera de cualquier producto puede ser solo cero o uno; ya que se
multiplican por 2 los números que son menores que uno. La sucesión de
dígitos partes enteras de arriba hacia abajo, da el equivalente binario
requerido. N = 0,5821 es equivalente a 0,10010 (2 (aproximadamente)

60
 Conversiones entre los distintos sistemas
• DECIMAL a HEXADECIMAL: Se divide el número que se quiere convertir
por la base del sistema al que se quiere cambiar. En este caso 16.
• Los resultados que se obtengan en el cociente deben seguir
dividiéndose hasta que este resultado sea menor que la base.
• Para convertir una fracción decimal a su equivalente hexadecimal,
aplicamos el algoritmo parte entera, con base 16.

Ej. Número Decimal : 1520

1520 16
Con lo que: 1520(10 = 5F0(16 080 95 16
0 15 5

61
 Conversiones entre los distintos sistemas
• BINARIO a HEXADECIMAL: se divide el número binario en grupos de cuatro
dígitos binarios, comenzando desde la derecha y se reemplaza cada grupo
por el correspondiente símbolo hexadecimal.
• Si el grupo de la extrema izquierda no tiene cuatro dígitos, se deben
agregar ceros hasta completar 4 dígitos.

Ej. Número Binario: 111110011011010011

= 0011 / 1110 / 0110 / 1101 / 0011
= 3 E 6 D 3
= 3E6D3 (hexadecimal)

62
 Conversiones entre los distintos sistemas
• HEXADECIMAL a BINARIO :
• Se reemplaza cada símbolo hexadecimal por el correspondiente grupo de
cuatro dígitos binarios y se descartan los ceros innecesarios.

Ej. Número Hexadecimal: 6 C 4 F 2 E

= 0110 / 1100 / 0100 / 1111 / 0010 / 1110
= 11011000100111100101110 (binario)

63
Operaciones Aritméticas
• SUMA BINARIA: Para poder efectuar operaciones aritméticas con
números de cualquier otra base se utilizan las reglas de la aritmética
decimal.

• Las reglas de la suma binaria son las siguientes:

• 0+0=0
• 0+1=1
• 1+0=1
• 1 + 1 = 10 (Con acarreo de un 1)
• 1 + 1 + 1 = 11 (Con acarreo de un 1)
11
Ejemplos: 101010 111
+ 001001 + 11
110011 1010

64
Operaciones Aritméticas
• RESTA BINARIA:
• Las cuatro reglas básicas para la resta de números binarios son:
0-0=0 1

1-1=0
1-0=1
0 – 1 = (con acarreo negativo de 1), es decir 10 - 1 = 1
Por ejemplo, restemos 101 – 011:
1 0 1
• En la columna derecha se realiza la resta de 1 – 1 = 0 – 0 1 1
0 1 0
• En la columna central hay que tomar prestado un 1 de columna a la izquierda, la cual
queda en 0 y da lugar a 10 en la columna central, luego 10 -1 = 1
• En la columna izquierda, se resta 0 – 0 = 0

65
 Resta binaria por complemento
• Es el método más eficiente para realizar sustracciones.
• Consiste en sumar al minuendo el complemento del sustraendo.
• Luego, la unidad que excede la longitud del minuendo se elimina de la
izquierda y se suma a la cifra de las unidades.

Ejemplo:
1011  Minuendo
- 101  Sustraendo

66
Resta binaria por complemento
• Los pasos a seguir son los siguientes:
a- Si la cantidad de dígitos del sustraendo es menor que la del minuendo se
completa el sustraendo con ceros a la izquierda de la parte entera, y a la
derecha de la parte decimal (encolumnar por la coma).
b- Se halla el complemento del sustraendo, restando el sustraendo del
máximo valor binario con la misma longitud que el minuendo.

1111
- 0101
1 0 1 0 Complemento del Sustraendo

67
 Resta binaria por complemento
c- Se suma al minuendo el complemento del sustraendo.
1 0 1 1 MINUENDO
+ 1 0 1 0 COMPLEMENTO DEL SUSTRAENDO
10101

d- Se elimina el 1 de la izquierda y se suma encolumnado con

el último dígito de la cifra, sin importar la coma decimal.
1011
Prueba:
+ 1010
101  Sustraendo
10101
+ 110  Resultado
+ 1
1011  Minuendo
0 1 1 0  Resultado
Un modo de controlar el resultado es sumar el mismo al sustraendo,
debiendo obtenerse el minuendo.

68
 Operaciones Aritméticas

• SUMA HEXADECIMAL: Sigue las mismas reglas que la suma

decimal y binaria.
• Cada vez que la suma de dos dígitos sobrepasa F (el símbolo
hexadecimal de mayor valor), se genera el acarreo de un 1 hacia
la posición de dígito inmediatamente superior.

69
 Operaciones Aritméticas

• Ejemplos de suma hexadecimal:

11
9654 6AE
+ 4528 + 1FA
DB7C 8A8

1 11
8F97,F
+ D44C,F9E
163E4,E9E

70
Operaciones Aritméticas
• Resta hexadecimal:

7 9 16+8
8 A 8 minuendo
- 1 F A sustraendo
6 A E
1. En la columna de las unidades, como 8 es menor que A se pide una
unidad (16) al número de al lado:
2. 16 + 8 = 24, 24 – A = 24 – 10 = 14 = E
3. En la columna de las decenas, 9 es menor que F, entonces se pide una
unidad:
4. 9 + 16 = 25, 25 – F = 25 – 15 = 10 = A
5. En la columna de las centenas: 7 – 1 = 6

71
Resta hexadecimal por complemento
• Se siguen los mismos pasos que los descriptos para la resta binaria:
Ejemplo:
8 E A D, 0 1  minuendo
- 3 B E 5  sustraendo

a- Determinación del complemento: se resta el sustraendo del máximo valor

hexadecimal que es FFFF,FF.
F F F F, F F
- 3 B E 5, 0 0
C 4 1 A, F F
No olvidar completar con ceros el sustraendo, para obtener la misma cantidad de dígitos
que el minuendo, encolumnando por la coma decimal.

72
 Resta hexadecimal por complemento
(continuación)
b- Suma del complemento del sustraendo al minuendo:
8 E A D, 0 1  Minuendo
+ C 4 1 A, F F  Complemento del sustraendo
1 5 2 C 8, 0 0

c- Se elimina el 1 de la izquierda y se suma al último dígito, sin importar la

coma decimal.
8 E A D, 0 1
+ C 4 1 A, F F
1 5 2 C 8, 0 0
+ 1
5 2 C 8, 0 1  Resultado

Para realizar la comprobación, se puede proceder de igual

manera que en la resta binaria.
73
Ejercitación