Informatica (1).pdf

Cristobal ParejaAngel Andeyro

Manuel Ojeda

Introduccion a la Informatica

I. Aspectos generales

1a Edicion

Febrero 1994

c Cristobal ParejaAngel Andeyro

Manuel Ojeda

ISBN: 84-7491-489-2

Deposito Legal: M-7713-94

Indice General

Presentacion 11

1 Conceptos Basicos 171.1 Informatica . . . . . . . . . . . . . . . . . . . . . . . . . . 171.2 Computador . . . . . . . . . . . . . . . . . . . . . . . . . . 181.3 Sistema operativo . . . . . . . . . . . . . . . . . . . . . . . 191.4 Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . 201.5 Algoritmos y programas . . . . . . . . . . . . . . . . . . . 21

1.5.1 Algoritmos . . . . . . . . . . . . . . . . . . . . . . 221.5.2 Programacion . . . . . . . . . . . . . . . . . . . . . 241.5.3 Lenguajes de Programacion . . . . . . . . . . . . . 25

1.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . 271.7 Comentarios bibliogracos . . . . . . . . . . . . . . . . . . 28

2 Representacion de la informacion 292.1 Conceptos previos . . . . . . . . . . . . . . . . . . . . . . 29

2.1.1 Informacion analogica y digital . . . . . . . . . . . 292.1.2 Unidades de informacion en los sistemas digitales . 302.1.3 Sistemas de numeracion posicionales . . . . . . . . 31

2.2 Representacion digital de los datos . . . . . . . . . . . . . 352.2.1 Representacion de los numeros enteros . . . . . . . 352.2.2 Representacion de los numeros reales . . . . . . . . 392.2.3 Limitaciones de los sistemas de representacion di-

gital de los numeros . . . . . . . . . . . . . . . . . 422.2.4 Representacion de los caracteres . . . . . . . . . . 462.2.5 Organizacion de datos mas complejos . . . . . . . 47

6 Indice general

2.2.6 Representacion de las instrucciones . . . . . . . . . 482.3 Codigos redundantes . . . . . . . . . . . . . . . . . . . . . 49

2.3.1 Informacion y redundancia . . . . . . . . . . . . . 492.3.2 Codigos solo autodetectores: p de n . . . . . . . . 512.3.3 Codigos autocorrectores: Hamming . . . . . . . . . 51


3 Estructura fsica de un computador 593.1 Componentes de un computador . . . . . . . . . . . . . . 60

3.1.1 Memoria principal . . . . . . . . . . . . . . . . . . 623.1.2 Unidad central de proceso . . . . . . . . . . . . . . 673.1.3 Perifericos . . . . . . . . . . . . . . . . . . . . . . . 703.1.4 Buses de comunicacion . . . . . . . . . . . . . . . . 74

3.2 Lenguajes de maquina . . . . . . . . . . . . . . . . . . . . 773.2.1 Formato de las instrucciones . . . . . . . . . . . . 783.2.2 Tipos de Instrucciones . . . . . . . . . . . . . . . . 79

3.3 Un ejemplo de recapitulacion . . . . . . . . . . . . . . . . 803.3.1 UCP con acumulador . . . . . . . . . . . . . . . . 813.3.2 Un juego de instrucciones de maquina de una di-

reccion . . . . . . . . . . . . . . . . . . . . . . . . . 823.3.3 Ejecucion de una instruccion. Detalle . . . . . . . 843.3.4 Traduccion y ejecucion de un programa sencillo . . 85

3.4 Observaciones complementarias . . . . . . . . . . . . . . . 883.4.1 Tipos de direccionamiento . . . . . . . . . . . . . . 893.4.2 Subrutinas . . . . . . . . . . . . . . . . . . . . . . 913.4.3 Interrupciones . . . . . . . . . . . . . . . . . . . . 94

3.5 Otras arquitecturas . . . . . . . . . . . . . . . . . . . . . . 953.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . 983.7 Comentarios bibliogracos . . . . . . . . . . . . . . . . . . 99

4 Sistemas Operativos 1014.1 Cometido de un sistema operativo . . . . . . . . . . . . . 102

4.1.1 Funciones de los sistemas operativos . . . . . . . . 1024.1.2 Formas de trabajo de los sistemas operativos . . . 103

4.2 Conceptos basicos de los sistemas operativos . . . . . . . . 105

Indice general 7

4.2.1 Procesos . . . . . . . . . . . . . . . . . . . . . . . . 1054.2.2 Archivos . . . . . . . . . . . . . . . . . . . . . . . . 1064.2.3 Nucleo . . . . . . . . . . . . . . . . . . . . . . . . . 1094.2.4 Multiprogramacion . . . . . . . . . . . . . . . . . . 1104.2.5 Interfaz de usuario . . . . . . . . . . . . . . . . . . 1114.2.6 Gestion de la memoria . . . . . . . . . . . . . . . . 112

4.3 Clasicacion de los sistemas operativos . . . . . . . . . . . 1164.4 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . 1174.5 Comentarios bibliogracos . . . . . . . . . . . . . . . . . . 117

5 Lenguajes de programacion 1195.1 Lenguajes de bajo y alto nivel . . . . . . . . . . . . . . . . 120

5.1.1 Lenguajes orientados a la maquina . . . . . . . . . 1205.1.2 Lenguajes de alto nivel . . . . . . . . . . . . . . . . 1225.1.3 Paradigmas de programacion . . . . . . . . . . . . 124

5.2 Descripcion de los lenguajes de programacion . . . . . . . 1315.2.1 Sintaxis . . . . . . . . . . . . . . . . . . . . . . . . 1315.2.2 Semantica . . . . . . . . . . . . . . . . . . . . . . . 137

5.3 Procesadores de lenguajes . . . . . . . . . . . . . . . . . . 1415.3.1 Compiladores e interpretes . . . . . . . . . . . . . 1445.3.2 Entornos de programacion . . . . . . . . . . . . . . 144


6 Bases de datos 1516.1 Bases de datos y SGBD . . . . . . . . . . . . . . . . . . . 151

6.1.1 Archivos y SGA . . . . . . . . . . . . . . . . . . . 1516.1.2 Bases de datos y SGBD . . . . . . . . . . . . . . . 1526.1.3 Niveles de una base de datos . . . . . . . . . . . . 154

6.2 El modelo entidad-relacion . . . . . . . . . . . . . . . . . . 1556.3 Modelos de datos basados en registros . . . . . . . . . . . 158

6.3.1 El modelo relacional . . . . . . . . . . . . . . . . . 1586.4 Lenguajes asociados a los SGBD . . . . . . . . . . . . . . 160

6.4.1 Lenguajes relacionales . . . . . . . . . . . . . . . . 1616.5 Elementos de un SGBD . . . . . . . . . . . . . . . . . . . 1636.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

8 Indice general

6.7 Comentarios bibliogracos . . . . . . . . . . . . . . . . . . 165

7 Historia de los instrumentos de calculo 1677.1 Precursores de los computadores digitales . . . . . . . . . 167

7.1.1 La antiguedad . . . . . . . . . . . . . . . . . . . . 1677.1.2 Antecedentes del calculo mecanico . . . . . . . . . 1687.1.3 La maquina de Pascal . . . . . . . . . . . . . . . . 1687.1.4 La maquina de Babbage . . . . . . . . . . . . . . . 1697.1.5 La tabulacion mecanica . . . . . . . . . . . . . . . 170

7.2 Nacimiento de los computadores . . . . . . . . . . . . . . 1717.2.1 El modelo de von Neumann . . . . . . . . . . . . . 1727.2.2 Generaciones tecnologicas . . . . . . . . . . . . . . 172

7.3 Evolucion de los lenguajes y de la metodologa . . . . . . 1757.4 Tecnologa actual, tendencias y perspectivas . . . . . . . . 176

7.4.1 Inteligencia articial . . . . . . . . . . . . . . . . . 1787.4.2 Las comunicaciones . . . . . . . . . . . . . . . . . . 178

7.5 Comentarios bibliogracos . . . . . . . . . . . . . . . . . . 179

A Introduccion al DOS 181A.1 Organizacion de recursos . . . . . . . . . . . . . . . . . . . 182

A.1.1 Principales dispositivos . . . . . . . . . . . . . . . 182A.1.2 Archivos . . . . . . . . . . . . . . . . . . . . . . . . 182A.1.3 Directorios . . . . . . . . . . . . . . . . . . . . . . 184A.1.4 Prompt . . . . . . . . . . . . . . . . . . . . . . . . 187

A.2 Ordenes del DOS . . . . . . . . . . . . . . . . . . . . . . . 187A.2.1 Ordenes basicas . . . . . . . . . . . . . . . . . . . . 190A.2.2 Manejo de archivos . . . . . . . . . . . . . . . . . . 191A.2.3 Manejo de directorios . . . . . . . . . . . . . . . . 193A.2.4 Indicadores del sistema . . . . . . . . . . . . . . . 194A.2.5 Procesamiento por lotes . . . . . . . . . . . . . . . 195

A.3 Conguracion del DOS . . . . . . . . . . . . . . . . . . . . 195A.4 Otros aspectos de interes . . . . . . . . . . . . . . . . . . . 198

A.4.1 Encauzamiento: tubos y demas . . . . . . . . . . . 198A.4.2 Atributos y proteccion de archivos . . . . . . . . . 201A.4.3 Ampliaciones de la memoria en los PCs . . . . . . 201

Indice general 9

B Introduccion a UNIX 205B.1 Breve descripcion tecnica . . . . . . . . . . . . . . . . . . 205B.2 Una sesion con UNIX . . . . . . . . . . . . . . . . . . . . 207B.3 Gestion de archivos . . . . . . . . . . . . . . . . . . . . . . 208

B.3.1 Identicadores . . . . . . . . . . . . . . . . . . . . 209B.3.2 Tipos de archivos en UNIX . . . . . . . . . . . . . 209B.3.3 Permisos asociados con un archivo . . . . . . . . . 210B.3.4 Ordenes para la gestion de archivos . . . . . . . . . 211

B.4 El shell de UNIX . . . . . . . . . . . . . . . . . . . . . . . 212B.4.1 Encauzamiento de la entrada y salida . . . . . . . 213B.4.2 Caracteres comodn . . . . . . . . . . . . . . . . . 213B.4.3 Guiones de shell . . . . . . . . . . . . . . . . . . . 214

B.5 UNIX como sistema multitarea . . . . . . . . . . . . . . . 214B.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . 216B.7 Prontuario de comandos UNIX . . . . . . . . . . . . . . . 216B.8 Diferencias entre DOS y UNIX . . . . . . . . . . . . . . . 221

Bibliografa 223

Indice alfabetico 228

Presentacion

Hay muchos y excelentes libros sobre informatica en un nivel intro-ductorio, con diversos enfoques y escritos en nuestra lengua. Muchos deellos estan dirigidos a futuros informaticos, por lo que resultan, quiza,demasiado profundos para quienes solo persiguen aplicar la informaticaen su trabajo; muchos otros, en cambio, se dirigen a no profesionales,por lo que ofrecen una vision panoramica demasiado general de diver-sos aspectos de la informatica, sin detenerse a analizar las implicacionespracticas de esos aspectos.

