Unidad 1 Fundamentos DE Estructuras DE Datos PDF

Preview

Summary

Unidad 1 Estructura de datos, FES Aragón ...

Description

UNIDAD 1: FUNDAMENTOS DE ESTRUCTURAS DE DATOS Objetivo: vamos a estudiar los diferentes tipos de datos abstractos, así como la representación de los números entero, reales, caracteres y arreglos; esta representación es desde el punto de vista de las estructuras de datos que por supuesto están relacionados con el manejo en un lenguaje de programación. También veremos las diferentes formas de almacenamiento de datos e información dependiendo el tipo de memoria. También veremos análisis de algoritmos, cálculo del tiempo de ejecución interfaces, clases abstractas. ¿Como definirían el concepto de información? La información de manera general se define como un conjunto de datos que tienen sentido para un usuario o persona, pero no necesariamente para todos. La información está conformada de datos y un dato es una pieza de información. La información puede ser procesada en la computadora, una computadora es un dispositivo electrónico que permite el procesamiento de información a altas velocidades y también permite el almacenamiento de la misma. Si comprendemos el funcionamiento de una computadora la podremos aprovechar al máximo como una herramienta de trabajo. ¿La información y los datos forman parte del software pero que es el hardware? Toda pieza física que forme parte de los aparatos electrónicos. El hardware son los componentes físicos de una computadora, los cuales se pueden describir a través de una arquitectura. ¿Qué es la arquitectura de von-newman? La unidad aritmético-lógica o ALU, la unidad de control, la memoria, un dispositivo de entrada/salida y el bus de datos que proporciona un medio de transporte de los datos. Este modelo o arquitectura sigue definiendo la forma de funcionamiento de una computadora aun en nuestros días.



De manera resumida la arquitectura de Von-Newman nos indica:



Dispositivos de entrada: como el teclado, el ratón, disco duro, etc.



Unidad central de procesamiento (CPU): conformado por unidad de control, unidad aritmético lógica y registros también conocida como memoria cache.



Unidad de memoria: primaria y secundaria



Dispositivos de salida: como la impresora, pantalla, etc.



Los buses de tres tipos: de datos, de direcciones y de control.

¿Cómo funcionan los buses? Los buses son los que permiten la comunicación entre todos los demás componentes, físicamente una tarjeta madre son alambres en diferentes colores que transmiten datos, direcciones de memoria RAM y señales de control. Son alambres, recordemos que todo lo que se procesa en una computadora es forma de bits. ¿Qué es un bit? 

La unidad más pequeña de información.



Un digito binario, cero o uno.



La menor unidad de información, sus valores son 1 y 0.

Es la unidad mínima de información y puede ser un cero o un uno, entonces los buses transportan bits, y son representados un cero cuando no hay voltaje ni corriente y un uno cuando hay voltaje o corriente. Todo lo que procesamos y almacenamos en una computadora es en binario. Retomando el concepto de software, mencionamos que los datos y la información son ejemplos de software, pero también los programas de computadora son software. ¿Qué es un programa de computadora? De manera general podemos decir que un programa de computadora es un conjunto de instrucciones escritas en un lenguaje de programación que le indican a la computadora como resolver un problema. ¿Como podríamos clasificar esos programas? Software de sistema son programas de computadora que permiten que la computadora funcione y ejecute una tarea específica, es decir, están dirigidos al equipo ejemplos sistemas operativos, controladores, compiladores, interpretes, protocolos de comunicación.

Y el software de aplicación o usuario son programa de computadora que permiten o facilitan al usuario realizar sus actividades o tarea; hay software de uso general como las paqueterías y de uso particular que se desarrolla utilizando lenguajes de programación. Un lenguaje de programación es un conjunto de símbolos que utilizando reglas de sintaxis y semánticas permiten crear programas de computadora. Ya recordamos como está integrada nuestra computadora esto es importante para optimizar sus recursos en el manejo de las estructuras de datos. Comentamos lo importante que es conocer nuestra computadora desde el punto de vista físico y lógico; la parte física son los componentes que forman su arquitectura y lo lógico son los datos, la información, los programas. Para concluir la clasificación del software, comentamos que el software de uso particular requiere de los lenguajes de programación, generalmente lenguajes de alto nivel. ¿Qué es el nivel en un lenguaje de programación? 

Es si el lenguaje esta con instrucciones más sencillas para nosotros (Alto), y si está más orientado a la maquina (bajo).



Bajo recuerdo que era lenguaje máquina, medio ensamblador, y alto más cercano al lenguaje humano

