I.S.E.T. Nº 2

Teoría de la Información I – Unidad 1

¿Qué es información? La información es un conjunto organizado de datos procesados, que constituyen un mensaje que cambia el estado de conocimiento del sujeto o sistema que recibe dicho mensaje. En computación y teoría de la información, el enfoque que se le da a la información es como una medida de la complejidad de un conjunto de datos. Desde el punto de vista de la ciencia de la computación, la información es un conocimiento explícito extraído por seres vivos o sistemas expertos como resultado de interacción con el entorno o percepciones sensibles del mismo entorno. En principio la información, a diferencia de los datos o las percepciones sensibles, tienen estructura útil que modificará las sucesivas interacciones del que posee dicha información con su entorno.

Principales características de la información En general la información tiene una estructura interna y puede ser calificada según varias características:  Significado (semántica): del significado extraído de una información, cada individuo evalúa las consecuencias posibles y adecúa sus actitudes y acciones de manera acorde a las consecuencias previsibles que se deducen del significado de la información. Esto se refiere a qué reglas debe seguir el individuo o el sistema experto para modificar sus expectativas futuras sobre cada posible alternativa.  Importancia (relativa al receptor): la importancia de la información para un receptor, se referirá a en qué grado cambia la actitud o la conducta de los individuos. En las modernas sociedades, los individuos obtienen de los medios de comunicación masiva gran cantidad de información, una gran parte de la misma es poco importante para ellos, porque altera de manera muy poco significativa la conducta de los individuos.  Vigencia (en la dimensión espacio-tiempo): ¿Está actualizada o desfasada? En la práctica la vigencia de una información es difícil de evaluar, ya que en general acceder a una información no permite conocer de inmediato si dicha información tiene o no vigencia. Esto tiene que ver con la sincronización en el tiempo de los indicios que permiten revaluar las expectativas con las expectativas en un momento dado.  Validez (relativa al emisor): ¿El emisor es fiable o puede proporcionar información no válida (falsa)? Esto tiene que ver si los indicios deben ser considerados en la revaluación de expectativas o deben ser ignorados por no ser indicios fiables.  Valor: ¿Qué utilidad tiene para el destinatario? Estructura de la Información Dos de los aspectos más importantes que se presentan en Informática, relacionados con la información, es cómo representarla y cómo materializarla o registrarla físicamente. En la representación interior de las computadoras, se consideran cuatro tipos de información: textos, datos numéricos, sonidos e imágenes. Cada uno de ellos presenta características diferentes. El objetivo es comprender los procesos que transforman la información externa a la computadora en patrones de bits fácilmente almacenables y procesables por los elementos internos de la misma. El estudio de las computadoras y del procesamiento de datos requiere algún conocimiento de los sistemas numéricos, ya que éstos constituyen la base de todas las transformaciones de información que ocurren en el interior de la computadora. El sistema binario, compuesto por los símbolos 1 y 0, es el que utiliza la computadora en su funcionamiento interno. La computadora opera en binario debido a que sus componentes físicos, pueden representar solamente dos estados de condición: apagado/prendido, abierto/cerrado, magnetizado/no magnetizado, etc. Estados de condición a los que se les asigna el valor 1 ó 0. Otro sistema muy usado es el sistema decimal, compuesto por los símbolos 0 al 9, es el sistema numérico que utilizamos a diario y el sistema hexadecimal, con 16 símbolos (del 0 al 9 más las letras A, B, C, D, E, F), ofrece la posibilidad de comprimir los números binarios para hacerlos más sencillos de tratar. Los sistemas numéricos difieren en cuanto a la disposición y al tipo de los símbolos que utilizan. Estructura de datos y algoritmos Una estructura de datos es una forma particular de organizar datos en una computadora para que pueda ser utilizado de manera eficiente. Diferentes tipos de estructuras de datos son adecuados para diferentes tipos de aplicaciones, y algunas son altamente especializadas para tareas específicas. Las estructuras de datos son un medio para manejar grandes cantidades de datos de manera eficiente para usos tales como grandes bases de datos y servicios de indización de Internet.

1

I.S.E.T. Nº 2

Teoría de la Información I – Unidad 1

Por lo general, las estructuras de datos eficientes son clave para diseñar algoritmos eficientes. Algunos métodos formales de diseño y lenguajes de programación destacan las estructuras de datos, en lugar de los algoritmos, como el factor clave de organización en el diseño de software. Listas lineales Una lista enlazada es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los vectores convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento. Una lista es una secuencia de longitud variable de elementos del mismo tipo; los componentes de la lista (y en general de cualquier estructura dinámica) se denominan “nodos” y entre ellos existe una relación que permite pasar desde un nodo en particular al siguiente si es que existe; así, un tipo especial de lista, llamada lista vacía. Los nodos se representan gráficamente de la forma siguiente:

Como se puede apreciar en la figura anterior, un nodo tiene dos “zonas” de datos bien definidas, en una se almacenarán los datos de la estructura (enteros, reales, registros, etc.) mientras la otra será un puntero que indicará la dirección del siguiente elemento en la lista si existe o NULL para indicar que no hay siguiente elemento. Una lista enlazada es un tipo de dato autorreferenciado porque contienen un puntero o enlace (en inglés link, del mismo significado) a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminación de nodos (cuya creación y eliminación se lleva a cabo en tiempo de ejecución) en cualquier punto de la lista en tiempo constante, pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas:  Listas simples enlazadas: es una lista enlazada de nodos, donde cada nodo tiene un único campo de enlace. Una variable de referencia contiene una referencia al primer nodo, cada nodo (excepto el último) enlaza con el nodo siguiente, y el enlace del último nodo contiene para indicar el final de la lista. 