Este libro se situa entre ambos extremos, ofreciendo un medio paraintroducir en la informatica a profesionales de otros campos que, sin em-bargo, necesiten aplicar adecuadamente los computadores en su trabajo,poniendo en marcha programas de aplicacion o manejando bancos dedatos e incluso, muchas veces, resolviendo por s mismos problemas nocontemplados en los programas comercializados.

As pues, el contenido del texto incluye los temas que consideramosbasicos para una introduccion practica a la informatica. Quiza sea esteenfoque practico lo que mejor distinga a este texto de otros de intro-duccion a la informatica, que adolecen muchas veces de contenidos muyextensos y teoricos, casi enciclopedicos, en los que es difcil diferenciarlos conocimientos utiles en general de aquellos que solo encontraran deutilidad informaticos profesionales.

Por lo tanto, este libro se dirige a quienes necesiten una formacionintroductoria en informatica, con un enfoque basico y practico, pero rigu-roso. Entre ellos se encuentran, en primer lugar, todos aquellos alumnos

12 Presentacion

de los primeros cursos universitarios que cuenten con asignaturas sobreinformatica, tanto si se utiliza como herramienta aplicada a la resolucionde problemas como si es el propio objeto de estudio.

Este libro se dirige asimismo a aquellas personas que, de una u otraforma, estan relacionadas con el mundo de la informatica (operadores,comerciales, empresarios, etc.) y, sin embargo, ignoran lo que se escondetras la fachada de un computador (como se almacena la informacion,cuales son los procesos que se estan ejecutando en su interior, etc.) yque utilizan una jerga tecnica sin entender bien de que hablan.

Por ultimo, este libro se dirige tambien a todos los usuarios de com-putadores que esten interesados en conocer mejor su herramienta detrabajo, en saber que estan haciendo y por que lo hacen. El desarrolloy abaratamiento de los sistemas informaticos hace que computadoresde gran potencia que antes solo se encontraban en grandes centros decalculo, atendidos por administradores de sistemas cualicados y dedi-cados por completo a dicha tarea, esten hoy sobre nuestra mesa, y que elusuario se tenga que encargar de administrar los recursos de su computa-dor, por ejemplo, gestionando la memoria, haciendo copias de seguridad,eliminando virus, etc. Por todo ello, cualquier usuario debera dedicarsiquiera una peque~na parte de su tiempo a conocer los principios basicosde funcionamiento y gestion de su computador.

A todos ellos, este texto les ofrece la posibilidad de adquirir esosconocimientos, partiendo de cero, o de actualizarlos.

Se ha seleccionado el contenido partiendo de las directrices se~naladasen [DCG*89] y [ACM91] aunque, en un nivel introductorio, no sea po-sible ni deseable abarcar todos los temas que solo interesan al futuroprofesional de la informatica. As por ejemplo, quedan completamentefuera del alcance de nuestro texto las areas de inteligencia articial yrobotica (AI) o la comunicacion hombre-maquina (HU).

Es frecuente, en cambio, que los destinatarios mencionados necesi-ten una parte de conocimientos generales sobre informatica y otra sobredesarrollo de algoritmos en un lenguaje de alto nivel: ambas partes se in-cluyen en los programas de asignaturas de introduccion a la informatica

Presentacion 13

de los primeros cursos universitarios, y tambien interesan esas dos par-tes a los profesionales que usen la informatica como una herramienta ydeseen sacar partido de ella.

El presente texto comprende dos volumenes, complementarios, dedi-cados respectivamente a esas dos partes, separando as la presentacionde los conceptos generales y el desarrollo y organizacion de algoritmosy estructuras de datos. En la primera parte, el enfoque practico nosha llevado a relacionar los contenidos estudiados con sus repercusionespracticas o su utilizacion. En la segunda, se ha unicado el estudio delos algoritmos con su desarrollo, haciendo uso de un lenguaje de progra-macion concreto.

Este primer volumen se ha dividido en siete captulos, de los cua-les el primero ofrece una vision panoramica de la informatica, de loscomputadores y de su uso en la actualidad: bien poniendo en marchaaplicaciones ya desarrolladas y adaptandolas a nuestras necesidades, opreparando soluciones para problemas nuevos. Se presentan asimismolas primeras aproximaciones a los conceptos de algoritmo, programaciony lenguajes de programacion.

En el captulo 2 se aborda la representacion digital de la informacion.Conociendo las distintas formas de representacion, el programador podraelegir las mas apropiadas a las caractersticas y naturaleza de su pro-blema y prever sus limitaciones. Por otra parte, el usuario de aplicacio-nes tendra una idea aproximada de como se almacena su informacion, elespacio que ocupa y las circunstancias en que los resultados podran noser del todo ables.

El captulo 3 esta dedicado al aspecto fsico de los computadores ysus perifericos. Se explica su funcionamiento introduciendo los lenguajesde bajo nivel, y se comentan brevemente las arquitecturas orientadas alprocesamiento en paralelo.

En el captulo 4 se estudian los conceptos basicos para entender loque son los sistemas operativos, cuales son sus funciones y como lasllevan a cabo.

El captulo 5 se dedica a los lenguajes de programacion, en espe-

14 Presentacion

cial los lenguajes evolucionados. Se tratan distintos modelos de progra-macion, ademas del imperativo, de amplia difusion en estos a~nos. Seintroducen los metalenguajes para describir su sintaxis por su utilidad,tanto a programadores como a simples usuarios de sistemas operativos,incluso en el nivel de los comandos. Finalmente, se estudian los distintostipos de traductores y los entornos de programacion.

El captulo 6 trata sobre las bases de datos, una de las aplicacionesde mayor aplicacion en el mundo empresarial. Entre los modelos des-arrollados, destacamos el relacional y, entre los lenguajes de consulta, elSQL, debido a la extensa difusion de ambos en la actualidad.

Hemos dedicado el captulo 7 a los orgenes, estado actual y pers-pectivas de futuro de la informatica. Aunque muchos textos situan estetema al principio, hemos preferido estudiarlo una vez que se conocenlos conceptos y la terminologa basicos. De esta forma mejora la com-prension del captulo y puede valorarse en su justa medida cada uno delos logros historicos que en el se recogen.

Debido al enfoque practico que perseguimos con este libro, se inclu-yen dos apendices dedicados a introducir en el manejo de dos sistemasoperativos concretos de gran difusion en la actualidad: el DOS y elUNIX. El hecho de traer aqu estos anexos responde a dos razones: porun lado, conocer las caractersticas de cada sistema interesa al estudiantecomo un ejemplo particular del captulo 4, permitiendo ver como se llevaa la practica lo estudiado en la teora; por otro, siempre resulta de uti-lidad al principiante disponer de un peque~no prontuario de las ordeneso mecanismos mas inmediatos que necesitara sin duda para empezar adesenvolverse en el entorno de esos sistemas operativos.

En la mayora de los captulos, se ha incluido una peque~na coleccionde cuestiones y sencillos ejercicios de aplicacion, utiles para aanzar losconceptos introducidos.

Ademas, en cada captulo se han seleccionado unas pocas referencias,para completar los contenidos presentados con otros enfoques, o bienpara profundizar en el tema.

Presentacion 15

Agradecimientos

En primer lugar, es inexcusable agradecer a la Editorial la conanzaque ha puesto en nosotros al aceptar una publicacion sobre un tema enel que, ya lo hemos dicho, existen abundantes textos en nuestra lengua,as como su paciencia en la recepcion de los originales.

Tambien debemos dejar constancia de nuestra gratitud hacia loscompa~neros que nos han alentado, desde el principio, a redactar estetrabajo. En especial, a Benjamn Hernandez Blazquez, Mara AngelesMedina Sanchez, Salvador Paz Martnez, Inma Perez de Guzman Mo-lina y Marisol Timoneda Salinas, y tambien a todos aquellos alumnosque, repetidamente, nos han sugerido la compilacion de unos apuntes declase.

Durante la redaccion de este trabajo, se han recogido numerosas opi-niones y sugerencias. En particular, debemos agraceder las minuciosasrevisiones y comentarios hechos por Manuel Enciso Garca-Oliveros, Car-los Rossi Jimenez, Jose Luis Galan Garca, Jaime Fernandez Martnez,Ma Angeles Cano Colorado, Oscar Martn Sanchez y Cristina RodrguezIglesias.

Finalmente, quisieramos pedir la colaboracion de los lectores parasubsanar las posibles deciencias que encuentren.

Captulo 1

Conceptos Basicos

1.1 Informatica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.2 Computador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.3 Sistema operativo . . . . . . . . . . . . . . . . . . . . . . . . . . 191.4 Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201.5 Algoritmos y programas . . . . . . . . . . . . . . . . . . . . . . 211.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271.7 Comentarios bibliogracos . . . . . . . . . . . . . . . . . . . . . 28

El objetivo principal de este captulo consiste en ofrecer una visiongeneral del contenido del libro, presentando los conceptos generales ylos terminos mas usados en informatica. Esta primera aproximacionnos permite situar cada uno de los temas siguientes en relacion con losdemas, y dentro del contexto de la informatica.

1.1 Informatica

La informatica es la ciencia que estudia el procesamiento automaticode la informacion. Aunque la necesidad de razonar sobre este tipo deprocesos existe desde tiempo atras, la consolidacion de la informaticacomo ciencia solo se produce con el desarrollo de los computadores, apartir de los a~nos cuarenta. Se trata, por lo tanto, de una ciencia muyjoven, pero que ha evolucionado a gran velocidad.

18 Captulo 1. Conceptos Basicos

La piedra maestra sobre la cual se ha podido desarrollar la infor-matica la representa el computador, que es una herramienta de granecacia en muy diversos trabajos, y en particular en aquellos que ma-nejan un gran volumen de datos o de operaciones. Esta versatilidadtiene dos aspectos: por un lado, es posible usarlo como herramientapara aplicaciones concretas ya desarrolladas (1.4), y por otro se pue-den dise~nar soluciones a la medida de problemas nuevos, mediante laprogramacion (1.5).

El desarrollo de un programa nuevo para resolver un determinadoproblema requiere, por una parte, conocer algun procedimiento siste-matico (algoritmo) que lleve a su solucion, y por otra, la necesidad deexpresarlo en un lenguaje de programacion que el computador puedacomprender y ejecutar.

1.2 Computador

Un computador es una maquina electronica que procesa informacionsiguiendo las instrucciones de un programa registrado.

Para comunicarse con el exterior dispone de unos medios de entrada,a traves de los que recibe la informacion, y unos medios de salida, pordonde la enva. Tiene dispositivos que le permiten almacenar la infor-macion (los datos, los resultados y el propio programa) y procesarlasiguiendo las instrucciones del programa.