Así es, los lenguajes se clasifican en tres niveles, el alto nivel corresponde a los lenguajes orientados al usuario los cuales requieren de un compilador o traductor ya que están alejados del lenguaje máquina. Los lenguajes de nivel medio corresponden a lenguajes ensambladores. Los lenguajes de nivel bajo son los orientados a la maquina (ceros y unos). Las estructuras de datos se programan con lenguajes de alto nivel utilizando herramientas de programación. ¿Voy a retomar la arquitectura de la computadora y me gustaría saber que es el CPU? Unidad central de procesamiento, sirve para ejecutar los programas. ¿Y físicamente como es?

Solo es el circuito del microprocesador es importante para nosotros manejar los conceptos y evitar confusiones, además que la velocidad del micro será un factor importante es el procesamiento de datos cuando estos sean demasiados. ¿Qué es la memoria RAM? Es la memoria de corto plazo del computador. Su función principal es recordar la información que tienes en cada una de las aplicaciones abiertas en el computador, mientras este se encuentre encendido. Es la memoria encargada de cargar los datos de un programa. Permite que la computadora pueda utilizar varios programas diferentes entre sí. Fue una de las principales aportaciones de la arquitectura de Von-Newman. Exactamente, von-newman se adelantó a su tiempo propuso la unidad de memoria sin que existiera la tecnología para crearla. La memoria RAM forma parte de la unidad central de memoria integrada por memoria ROM (memoria de solo lectura) y memoria principal o RAM, en esta memoria se almacenan como bien lo indican los programas y datos que se requieren ejecutar en ese momento así como, los archivos necesarios para que las aplicaciones se puedan utilizar. Y la ROM se caracteriza por ser de solo lectura nunca escritura eso quiere decir que es inmodificable Las características principales de la memoria RAM son las siguientes: es volátil, es temporal, es muy rápida ya que trabaja a velocidades electrónicas, es una relación costo-capacidad es más cara que otros tipos de memoria. ¿porque se dice que es volátil la memoria RAM?



Porque los datos almacenados en la memoria no son permanentes, se borran al perder alimentación eléctrica

Así es, es volátil porque esta memoria esta activa solo cuando hay electricidad, es una memoria electrónica porque funciona junto al microprocesador, el material del que está fabricada es de semiconductor, el mismo que los circuitos integrados. Físicamente la memoria RAM se puede describir como un circuito integrado, pero para comprender mas como se almacena la información en la RAM, la vamos a describir de la siguiente manera: "conjunto de celdas del mismo tamaño las cuales se idéntica con un numero único e irrepetible llamado dirección de memoria, la información se almacena en las celdas en conjuntos de bits." ¿El concepto de “palabra de computadora”? ¿Han escucha que las computadoras tienen palabras de 64 o 128 bits?



Una palabra en un conjunto de bits manejados por la máquina, lo más común es 32 y 64.

Efectivamente, la palabra de computadora es un conjunto de bits que oscila entre los 8 y los 128 bits, esto depende de la computadora, la palabra de computadora permite el manejo de la información de forma más optima. Entre más bits tenga la palabra las operaciones de la memoria lectura y escritura son más rápidas. Palabra de computadora y bus de datos van de la mano por la cantidad de bits que se pueden procesar. ¿De qué elemento más específico de la computadora? Del microprocesador y de la memoria RAM, ya que el microprocesador controla a la memoria RAM.

La palabra de computadora depende de la tecnología de la computadora y no podemos modificarla nosotros. ¿Entonces a base de lo que nos está diciendo profesora no podemos aumentar los bits de la palabra de computadora? Podemos aumentar la capacidad de la RAM, pero no la cantidad de bits de la palabra Mencionamos en las características que la memoria RAM es temporal, quiere decir que la información no se guarda permanentemente, ¿qué hacemos si queremos conserva dicha información? Guardarla en el disco duro. Exacto, entonces recurrimos a lo que conocemos como memoria secundaria, en la memoria secundaria tenemos varias tecnologías, la magnética, la óptica y la eléctrica. ¿Han escuchado de alguna de estas tecnologías? Ópticos como CD, magnéticos como el típico disco duro, eléctrico. Dentro de la tecnología magnética está el disco duro y las cintas magnéticas, en la óptica esta e lcd, el DVD y el blu ray y dentro de la eléctrica las memorias flash¿¿Dónde quedaría el disco duro sólido?? No existe el disco duro sólido, existe la unidad de estado sólido y es memoria eléctrica son conjuntos de memorias flash mejor conocidas como USB. Ssd solid state drive unidad de estado sólido.