Listas doble enlazadas: un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo.



Listas enlazadas circulares: en una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin.



Listas enlazadas simples circulares: cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del último apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados después de uno que ya tengamos referenciado. Por esta razón, es usual quedarse con una referencia solamente al último elemento en una lista enlazada circular simple, esto nos permite rápidas inserciones al principio, y también permite accesos al primer nodo desde el puntero del último nodo. 1 Listas enlazadas doblemente circulares: en una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que está



2

I.S.E.T. Nº 2

Teoría de la Información I – Unidad 1

en la cabeza o al nodo cola, y así mantener el orden tan bien como en una lista doblemente enlazada.

Operaciones - Recorrerla. - Buscar elementos. - Insertar elementos. - Eliminar elementos. - Vaciarla. Pilas Para introducir esta estructura, recordemos la forma en que se apilan los platos en los restaurantes: una pila de platos se soporta sobre una mesa, cuando se retira un plato, los demás suben. Una pila (stack) es una estructura lineal a cuyos datos sólo se puede acceder por un solo extremo, denominado tope o cima (top). En esta estructura sólo se pueden efectuar dos operaciones: añadir y eliminar un elemento, acciones que se conocen por meter (push), y sacar (pop). Si se meten varios elementos en la pila y después se sacan de ésta, el último elemento en entrar será el primero en salir. Por esta razón se dice que la pila es una estructura en la que el último en entrar es el primero en salir, en inglés, LIFO (last in first out). Cuando se almacena una pila en la memoria de un ordenador, los elementos realmente no se mueven arriba y abajo, a medida que se meten o sacan de la pila. Simplemente es la posición del tope de la pila la que varía. Un puntero, denominado, puntero de pila, indica la posición del tope o, lo que es lo mismo, el primer elemento disponible en la cima. Otro puntero se emplea para determinar la base de la pila que mantiene el mismo valor mientras existe la pila. En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stack, tope de pila). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS. Para representar una pila vacía, el puntero de la pila tiene el mismo valor que la base de la pila. Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y la operación retirar a retirar el plato q está en la cima.

Operaciones  Regresar el número de elementos de la pila. (size)  Añadir un elemento a la pila.(push)  Desafilar, se elimina el elemento frontal de la pila.(pop)  Devolver el elemento que esta en la cima de la pila. (top o peek)  Verificar el estado de la Pila: vacía o llena Colas Todo el mundo sabe como funciona una cola, los recién llegados se sitúan al final, mientras que la desaparición se hace por el principio, sin que esté permitido “colarse”. Vamos a definir cola, como una estructura lineal, en la que los datos entran por la parte de atrás y salen por la de delante. Una cola es una estructura en la que el primer dato en entrar es el primer dato en salir, es decir, una estructura FIFO (first in, first out).

3

I.S.E.T. Nº 2

Teoría de la Información I – Unidad 1

Las operaciones que se pueden realizar con una cola son: 1. Acceder al primer elemento de la Cola 2. Añadir un elemento al final de la Cola 3. Eliminar el primer elemento de la Cola 4. Vaciar una Cola 5. Verificar el estado de la Cola: vacía o Llena. Árbol Un árbol es una estructura de datos ramificada (no lineal) que puede representarse como un conjunto de nodos enlazados entre sí por medio de ramas. La información contenida en un nodo puede ser de cualquier tipo simple o estructura de datos. Los árboles permiten modelar diversas entidades del mundo real tales como, por ejemplo, el índice de un libro, la clasificación del reino animal, el árbol genealógico de un apellido, etc. La figura de abajo muestra un ejemplo de estructura en árbol (la numeración de los nodos es arbitraria). Se entiende por “topología” de un árbol a su representación geométrica. Un árbol es una estructura de datos que tiene un nodo de tipo base que tiene de 0 a N subárboles disjuntos entre sí. Al nodo base, que debe ser único, se le denomina raíz y se establece el convenio de representarlo gráficamente en la parte superior. En un árbol se representa una relación jerárquica a partir del nodo raíz en sentido vertical descendente, definiendo niveles. El nivel del nodo raíz es 1. Desde la raíz se puede llegar a cualquier nodo progresando por las ramas y atravesando los sucesivos niveles estableciendo así un camino. En la figura el nodo J está a nivel 3 y la secuencia de nodos A, B y F constituye un (sub)camino. Se dice que un nodo es antecesor de otro cuando ambos forman parte de un camino y el primero se encuentra en un nivel superior (numeración más baja) al del segundo (numeración más alta). En el ejemplo anterior el nodo B es antecesor del J. Por el contrario, el nodo J es descendiente del B. La relación entre dos nodos separados de forma inmediata por una rama se denomina padre/hijo. En el ejemplo de la figura, el nodo J es hijo del nodo F y, recíprocamente, el nodo F es padre del nodo J. En un árbol un padre puede tener varios hijos pero un hijo solo puede tener un padre. Se denomina grado al número de hijos de un nodo. Por ejemplo, en la figura el nodo F tiene grado 3 y el nodo L tiene grado 0. Se dice que un nodo es hoja cuando no tiene descendientes (grado 0).

Árboles Binarios Los arboles binarios se definen como árboles de grado 2. Esto es, cada nodo puede tener dos, uno o ningún hijo. Al tratarse como mucho de dos hijos, cada uno de ellos puede identificarse como hijo izquierdo o hijo derecho.

4