La informacion que se procesa en el computador (programas, da-tos y resultados) esta expresada en forma digital binaria, combinandoceros y unos. En consecuencia, tanto los programas como los datos yresultados deben codicarse en este formato para poder ser procesados.Una vez obtenidos los resultados, estos tienen que ser decodicados paramostrarlos al usuario.

Como hemos visto, un computador se compone de dos partes cla-ramente diferenciadas: una fsica, que podemos tocar, constituida porcircuitos electronicos, teclado, pantalla, unidades de disco, etc., llamadohardware, o en castellano soporte fsico, y otra parte inmaterial, que no

1.3. Sistema operativo 19

usuariosoftware de aplicaciones y del sistema

sistema operativohardware

Tabla 1.1. Estructura de niveles en un computador.

podemos tocar, constituida por los programas y datos, llamada softwareen ingles y soporte logico en castellano. Ambas partes estan ntimamenterelacionadas de forma que una no puede operar sin la otra y viceversa.

1.3 Sistema operativo

Cuando se pone en marcha el computador, el primer programa queentra en funcionamiento es el sistema operativo, que gestiona y coordinalos dos aspectos, fsico y logico, del computador. Se trata de un conjuntode programas que se interrelacionan estrechamente con el hardware, ges-tionando los procesos en ejecucion, las operaciones de entrada y salida yla memoria. Por ello, resulta imprescindible para el funcionamiento delcomputador.

Los demas programas funcionan sobre el sistema operativo, y songestionados por el. Entre ellos, se encuentran las herramientas parael desarrollo de programas (tales como los editores y traductores delenguajes), y tambien los programas de aplicaciones.

Por lo tanto, podemos decir que dentro del computador existe ciertaorganizacion por niveles (vease la tabla 1.1): en el nivel mas bajo seencuentra el hardware, que por s mismo no puede realizar ninguna tarea;a continuacion se encuentra el sistema operativo, y desde el se arrancanlos otros programas, que a su vez se relacionan directamente con elusuario.

En resumen, el hardware no puede funcionar por s mismo: nece-sita la ayuda del software. La union de ambos constituye una maquinavirtual, tremendamente versatil.


1.4 Aplicaciones

El software de aplicaciones esta formado por aquellos programas quehan sido desarrollados para realizar tareas concretas. Se llama as por-que el computador \se aplica" a un trabajo determinado, facilitando suejecucion y resolucion. Por ejemplo, un procesador de textos, una hojade calculo, un gestor de bases de datos, un generador de gracos, unprograma de contabilidad, juegos, etc.

Entre las aplicaciones mas utilizadas se encuentran las siguientes:

Los procesadores de textos son programas que facilitan la elabo-racion de textos en el computador, desde una carta hasta un li-bro. Permiten operar con margenes, tabuladores, justicacion,sangrado, tipos de letra, busqueda y sustitucion de palabras, pa-ginacion, separacion de slabas, sinonimos, ortografa, etc. Sonprobablemente los programas mas usados.

Las hojas de calculo son programas utilizados en la creacion detablas, con datos relacionados entre s, inicialmente ideados parael analisis nanciero. Tienen un formato matricial, en el que sepueden denir operaciones y funciones sobre las distintas compo-nentes de la matriz. Al modicar algun dato, todas las operacionesque lo utilizan son actualizadas de forma automatica.

Los gestores de bases de datos permiten gestionar la informacionreferida a personas o artculos, realizando operaciones de edicion,ordenacion, busqueda, etc.

Los generadores de gracos facilitan la creacion de distintos tiposde gracos, a partir de datos de hojas de calculo o bases de datos,o directamente introducidos por el usuario.

Existen muchas otras aplicaciones, de uso menos general, como sonlos programas matematicos, estadsticos, de CAD (Dise~no Asistido porComputador), aplicaciones contables y de gestion de empresas, comuni-caciones, juegos, etc.

1.5. Algoritmos y programas 21

El desarrollo del software de aplicaciones ha sido muy grande (se cal-cula que para los computadores compatibles con IBM hay mas de cienmil aplicaciones diferentes). A su vez, los distintos programas van evo-lucionando, y aparecen nuevas versiones con mas posibilidades y mayorvelocidad de ejecucion, aunque tambien con mayor demanda de potenciay memoria.

En algunos casos, varios de estos programas se unen en uno solo,compartiendo datos e instrucciones, y constituyen un paquete integrado.En general suele integrarse una hoja de calculo con un generador degracos y, a veces, con una base de datos y un procesador de textos.

Gran parte de los programas de aplicacion pueden congurarse, enmayor o menor medida, de acuerdo con los gustos y necesidades delusuario; sin embargo, es posible que un programa concreto no puedaatender esas necesidades. En este caso, resulta muy difcil, por no decirimposible (e ilegal en muchos casos), modicar el programa para incluiruna nueva tarea. Conscientes de esta falta de exibilidad del software,muchos fabricantes estan presentando programas de aplicacion que asu vez pueden ser programados, mediante lenguajes de programacionpropios o estandares.

As pues, aunque la mayora de las personas que utilizan los compu-tadores trabajan con programas de aplicacion y no necesitan recurrir ala programacion, tambien hay un buen numero de usuarios que, sin serinformaticos profesionales, pueden obtener un mayor rendimiento de es-tos programas a traves de la programacion. Por ejemplo, muchas hojasde calculo, gestores de bases de datos y paquetes matematicos, hoy enda, son programables.

1.5 Algoritmos y programas

El desarrollo de programas es otro de los aspectos fundamentalesde la utilizacion de los computadores porque continuamente aparecennuevos problemas o tareas susceptibles de ser procesados de forma au-tomatica. Al mismo tiempo se van detectando las lagunas o decienciasen las aplicaciones existentes, lo que impulsa a su renovacion con la


creacion de nuevas versiones de los programas existentes. El desarrollodel hardware posibilita tambien la aparicion de nuevas aplicaciones maspotentes y con mayores demandas de recursos.

Desde el planteamiento de un problema hasta la obtencion de susolucion en el computador hay que recorrer una serie de etapas:

1. En primer lugar, antes de resolver un problema en el computadorhay que conocer los pasos y operaciones que hay que realizar paraobtener la solucion del problema, es decir, su algoritmo, porqueel computador solamente es capaz de seguir aquellas instruccionesque nosotros le indiquemos. Si no conocemos el proceso que nosconduce a la solucion del problema, el computador no nos la va adar. Esta secuencia de pasos y operaciones constituye una soluciongeneral al problema planteado de forma que, siguiendo el proceso,se llega a la solucion del problema sean cuales fueran los datosproporcionados.

2. Una vez conocida esta solucion general del problema, hay que ex-presarla en un lenguaje especial, que pueda ser comprendido yejecutado por el computador, es decir, en un lenguaje de progra-macion, creando un programa.

3. Posteriormente, hay que comprobar que el programa produce lassoluciones esperadas (ya sea utilizando datos de prueba o mediantemetodos formales) y subsanar los errores detectados.

4. Por ultimo, es importante documentar el programa de forma quesi cambiaran algunas de las circunstancias iniciales, sea posiblemodicar y adaptar convenientemente, facilitando las labores demantenimiento.

1.5.1 Algoritmos

Una de las caractersticas de los seres humanos es su capacidad paraplantearse y resolver problemas. Estos pueden ser de naturaleza muy


diversa, desde los problemas mas inmediatos relacionados con la pro-pia subsistencia, hasta los problemas mas abstractos de naturaleza ma-tematica o losoca.

Un algoritmo es la descripcion precisa de los pasos que nos permitenobtener la solucion de un problema determinado. En general, los pa-sos son acciones u operaciones que se efectuan sobre ciertos objetos. Alcomienzo del algoritmo, los objetos tienen unos valores iniciales (los da-tos) que varan como consecuencia del proceso descrito por el algoritmo,obteniendose los valores de salida o resultados.

La informatica estudia el procesamiento de la informacion mediantealgoritmos, aunque el concepto de algoritmo, que proviene de las ma-tematicas, es muy anterior e independiente de la existencia de la in-formatica y los computadores. 1

El concepto de algoritmo tiene una importancia fundamental den-tro de la informatica, por ser previo a la resolucion del problema en elcomputador; si no se conoce el algoritmo para resolver un problema, nopuede plantearse su resolucion en el computador.

Aunque existen algoritmos registrados para la realizacion de tareasmuy variadas, en general los algoritmos desarrollados resuelven solo de-terminadas partes de un problema como, por ejemplo, la ordenacion deuna lista de valores, pero no un problema real completo. En consecuen-cia, habra que dise~nar un algoritmo para su resolucion.

El dise~no de algoritmos implica un analisis profundo del problema,de sus datos iniciales, del proceso que se les aplica y de los resultadosesperados. A partir de este analisis debe establecerse cual es la mejorestructura de datos para resolver el problema. De hecho, Niklaus Wirth,uno de los padres de la programacion estructurada, titula una de susobras fundamentales Algoritmos + Estructuras de Datos = Programas,mostrando la importancia que concede a dichas estructuras [Wir86b].

1Se conoce un algoritmo para el calculo del maximo comun divisor de dos numerosnaturales, debido a Euclides, que data del siglo IV a.C., al que se conoce como el\abuelo" de todos los algoritmos.


Existen tecnicas que facilitan el dise~no de algoritmos, tales como laprogramacion estructurada, la programacion modular, el renamientopor pasos, el dise~no descendente y la estructuracion y abstraccion de losdatos.

Para poder expresar algoritmos se utilizan lenguajes con la necesariaprecision, llamados lenguajes algortmicos, que son independientes de loslenguajes de programacion. Los mas utilizados son el seudocodigo y losdiagramas de ujo.

Dado un problema concreto y conocido el algoritmo que lo resuelve,para obtener la solucion del problema tenemos que partir de los datosde entrada, y ejecutar las acciones descritas en el algoritmo. Al procesode ejecutar un algoritmo concreto para unos datos determinados se lellama computo, de donde procede el termino computador. El procesadores quien ejecuta materialmente el computo.

1.5.2 Programacion

Como decamos al principio, consideramos al computador como unaherramienta que nos ayuda en la resolucion de problemas; para ello espreciso conocer previamente un algoritmo que lleve a su solucion. Acontinuacion hay que expresar el algoritmo en un lenguaje de progra-macion, que pueda ser comprendido y ejecutado por el computador,desarrollandose un programa. A este proceso se le llama programacion.

Una aportacion sustancial para realizar este paso tan delicado con lacorreccion necesaria la constituyen:

1. El renamiento por pasos, que permite aumentar el grado de de-talle en la expresion del algoritmo segun convenga, para adaptarloa las necesidades del lenguaje.

2. La programacion estructurada, que utiliza las estructuras de pro-gramacion propias de los lenguajes evolucionados.

3. La programacion modular que, al permitir el uso de modulos osubprogramas, facilita el empleo de otras tecnicas de dise~no dealgoritmos y la depuracion de los programas .


4. No debe olvidarse la importancia de la estructuracion y abstraccionde datos, presente tambien en los lenguajes evolucionados, quedebe emplearse con todo su potencial en el dise~no de algoritmos y,posteriormente, en los programas.