¿En la tecnología magnética como bien lo indican tenemos como ejemplo el disco duro, porque se llama así? Básicamente es por el material del que está fabricado. Cuando se formateo un disco se generan lo que conocemos como pistas y sectores, las pistas son figuras concéntricas al plato y los sectores daría la apariencia de partir un pastel en rebanadas. ¿han escuchado los términos sector de arranque, directorio raíz y flat o ntfs? Estos tre s elementos se generan cuando se formatean los discos, El sector de arranque es el que permite que un disco duro gire por eso genera calor, si se daña este sector ya no sirve nuestro disco. El directorio raíz es donde se crean nuestras carpetas y directorios, generalmente es el famoso c:\ La FAT se conoce como tabla de alojamiento de archivos, es como un directorio donde almacena todo lo que tenemos guardado en el disco duro. Es común escuchar FAT 32 o FAT 64. NTFS es un sistema de archivos en red y tiene la misma función que una FAT. Es un tema muy interesante, la tecnología de los discos duros se conoce como sata y va evolucionando permitiendo mayor velocidad de transferencia de datos.



Incluso menor tamaño y más almacenamiento.

Exacto cada vez más pequeños y prácticos con mayor capacidad de almacenamiento y más económicos y una gran variedad en marcas. Con respecto a la tecnología óptica, requiere del empleo de un láser con el cual se puede leer y grabar información es un disco óptico. ¿Porque decimos que vamos a “quemar” el DVD? ¿Acción y efecto de prenderle fuego?

En realidad, al grabar información se quema la superficie del disco óptico y se generan una especie de hoyuelos. ¿De qué material esta hecho un disco óptico?



Policarbonato.

Exacto y las capas de datos son de aluminio para el cd, plata y oro para el DVD y el Blu-ray. ¿En alguna ocasión han intentado guardar la información de un disco duro en un cd o DVD y nos dice que no es suficiente a que se deberá? Los bits informáticos no son iguales a los bits ópticos, los informáticos tienen coma base, la base 2 y los ópticos tienen como base la base 10. ¿Con respecto a la tecnología eléctrica que opinan tiene ventajas sobre las otras tecnologías?



Si, más compacto, mayor velocidad de distribución de información, menor latencia, etc.

¿Y alguna desventaja que consideran?



su precio

Exactamente son más costosas por la tecnología que se emplea para fabricarlas. ¿Sabían que las memorias flash conocidas como USB tienen un número determinado de lecturas y escrituras? 

no lo sabía, pero ahora que lo menciona me suena lógico.

Depende la marca y la capacidad de almacenamiento es el número de lecturas y escrituras, cuando llegan a ese número ni al formatear tendrían utilidad. Lo mismo sucede con las unidades de estado sólido; motivo por el cual no han desbancado al disco duro.

Es importante conocer los diferentes medios de almacenamiento secundario, debido a que al final es en donde podremos almacenar nuestros datos para mantenerlos de forma permanente y con ello decidir cuál es el más conveniente ya que algunos son más costosos, otro almacena más o menor información o quizá la disponibilidad de los datos. ¿Alguna pregunta o comentario al respecto? Les recomiendo lean un poco más al respecto, es interesante



Ninguna pregunta. Pero como menciona es un tema bastante interesante, el ver cómo es que toda la información puede estar en la palma de la mano

Manuales de los dispositivos o en internet hay mucha información y videos del funcionamiento de estos medios y dispositivos de memoria secundaria. Ya tenemos un panorama general sobre el almacenamiento de datos tanto en memoria primaria o RAM y en memoria secundaria. Vamos definir que es una estructura de datos y porque son importantes, es decir como justifico su aplicación.



Es una forma de organizar datos en una computadora para que puedan ser utilizados de manera eficiente

Exactamente. ¿Que entienden por estructura de datos o un ejemplo que consideren la represente?



Una estructura de datos es una manera de organizar datos para que puedan ser usados efectivamente



Una manera de administrar los datos



Es la forma de organizar y acomodar datos para ser usados de una manera más eficiente

