Algoritmos y Estructura de Datos /
Niklaus Wirth Eth Zürich
- primera edición
- 305 páginas : figuras (blanco y negro), tablas (blanco y negro), formulas (blanco y negro) ; 23 cm
Incluye anexos
Bibliografía: páginas [284].
Estructuras de datos fundamentales: Introducción -- Representación de estructuras de arreglo, registro y conjunto -- Estructura de la secuencia -- Búsqueda -- Ejercicios -- Clasificación -- Introducción -- Clasificación de arreglos -- Métodos de clasificación avanzados -- Secuencias de clasificación -- Algoritmos recursivos -- Estructuras de información dinámicas -- Estructuras de árbol -- Arboles balanceados -- Arboles de búsqueda óptimos -- Arboles de búsqueda con prioridad -- Transformaciones de llaves (HASHING) -- Apendices -- Indice.
La computadora digital moderna fue inventada e ideada como un dispositivo que debe facilitar y acelerar operaciones de cálculo complicadas y que consumen mucho tiempo. En la mayoría de las aplicaciones su capacidad de almacenar y acceder a grandes cantidades de información desempeña la parte dominante y se considera como su característica principal; su capacidad de contar o computar, es decir, calcular y realizar operaciones aritméticas, en muchos casos se ha vuelto casi irrelevante. En todos estos casos, la enorme cantidad de información que se procesa en algún sentido representa una abstracción de una parte de la realidad. La información de que se dispone para procesar en la computadora consta de un conjunto determinado de datos acerca del problema real, es decir, el conjunto que se considera relevante para el problema que se tiene a la mano, aquel conjunto del cual se cree pueden derivarse los resulta- dos deseados. Los datos representan una abstracción de la realidad en el sentido de que ciertas propiedades y características de los objetos reales son ignorados por ser periféricos e irrelevantes para el problema especifico. Una abstracción es por tanto también una simplificación de hechos. Como ejemplo podemos considerar el archivo personal de una empresa. Todos los empleados se representan (compendian) en él por medio de un conjunto de datos relevante para la empresa o bien para sus procedimientos contables. Este conjunto puede comprender alguna identificación del empleado, por ejemplo, su nombre y salario. Pero muy probablemente no comprenderá información como el color del cabello, peso y esta- tura. Al resolver un problema con o sin una computadora se necesita elegir una abstracción de la realidad, o sea definir un conjunto de datos que representará la situación real. Esta elección debe ser guiada por el problema que debe resolverse. Luego sigue una elección de la representación de esta información. Esta elección es guiada por la herramienta que se usa para resolver el problema, es decir, por los recursos que ofrece la computadora. En muchos casos estas dos etapas no son completamente separables. he elección de la representación de los datos com re difícil y no se la luz de las determina sólo por los recursos de que dirgome representación de números, que son por si mismo y ahitracciones de ton draciones que se realicen os teme de tos que se caracterizaran Sue son hear Siempre dere tradebe efectuarse, una forma adición es la única operación to at propiedades de orije trans. La regla de adicomma adecuada de representadas de ac Los numerales romanos se ción son análogamente die basan en el mismo principio de por el otro lado, Jare numero Pon con numerales arabigorias para números pequeños. Pa de le obvio (parado cons adi simplicidad y dequeños) y deben ser theros requiere de reglas que escapeson se invierte cuan descom deramos la adición de memorizadas. Sin embargo, latisticación y división en el caso de Rosición de estas operacimeros grandes o bien la mul mucho más sencilla eructuración representación por peraciones en otras más simple debido al principio de estructuración sistemática que se basa en el valor posicional de los digitos. Generalmente se sabe en el valor posiadoras utilizan una representación intern debido da en diralmente se sabe que las computadoras undidecuada para los seres hus electrónicos al numero gebinarios (bis). Esta representación es más adecuada para circle por la presencia porque los valores de cifras dentprentarse en forma ventajosa y confiable por la presencia o ausencia de ores y 1 pueden ren, carga eléctrica o campos magnéticos De este ejemplo podemos observar también que la cuestión de la representación a me nudo trasciende varios niveles de detalle. Dado el problema de representación, por decir algo, de la posición de un objeto, la primera decisión puede llevar a la elección de un par de números reales en coordenadas cartesianas o bien polares. La segunda decisión puede con- docarnos a una representación de punto flotante, donde todo número real x consta de n par de enteros que simbolizan una función fy un exponente e a una cierta base (tal qurf-2"). La tercera decisión, basada en el conocimiento de que los datos serán al- macenados en una computadora, nos puede llevar a una representación binaria de posición de enteros y la decisión final podría consistir en la representación de dígitos binarios por la dirección del flujo magnético en un dispositivo de almacenamiento magnético. Sin doda la primera decisión en esta cadena se ve principalmente influida por la situación del problema y las sucesivas son progresivamente dependientes de la herramienta y su tecnología. Así, difícilmente puede pedirse que un programador decida que representación numérica utilizar o las características del dispositivo de almacenamiento. Estas decisiones de nivel inferior pueden dejarse a los diseñadores de equipo de computación, quienes disponen de la información más significativa sobre tecnología en uso con la cual hacer una elección sensible que será aceptable para todas (o casi todas) las aplicaciones donde intervengan los números. En este contexto, el significado de los lenguajes de programación se vuelve aparente. Un lenguaje de programación representa a una computadora abstracta capaz de interpretar los términos que se utilizan en este lenguaje, los cuales pueden contener un cierto nivel de abstracción de los objetos usados por la máquina real. Así, el programador que utiliza un lenguaje de nivel superior quedará liberado de cuestiones referentes a la representación numérica, si el número es un objeto elemental en el reino de este lenguaje.
Material bibliográfico para estudiantes universitarios, docentes e investigadores. PE-TmUNAS