El desarrollo de aplicaciones cada vez mas complejas y el crecimientodel sector de produccion de software, ha hecho que se apliquen a la pro-gramacion tecnicas de ingeniera que garanticen la viabilidad y calidadde los grandes proyectos de aplicaciones, lo que se conoce como inge-niera del software.

1.5.3 Lenguajes de Programacion

El computador dispone de un conjunto de instrucciones que son reco-nocidas y ejecutadas por el procesador. Estas instrucciones se expresan,al igual que los datos, en forma digital binaria, si bien para reconocerlasmejor y evitar errores se les asignan unos nombres mnemotecnicos quepermiten recordar sus funciones. Estas instrucciones constituyen el len-guaje de maquina del computador, y suelen ser diferentes en funcion delfabricante del procesador.

El lenguaje de maquina es ejecutado a gran velocidad por el procesa-dor, en los computadores actuales esta velocidad se mide en millones deoperaciones por segundo; por otra parte, el lenguaje de maquina permiteel acceso directo a todos los organos del computador. Por estos motivosel lenguaje maquina es insustituible en aquellas aplicaciones donde seanecesaria una gran rapidez de ejecucion, o el acceso directo a ciertosorganos del computador.

Las instrucciones del lenguaje de maquina son en general muy pocopotentes, operan sobre datos de peque~no tama~no, y en muchos casos noincluyen ni multiplicaciones ni divisiones. Para poder operar sobre da-tos mayores o realizar operaciones mas complejas, tales como potenciaso logaritmos, hay que fraccionar los datos y aplicar sucesivamente lasoperaciones simples, siguiendo algoritmos especcos. Por este motivo,y por su estrecha relacion con el hardware, a los lenguajes de maquina seles llama lenguajes de bajo nivel . En consecuencia, la tarea de escribir


programa en ejecucion

programa objeto

programa fuente

algoritmo

problemaJJJ^

JJJ^

JJJ^

JJJ^

dise~no de algoritmos

programacion

traductor

procesador

Figura 1.1. Resolucion de un problema mediante la programacion.

programas en lenguaje de maquina es tediosa y esta sujeta a muchoserrores.

Ante la necesidad de escribir programas cada vez mas complejos yables, los informaticos desarrollaron lenguajes con niveles mas elevadosde abstraccion, que incluan operaciones y datos mas complejos a losque llamaron lenguajes de alto nivel. De esta forma se acorta el caminoentre el algoritmo y su expresion en forma de programa, porque loslenguajes de alto nivel pueden expresar mejor las acciones y objetos queintervienen en los algoritmos.

Una de las grandes ventajas de estos lenguajes radica en que la tra-duccion del programa escrito en lenguaje de alto nivel (programa fuente)al lenguaje de maquina (programa objeto) que, como recordamos, es elunico que puede ser ejecutado por el computador, es automatica y serealiza por un programa traductor.

Para ello, junto con las especicaciones del lenguaje, reglas de sinta-xis y semantica, se desarrollan los necesarios programas de traduccion.Durante el proceso de traduccion se suelen detectar errores, debidos al

1.6. Ejercicios 27

incumplimiento de las reglas sintacticas del lenguaje o a causas mas suti-les, que deben corregirse antes de poder ejecutar el programa. Si durantela ejecucion de un programa se realizan operaciones no permitidas (talescomo divisiones por cero, accesos fuera de lmites, . . . ) se producen losllamados errores de ejecucion.

Aunque un programa se haya traducido eliminando todos los erroressintacticos y de ejecucion, aun puede no realizar correctamente la tareapara la que fue creado, por contener errores logicos. Por lo tanto esnecesario comprobar el funcionamiento del programa utilizando datosde prueba que permitan realizar los calculos a mano y comprobar aslas partes mas conictivas del programa. Este proceso se conoce comodepuracion de los programas.

En la actualidad la mayora de los programas se escriben en lengua-jes de alto nivel, reservandose los lenguajes de bajo nivel para aquellasaplicaciones donde se necesite una elevada velocidad o un acceso directoa los organos del computador; por ejemplo, en los programas traductoreso en programas de gestion del computador.

1.6 Ejercicios

1. Trate de describir con precision mediante frases sencillas algunas tareascotidianas, como leer un libro o realizar un trayecto en autobus.

2. Dado el algoritmo de Euclides que se menciona en el apartado 1.5.1,

Sean A,B,R IN.Mientras B 6= 0, hacer: R A modulo BA B

B REscribir A

trate de seguirlo, utilizando lapiz y papel (por ejemplo, para A = 12 yB = 8). Esta formulado desde el punto de vista del procesador: cuando sedice \leer A, B", el procesador debe pedir dos valores para las variablesA y B al usuario; la instruccion \mientras b 6= 0 hacer ..." signicaque mientras la condicion sea cierta hay que realizar las operaciones


comprendidas entre dicha instruccion (...) que, en nuestro caso, es unasecuencia de tres. La operacion \modulo" expresa el resto de la divisionentera, y el smbolo \" indica que, tras calcular el resultado de laexpresion a su derecha, se retendra como el valor de la variable a suizquierda.

3. Clasique los siguientes elementos del computador como pertenecientes alhardware, al software del sistema o al de aplicaciones: pantalla, teclado,unidad de entrada y salida, programa del sistema operativo, compilador,procesador de textos, etc.

1.7 Comentarios bibliogracos

Existe una gran cantidad de textos de introduccion a la informatica quese pueden recomendar con caracter general. Aun ci~nendonos a los escritos encastellano o traducidos, existen bastantes textos excelentes sobre el tema, condiversos enfoques.

En [GL86] encontramos un panorama general sobre informatica en el que seutiliza como tema unicador el concepto de algoritmo, que sus autores juzgancomo el concepto central de la computacion. Se trata de un texto apropiadopara el principiante y de lectura amena. El libro de Bishop ([Bis91]) es tambienun libro muy asequible de introduccion en informatica.

[PLT89] trata con gran detalle la estructura fsica de los computadores, porlo que interesara a quienes deseen detenerse en este aspecto de la informatica.

Recomendamos [FSV87] a quien desee dirigirse hacia los fundamentos teori-cos de la informatica (la teora de algoritmos, la logica y la teora de automatasy lenguajes formales).

Por ultimo, puesto que la informatica es una ciencia reciente, cuenta conmuchos vocablos nuevos, en su mayora anglicismos, que muchas veces se em-plean de forma ilegtima, o que se aplican con un sentido equivocado. En [VJ85]y [MA85] puede consultarse el signicado de esos terminos.

Captulo 2

Representacion digital dela informacion

2.1 Conceptos previos . . . . . . . . . . . . . . . . . . . . . . . . . 292.2 Representacion digital de los datos . . . . . . . . . . . . . . . . 352.3 Codigos redundantes . . . . . . . . . . . . . . . . . . . . . . . . 492.4 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552.5 Comentarios bibliogracos . . . . . . . . . . . . . . . . . . . . . 57

La representacion de la informacion en los computadores digitalespersigue dos objetivos: en primer lugar, procesarla, permitiendo su ma-nipulacion eciente, para lo cual se han ideado diferentes convenios, delos que veremos los mas importantes; y en segundo, asegurarla contraerrores durante su almacenamiento o durante las transmisiones, lo quese consigue incorporando en la codicacion el empleo de la redundanciapara detectar y corregir dichos errores.

2.1 Conceptos previos

2.1.1 Informacion analogica y digital

Las magnitudes continuas son las que pueden adoptar los innitosvalores de un intervalo de numeros reales, tales como la longitud de unsegmento, velocidad, temperatura, intensidad de un sonido, etc.

30 Captulo 2. Representacion de la informacion

Las magnitudes discretas tienen naturaleza discontinua, tales comola longitud (numero de slabas) de una palabra, capacidad (numero depasajeros) de un vehculo, etc.

En la practica, es frecuente que las magnitudes continuas sean trata-das como discretas: el peso de una persona (que se redondea en kilos); latemperatura (en grados y decimas de grado); la longitud de un segmento,medida con un dispositivo de precision hasta los milmetros.

En relacion con ambos tipos de magnitud se considera la informacionanalogica, que es de naturaleza continua, pudiendo tomar innitos valo-res; y la informacion digital, que es de naturaleza discreta. Aunque estaultima puede tomar innitos valores ( IN), en un computador digital lainformacion es discreta y, ademas, nita.

En las calculadoras, la digitalizacion de variables analogicas produceun efecto de redondeo, que debe ser tenido en cuenta y tratado con-venientemente para evitar errores de calculo (vease la seccion 2.3); enel monitor de un ordenador, supone el ajuste de la imagen proyectadasobre una matriz de puntos.

2.1.2 Unidades de informacion en los sistemas digitales

La razon de ser de un computador es el procesamiento de infor-macion. Para poder hablar con propiedad de este procesamiento, debe-mos denir unidades de medida que nos permitan cuanticar de algunmodo la accion del computador sobre la informacion suministrada. Con-sideramos las siguientes:

Bit (BInary digiT ) es la cantidad de informacion que puede alma-cenarse en una variable binaria. No hay que confundir el bit conla variable ni con su valor: una variable binaria es la que puedetomar dos valores estables: 0 o 1, blanco o negro, s o no, etc.

La necesidad de codicar informaciones mas complejas ha llevadoa agrupar varios bits, apareciendo as las siguientes unidades:

El byte u octeto es la cantidad de informacion que puede codicarseen 8 bits; representa por tanto 28 = 256 valores.

2.1. Conceptos previos 31

La palabra se dene en relacion con la maquina considerada, comola cantidad de informacion que la maquina puede manejar de unasola vez. Para evitar equvocos, se habla de palabras de 8 bits, 16bits, 32 bits, etc.

1 Kbyte = 210 bytes = 1.024 bytes. Se suele llamar kilobyte, aun-que esto puede resultar equvoco, ya que el prejo \kilo" signica1.000 (y no 1.024).

1 Mbyte = 1.048.576 bytes (220 = 1.0242). Analogamente, debeadvertirse que \mega" no signica un millon en este contexto.

2.1.3 Sistemas de numeracion posicionales

Aunque se conocen sistemas no posicionales, tales como el de nume-racion romana o el sexagesimal, que usamos para medir el tiempo y losangulos, el sistema de numeracion mas difundido en la actualidad es sinduda el sistema decimal posicional, o sistema arabigo-hindu, inventadohacia el siglo VIII.

Por otra parte, en el contexto de la informatica se usan frecuente-mente sistemas de numeracion posicional en bases tales como 2 (ya queel bit tiene dos posiciones), 16 (como compactacion de palabras de 4bits), etc.

Para aprender a manejarlos, se recurre frecuentemente a la analogacon el sistema de numeracion mas conocido: el de base 10. Se llamadecimal porque cada cifra o dgito puede tomar diez posibles valores: del0 al 9; se llama posicional porque el valor real de cada dgito dependede su posicion.