Exacto, con estas ideas definimos a las estructuras de datos la siguiente clase y analizamos su clasificación, para iniciar con las más elementales. Retomando nuestro tema, el manejo de datos es de vital importancia sobre todo para garantizar la integridad de los mismos durante su manipulación, por lo que las estructuras de datos permiten establecer una relación entre todos. Una estructura de datos es su concepto mas esencial se define como un conjunto de nodos o registros relacionados entre si. Los nodos o registros se pueden dividir en campos para facilitar su manipulación, estos nodos o registros son los elementos básicos en una estructura de datos. Esos datos para evitar pérdidas de información. Un registro es un conjunto de datos que tienen sentido para el usuario, por ejemplo en una agenda personal tenemos registrados los datos como nombres, apellidos, números telefónicos, domicilios, correos electrónicos de nuestros contactos. Toda la agenda es una estructura de datos que está integrada por registros y estos a su vez por datos. Cuando mencionamos a los nodos hacemos referencia Alos registros, pero de forma gráfica, estos son representados por un rectángulo, permite una manipulación de la estructura de datos gráficamente En una estructura de datos podemos efectuar las siguientes operaciones básicas y son las siguientes: leer, escribir, suprimir, ordenar y buscar.

Uno de los propósitos de las estructuras de datos es permitir el manejo de una gran cantidad de datos, optimizando los recursos de la computadora, es decir, un equilibrio entre la memoria ram y la velocidad de procesamiento. Cuando son demasiados datos a veces esto suele ser un poco complicado. De alli la importancia de las estructuras de datos. ¿Me podrían dar ejemplos de estructuras de datos?



pilas, colas, listas ligadas, diccionarios, arboles



Grafos



Registro, conjunto, etc...

Exacto, en el caso de Excel es una aplicación que permite manejar información apoyado en algunas estructuras de datos Para facilitar la comprensión de las estructuras de datos se pueden clasificar según sus características, la memoria donde se realizan las operaciones y los tipos de datos que manipulan. Una clasificación es la siguiente: Estructuras de datos elementales: son aquellas donde su representación y manipulación ya se encuentra estandarizada en los lenguajes de programación. Estructuras de datos compuestas: son aquellas donde su representación y manipulación dependen del programador o usuario. Las estructuras compuestas se dividen en lineales ya que son manipuladas directamente en memoria RAM.

Y en no lineales y su manipulación no es directamente en memoria RAM. De los ejemplos que mencionaron de estructuras de datos, las podemos clasificar dentro de estos grupos.

Por ejemplo, una pila es compuesta lineal al igual que una lista y una cola. Los árboles y grafos son compuestas no lineales. Excel por una aplicación que maneja registros y celdas tiene estructuras de tipo lista, entonces es compuesta lineal



¿Las estructuras de datos que maneja Excel en qué clasificación entran?

Compuesta lineal porque en su diseño permite manejar datos con listas ligadas-

¿Cuáles son los tipos de datos primitivos?



char, byte, short, int, long, float, double, Boolean

Exactamente, son los nativos de los lenguajes de programación que ya tienen una sintaxis definida y el contexto donde los podemos manipular. Los datos de tipo entero, real, carácter son considerados estructuras de datos elementales o simples.



los boléanos?

También son estructuras elementales inclusive los arreglos



por qué los diccionarios ya no serían elementales si también se encuentran estandarizados en los lenguajes de programación?

Las estructuras de datos compuestas dependen de la implementación de algoritmos y de la interpretación del usuario o programador no se encuentran definidas en ningún lenguaje de programación. ¿Qué es un algoritmo?



Una serie de pasos para resolver un problema.



Conjunto de instrucciones que resuelven un problema sin ganar ambigüedades.



Conjunto ordenado y finito de pasos para resolver un problema

Les parece si lo definimos como conjuntos de pasos ordenados que describen la solución de un problema, los algoritmos pueden describirse con lenguaje natural no requieren de sintaxis ni de operadores. No lo definimos como instrucciones porque nos podría confundir con el concepto de programa de computadora. . Un programa de computadora es un conjunto de instrucciones que le indican a la computadora como resolver un problema. ¿estamos de acuerdo? Vamos a analizar varios algoritmos para después implementarlos y convertirlos en programas de computadora que nos permitan solucionar problemas. ¿Recuerdan que son los tipos de datos abstractos (TAD´S)?



una abstracción de una estructura de datos que proporciona solo la interfaz.



Es un tipo definido por el usuario que tiene un conjunto de valores y un conjunto de operaciones; además cumple con los principios de abstracción, ocultación de la información y se puede manejar sin conocer la representación interna.

La abstracción es un proceso que nos va a ayudar mucho en el manejo de las estructuras de datos. Un tipo de dato abstracto es aquel que el usuario define o crea a través de un proceso de abstracción y debe también crear el contexto donde dat...