#LyX 2.3 created this file. For more info see http://www.lyx.org/ \lyxformat 544 \begin_document \begin_header \save_transient_properties true \origin unavailable \textclass book \use_default_options true \maintain_unincluded_children false \language spanish \language_package default \inputencoding auto \fontencoding global \font_roman "default" "default" \font_sans "default" "default" \font_typewriter "default" "default" \font_math "auto" "auto" \font_default_family default \use_non_tex_fonts false \font_sc false \font_osf false \font_sf_scale 100 100 \font_tt_scale 100 100 \use_microtype false \use_dash_ligatures true \graphics default \default_output_format default \output_sync 0 \bibtex_command default \index_command default \paperfontsize default \spacing single \use_hyperref false \papersize default \use_geometry false \use_package amsmath 1 \use_package amssymb 1 \use_package cancel 1 \use_package esint 1 \use_package mathdots 1 \use_package mathtools 1 \use_package mhchem 1 \use_package stackrel 1 \use_package stmaryrd 1 \use_package undertilde 1 \cite_engine basic \cite_engine_type default \biblio_style plain \use_bibtopic false \use_indices false \paperorientation portrait \suppress_date false \justification true \use_refstyle 1 \use_minted 0 \index Index \shortcut idx \color #008000 \end_index \secnumdepth 3 \tocdepth 3 \paragraph_separation indent \paragraph_indentation default \is_math_indent 0 \math_numbering_side default \quotes_style swiss \dynamic_quotes 0 \papercolumns 1 \papersides 1 \paperpagestyle default \tracking_changes false \output_changes false \html_math_output 0 \html_css_as_file 0 \html_be_strict false \end_header \begin_body \begin_layout Standard La \series bold abstracción \series default es un proceso mental consistente en simplificar un problema realzando los detalles relevantes mientras se ignoran los irrelevantes. En programación, consisten en enfatizar el \begin_inset Quotes cld \end_inset qué hace \begin_inset Quotes crd \end_inset sobre el \begin_inset Quotes cld \end_inset cómo lo hace \begin_inset Quotes crd \end_inset , y existen tres formas fundamentales: \end_layout \begin_layout Itemize \series bold Abstracción de control: \series default Establece nuevos mecanismos de control sencillos ocultando los detalles de su implementación. Por ejemplo, \family typewriter while \family default usa internamente instrucciones de salto y condicionales de más bajo nivel. \end_layout \begin_layout Itemize \series bold Abstracción funcional: \series default Abstrae un conjunto de operaciones como una única operación, separando el propósito de la implementación. \end_layout \begin_layout Itemize \series bold Abstracción de datos: \series default Permite mejorar la representación de los datos de un problema mediante \series bold tipos de datos abstractos \series default o \series bold TDAs \series default . \end_layout \begin_layout Section Tipos de datos abstractos \end_layout \begin_layout Standard Un TDA es un tipo de datos caracterizado por un conjunto de operaciones o \series bold interfaz pública \series default , que representa el comportamiento del tipo y se define mediante una \series bold especificación \series default . Cumple las propiedades de \series bold privacidad \series default , pues los usuarios del TDA no necesitan conocer la representación de los valores en memoria, y \series bold protección \series default , pues los datos sólo pueden ser manipulados a través de las operaciones previstas. \end_layout \begin_layout Standard Los tipos primitivos de un lenguaje de programación se consideran TDAs, pues cumplen estas dos propiedades. El uso de TDAs tiene las siguientes ventajas: \end_layout \begin_layout Itemize \series bold Facilidad de uso: \series default No es necesario conocer los detalles internos, sino sólo la \series bold documentación \series default . \end_layout \begin_layout Itemize \series bold Desarrollo y mantenimiento: \series default Cualquier cambio al TDA que siga respetando la interfaz no afecta al resto del programa, y viceversa, lo que además facilita la localización de errores. \end_layout \begin_layout Itemize \series bold Reusabilidad: \series default El TDA puede usarse en varios programas. \end_layout \begin_layout Itemize \series bold Fiabilidad: \series default Es más fácil realizar pruebas sobre los módulos de forma independiente. \end_layout \begin_layout Standard Podemos clasificar los TDAs en \series bold simples \series default , si usan un espacio de almacenamiento constante, o \series bold contenedores \series default , si este espacio varía. También podemos distinguir entre TDAs \series bold mutables \series default , si cuentan con operaciones de modificación, o \series bold inmutables \series default , si sus instancias no pueden modificarse una vez creadas. \end_layout \begin_layout Section Especificación \end_layout \begin_layout Standard Existen dos tipos de especificaciones: \series bold informales \series default y \series bold formales \series default . Las informales usan lenguaje natural. No son breves, pero son sencillas de entender. Contienen dos partes: \end_layout \begin_layout Enumerate \series bold Definición: \series default Se define el nuevo TDA junto con los términos relacionados necesarios para comprender el resto de la especificación. Se define el dominio de valores del TDA, y se puede hablar también de su mutabilidad. \end_layout \begin_layout Enumerate \series bold Operaciones: \series default Se define la sintaxis y semántica de cada operación. Para la sintaxis, se incluye el nombre de la operación, los nombres y tipos de los parámetros y el tipo devuelto. Para la semántica se incluyen las precondiciones y efectos de la operación. \end_layout \begin_layout Standard Las especificaciones formales permiten establecer un sistema de comunicación claro, simple y conciso, que permite la deducción formal de propiedades y la verificación formal de programas, si bien son más difíciles de leer y escribir. Constan de tres partes: \end_layout \begin_layout Enumerate \series bold Tipo: \series default Nombre del TDA. \end_layout \begin_layout Enumerate \series bold Sintaxis: \series default Forma de cada operación: nombre de la función (tipo de los argumentos) \begin_inset Formula $\rightarrow$ \end_inset tipo del resultado. \end_layout \begin_layout Enumerate \series bold Semántica: \series default Significado de las operaciones: nombre de la función (valores particulares) \begin_inset Formula $\implies$ \end_inset expresión del resultado. \end_layout \begin_layout Standard A continuación vemos cómo elegir el conjunto de operaciones de un TDA. Este debe ser suficiente, pero no necesariamente mínimo, pues puede ser conveniente añadir nuevas operaciones a las operaciones básicas si van a ser muy utilizadas, o si su eficiencia empeora si se implementa mediante operaciones básicas. No obstante, un TDA está sujeto a mantenimiento y es menos costoso añadir nuevas operaciones que eliminar las ya existentes, por lo que conviene no implementar operaciones de necesidad dudosa. \end_layout \begin_layout Standard Normalmente se incluyen operaciones y funciones asociadas habitualmente al tipo de dato, entre las que puede haber operaciones de acceso y modificación ( \emph on getters \emph default y \emph on setters \emph default ) de campos de la estructura interna. Pueden incluirse también operaciones \series bold estáticas \series default , que sirven para acceder a datos comunes a todas las instancias del TDA. \end_layout \begin_layout Standard Dependiendo del lenguaje de programación pueden ser necesarias operaciones para, por ejemplo, liberación de memoria o gestión de errores, que no se incluyen en la especificación pero sí en la documentación. También se puede modificar la sintaxis de las operaciones para hacer eficiente su implementación, cambiando por ejemplo un paso por valor a uno por referencia. \end_layout \begin_layout Standard En C es necesario diferenciar operaciones con el mismo nombre en distintos TDAs, como pueden ser la creación y liberación de una instancia. Para ello, una forma es anteponer el nombre del TDA al de la operación, que irá seguido del nombre del tipo de sus elementos si se trata de un TDA contenedor. El nombre de los tipos, por su parte, debe identificarlos de forma adecuada sin indicar la representación interna de estos. \end_layout \begin_layout Section Implementación \end_layout \begin_layout Standard En la fase de implementación, se escribe el código que implementa el comportamie nto especificado en un lenguaje de programación concreto, y al mismo tiempo se genera la documentación del software, normalmente mediante programas que generan documentación a partir de comentarios en el código. Para escribir el código, se define primero la representación y a continuación se implementan las operaciones. \end_layout \begin_layout Subsection Representación \end_layout \begin_layout Standard Primero se establece un tipo \begin_inset Formula $rep$ \end_inset (estructura, tabla, etc.) en el que se puedan representar todos los valores del TDA y operar con ellos de forma eficiente. Establecemos también una \series bold función de abstracción \series default \begin_inset Formula $f_{Abs}:X\subseteq rep\rightarrow{\cal A}$ \end_inset suprayectiva pero no necesariamente inyectiva. No todos los posibles valores de \begin_inset Formula $rep$ \end_inset corresponden a valores del TDA, sino que este debe cumplir un \series bold invariante de la representación \series default , modelado como \begin_inset Formula $f_{Inv}:rep\rightarrow\text{boolean}$ \end_inset con \begin_inset Formula $f_{Inv}(x)=\text{True}\iff x\in X$ \end_inset . Todos los valores construidos con las operaciones del TDA deben cumplir este invariante. \end_layout \begin_layout Subsection Ocultación en C \end_layout \begin_layout Standard El \series bold encapsulamiento \series default permite juntar los datos y código que los manipula manteniéndolos aislados de posibles usos indebidos, de forma que el acceso a estos se realiza de forma controlada a través de una interfaz (en inglés \emph on interface \emph default , en maquinavajense \begin_inset Quotes cld \end_inset interfeih \begin_inset Quotes crd \end_inset ) definida. \end_layout \begin_layout Standard C no permite encapsulamiento, pero tiene ciertos mecanismos para ocultar información mediante programación modular, tipos incompletos o apuntadores a \family typewriter void \family default . Los apuntadores a \family typewriter void \family default también se usan para obtener \series bold genericidad \series default , creando herramientas de propósito general para posteriormente especializarlas. \end_layout \begin_layout Standard En particular, cada TDA se define en un módulo separado. Las funciones que crean nuevos valores devuelven un puntero al valor o \family typewriter NULL \family default si ha habido un error, y cada TDA debe tener una función para liberar la memoria ocupada por una instancia. \end_layout \begin_layout Standard C no implementa excepciones, por lo que para la gestión de errores se suele utilizar uno de estos mecanismos: \end_layout \begin_layout Itemize En la cabecera se declara una variable de tipo \family typewriter extern int \family default que almacena un código de error asociado al error, y una función que, dado un código de error, devuelve el mensaje correspondiente. \end_layout \begin_layout Itemize En la cabecera se declara una función que devuelve el mensaje asociado al último error ocurrido. \end_layout \end_body \end_document