10475 = 1 104 + 0 103 + 4 102 + 7 101 + 5 100

A la cantidad 10 se le llama base; las potencias de 10 son los pesosasociados a cada posicion, y los factores o coecientes de cada peso sonlas cifras de la representacion. Tambien se podra haber representadoen forma polinomica del siguiente modo:

10475 = 1 104 + 0 103 + 47 101 + 5 100


pero la primera forma es la unica donde las cifras son todas menoresque la base. En general, esta armacion adopta la siguiente forma, cuyademostracion se incluye al nal de este captulo.

Teorema 2.1 En un sistema de numeracion en base b > 1, todo enteroN positivo tiene una unica representacion de la forma

N = cpbp + cp1bp1 + . . .+ c1b1 + c0b0

donde 0 ci < b para todo i = 0, 1, . . . , p

Conversion entre sistemas

En primer lugar, la expresion decimal de un numero de cifras cp . . . c0en base b se obtiene sencillamente sumando los valores reales correspon-dientes a los diferentes dgitos:

[cp . . . c0](b = cp bp + . . .+ c0 b0

Por ejemplo, 275(8 = 2 82 + 7 81 + 5 80 = 189(10En segundo lugar, representar el numero 241(10 en el sistema de base

5, equivale a expresarlo en forma polinomica con las sucesivas potenciasde esa base, siguiendo la idea de la demostracion del teorema:

241 5 241 = 48 * 5 + 11 48 5 48 = 9 * 5 + 3

3 9 5 9 = 1 * 5 + 44 1 1 = 0 * 5 + 1

Por lo tanto,

241 = 48 5 + 1= (9 5 + 3) 5 + 1= ((1 5 + 4) 5 + 3) 5 + 1= 1 53 + 4 52 + 3 51 + 1 50 = 1431(5

2.1. Conceptos previos 33

Sistemas de numeracion mas usuales

El sistema mas empleado en electronica digital es el de base 2, lla-mado binario (natural). En informatica tienen interes los sistemas cuyabase es una potencia de dos: 2, 4, 8, 16. La siguiente tabla recoge losprimeros numeros naturales, expresados en algunos de esos sistemas yen el decimal:

dec. binario octal hexad.

0 0 0 01 1 1 12 10 2 23 11 3 34 100 4 45 101 5 56 110 6 67 111 7 78 1000 10 8

dec. binario octal hexad.

9 1001 11 910 1010 12 A11 1011 13 B12 1100 14 C13 1101 15 D14 1110 16 E15 1111 17 F16 10000 20 1017 10001 21 11

En el sistema hexadecimal se usan los dgitos 0, . . . , 9, A, . . . F para lascantidades cero, . . . , nueve, diez, . . . , quince respectivamente. As porejemplo, C7A(16 = 12 162 + 7 161 + 10 160 = 3194(10, ya que losvalores de A y C en el sistema de base 16 son 10 y 12, respectivamente.

Se observa que, en una base cualquiera b, con N cifras (o menos)es posible expresar bN cantidades distintas; inversamente, para podercomponer C combinaciones distintas se necesita disponer de un numerode cifras igual a logb C, redondeado por exceso.

Como consecuencia de lo anterior, cuanto mayor sea la base adoptadase pueden expresar mas cantidades (combinaciones) para un numero jode cifras; inversamente, cuanto mayor sea la base, es posible usar menoscifras para expresar una misma cantidad.


Observacion

La conversion de binario en octal o en hexadecimal se puede abreviardel siguiente modo:

11 001 111 010 101 100(2= 11 001 111 010 101 100= 3 1 7 2 5 4 = 317254(8= 1 1001 1110 1010 1100= 1 9 14 10 12 = 19EAC(16

>A que se debe el funcionamiento de este mecanismo?

Operaciones aritmeticas en base dos

Para las operaciones elementales se usan las tablas correspondientesa la base de que se trate. Por ejemplo, para el caso binario la tabla desumar es la siguiente:

+ 0 10 0 11 1 10

Y entonces, son validas las reglas conocidas para las operaciones en basediez. Por ejemplo, en el sistema binario natural, tenemos:

1001+ 1011

10100

100101 11011

01010

Para la resta se usa frecuentemente el metodo del complemento: enlugar de la resta propuesta, se halla la suma correspondiente comple-mentando el sustraendo (min sus min+ comp(sus), siendo el com-plemento (comp) el numero resultante de cambiar cada cero por un unoy viceversa), suprimiendo la cifra excedente, posiblemente aparecida porel arrastre, y sumando una unidad al resultado obtenido:

100101 11011

100101+ 100100

1001001 001010

2.2. Representacion digital de los datos 35

2.2 Representacion digital de los datos

En los sistemas digitales, no resulta viable dar una representacionvalida para codicar todos los numeros; por otra parte, los diversossistemas empleados dan diferentes tratamientos a numeros tan usualescomo el uno (segun se considere como real o como entero). Estudiaremosdiversos convenios para diferentes conjuntos de numeros, as como suslimitaciones.

En este apartado, supondremos que disponemos de un espacio de Nbits, con lo que es posible representar 2N enteros distintos.

2.2.1 Representacion de los numeros enteros

Numeros enteros positivos

Si se considera unicamente numeros enteros positivos, con N bits deespacio sera posible representar los numeros de 0 a 2N1. La forma masnatural de lograrlo consiste en interpretar cada combinacion mediantela cantidad que representa en binario. Por ejemplo, con 1 byte (es decir,N = 8) se representaran los numeros 0, . . . , 255 en este sistema.

Numeros enteros con signo. Convenio del signo-magnitud

Para representar los numeros enteros (con signo), el sistema massimple es el convenio de signo-magnitud, consistente en reservar el pri-mer dgito binario para codicar el signo (suele representarse el signo+ con un cero y el con un uno) y los siguientes N 1 para el va-lor absoluto. As, en este sistema tienen representacion las cantidades0, . . . ,(2N 1). En el caso particular de 1 byte, esas cantidades son127, . . . ,0,+0, . . . ,+127.

En este sistema, la aritmetica es bastante simple: la suma de canti-dades del mismo signo y la resta de cantidades de distinto signo siguenla regla basica en binario. Para sumar cantidades de distinto signo, orestar cantidades del mismo signo, resulta mas practico el metodo delcomplemento.


Se observa el inconveniente de que el cero tiene una doble represen-tacion, por lo que el test de la comparacion para la igualdad en estesistema debe tenerlo en cuenta. Por otra parte, la suma/resta de signosy valores absolutos necesita dos algoritmos distintos, que no resultanmuy ecientes. Los siguientes sistemas surgen precisamente para tratarde paliar estas deciencias.

Numeros enteros con signo. Complemento restringido

Para comprender mejor el funcionamiento de este convenio en bina-rio, conviene introducirlo primero en base diez. Si consideramos palabrasde N = 2 dgitos (decimales), es posible representar 102 = 100 canti-dades distintas. En este convenio se opta por considerar los numerosnegativos de {49, . . . ,0}, y los positivos de {0, . . . , 49}, del siguientemodo: los numeros positivos se representan en decimal natural, mientrasque para cada negativo z se toma la cantidad 99 z (complemento dez respecto de 102 1, que es la N=2 potencia de la base menos uno).As por ejemplo, tenemos:

repr(29) = 2 9

repr(29) = 99 29 = 7 0Con este convenio, las cantidades

49,48, . . . ,0, 0, 1, . . . , 48, 49se representan respectivamente mediante

5 0 , 5 1 , . . . , 9 9 , 0 0 , 0 1 , . . . , 4 8 , 4 9

Aunque se observa el inconveniente de que el cero tiene dos repre-sentaciones, la ventaja de este convenio consiste en que la suma de dosnumeros, sea cual fuere su signo, se lleva a cabo con un mismo algoritmo,que solo se diferencia de la suma de enteros en que el posible arrastre seagrega al resultado nal:

+ 23+ 15

2 3+ 8 41 0 7 +1 0 8


Consideremos ahora esta representacion con palabras de N = 4 dgitosbinarios: las cantidades representables son

7,6, . . . ,0,+0, . . . ,+6,+7 111(2,110(2, . . . ,0(2,+0(2, . . . ,+110(2,+111(2

que, al complementar las negativas respecto de 1111, resulta:

1000, 1001, . . . , 1111, 0000, . . . , 0110, 0111

Numeros enteros con signo. Complemento autentico

Empezamos nuevamente con la base decimal como punto de partida,y consideremos tambien palabras de longitud N = 2. Ahora se opta porconsiderar los numeros negativos de {50, . . . ,1}, y los positivos de{0, . . . , 49}, del siguiente modo: los numeros positivos se representan enbinario natural, mientras que para cada negativo z se toma la cantidad100 z (complemento de z respecto de 10, que es la base para N = 2).

repr(29) = 2 9

repr(29) = 100 29 = 7 1Con frecuencia se emplea otra regla equivalente para complementar

los numeros negativos, consistente en a~nadir una unidad al correspon-diente complemento restringido.

Con este convenio, las cantidades

50,49, . . . ,1, 0, 1, . . . , 48, 49

se representan respectivamente mediante

5 0 , 5 1 , . . . , 9 9 , 0 0 , 0 1 , . . . , 4 8 , 4 9

Este sistema tiene las mismas ventajas que el anterior, y ademas elcero se representa de un unico modo.


Como en el caso anterior, consideremos ahora la base dos, con pala-bras de N = 4 dgitos, donde tienen cabida las cantidades

8,7, . . . ,1,+0, . . . ,+7 1000(2,111(2, . . . ,1(2,+0(2, . . . ,+110(2,+111(2

que, al complementar las negativas respecto de 10000, resulta:

1000, 1001, . . . , 1111, 0000, . . . , 0110, 0111.En este sistema, la suma tambien se lleva a cabo con un mismo algo-

ritmo, igual al usado para el complemento restringido, pero ignorandola posible cifra de arrastre:

+ 23+ 15

2 3+ 8 51 0 8 0 8

Funcionamiento de las operaciones aritmeticas

Debe subrayarse que las operaciones anteriores no coinciden con lasaritmeticas, debido a la posibilidad de que se produzca un desborda-miento; los diferentes sistemas responden ante esta circunstancia de di-ferentes modos: por ejemplo, ignorando la ultima cifra de arrastre, ointerrumpiendo su trabajo para delatar una condicion de error. Por lotanto, es necesario prever esta posibilidad y conocer de que modo re-acciona nuestro sistema. Sobre este asunto volveremos mas adelante,dentro de este mismo captulo.

Formatos de los numeros enteros en las computadoras

Entre los convenios presentados, el mas frecuente es el del comple-mento autentico en base dos, llamado simplemente complemento a dos.Ahora bien, dependera de la longitud de palabra la cantidad de com-binaciones posibles y, por tanto, el rango de enteros considerado. Porotra parte, aunque ciertos sistemas trabajan con palabras de longitudvariable, lo corriente es optar por uno o varios formatos con tama~no jo:simple (1 byte), doble (2 bytes), cuadruple (4 bytes) u octuple (8 bytes).


2.2.2 Representacion de los numeros reales

Debe resaltarse que, en general, solo resulta posible representar apro-ximaciones de los numeros reales mediante numeros decimales, con solounas pocas cifras signicativas. En el siguiente apartado estudiaremoslos efectos de este redondeo.

En este apartado, supondremos que disponemos de un espacio de Nbits, con lo que es posible representar 2N enteros distintos.

Convenio con coma ja

Si disponemos de un espacio de N bits para representar un numeroreal, la caracterstica principal de este convenio es la reserva implcitade algunos bits jos para la parte decimal, asumiendose la coma en unaposicion ja. A su vez, existen los siguientes modos de representacionen coma ja:

Sistema signo y valor absolutoEn este convenio se reserva un bit para codicar el signo, y del restose destina una cantidad ja para representar el valor absoluto dela parte entera, y los demas para la decimal:

1 0 1 0 0 1 0 0 1 0 1 1 1 1 0 1

p. entera

. dec.

Si consideramos por ejemplo N = 16, siendo el primer bit el quecodica el signo, los siguientes 12 los de la parte entera, y los3 restantes los de la parte decimal, resulta que la representacionanterior signicara

010010010111.101= (210 + 27 + 24 + 22 + 21 + 20 + 21 + 23)= 1175625.


Complemento restringido y complemento autenticoSea D = 3 el numero (jo) de decimales asumidos. La represen-tacion de un numero x, en cualquiera de estos convenios, consisteen codicar en su lugar la parte entera de x 23 en el convenioelegido. La cantidad despreciada al truncar los decimales de x 23es menor que 0125(10(= 23).

Por ejemplo, para representar 28 en palabras de N = 8 y D = 3,debemos conformarnos con una aproximacion: al ser D = 3, solo po-demos representar cantidades decimales multiplos enteros de 0001(2 =23(10 = 0

125(10. Como trunc(28 8) = trunc(224) = 22, repre-sentamos 22/8 = 275. Comprobamos que esta cantidad es efectiva-mente multiplo de 0125, y que el siguiente multiplo (2875) excede lacantidad inicial (28). Signo y valor absoluto:

2.75 = 2 +12

+14

= 1 0 0 1 0 1 1 0

p. entera

. dec.

Complemento restringido (8 dgitos):

22 = {

1111111110110(2

} 11101001 = 1 1 1 0 1 0 0 1

Complemento autentico (8 dgitos):

22 = {

10000000010110(2

} 11101010 = 1 1 1 0 1 0 1 0

Convenios con coma otante

El principal inconveniente de la coma ja consiste en condicionarel orden de magnitud de las cantidades codicadas. Un sistema masgeneral debera adaptarse a ordenes tan distantes como los de la masa de


la tierra y la del atomo. El sistema mas conocido con esta caractersticaes la llamada notacion exponencial (o cientca):

140 = +0.14 103 = +0.14E36.02215 1023 = +0.602215E240.00000015 = +0.15E 6

Los convenios con coma otante funcionan del mismo modo, divi-diendo la informacion sobre una cantidad en tres partes: su signo, sumantisa (es decir, las cifras signicativas de mayor orden), y el exponente(que expresa el orden de magnitud). As por ejemplo, consideremos lasiguiente representacion en palabras de N bits:

El signo, adscrito al primer bit, donde el uno representa al signomenos.

El exponente (z), situado en los siguientes e bits, puede tomar losvalores de {2e1, . . . , 2e1 1}. Frecuentemente se representadesplazado en +2e1 unidades:

z {2e1, . . . , 2e1 1} repr(z) {0, . . . , 2e 1}

Para la mantisa quedan M = N e 1 bits con lo que, para surepresentacion, se toman los primeros M dgitos de su escritura enbinario natural.

Como ejemplo concreto, consideremos el convenio estandar IEEE 754(real con precision simple, o real corto), que es una de las codicacionesde reales mas utilizadas. Su representacion requiere un total de 32 bits,de los cuales un bit se utiliza para el signo, 8 bits para el exponentey 23 bits para la mantisa. Este convenio en concreto, utiliza un trucollamado bit oculto: como el bit mas signicativo de la mantisa es un 1,ahorramos un bit simplemente asumiendolo. Se logra as espacio parauna mantisa de 24 dgitos signicativos. El inconveniente de emplear unbit oculto consiste en que se requiere una representacion especial parael cero.


2.2.3 Limitaciones de los sistemas de representaciondigital de los numeros

Debido a que los sistemas de codicacion considerados estan inmer-sos en sistemas nitos, solo pueden representar una cantidad nita deelementos distintos. Esta limitacion resulta crtica a la hora de repre-sentar elementos pertenecientes a conjuntos innitos, como son los delos numeros enteros o reales. Como consecuencia, pueden producirsesituaciones de error no deseables, por lo cual se hace necesario estudiarel alcance de esas limitaciones, as como la manera de afrontarlas.

Limitaciones en los enteros

En los enteros, las representaciones se limitan a un intervalo reducido[mn, max ], de cardinal no superior a 2n, siendo n el tama~no (en bits)de la representacion. As, cuando surge la codicacion de numeros fueradel rango considerado, se produce el llamado desbordamiento (overowen ingles).

Por ejemplo, en una representacion con 4 bits seran posibles 16 con-guraciones. Si optamos por el convenio de complementacion autentica,el intervalo considerado sera [8, 7]. Veamos que ocurre al sumar 5 y 6.

5+ 6

0101+ 0110

1011 5El comportamiento de las operaciones de suma y resta en el sistema

de complementacion autentica para una representacion de n bits se puededescribir as: llamemos x e y a la representacion de x e y, y + y a lasoperaciones de suma y resta en este sistema, x, y [2n1, 2n1 1],tenemos:

x y =

(x y + 2n), si x y < 2n1(x y), si x y [2n1, 2n1 1](x y 2n), si x y > 2n1 1

Para paliar en cierta medida esta limitacion, es frecuente incorpo-rar tipos de datos correspondientes a rangos de enteros mas amplios


(por ejemplo, duplicando la longitud de palabra de la representacion),pudiendo as manipular con seguridad enteros de mayor orden. Aspor ejemplo, el calculo de 8! desbordara un sistema de complementoautentico con 16 dgitos, resultando en cambio correcto para palabrasmas largas. En ocasiones, el programador tiene la posibilidad de cam-biar de estrategia para evitar el desbordamiento. Por ejemplo, el calculode(8

3)

se puede obtener evaluando 8!3!5! o876321 indistintamente; sin em-

bargo, el primero de ellos necesita manipular numeros mayores, por loque el segundo nos permite eludir en cierta medida el error por desbor-damiento.

Por otra parte, muchos de los lenguajes que se comercializan en laactualidad ofrecen la opcion de vericar o no los desbordamientos quepuedan producirse durante la ejecucion, para que los consiguientes erro-res no pasen inadvertidos.

Finalmente, la mayora de los lenguajes de alto nivel presentan sis-temas de construccion de tipos de datos con capacidad para denir co-dicaciones (y operaciones de manipulacion sobre los objetos cifrados)a la medida de nuestras necesidades.

Limitaciones en los reales

En este caso, incluso limitandonos a los reales contenidos en un pe-que~no intervalo acotado, estos seran innitos, por lo cual las limitacionesen su representacion no solo afectan al tama~no de los numeros consi-derados, sino tambien a la precision. En efecto, en cualquiera de losconvenios estudiados se toma como mantisa solo cierto numero reducidode dgitos(binarios) signicativos, despreciandose los demas.

En otras palabras, cada codicacion de un numero real en comaotante representa en realidad un intervalo, cuyo tama~no vara segunla magnitud del real representante. Por consiguiente, la distribucion derepresentantes no es uniforme: un intervalo tan peque~no como [0'1, 1]cuenta con tantos representantes como [1000, 10000].

Ademas de las limitaciones de la precision, la representacion de losreales esta limitada por su tama~no: existe un valor a partir del cual no


hay representantes reales y que determina el rango de desbordamiento.

Debe observarse en este punto que existen cantidades cuya expresiondecimal es exacta, sin serlo su expresion escrita en binario natural (porejemplo, 01(10 = 00 0011 0011 . . .(2), por lo que, en principio, debe des-conarse de la precision en la codicacion de todo numero no entero.

Aunque esta diferencia entre una cantidad y su representacion es enmuchos casos despreciable, su aparicion puede ocasionar grandes desvia-ciones respecto del comportamiento teorico.

Una situacion as se produce cuando se comparan dos numeros realespara determinar su igualdad, ya que el resultado de la comparacionignora si esa diferencia producida es peque~na o grande, lo que puedeocasionar una respuesta drasticamente distinta de la correcta. As porejemplo, la ejecucion del siguiente programa escrito en Pascal

Program errores (output);var suma: real;begin

suma := 0;repeat

suma := suma + 0.1;writeln(suma);

until suma = 1end.

no para.1 Frecuentemente esta situacion puede evitarse cambiando laexpresion x = y por | x y |< , siendo la diferencia admitida.

En realidad, la aparicion de errores intolerables es posible inclusoen expresiones sencillas. Concretamente, deberan evitarse las opera-ciones de suma y resta, cuando uno de los operandos es muy peque~noen comparacion con el otro, y la division cuando el divisor es cero o\proximo a cero". Por ejemplo, la relacion |t/x| debera sustituirsepor |t| |x|.

1Suponiendo una representacion en binario puro.


Mas aun, aun cuando se trate de un error despreciable, es frecuenteque ese error intervenga en calculos repetidos, como ocurre en la ma-nipulacion de matrices, el calculo con series recurrentes, etc.; en talessituaciones, la propagacion de un error inicial, aunque peque~no, puedegenerar un error mucho mayor. El estudio y la cuanticacion de loserrores, as como su propagacion en calculos repetitivos y los metodospara encontrar soluciones satisfactorias, escapan del alcance y objetivosde este curso, siendo materia propia de los metodos numericos.

Otros sistemas de representacion (paquetes matematicos)

Durante la pasada decada, se han desarrollado y difundido paquetesde programas matematicos, capaces de resolver ecientemente un ex-tenso numero de problemas, manipulando expresiones tanto numericascomo simbolicas. Para ello estan provistos (aparte de otros mecanismos)de potentes sistemas aritmeticos de representacion no convencionales.Veamos dos ejemplos de estas posibilidades:

Capacidad de representar enteros con tama~no limitado solo porla memoria del ordenador, fracciones y reales con una precisionarbitraria, elegida por el usuario. Por ejemplo:

sea precision decimales = 25escribir pi

3.1415926535897932384626433

Capacidad de establecer valores numericos (reales o complejos)mediante su denicion, en lugar de su calculo, con lo que no hayperdida de precision. As, es posible establecer sentencias del estilode las siguientes:

sea x0 := x tal que x2 + 5 = 0escribir (1 x02)/2

cuya ejecucion producira la escritura de 3, exactamente.


2.2.4 Representacion de los caracteres

Existen otros convenios, ademas de los numericos, para representarlos caracteres disponibles habitualmente en un teclado de computador:los dgitos, las letras minusculas y mayusculas, los signos de puntuaciony de operacion y otros smbolos especiales, tales como #, &, @, %, etc.

Inicialmente surgieron numerosos convenios para codicar los carac-teres, variando el numero n de bits empleados (y con el su capacidad derepresentacion), as como la posicion, entre 0 y 2n 1, asignada a cadacaracter. Sin embargo, en seguida se observo la necesidad de adoptarconvenios normalizados, as como la conveniencia de que estos tenganciertas cualidades:

Debe incluirse el juego de letras mnimo internacional, en dos in-tervalos de posiciones consecutivas, correspondientes a las letrasminusculas y mayusculas.

Los caracteres correspondientes a los dgitos deben ocupar tambienposiciones correlativas, de \facil" cifrado y descifrado.

Ademas, cuando la capacidad de representacion lo permita, sera deseableque en un sistema sea posible:

A~nadir otros caracteres mas especcos: frecuentemente, los pro-pios de una lengua (las \a" y \~n" espa~nolas, la \u^" francesa, etc.)

Destinar ese exceso de capacidad a prevenir y subsanar posibleserrores, como veremos en el siguiente apartado.

Uno de los convenios mas extendidos en la actualidad es el ASCII, con7 bits, por lo que admite hasta 27 = 128 caracteres. Damos la siguientetabla, omitiendo los primeros 32 caracteres, por ser caracteres de control.


32 44 , 56 8 68 D 80 P 92 \ 104 h 116 t33 ! 45 - 57 9 69 E 81 Q 93 ] 105 i 117 u34 " 46 . 58 : 70 F 82 R 94 ^ 106 j 118 v35 # 47 / 59 ; 71 G 83 S 95 107 k 119 w36 $ 48 0 60 < 72 H 84 T 96 ` 108 l 120 x37 % 49 1 61 = 73 I 85 U 97 a 109 m 121 y38 & 50 2 62 > 74 J 86 V 98 b 110 n 122 z39 ' 51 3 63 ? 75 K 87 W 99 c 111 o 123 {40 ( 52 4 64 @ 76 L 88 X 100 d 112 p 124 |41 ) 53 5 65 A 77 M 89 Y 101 e 113 q 125 }42 * 54 6 66 B 78 N 90 Z 102 f 114 r 126 ~43 + 55 7 67 C 79 O 91 [ 103 g 115 s

En este convenio, se observa en primer lugar que los dgitos decimales\0", . . . , \9" ocupan las posiciones 48, . . . , 57: sus valores (0000, . . . ,1001 ) coinciden con las terminaciones de sus posiciones (0110000, . . . ,0111001 ).

Siguiendo la segunda condicion, las letras mayusculas y minusculasse hallan situadas en las posiciones 65 a 90 y 97 a 122, respectivamente.

En la practica no se utilizan palabras de 7 bits, siendo frecuenteen cambio adoptar el byte (= 8 bits) como unidad. As, es posibleextender el convenio anterior y dar cabida a otros caracteres de usotambien interesante en ciertas aplicaciones; he aqu algunos ejemplos:

Posicion: 130 145 156 164 165 168 248Caracter: e $ ~n ~N >

2.2.5 Organizacion de datos mas complejos

Los computadores no solo almacenan y manipulan numeros y ca-racteres, sino que tambien deben organizar y tratar informaciones mascomplejas, tales como sucesiones de datos (por ejemplo, cadenas de ca-racteres), vectores, tablas, etc., ya sea formadas por datos simples o bienpor conjuntos de informacion con alguna organizacion. Con tal nalidadse han ideado diversas estrategias; aunque su estudio excede el alcancede este captulo, veamos un ejemplo orientativo.


Supongamos una maquina de 1 byte (tama~no de palabra). Si seadopta para los numeros enteros un convenio de 2 bytes, cada numeroocupara dos palabras consecutivas. Una forma natural y sencilla deorganizar un vector de n enteros consiste en situarlos secuencialmente,empezando en las posiciones m0,m0 + 2, . . . ,m0 + 2(n 1), y la compo-nente i-esima del vector reside en las posiciones m0+2(i1) y m0+2i1,para i {1, . . . , n}.

Si se tratase de una matriz de m n, cuyas componentes ocupan kpalabras de memoria, se establece facilmente la posicion inicial para lacomponente i, j-esima:

m0 + k(n(i 1) + j 1)

para i {1, . . . , n}, j {1, . . . ,m} y siendo m0 la posicion inicial de lamatriz.

2.2.6 Representacion de las instrucciones

Aunque podra parecer impropio considerar las instrucciones comoinformaciones, lo cierto es que los programas se almacenan en la memoriadel ordenador y manipulan del mismo modo que los datos. De hecho,desde el punto de vista de la maquina, un programa no es mas que unasecuencia de elementos, cada uno de los cuales es un descriptor de unainstruccion elemental.

El formato de las instrucciones (es decir, de sus descriptores) dependede la maquina destinada a seguirlas. Si consideramos por ejemplo unamaquina de tres direcciones (vease cap. 3), sus instrucciones se compo-nen de cuatro campos que codican respectivamente la operacion quedebe efectuarse y las posiciones de memoria en que se encuentran los(como maximo dos) argumentos y la de la palabra donde debe situarsenalmente el resultado. En el captulo siguiente se presenta con detalleuno de estos formatos.

2.3. Codigos redundantes 49

2.3 Codigos redundantes

2.3.1 Informacion y redundancia

Informacion e incertidumbre.- El termino informacion tiene en ge-neral un signicado muy amplio: piensese en la informacion proporcio-nada por una fotografa o un poema. Por eso, en el contexto de la in-formatica como ciencia que trata sobre el tratamiento automatico de lainformacion, se asocia a esta un signicado mas restringido y manejable.

Para denir este signicado, consideremos que deseamos determinarun cierto fenomeno, que puede presentar una cantidad nita de estados.Entonces, una informacion (sobre ese fenomeno) es una sentencia capazde aportar algun conocimiento sobre tal fenomeno; esto es, capaz dedelimitar en cierta medida su estado.

As por ejemplo, si consideramos el fenomeno \colores del atuendoque llevaba anoche el asesino del callejon", sabiendo que el pantalonera negro o marron, que la camisa era azul, gris o marron, y que elsombrero era gris o negro, resulta que el numero de estados es 12. Unainformacion sobre este fenomeno podra consistir en la sentencia \lacamisa y el pantalon eran de distinto color"; con esta informacion, soloson posibles 10 estados de nuestro fenomeno. Ahora, la armacion \lacamisa y el pantalon no eran ambos marrones" resulta redundante puestoque, considerandola, siguen siendo posibles los mismos 10 estados queignorandola.

En lugar de hablarse de cantidad de informacion, resulta mas facilmanipular la de incertidumbre. Una medida indirecta de ello consisteen la cantidad de estados posibles: su grado de indeterminacion. Sicierto fenomeno ofrece 12 estados posibles, su grado de indeterminaciones 12, pero resulta mas conveniente considerar como medida de la in-certidumbre el logaritmo (en base dos) de esta cantidad, puesto que laincertidumbre crece de forma exponencial (con base dos) respecto de lalongitud (numero de bits) del mensaje. Esta medida de la incertidumbrese llama entropa asociada a un fenomeno, y se denota mediante H:

H = log2(numero de estados posibles de un fenomeno)


Entonces, la informacion asociada a una sentencia se dene comodisminucion de incertidumbre proporcionada. Siendo H0 = log2(n0)y H1 = log2(n1) las entropas correspondientes a los estados previo yposterior a la sentencia, con n0 y n1 posibles estados, respectivamente,tenemos:

I = H0 H1 = log2(n0) log2(n1) = log2(n0n1

).

Por ejemplo, para la primera sentencia, tenemos:

I1 = log2 12 > 0

mientras que la segunda proporciona una cantidad de informacion nula,al ser redundante.

La redundancia en la codicacion.- En los convenios de codica-cion/decodicacion estudiados hasta ahora, se ha supuesto que su trans-mision o su almacenamiento se efectua siempre sin ruido. En ellos, elobjetivo principal consiste en dise~nar convenios ecaces (sin emplear masdgitos que los estrictamente necesarios, minimizando as la redundan-cia), unvocos (donde el cifrado es unico) y sin ambiguedad, siendo unicatoda decodicacion.

Para prever la posibilidad de que se produzcan perturbaciones, sehan ideado metodos capaces de descubrir en ciertas condiciones cuandose ha alterado un mensaje (codigos detectores), as como otros capacesde restituir su estado inicial (codigos correctores).

Ambas clases de mecanismos se apoyan en el uso de la redundan-cia. Anticipamos un par de ejemplos para aclarar ambos tipos de me-canismos.

Adicion de un bit de paridad.- Para un mensaje de n bits se a~nadeuno, cuyo valor consigue que haya en total un numero par de unos. Seignora la posibilidad de que se altere mas de un bit, por considerarlaextremadamente improbable. En la interpretacion del mensaje se vericapreviamente la paridad, detectandose un error si se ha producido, aunqueno sera posible identicar cual para restablecer su estado.

2.3. Codigos redundantes 51

Codigo dos entre tres.- Este mecanismo consiste sencillamente entriplicar las copias de cierta informacion. Se consideran dos posibilida-des: que no se produzca ninguna alteracion, o que se produzca en una delas copias, descartandose mayores perturbaciones. En ambos casos, seinterpreta el mensaje cifrado en la mayora de las copias: dos (al menos)entre tres.

2.3.2 Codigos solo autodetectores: p de n

Si en una palabra de n bits (que admite 2n conguraciones) estable-cemos la restriccion de considerar validas solo aquellas con exactamentep unos (y np ceros), sera posible detectar si se efectua una perturbacionsimple, o una multiple, siempre que no se alteren tantos unos como ce-ros. En un codigo p de n, el grado de indeterminacion es el numero depermutaciones con repeticion de p unos y n p ceros(

n

p

)=

n!p!(n p)!

que alcanza su maximo cuando p = ndiv 2.

2.3.3 Codigos autocorrectores: Hamming

Fundamento

Consideremos un mensaje de n bits. La idea basica consiste en a~nadirun cierto numero p de bits, cada uno de los cuales asegura un ciertosubconjunto de los n+ p dgitos totales mediante un control de paridad.Se considera la posibilidad de que exista, a lo sumo, una alteracion enuno de los n+ p bits y deseamos conocer si ha habido o no perturbaciony, en caso armativo, cual de los n+ p bits ha sido alterado. Puesto queel mensaje debe codicarse en los n bits, la informacion sobre el estadode perturbacion debe cifrarse en los p bits, para poder as restablecerla.Por tanto, conocido n, p debe ser la mnima cantidad de bits tal que los2p estados posibles de los p bits de paridad acepten al menos n+ p+ 1estados distintos: no alteracion (1) o la posicion del bit alterado (n+p).Es decir:

p = mn k IN tal que 2k n+ k + 1


Por otra parte, los p conjuntos de bits deben elegirse de modo queel estado de los p bits de paridad asociados a esos conjuntos permitalocalizar el bit alterado, en su caso y, si es posible, con facilidad.

Un modo de conseguir el objetivo descrito consiste en intercalar elbit i-esimo en la posicion 2i1, para i = 1, . . . , p, siendo su conjuntoasociado el de los dgitos cuyo numero de posicion, escrito en binarionatural, tiene un 1 como cifra i-esima.

Sea por ejemplo n = 4. Necesitamos p = 3 bits de paridad, quecolocaremos en las posiciones 1, 2 y 4:

posicion : 1 2 3 4 5 6 7id. en binario : 001 010 011 100 101 110 111

Ahora, el bit 001(2 esta asociado al conjunto de los bits del mensajecuya posicion acabe en 1 (1, 3, 5 y 7); el bit 010(2 esta asociado alconjunto de los bits del mensaje cuya posicion tenga un 1 en la segundacifra (2, 3, 6 y 7), y el bit 100(2 esta asociado al conjunto de los bits delmensaje cuya cifra inicial sea un 1 (4, 5, 6 y 7).

Codicacion

Sencillamente, se trata de ajustar los bits de paridad con respecto asus conjuntos asociados. Por ejemplo, si se desea transmitir el mensaje0110

0 1 1 0

bastara con ajustar el bit 10 con los 30, 50 y 70 (resultando un 1); el bit20 con los 30, 60 y 70 (resultando un 1), y el bit 40 con los 50, 60 y 70

(resultando un 0):

1 1 0 0 1 1 0

Anexo 53

Decodicacion con autocorreccion

Para recticar y descifrar un mensaje recibido, se detectan en pri-mer lugar los bits de paridad que reejan alguna alteracion. Si no hayninguno, el mensaje se ha mantenido intacto durante la transmision; encaso contrario, la suma de las posiciones de los bits alterados se~nala elbit modicado.

Por ejemplo, si el mensaje anterior se recibe as:

1 1 0 0 0 1 0

el control de paridad arroja el siguiente resultado:

bit 10(+3 + 5 + 7) = 1 (impar) alteradobit 20(+3 + 6 + 7) = 2 (par) sin alterarbit 40(+5 + 6 + 7) = 1 (impar) alterado

Al ser 1 + 4 = 5, concluimos que el 50 bit es erroneo, por lo que elmensaje original era

1 1 0 0 1 1 0

Anexo: demostracion del teorema 2.1

Incluimos aqu esta demostracion por ser constructiva, mostrandoel proceso de expresar una cantidad en cualquier base mayor que uno.Procederemos en cuatro fases: en primer lugar, la existencia de esarepresentacion en las condiciones del teorema se demuestra facilmentepor induccion, dando un metodo para hallar esa construccion. En se-gundo, se demuestra (tambien por induccion) que ese metodo convergey a continuacion que la solucion que proporciona equivale efectivamentea la cantidad dada. Finalmente, se demuestra que no hay mas que unarepresentacion de un numero en una base ( 2) dada.


1. Dada la cantidad entera y positiva N , y la base b > 1, la represen-tacion de N en base b sigue el siguiente esquema:

reprb(N) =

N si N < b

reprb(D).R en otro caso, dondeD = N div b y R = N mod b

donde el punto expresa la separacion entre las cifras de N , expre-sado en la base b, y donde div y mod representan, respectivamente,el cociente y el resto de la division entera.

2. La convergencia del metodo resulta obvia considerando que, par-tiendo de cualquier numero entero positivo N , la secuencia N =N0, N1, ... conduce al conjunto {0, ..., b} mediante la aplicacion deNi = Ni1 div b, en un numero nito, trunc(logb N), de pasos.

3. La equivalencia queda demostrada por induccion sobre el numerode cifras de la representacion obtenida: cuando N < b, tenemos elcaso base reprb(N) = N ; en caso contrario, basta considerar quela cantidad representada por reprb(D).R es

b reprb(D) +R= b reprb(N div b) + (N mod b)Asumiendo ahora como hipotesis inductiva que reprb(N div b) re-presenta la cantidad N div b, podemos expresar la cantidad ante-rior como

= b (N div b) + (N mod b)que es precisamente N : recuerdese que

dividendo = divisor cociente + resto

4. En las condiciones del teorema, esa representacion es unica. Lo de-mostraremos por reduccion al absurdo. Supongamos que es posibleexpresar una cantidad x de dos modos distintos, cuyas represen-taciones tienen las cifras ...a0 y ...a0 , siendo L la posicion de lascifras distintas de mayor peso, y consideremos por ejemplo que esaL > a

L. Entonces, se tiene:

2.4. Ejercicios 55

(a) La diferencia entre aL y aL representa al menos bL unidades:

aL bL > aL bL aL bL (aL + 1) bL = aL bL + bL

(b) Por otra parte, la cantidad maxima que pueden representarlos dgitos siguientes es de

L1i=0

(b 1) bi = bL 1.

Resulta entonces que la diferencia que supone la cifra distinta demayor orden ( bL) no puede compensarse por ninguna combi-nacion de las siguientes ( bL 1). Por tanto, si dos representa-ciones son distintas en alguna cifra, tambien lo son las cantidadesrepresentadas.

2.4 Ejercicios

1. Exprese los siguientes numeros en las demas bases:

binario puro decimal hexadecimal1001110011

67231A9E

2. Efectue las siguientes operaciones, en la base indicada:

11011101(2 + 11110000(2 11000101(2 101001(2 A2396(16 + 24BC2(16 A2396(16 1A(16

Para el ultimo apartado es recomendable construir previamente la tablade multiplicar por A, en base hexadecimal.

3. Halle el rango de los posibles enteros,

si consideramos palabras de tama~no medio si consideramos palabras de tama~no simple


si consideramos palabras de tama~no doble4. Represente 7 y 3 en los siguientes formatos, y realizar la suma corres-

pondiente:

complemento restringido, en decimal dem, en binario complemento autentico, en decimal dem, en binario

Haga lo mismo con 12 y 7.

5. Represente los numeros 35, 0'25 y 2'6 en los siguientes formatos:

en coma ja, con 5 bits enteros y 3 decimales coma otante: signo (1 bit), mantisa (9) y exponente (6)

6. Generalice la representacion en memoria de vectores y matrices a matri-ces tridimensionales.

7. Se desea dise~nar un codigo capaz de cifrar una informacion con 33 posiblesestados.

>Cuantos bits son necesarios? Con ese numero de dgitos, >cuantos estados son posibles? Un control del tipo 2 de n, >cuantos dgitos necesita?

8. Se desea transmitir mensajes de 31 bits, asegurandolos mediante uncodigo de Hamming.

>Cuantos dgitos de paridad se necesitan? >En que posiciones? >Cuales son los dgitos asociados a cada uno de los de paridad?

9. Para el codigo de Hamming para mensajes de 4 bits introducido en elapartado 2.3.3, se desea transmitir la informacion 1001.

Cifre el mensaje que debe enviarse Si consideramos las cinco posibilidades: que el mensaje llegue inal-

terado a su destino, o que uno de sus cuatro dgitos haya cambiadosu valor, descifre cada uno de esos mensajes.

2.5. Comentarios bibliograficos 57

10. Para cifrar un codigo de Hamming para mensajes de 11 bits, construimosun vector de 15 bits.

De formulas apropiadas para hallar la paridad de los bits insertados. Idem para la autocorreccion que se efectua en el descifrado.

2.5 Comentarios bibliogracos

El material incluido en este captulo sobre la representacion de los numerosreales en coma otante solo es una aproximacion conceptual. En [Gol91] seencontraran muchos de los detalles tecnicos omitidos aqu, tales como el tra-tamiento dado en la practica a los errores (absolutos y relativos) debidos alredondeo, el manejo de las excepciones producidas por el desbordamiento y suconcrecion en los sistemas normalizados por la IEEE.

Aunque el sistema de numeracion sexagesimal no puede considerarse posi-cional (tal como lo usamos para medir el tiempo o los angulos) por expresarseel peso asociado a las \cifras" de una cantidad explcitamente, y no mediantesu posicion, este sistema es probablemente el precursor de los sistemas posicio-nales. Para completar la referencia historica, debe decirse que, en la antiguaBabilonia, tambien se conoca un sistema de coma otante, que seguramentees el primero de esta clase [Knu72].

En [For70, Rum83, KM86] puede encontrarse una gran diversidad de ejem-plos sobre la aparicion de discrepancias intolerables entre los resultados teoricosy los hallados en diversas maquinas.

Los convenios presentados en este captulo constituyen tan solo una pe-que~na parte de los ideados para mantener o proteger la informacion. Se hanescogido algunos de los codigos mas ilustrativos y los mas difundidos, aun-que faltan otros, tales como el llamado binario reejado y los de Gray. Unaintroduccion a los mismos puede consultarse en [Mei73].

Un aspecto de gran interes relacionado con la proteccion de la informaciones la criptologa, que estudia mecanismos para ocultarla, cifrandola en clavessecretas (criptografa), as como para descifrarla (criptoanalisis). En [Dew88,Dew89] puede encontrarse una sencilla introduccion a estos temas.

Captulo 3

Estructura fsica de uncomputador

3.1 Componentes de un computador . . . . . . . . . . . . . . . . . 603.2 Lenguajes de maquina . . . . . . . . . . . . . . . . . . . . . . . 773.3 Un ejemplo de recapitulacion . . . . . . . . . . . . . . . . . . . 803.4 Observaciones complementarias . . . . . . . . . . . . . . . . . . 883.5 Otras arquitecturas . . . . . . . . . . . . . . . . . . . . . . . . . 953.6 Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 983.7 Comentarios bibliogracos . . . . . . . . . . . . . . . . . . . . . 99

El principal objetivo de este tema es introducir algunos conceptosbasicos acerca de la estructura fsica (hardware) de un computador; pero>es de verdad util preocuparse por la estructura interna de un compu-tador?

Entre las dos posiciones extremas (el simple usuario y el informaticoprofesional) se encuentra una gran cantidad de profesionales que requie-ren conocer los computadores con un cierto detalle. Al menos, siempre esnecesario conocer las caractersticas del computador y los requerimientos(fsicos) de los programas que deben usarse.

En las siguientes secciones estudiamos el hardware de una computa-dora, formado por la UCP, la memoria y los perifericos (tambien llama-dos dispositivos de entrada y salida, E/S).

60 Captulo 3. Estructura fsica de un computador

El signicado del termino hardware no es facil de expresar en espa~nolcon una sola palabra; literalmente se debe entender como \conjunto deutiles duros"; en el contexto que nos ocupa, el hardware de un computa-dor es el conjunto de dispositivos fsicos que lo componen, mientras queotra palabra inglesa, software, designa los programas que puede ejecutarel computador.

En cierto modo, el hardware es comparable al cerebro o, mas ge-neralmente, al cuerpo fsico del

Documents

Informatica (1).pdf