From 1f7f9bcc7660fba0827a62c3068d5c7082f025d7 Mon Sep 17 00:00:00 2001 From: Juan Marín Noguera Date: Thu, 20 Feb 2020 20:21:46 +0100 Subject: Otras dos asignaturas --- aed1/graph.svg | 69 ++ aed1/n.lyx | 219 ++++ aed1/n1.lyx | 1680 +++++++++++++++++++++++++++ aed1/n2.lyx | 788 +++++++++++++ aed1/n3.lyx | 753 ++++++++++++ aed1/n4.lyx | 3547 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 7056 insertions(+) create mode 100644 aed1/graph.svg create mode 100644 aed1/n.lyx create mode 100644 aed1/n1.lyx create mode 100644 aed1/n2.lyx create mode 100644 aed1/n3.lyx create mode 100644 aed1/n4.lyx (limited to 'aed1') diff --git a/aed1/graph.svg b/aed1/graph.svg new file mode 100644 index 0000000..b5e834f --- /dev/null +++ b/aed1/graph.svg @@ -0,0 +1,69 @@ + + + + + + +untitled + + +1 + +1 + + +2 + +2 + + +1--2 + + + +3 + +3 + + +2--3 + + + +5 + +5 + + +2--5 + + + +4 + +4 + + +3--4 + + + +4--5 + + + +5--1 + + + +6 + +6 + + +6--4 + + + + \ No newline at end of file diff --git a/aed1/n.lyx b/aed1/n.lyx new file mode 100644 index 0000000..069c70b --- /dev/null +++ b/aed1/n.lyx @@ -0,0 +1,219 @@ +#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 10 +\spacing single +\use_hyperref false +\papersize a5paper +\use_geometry true +\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 +\leftmargin 0.2cm +\topmargin 0.7cm +\rightmargin 0.2cm +\bottommargin 0.7cm +\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 empty +\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 Title +Algoritmos y Estructuras de Datos I +\end_layout + +\begin_layout Date +\begin_inset Note Note +status open + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +def +\backslash +cryear{2018} +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "../license.lyx" + +\end_inset + + +\end_layout + +\begin_layout Standard +Bibliografía: +\end_layout + +\begin_layout Itemize +Programa de teoría (diapositivas), A.E.D. + 1, Facultad de Informática, Universidad de Murcia. +\end_layout + +\begin_layout Itemize +Texto guía, anónimo. +\end_layout + +\begin_layout Itemize +Wikipedia, la Enciclopedia Libre ( +\begin_inset Flex URL +status open + +\begin_layout Plain Layout + +https://es.wikipedia.org/ +\end_layout + +\end_inset + +). +\end_layout + +\begin_layout Itemize +Competitive Programming 3: The New Lower Bound of Programming Contests (2013), + Steven & Felix Halim. +\end_layout + +\begin_layout Chapter +Abstracción y especificación +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "n1.lyx" + +\end_inset + + +\end_layout + +\begin_layout Chapter +Conjuntos y diccionarios +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "n2.lyx" + +\end_inset + + +\end_layout + +\begin_layout Chapter +Árboles +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "n3.lyx" + +\end_inset + + +\end_layout + +\begin_layout Chapter +Grafos +\end_layout + +\begin_layout Standard +\begin_inset CommandInset include +LatexCommand input +filename "n4.lyx" + +\end_inset + + +\end_layout + +\end_body +\end_document diff --git a/aed1/n1.lyx b/aed1/n1.lyx new file mode 100644 index 0000000..d39e26b --- /dev/null +++ b/aed1/n1.lyx @@ -0,0 +1,1680 @@ +#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 french +\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 +Una +\series bold +abstracción +\series default + consiste en dejar a un lado lo irrelevante y centrarse en lo importante. + Distinguimos +\series bold +niveles de abstracción +\series default + según el nivel de detalle. + El +\series bold +diseño mediante abs +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +- +\end_layout + +\end_inset + +trac +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +- +\end_layout + +\end_inset + +cio +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +- +\end_layout + +\end_inset + +nes +\series default + consiste en identificar los subproblemas de cierto problema, especificar + cada uno de forma abstracta, resolverlos de forma separada, unir las soluciones + y verificar la solución para el problema original. + Esto se hace de forma recursiva. +\end_layout + +\begin_layout Standard +Junto con el concepto de abstracción viene el de +\series bold +especificación +\series default + de dicha abstracción. +\end_layout + +\begin_layout Standard + +\series bold +Mecanismos de abstracción +\series default +: +\end_layout + +\begin_layout Itemize + +\series bold +Por especificación +\series default +: Nos quedamos con la descripción del efecto o resultado, in +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +- +\end_layout + +\end_inset + +de +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +- +\end_layout + +\end_inset + +pen +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +- +\end_layout + +\end_inset + +dien +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +- +\end_layout + +\end_inset + +te +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +- +\end_layout + +\end_inset + +men +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +- +\end_layout + +\end_inset + +te de cómo calcularlo ( +\series bold +principio de ocultación de la implementación +\series default +). + Da lugar a la +\series bold +encapsulación +\series default +, agrupar un conjunto de operaciones o tipos relacionados en un mismo módulo + o paquete. +\end_layout + +\begin_layout Itemize + +\series bold +Por parametrización +\series default +: El significado de la abstracción no es fijo, sino que depende de parámetros. + En la +\series bold +parametrización de tipo +\series default +, el parámetro es un tipo de datos. +\end_layout + +\begin_layout Section +Especificaciones informales +\end_layout + +\begin_layout Standard +Una +\series bold +especificación +\series default + es la descripción de una abstracción, bien textualmente mediante el lenguaje + natural (especificación +\series bold +informal +\series default +) o bien con una notación precisa de las propiedades de la abstracción (especifi +cación +\series bold +formal +\series default +), mediante una +\series bold +notación +\series default +. + A continuación vemos los tipos de abstracciones y una notación propuesta + para su especificación informal. +\end_layout + +\begin_layout Itemize + +\series bold +Funcionales +\series default +: Abstraemos un trozo de código en una +\series bold +rutina +\series default +, +\series bold +procedimiento +\series default + o +\series bold +función +\series default +, al que asignamos un nombre. + Su especificación indica los parámetros de entrada, los de salida y el + efecto que tendrá su ejecución. +\begin_inset Newline newline +\end_inset + + +\begin_inset Tabular + + + + + +\begin_inset Text + +\begin_layout Plain Layout +Especificación informal +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout + +\family sans +\series bold +Operación +\series default + +\emph on +nombre +\emph default + +\family default +[ +\family sans +[ +\emph on +T +\emph default +, +\family default +... +\family sans +: +\emph on +TipoDeTipo +\emph default +; +\family default +... +\family sans +] +\family default +] +\family sans + ( +\family default +[ +\family sans +\series bold +ent +\series default + +\emph on +v1 +\emph default +, +\family default +... +\family sans +: +\emph on +Tipo +\emph default +1; +\emph on +vn +\emph default +, +\family default +... +\family sans +: +\emph on +Tipo2 +\emph default +; +\family default +...[ +\family sans +; +\family default +]] +\family sans + +\family default +[ +\family sans +\series bold +sal +\series default + +\emph on +tipoResultado +\family default +\emph default +] +\family sans +) +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\series bold +Require: +\series default + +\emph on +Opcional, requisitos y restricciones de uso de la operación. +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\series bold +Modifica: +\series default + +\emph on +Opcional, lista de parámetros de entrada que pueden ser +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + + +\emph on +modificados. +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\series bold +Calcula: +\series default + +\emph on +Descripción del resultado de la operación. +\end_layout + +\end_inset + + + + +\end_inset + + +\begin_inset Newline newline +\end_inset + +Donde el +\family sans +\emph on +TipoDeTipo +\family default +\emph default + suele ser +\family sans +tipo +\family default +. + Tanto en la especificación informal como en el pseudocódigo, los tipos + tanto de los parámetros de tipo como los propios de la función pueden depender + de parámetros anteriores. +\end_layout + +\begin_layout Itemize + +\series bold +De datos +\series default +: Se abstrae un dominio de valores, junto con operaciones sobre ese dominio + con +\series bold +ocultación de la implementación +\series default +, en un +\series bold +tipo abstracto de datos +\series default + ( +\series bold +TAD +\series default +). + Un +\series bold +tipo contenedor +\series default + es un TAD compuesto por un número arbitrario de valores de otro tipo. + Generalmente están +\series bold +parametrizados +\series default +: dependen de un parámetro que indica el tipo de objetos almacenados. +\begin_inset Newline newline +\end_inset + + +\begin_inset Tabular + + + + + +\begin_inset Text + +\begin_layout Plain Layout +Especificación informal +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout + +\family sans +\series bold +TAD +\series default + +\emph on +nombre +\emph default + +\series bold +es +\series default + +\emph on +listaDeOperaciones +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +Descripción +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\emph on +Descripción del significado, comportamiento y modo de uso del TAD. +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +Operaciones +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\emph on +Especificación informal de cada operación de la lista, según el punto anterior. +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +Fin +\series default + +\emph on +nombre +\emph default +. +\end_layout + +\end_inset + + + + +\end_inset + + +\begin_inset Newline newline +\end_inset + +Así, un +\series bold +tipo de datos +\series default + es un concepto de implementación que debe ajustarse al comportamiento de + un TAD, y una +\series bold +estructura de datos +\series default + es la disposición en memoria de estos datos. +\end_layout + +\begin_layout Itemize + +\series bold +De iteradores +\series default +: Permiten realizar un recorrido de forma abstracta sobre los elementos + de una colección. + La especificación informal puede ser: +\end_layout + +\begin_deeper +\begin_layout Itemize +Similar a la de una abstracción funcional, cambiando +\family sans +\series bold +Operación +\family default +\series default + por +\family sans +\series bold +Iterador +\family default +\series default + y añadiendo un parámetro de entrada de tipo +\family sans +Operacion +\family default +. + La función puede devolver un valor si, por ejemplo, el iterador filtra + una colección de valores de un cierto tipo. +\end_layout + +\begin_layout Itemize +Similar a la de un TAD, cambiando +\family sans +\series bold +TAD +\family default +\series default + por +\family sans +\series bold +TipoIterador +\family default +\series default + y añadiendo operaciones como +\family sans +Iniciar +\family default +, +\family sans +Actual +\family default +, +\family sans +Avanzar +\family default + y +\family sans +EsUltimo +\family default +. +\end_layout + +\end_deeper +\begin_layout Standard +La abstracción en lenguajes de programación generalmente consiste en ofrecer + características más próximas al concepto teórico de TAD. + Los lenguajes primitivos como Fortran o BASIC ofrecían un conjunto predefinido + de tipos elementales, pero no permitían definir nuevos tipos, con lo que + el programador debía definir y manejar las variables adecuadas de forma + manual. + Posteriormente, lenguajes como C y Pascal permiten agrupar un conjunto + de variables bajo un mismo nombre, aunque no hay ocultación. + Los módulos o paquetes permiten agrupar bajo un mismo nombre una serie + de tipos y operaciones relacionados, y en algunos casos como en Modula-2, + estos ofrecen ocultación de la implementación: los tipos definidos en un + módulo sólo se pueden usar a través de las operaciones de este. +\end_layout + +\begin_layout Standard +Finalmente, en la programación orientada a objetos surge el concepto de + clase, que es al mismo tiempo un tipo definido por el usuario y un módulo + donde se encapsulan sus datos y operaciones, y soportan ocultación. + Un objeto es una instancia de una clase. + El +\series bold +principio de acceso uniforme +\series default + consiste en que los atributos y operaciones de una clase están conceptualmente + al mismo nivel, y se accede con +\family typewriter +\emph on +objeto +\emph default +. +\emph on +atributo +\family default +\emph default + u +\family typewriter +\emph on +objeto +\emph default +. +\emph on +operación +\emph default +( +\family default +... +\family typewriter +) +\family default +. + Algunos lenguajes orientados a objetos permiten parametrización de tipo, + dando lugar a TAD genéricos o parametrizados. +\end_layout + +\begin_layout Standard +Una implementación es +\series bold +robusta +\series default + si se autoprotege de valores inconsistentes de entrada, bien lanzando una + excepción o mediante programación por contrato, en la que el usuario se + compromete, de forma comprobable, a no pasar un valor inconsistente según + la especificación de la función. + +\end_layout + +\begin_layout Section +Especificaciones formales +\end_layout + +\begin_layout Standard +Una +\series bold +especificación formal +\series default + define un TAD u operación de forma precisa, permitiendo la verificación + automática y formal de la corrección del programa y el uso de la especificación + en distintos ámbitos. + Estas especificaciones pueden llegar a ser ejecutables. + Distinguimos entre el +\series bold +método axiomático +\series default + o +\series bold +algebraico +\series default +, que establece el significado de las operaciones de forma implícita mediante + +\series bold +axiomas +\series default + que especifican sus relaciones, y el +\series bold +método constructivo +\series default + u +\series bold +operacional +\series default +, en el que cada operación se define por sí misma con significado explícito. +\end_layout + +\begin_layout Standard +Veremos un método constructivo al que llamaremos método axiomático, y que + escribimos en lenguaje Maude, describiendo un TAD del siguiente modo: +\end_layout + +\begin_layout Standard +\align center +\begin_inset Tabular + + + + + + +\begin_inset Text + +\begin_layout Plain Layout +Especificación formal +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout +Maude +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout + +\family sans +\series bold +NOMBRE +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\emph on +NombreTAD +\family default +\emph default + [ +\family sans +[ +\emph on +T1 +\emph default +, +\family default +... +\family sans +] +\family default +] +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\family typewriter +\series bold +fmod +\series default + +\emph on +NOMBRETAD +\emph default + +\series bold +is +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout + +\family sans +\series bold +CONJUNTOS +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\emph on +CONJ +\emph default + +\begin_inset space \qquad{} +\end_inset + + +\emph on +Descripción +\end_layout + +\begin_layout Plain Layout + +\family typewriter +\begin_inset space \qquad{} +\end_inset + + +\family default +... +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\family typewriter +\begin_inset space \qquad{} +\end_inset + +protecting +\emph on +TADIMPORTADO +\emph default + . +\end_layout + +\begin_layout Plain Layout + +\family typewriter +\begin_inset space \qquad{} +\end_inset + +sort +\emph on +CONJ +\emph default + . +\end_layout + +\begin_layout Plain Layout + +\family typewriter +\begin_inset space \qquad{} +\end_inset + +subsort +\emph on +A +\emph default + < +\emph on +B +\emph default + . +\end_layout + +\begin_layout Plain Layout + +\family typewriter +\begin_inset space \qquad{} +\end_inset + + +\family default +... +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout + +\family sans +\series bold +SINTAXIS +\end_layout + +\begin_layout Plain Layout + +\family typewriter +\begin_inset space \qquad{} +\end_inset + + +\family sans +\emph on +operación +\emph default +: +\family default + [ +\family sans +\emph on +conjPar1 +\family default +\emph default + +\begin_inset Formula $\times$ +\end_inset + +...] +\family sans + +\begin_inset Formula $\rightarrow$ +\end_inset + + +\emph on +conjResultado +\end_layout + +\begin_layout Plain Layout + +\family typewriter +\begin_inset space \qquad{} +\end_inset + + +\family default +... +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\family typewriter +\begin_inset space \qquad{} +\end_inset + +op +\emph on +operación +\emph default + : +\family default +[ +\family typewriter +\emph on +conjPar11 +\emph default + +\begin_inset Formula $\times$ +\end_inset + + ... +\family default +] +\family typewriter + -> +\emph on +conjResultado1 +\emph default + . +\end_layout + +\begin_layout Plain Layout + +\family typewriter +\begin_inset space \qquad{} +\end_inset + +ops +\emph on +op1 +\emph default + +\family default +... + +\family typewriter + : +\family default +[ +\family typewriter +\emph on +conjPar21 +\emph default + +\begin_inset Formula $\times$ +\end_inset + + ... +\family default +] +\family typewriter + -> +\emph on +conjResultado2 +\emph default + . +\end_layout + +\begin_layout Plain Layout + +\family typewriter +\begin_inset space \qquad{} +\end_inset + + +\family default +... +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout + +\family sans +\series bold +SEMÁNTICA +\end_layout + +\begin_layout Plain Layout +\begin_inset Formula $\forall$ +\end_inset + + +\family sans +\emph on + var1 +\emph default +, +\family default +... + +\family sans + +\begin_inset Formula $\in$ +\end_inset + + +\emph on + CONJ +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\emph on +ExprA +\emph default + = +\emph on +ExprB +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\family default +... +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\family typewriter +\begin_inset space \qquad{} +\end_inset + +var +\emph on +v +\emph default + : +\emph on +CONJ +\emph default + . +\end_layout + +\begin_layout Plain Layout + +\family typewriter +\begin_inset space \qquad{} +\end_inset + +vars +\emph on +v1 +\emph default + +\family default +... + +\family typewriter + : +\emph on +CONJ +\emph default + . +\end_layout + +\begin_layout Plain Layout + +\family typewriter +\begin_inset space \qquad{} +\end_inset + + +\family default +... +\end_layout + +\begin_layout Plain Layout + +\family typewriter +\begin_inset space \qquad{} +\end_inset + +eq +\emph on +ExprA +\emph default + = +\emph on +ExprB +\emph default + . +\end_layout + +\begin_layout Plain Layout + +\family typewriter +\begin_inset space \qquad{} +\end_inset + + +\family default +... +\end_layout + +\end_inset + + + + +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset + + +\begin_inset Text + +\begin_layout Plain Layout + +\family typewriter +\series bold +endfm +\end_layout + +\end_inset + + + + +\end_inset + + +\end_layout + +\begin_layout Standard +El nombre de los conjuntos suele ser de una letra, y debe haber un conjunto + asociado al TAD, y si el TAD es genérico, uno para cada parámetro con el + mismo nombre dado en la sección anterior ( +\family sans +\emph on +T1 +\family default +\emph default +, etc.). + También, en la especificación se declaran conjuntos asociados a otros TADs + pero que se usan en este, mientras que en Maude se usa +\family typewriter +protecting +\family default + para importar todos los conjuntos, junto con sus operaciones, de otro TAD. + Para tipos finitos en la especificación, si en la +\family sans +\emph on +Descripción +\family default +\emph default + se añade al final +\family sans +{ +\emph on +valor1 +\emph default +, +\family default +... +\family sans +} +\family default +, estos valores se pueden usar en la semántica. +\end_layout + +\begin_layout Standard +Entre las operaciones encontramos +\series bold +constructores +\series default +, operaciones cuya semántica no se define y que sirven para definir elementos + del TAD, y tales que, si es posible, un elemento del TAD debería tener + representación única en términos de estos. + El resto son de +\series bold +modificación +\series default + o de +\series bold +consulta +\series default + según si devuelven un elemento del conjunto asociado al TAD o de otro tipo, + respectivamente. +\end_layout + +\begin_layout Standard +Si una operación que normalmente devuelve valores de tipo +\family sans +T +\family default + no esta definida para cierta entrada, se crea un conjunto +\family sans +M +\family default + de mensajes cuya descripción contiene al final +\family sans +{ +\begin_inset Quotes fls +\end_inset + + +\emph on +Texto mensaje 1 +\emph default + +\begin_inset Quotes frs +\end_inset + +, +\family default +... +\family sans +} +\family default +, y el conjunto resultado de la operación se declara +\family sans +T +\begin_inset Formula $\cup$ +\end_inset + +M +\family default +, mientras que en Maude se crea un tipo de errores +\family typewriter +NoT +\family default + con un constructor sin parámetros para cada tipo de error y se usa +\family typewriter +subsort No +\emph on +T +\emph default + < +\emph on +T +\family default +\emph default + para indicar que toda operación que toda operación que devuelva un valor + de +\family typewriter +\emph on +T +\family default +\emph default + también puede devolver uno de +\family typewriter +No +\emph on +T +\family default +\emph default +. +\end_layout + +\begin_layout Standard +La semántica consiste en una serie de reglas que, dada una expresión, Maude + va comprobando de arriba a abajo sucesivamente para ver si parte de la + expresión coincide con +\family sans +\emph on +ExprA +\family default +\emph default + y sustituirla en tan caso por +\family sans +\emph on +ExprB +\family default +\emph default + hasta que no queden sustituciones por hacer, momento en que la expresión + debería estar en términos de constructores. + Una expresión tiene sintaxis +\family typewriter +\emph on +op +\family default +\emph default +[ +\family typewriter +( +\emph on +par1 +\emph default +, +\family default +... +\family typewriter +) +\family default +], donde los parámetros de la operación son a su vez otras expresiones. + +\family sans +\emph on +ExprB +\family default +\emph default + o alguna de sus subexpresiones puede ser +\family sans +\series bold +SI +\series default + +\emph on +condición +\emph default + +\begin_inset Formula $\implies$ +\end_inset + + +\emph on +valorSiCierto +\emph default + | +\emph on +valorSiFalso +\family default +\emph default +, o en Maude, +\family typewriter +if +\emph on +condición +\emph default + then +\emph on +valorSiCierto +\emph default + else +\emph on +valorSiFalso +\emph default + fi +\family default +. +\end_layout + +\begin_layout Standard +En Maude, fuera de la definición de un TAD podemos usar +\family typewriter +in +\emph on +nombre +\emph default + . + +\family default + para leer todo lo que hay en un fichero llamado +\family typewriter +\emph on +nombre +\family default +\emph default + o +\family typewriter +\emph on +nombre +\emph default +.maude +\family default + o +\family typewriter +red +\emph on +expr +\family default +\emph default + para reducir una expresión según la semántica de las operaciones. + Un fallo en Maude puede tiene consecuencias impredecibles porque Maude + es una mierda. +\end_layout + +\begin_layout Standard +Si el orden de las reglas no es relevante las llamamos axiomas +\begin_inset Foot +status open + +\begin_layout Plain Layout +Cada vez que llamas axiomas a algo que depende del orden muere un matemático + y un gatito. +\end_layout + +\end_inset + +, y estos deben cumplir las propiedades de +\series bold +completitud +\series default + (deben ser suficientes para deducir el significado de cualquier expresión) + y +\series bold +corrección +\series default +; dicho de otra forma, se deben considerar todos los casos al definir cada + operación no constructora. +\end_layout + +\begin_layout Section +Órdenes de ejecución +\end_layout + +\begin_layout Standard +Medimos el tiempo que tarda en ejecutarse un algoritmo con una función +\begin_inset Formula $t:\mathbb{N}\rightarrow\mathbb{R}^{\geq0}$ +\end_inset + + para cada uno de los casos mejor, peor y promedio, que toma el tamaño del + problema medido de algún modo y devuelve el tiempo que tarda en realizarse + en cierta máquina, el número de instrucciones total o el de un tipo de + instrucción que sabemos que es la más relevante. + En la práctica se usan +\series bold +notaciones asintóticas +\series default +: +\end_layout + +\begin_layout Itemize +\begin_inset Formula $f(x)=O(g(x)):\iff\exists x_{0},k>0:\forall x\geq x_{0},|f(x)|\leq k|g(x)|$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +\begin_inset Formula $f(x)=\Omega(g(x)):\iff\exists x_{0},k>0:\forall x\geq x_{0},kg(x)\leq f(x)$ +\end_inset + +. +\end_layout + +\begin_layout Standard +\begin_inset Note Comment +status open + +\begin_layout Itemize +\begin_inset Formula $f(x)=\Theta(g(x)):\iff f(x)=O(g(x))\land f(x)=\Omega(g(x))$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +\begin_inset Formula $f(x)=o(g(x)):\iff\lim_{x\rightarrow+\infty}\frac{f(x)}{g(x)}=0$ +\end_inset + +. +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Estas definiciones sólo son válidas cuando +\begin_inset Formula $x$ +\end_inset + + tiende a +\begin_inset Formula $+\infty$ +\end_inset + +. +\end_layout + +\end_body +\end_document diff --git a/aed1/n2.lyx b/aed1/n2.lyx new file mode 100644 index 0000000..26201e5 --- /dev/null +++ b/aed1/n2.lyx @@ -0,0 +1,788 @@ +#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 french +\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 Section +Conjuntos +\end_layout + +\begin_layout Standard +Un conjunto es una colección no ordenada de elementos distintos. + El TAD +\family sans +Conjunto[ +\begin_inset Formula $T$ +\end_inset + +] +\family default + define conjuntos finitos con elementos de un cierto tipo. + Operaciones comunes: +\end_layout + +\begin_layout Standard +\begin_inset Formula +\[ +\begin{array}{rrr} +\mathsf{Vacío}:\rightarrow C & \mathsf{Unión}:C\times C\rightarrow C & \mathsf{Intersección}:C\times C\rightarrow C\\ +\mapsto\emptyset & (a,b)\mapsto a\cup b & (a,b)\mapsto a\cap b\\ +\\ +\mathsf{Diferencia}:C\times C\rightarrow C & \mathsf{Combina}:C\times C\rightarrow C & \mathsf{Miembro}:T\times C\rightarrow B\\ +(a,b)\mapsto a\backslash b & (a,b)\rightarrow a\dot{\cup}b & (x,a)\mapsto x\in a\\ +\\ +\mathsf{Inserta}:T\times C\rightarrow C & \mathsf{Suprime}:T\times C\rightarrow C & \mathsf{Igual}:C\times C\rightarrow B\\ +(x,a)\mapsto a\cup\{x\} & (x,a)\mapsto a\backslash\{x\} & (a,b)\mapsto a=b +\end{array} +\] + +\end_inset + + +\end_layout + +\begin_layout Standard +Si además tenemos un orden total sobre +\begin_inset Formula $T$ +\end_inset + +, podemos definir +\begin_inset Formula $\mathsf{Min}:C\rightarrow T$ +\end_inset + + y +\begin_inset Formula $\mathsf{Max}:C\rightarrow T$ +\end_inset + + para conjuntos no vacíos. + Implementaciones básicas: +\end_layout + +\begin_layout Itemize + +\series bold +Tabla de booleanos +\series default +, donde cada elemento de +\family sans +T +\family default + se representa con un bit 1 si pertenece al conjunto o 0 en caso contrario. + La unión, intersección, diferencia y comprobación de igualdad son +\begin_inset Formula $O(n)$ +\end_inset + + con +\begin_inset Formula $n:=|T|$ +\end_inset + +, mientras que la inserción y eliminación y comprobación de pertenencia + son +\begin_inset Formula $O(1)$ +\end_inset + +. + Las operaciones son muy sencillas de implementar y no hace falta memoria + dinámica, pero el tamaño de un conjunto es proporcional a +\begin_inset Formula $|T|$ +\end_inset + + y por tanto solo es adecuado cuando +\begin_inset Formula $|T|$ +\end_inset + + es pequeño. +\end_layout + +\begin_layout Itemize + +\series bold +Lista de elementos +\series default +. + +\series bold + +\series default +La unión, intersección y diferencia son +\begin_inset Formula $O(mn)$ +\end_inset + + siendo +\begin_inset Formula $m$ +\end_inset + + y +\begin_inset Formula $n$ +\end_inset + + el tamaño de los conjuntos de entrada, mientras que la comprobación de + pertenencia, inserción y eliminación son +\begin_inset Formula $O(n)$ +\end_inset + +. + La comprobación de igualdad es +\begin_inset Formula $O(1)$ +\end_inset + + en el caso mejor ( +\begin_inset Formula $m\neq n$ +\end_inset + +) y +\begin_inset Formula $O(n^{2})$ +\end_inset + + en el peor. + Se usa un espacio proporcional al del conjunto representado, pero es más + complejo de implementar, y las operaciones son menos eficientes si el conjunto + es grande o +\begin_inset Formula $|T|$ +\end_inset + + es pequeño. +\end_layout + +\begin_layout Itemize +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +begin{sloppypar} +\end_layout + +\end_inset + + +\series bold +Lista de elementos ordenada +\series default +. + La unión, intersección y diferencia pasan a ser +\begin_inset Formula $O(\max\{m,n\})$ +\end_inset + + en el caso mejor y +\begin_inset Formula $O(m+n)$ +\end_inset + + en el peor, y la comprobación de igualdad en el caso peor pasa a ser +\begin_inset Formula $O(n)$ +\end_inset + +. +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +end{sloppypar} +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +Diccionarios +\end_layout + +\begin_layout Standard +Una asociación es un par clave-valor, y un diccionario es un conjunto de + asociaciones sin más de un valor para una misma clave. + Nos limitamos a +\family sans +Diccionario[ +\begin_inset Formula $T_{k}$ +\end_inset + +, +\begin_inset Formula $T_{v}$ +\end_inset + +] +\family default +, diccionarios finitos con claves de un cierto tipo +\begin_inset Formula $T_{k}$ +\end_inset + + y valores de tipo +\begin_inset Formula $T_{v}$ +\end_inset + +. + Operaciones comunes: +\end_layout + +\begin_layout Standard +\begin_inset Formula +\[ +\begin{array}{rr} +\mathsf{Inserta}:T_{k}\times T_{v}\times D\rightarrow D & \mathsf{Consulta}:T_{k}\times D\rightarrow T_{v}\\ +(k,v,d)\overset{k\notin\text{Dom}(d)}{\mapsto}D\cup\{(k,v)\} & (k,d)\overset{k\in\text{Dom}(d)}{\mapsto}d(k)\\ +\mathsf{}\\ +\mathsf{Suprime}:T_{k}\times D\rightarrow D & \mathsf{Vacío}:\rightarrow D\\ +(k,d)\mapsto\{(a,b)\in d:a\neq k\} & \mapsto\emptyset +\end{array} +\] + +\end_inset + + +\end_layout + +\begin_layout Standard +La representación más sencilla es mediante una lista de asociaciones. +\end_layout + +\begin_layout Section +Tablas de dispersión +\end_layout + +\begin_layout Standard +Permiten una representación más eficiente de conjuntos y diccionarios mediante + una lista contigua de +\begin_inset Formula $M$ +\end_inset + + elementos y una +\series bold +función +\series default + +\series bold +\emph on +hash +\series default +\emph default + o +\series bold +de dispersión +\series default + +\begin_inset Formula $h:T\rightarrow\{0,\dots,M-1\}$ +\end_inset + +. + La idea es que, para diccionarios, +\begin_inset Formula $h$ +\end_inset + + solo dependa de la clave de la asociación, no del valor. + Se dice que +\begin_inset Formula $x\neq y\in T$ +\end_inset + + son sinónimos si +\begin_inset Formula $h(x)=h(y)$ +\end_inset + +. + Existen dos formas de dispersión: +\end_layout + +\begin_layout Itemize + +\series bold +Abierta +\series default +: Los elementos de la tabla son apuntadores a listas (enlazadas) de elementos, + llamadas +\series bold +cubetas +\series default +, que contienen los elementos +\begin_inset Formula $\{e\in c:h(e)=k\}$ +\end_inset + +, siendo +\begin_inset Formula $c$ +\end_inset + + el conjunto y +\begin_inset Formula $k$ +\end_inset + + el índice de la cubeta. +\begin_inset Newline newline +\end_inset + +El tamaño de las cubetas en un reparto uniforme (lo ideal) es +\begin_inset Formula $\frac{n}{M}$ +\end_inset + +, siendo +\begin_inset Formula $n$ +\end_inset + + el número de elementos del conjunto, luego en este caso la búsqueda es + +\begin_inset Formula $O(\frac{n}{M})$ +\end_inset + + y la inserción es +\begin_inset Formula $O(1+\frac{n}{M})$ +\end_inset + +. + El uso de memoria es el de +\begin_inset Formula $M+n$ +\end_inset + + apuntadores y +\begin_inset Formula $n$ +\end_inset + + elementos. + Así, a más cubetas las operaciones son más rápidas, pero se usa más memoria. +\end_layout + +\begin_layout Itemize + +\series bold +Cerrada +\series default +: Los elementos de la tabla son del tipo +\begin_inset Formula $T$ +\end_inset + +, y si al ir a insertar un elemento +\begin_inset Formula $e$ +\end_inset + + en el índice +\begin_inset Formula $h(e)$ +\end_inset + + este ya está ocupado se dice que ocurre una +\series bold +colisión +\series default +, y se hace una +\series bold +redispersión +\series default +: se aplican sucesivamente los elementos de una sucesión de funciones +\begin_inset Formula $(h_{n}:T\rightarrow\{0,\dots,M-1\})_{n}$ +\end_inset + + sobre +\begin_inset Formula $e$ +\end_inset + + hasta que devuelva un índice de la tabla no ocupado, donde se guarda +\begin_inset Formula $e$ +\end_inset + +. + +\begin_inset Newline newline +\end_inset + +Llamamos +\series bold +cadena +\series default + o +\series bold +secuencia de búsqueda +\series default + a la secuencia +\begin_inset Formula $h(e),h_{1}(e),\dots$ +\end_inset + + de posiciones recorridas en este proceso. + Al consultar un elemento se recorre esta secuencia hasta encontrar el elemento + o una celda vacía, que indica que este no está. + En la eliminación, para no romper la secuencia, se sustituye el elemento + por una marca de eliminado, que se trata como celda libre en la inserción + pero no en la búsqueda, o bien se mueven elementos cuya secuencia de búsqueda + pase por la posición eliminada. +\begin_inset Newline newline +\end_inset + +Como la probabilidad de colisión es +\begin_inset Formula $\frac{n}{M}$ +\end_inset + + y se ha de encontrar un elemento libre, el coste de una inserción es +\begin_inset Formula $O(\frac{1}{1-\frac{n}{M}})$ +\end_inset + +, que tiende a infinito cuando +\begin_inset Formula $n\rightarrow M$ +\end_inset + +, mientras que el de búsqueda es de +\begin_inset Formula $O(\frac{1}{1-\frac{n-1}{M}})$ +\end_inset + +. + El uso de memoria es el de +\begin_inset Formula $M$ +\end_inset + + elementos, o el de +\begin_inset Formula $M$ +\end_inset + + apuntadores más +\begin_inset Formula $n$ +\end_inset + + elementos si se decide que la tabla almacene apuntadores. +\end_layout + +\begin_layout Standard +Para evitar la pérdida de eficiencia cuando +\begin_inset Formula $n$ +\end_inset + + aumenta, la tabla se puede +\series bold +reestructurar +\series default +, creando una nueva con distinto +\begin_inset Formula $M$ +\end_inset + + y copiando los elementos, por ejemplo cuando +\begin_inset Formula $n>2M$ +\end_inset + + en dispersión abierta o cuando +\begin_inset Formula $n>\frac{3}{4}M$ +\end_inset + + en cerrada. + Para que las tablas de dispersión sean eficientes se debe usar una buena + función, que reparta los elementos de la forma más aleatoria pero a la + vez sea fácil de calcular. +\end_layout + +\begin_layout Standard +Métodos para enteros: +\end_layout + +\begin_layout Itemize + +\series bold +División +\series default +: +\begin_inset Formula $h(k):=k\mod M$ +\end_inset + +, siendo +\begin_inset Formula $M$ +\end_inset + + normalmente primo. +\end_layout + +\begin_layout Itemize + +\series bold +Multiplicación +\series default +: +\begin_inset Formula $h(k):=\lfloor Ck\rfloor\mod M,C\in\mathbb{R}$ +\end_inset + +. + +\begin_inset Newline newline +\end_inset + +Variante: +\begin_inset Formula $h(k):=\lfloor\text{d}(\frac{Ak}{W})M\rfloor,\text{mcd}(A,K)=1$ +\end_inset + +, donde +\begin_inset Formula $\text{d}(x)$ +\end_inset + + es la parte decimal de +\begin_inset Formula $x$ +\end_inset + +. +\end_layout + +\begin_layout Itemize + +\series bold +Centro del cuadrado +\series default +: +\begin_inset Formula $h(k):=\lfloor\frac{k^{2}}{C}\rfloor\mod M$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Para secuencias: +\end_layout + +\begin_layout Itemize + +\series bold +Suma +\series default +: +\begin_inset Formula $h(k):=\sum_{i}x_{i}\mod M$ +\end_inset + +. + Muchas colisiones. +\end_layout + +\begin_layout Itemize + +\series bold +Suma posicional +\series default +: +\begin_inset Formula $h(k):=\sum_{i}k^{i}x_{i}\mod M$ +\end_inset + +, siendo +\begin_inset Formula $k$ +\end_inset + + normalmente primo. +\end_layout + +\begin_layout Itemize + +\series bold +Plegado +\series default + ( +\emph on +folding +\emph default +): +\begin_inset Formula $h(k):=\sum_{i=0}^{\lfloor n/p\rfloor}\prod_{j=1}^{p}x_{ip+j}\mod M$ +\end_inset + +, tomando +\begin_inset Formula $x_{k}=1\forall k>n$ +\end_inset + +. +\end_layout + +\begin_layout Itemize + +\series bold +Extracción +\series default +: +\begin_inset Formula $h(k):=x_{n_{1}}\cdots x_{n_{k}}\mod M$ +\end_inset + +. +\end_layout + +\begin_layout Itemize + +\series bold +Iterativos +\series default +: Tomar un valor inicial y, para cada +\begin_inset Formula $x_{i}$ +\end_inset + +, en orden, multiplicar por un valor base y combinar el resultado con +\begin_inset Formula $x_{i}$ +\end_inset + + mediante alguna operación. + Devolver esto módulo +\begin_inset Formula $M$ +\end_inset + +. + Así, la suma posicional toma como valor inicial, base y combinación, respectiva +mente, 0, +\begin_inset Formula $k$ +\end_inset + + y +\begin_inset Formula $+$ +\end_inset + +; djb2 toma 5381, 33 y +\begin_inset Formula $+$ +\end_inset + +; djb2a toma 5381, 33 y XOR, y FNV-1 toma 2166136261, 16777619 y XOR. +\end_layout + +\begin_layout Standard +Funciones de redispersión: +\end_layout + +\begin_layout Itemize + +\series bold +Lineal +\series default +: +\begin_inset Formula $h_{i}(k):=h(k)+i\mod M$ +\end_inset + +. + Sufre +\series bold +agrupamiento +\series default +: Si se llenan varias cubetas consecutivas y hay colisión, se debe consultar + todo el grupo. +\end_layout + +\begin_layout Itemize + +\series bold +Con saltos +\series default +: +\begin_inset Formula $h_{i}(k):=h(k)+Ci\mod M$ +\end_inset + +. + Sufre agrupamiento. +\end_layout + +\begin_layout Itemize + +\series bold +Cuadrática +\series default +: +\begin_inset Formula $h_{i}(k):=h(k)+D(i)\mod M$ +\end_inset + + con +\begin_inset Formula +\[ +D(i)=\begin{cases} +\left(\frac{i+1}{2}\right)^{2} & \text{si }x\text{ es impar}\\ +-\left(\frac{i}{2}\right)^{2} & \text{si }x\text{ es par} +\end{cases} +\] + +\end_inset + +Funciona cuando +\begin_inset Formula $M=4R+3$ +\end_inset + + para algún +\begin_inset Formula $R\in\mathbb{N}$ +\end_inset + +. +\end_layout + +\begin_layout Itemize + +\series bold +Doble +\series default +: +\begin_inset Formula $h_{i}(k)=h(k)+C(k)i\mod M$ +\end_inset + + para +\begin_inset Formula $C:T\rightarrow\{1,\dots,M-1\}$ +\end_inset + +. +\end_layout + +\end_body +\end_document diff --git a/aed1/n3.lyx b/aed1/n3.lyx new file mode 100644 index 0000000..955b960 --- /dev/null +++ b/aed1/n3.lyx @@ -0,0 +1,753 @@ +#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 french +\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 Section +Árboles Trie +\end_layout + +\begin_layout Standard +Sea +\begin_inset Formula $A$ +\end_inset + + un conjunto llamado +\series bold +alfabeto +\series default +, un árbol Trie o +\series bold +de prefijos +\series default + es aquél en que la raíz del árbol representa una cadena vacía ( +\begin_inset Formula $()$ +\end_inset + +) y un nodo puede tener un hijo etiquetado para cada elemento de +\begin_inset Formula $A\cup\{\$\}$ +\end_inset + +, con la condición de que un nodo etiquetado con +\begin_inset Formula $\$$ +\end_inset + +, la +\series bold +marca de fin +\series default +, es hoja. + Llamamos +\series bold +palabra +\series default + a la tupla de etiquetas desde la raíz hasta un nodo con +\begin_inset Formula $\$$ +\end_inset + +, sin contarlo. + Un +\family sans +ArbolTrie[ +\begin_inset Formula $A$ +\end_inset + +] +\family default + ( +\begin_inset Formula $T$ +\end_inset + +) es un apuntador a un +\family sans +NodoTrie[ +\begin_inset Formula $A$ +\end_inset + +] +\family default + ( +\begin_inset Formula $N$ +\end_inset + +), un +\family sans +Diccionario[ +\begin_inset Formula $A$ +\end_inset + +,ArbolTrie[ +\begin_inset Formula $A$ +\end_inset + +]] +\family default +. + Operaciones: +\end_layout + +\begin_layout Standard +\begin_inset Formula +\[ +\begin{array}{rrr} +\mathsf{Consulta}:N\times A\rightarrow T & \mathsf{Inserta}:N\times A\rightarrow N & \mathsf{PonMarca}:N\rightarrow N\\ +(n,x)\overset{x\in Dom(n)}{\mapsto}n(x) & (n,x)\overset{x\notin Dom(n)}{\mapsto}n\cup\{(x,\emptyset)\} & n\mapsto n\cup\{(\$,\emptyset)\}\\ +\\ +\mathsf{QuitaMarca}:N\rightarrow N & \mathsf{HayMarca}:N\rightarrow B\\ +n\mapsto n\backslash\{(\$,\emptyset)\} & n\mapsto(\$,\emptyset)\in n +\end{array} +\] + +\end_inset + + +\end_layout + +\begin_layout Standard +Los objetos devueltos por +\family sans +Consulta +\family default + son apuntadores, luego se puede insertar sobre ellos. + Otra operación es +\family sans + +\begin_inset Formula $\mathsf{Inserta}:T\times\bigcup_{n=1}^{\infty}A^{n}\rightarrow T$ +\end_inset + + +\family default +, que inserta una palabra en un árbol. + Podemos implementar un nodo trie: +\end_layout + +\begin_layout Itemize +Como una tupla de apuntadores en la que cada índice corresponde a un elemento + de +\begin_inset Formula $A\cup\{\$\}$ +\end_inset + + de forma biyectiva. + Permite un acceso a los valores en +\begin_inset Formula $O(n)$ +\end_inset + +, siendo +\begin_inset Formula $n$ +\end_inset + + la longitud de la palabra, pero si +\begin_inset Formula $p$ +\end_inset + + es el total de prefijos y +\begin_inset Formula $d=|A\cup\{\$\}|$ +\end_inset + +, esto requerirá la memoria usada por +\begin_inset Formula $(p+1)d$ +\end_inset + + apuntadores (mucha). +\end_layout + +\begin_layout Itemize +Como una lista enlazada de asociaciones. + Presenta un uso de memoria razonable, el usado por +\begin_inset Formula $4p+2$ +\end_inset + + apuntadores y +\begin_inset Formula $2p+1$ +\end_inset + + caracteres de +\begin_inset Formula $A$ +\end_inset + +, pero el acceso es +\begin_inset Formula $O(ns)$ +\end_inset + + en promedio, siendo +\begin_inset Formula $s$ +\end_inset + + la longitud media de las listas (normalmente despreciable). +\end_layout + +\begin_layout Standard +Si el total de la longitud de las palabras entre el número de prefijos es + grande, digamos mayor que 6, las palabras comparten muchos prefijos y suele + ser conveniente una representación como tupla, mientras que de lo contrario + es mejor usar una lista enlazada. +\end_layout + +\begin_layout Section +Relaciones de equivalencia +\end_layout + +\begin_layout Standard +Definimos el TAD +\family sans +RelEquiv[ +\begin_inset Formula $T$ +\end_inset + +] +\family default + como el de las relaciones de equivalencia en un +\family sans +Conjunto[ +\begin_inset Formula $T$ +\end_inset + +] +\family default +. + Operaciones: +\end_layout + +\begin_layout Itemize +\begin_inset Formula $\mathsf{Crear}:C\rightarrow R$ +\end_inset + +: Crea una relación de equivalencia con +\begin_inset Formula $x\approx y:\iff x=y$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +\begin_inset Formula $\mathsf{Encuentra}:R\times T\rightarrow R$ +\end_inset + +: Devuelve un representante canónico de la clase del elemento dado. +\end_layout + +\begin_layout Itemize +\begin_inset Formula $\mathsf{Unión}:R\times T\times T\rightarrow R$ +\end_inset + +: Hace equivalentes a los dos elementos dados de +\begin_inset Formula $T$ +\end_inset + +, combinando sus clases de equivalencia. + En el análisis posterior supondremos que los elementos dados son representantes + canónicos. +\end_layout + +\begin_layout Standard +Representaciones básicas: +\end_layout + +\begin_layout Itemize +Mediante una tabla en la que cada índice corresponde a un elemento del conjunto + y contiene el índice de su representante canónico. + La búsqueda de clase de equivalencia es +\begin_inset Formula $O(1)$ +\end_inset + + pero la unión es +\begin_inset Formula $O(n)$ +\end_inset + + con +\begin_inset Formula $n$ +\end_inset + + el cardinal del conjunto. +\end_layout + +\begin_layout Itemize +Mediante listas (enlazadas) de clases, con una lista para cada clase cuyo + nombre es el del representante canónico. + La unión es +\begin_inset Formula $O(1)$ +\end_inset + + con una representación adecuada de las listas, pero la búsqueda es +\begin_inset Formula $O(n)$ +\end_inset + + con +\begin_inset Formula $n$ +\end_inset + + el cardinal del conjunto. +\end_layout + +\begin_layout Standard +Otra forma es una estructura de árboles disjuntos, una representación por + tabla en la que cada índice contiene el índice del padre en su árbol (o + un valor especial si es la raíz), cada árbol es una clase de equivalencia + y el representante canónico es la raíz del árbol. + De esta forma la unión es +\begin_inset Formula $O(1)$ +\end_inset + + y la búsqueda es +\begin_inset Formula $O(\log n)$ +\end_inset + + en caso promedio, siendo +\begin_inset Formula $n$ +\end_inset + + el cardinal de la clase de equivalencia, aunque sigue siendo +\begin_inset Formula $O(n)$ +\end_inset + + en el caso peor. + Para evitar esto: +\end_layout + +\begin_layout Itemize + +\series bold +Balanceo +\series default +: Al unir los árboles +\begin_inset Formula $a$ +\end_inset + + y +\begin_inset Formula $b$ +\end_inset + +, podemos poner como hijo al menos alto, para lo cual guardamos en la raíz + (indicando apropiadamente que es la raíz, por ejemplo, con números negativos) + la altura del árbol. +\end_layout + +\begin_layout Itemize + +\series bold +Compresión de caminos +\series default +: Al hacer una búsqueda, poner la raíz del árbol como el padre del elemento + buscado, y del resto de elementos recorridos. +\end_layout + +\begin_layout Standard +Así, la búsqueda es +\begin_inset Formula $O(1)$ +\end_inset + + en el caso mejor y +\begin_inset Formula $O(\log n)$ +\end_inset + + en el peor. +\end_layout + +\begin_layout Section +Árboles AVL +\end_layout + +\begin_layout Standard +Un +\series bold +árbol binario de búsqueda +\series default + (ABB) es un árbol binario en que, para cada nodo, los elementos del subárbol + izquierdo son menores que el valor del nodo y los del derecho son mayores. + El recorrido ordenado es +\begin_inset Formula $O(n)$ +\end_inset + + y la búsqueda e inserción son +\begin_inset Formula $O(\log n)$ +\end_inset + + en el caso promedio, pero +\begin_inset Formula $O(n)$ +\end_inset + + en el peor. +\end_layout + +\begin_layout Standard +Un +\series bold +ABB perfectamente balanceado +\series default + es aquel en que, para cada nodo, la cantidad de elementos en sus dos subárboles + difiere como mucho en 1. + La búsqueda es +\begin_inset Formula $O(\log n)$ +\end_inset + + en el peor caso, pero en este caso la inserción es +\begin_inset Formula $O(n)$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Un +\series bold +árbol balanceado +\series default + o +\series bold +Adelson-Velskii-Landis +\series default + ( +\series bold +AVL +\series default +) es un ABB en que, para cada nodo, la altura de sus subárboles difiere + como mucho en 1. + La búsqueda es +\begin_inset Formula $O(\log n)$ +\end_inset + + en el caso peor y se hace igual que en un ABB. + La inserción y eliminación requieren +\series bold +rebalancear +\series default + el árbol a la vuelta de la llamada recursiva usada para insertar o eliminar + el elemento, lo que se hace almacenando la altura de cada nodo en el propio + nodo y mediante +\series bold +rotaciones +\series default +: +\end_layout + +\begin_layout Itemize + +\series bold +RSI +\series default + (rotación simple a la izquierda): Sobre un nodo +\family typewriter +A +\family default +, el proceso es: +\begin_inset Newline newline +\end_inset + + +\begin_inset Formula $\mathtt{B}\leftarrow\mathtt{LEFT[A]}$ +\end_inset + +, +\begin_inset Formula $\mathtt{LEFT[A]}\leftarrow\mathtt{RIGHT[B]}$ +\end_inset + +, +\begin_inset Formula $\mathtt{RIGHT[B]}\leftarrow\mathtt{A}$ +\end_inset + +, +\begin_inset Newline newline +\end_inset + + +\begin_inset Formula $\mathtt{HEIGHT[A]}\leftarrow1+\max\{\mathtt{HEIGHT[LEFT[A]]},\mathtt{HEIGHT[RIGHT[A]]\}}$ +\end_inset + +, +\begin_inset Newline newline +\end_inset + + +\begin_inset Formula $\mathtt{HEIGHT[B]}\leftarrow1+\max\{\mathtt{HEIGHT[LEFT[B]]},\mathtt{HEIGHT[A]}\}$ +\end_inset + + y +\begin_inset Formula $\mathtt{A}\leftarrow\mathtt{B}$ +\end_inset + +. +\end_layout + +\begin_layout Itemize + +\series bold +RSD +\series default + (rotación simple a la derecha): Simétrico de RSI. +\end_layout + +\begin_layout Itemize + +\series bold +RDI +\series default + (rotación doble a la izquierda): Equivale a +\begin_inset Formula $\mathtt{RSD(LEFT[A])}$ +\end_inset + + seguido de +\begin_inset Formula $\mathtt{RSI(A)}$ +\end_inset + +. +\end_layout + +\begin_layout Itemize + +\series bold +RDD +\series default + (rotación doble a la derecha): Simétrico de RDI. +\end_layout + +\begin_layout Standard +Tras la inserción, si +\begin_inset Formula $|\mathtt{HEIGHT[LEFT[A]]}-\mathtt{HEIGHT[RIGHT[A]]}|>1$ +\end_inset + + se rebalancea, con 4 situaciones según cuál de las ramas que hay 2 niveles + bajo +\family typewriter +A +\family default + tiene mayor altura (dónde se ha insertado). + Si es la rama II (izquierda-izquierda) se hace RSI, para DD se hace RSD, + para ID (izquierda y después derecha) se hace RDI y para DI se hace RDD. + Ninguno de los casos cambia la altura final del árbol. +\end_layout + +\begin_layout Standard +Para la eliminación, si el nodo a eliminar es hoja, se elimina directamente. + Si solo tiene un hijo, se conecta el padre del nodo eliminado con este + hijo. + Si tiene dos hijos, se escoge el más a la derecha del subárbol izquierdo, + o el más a la izquierda del derecho, para sustituirlo. + +\end_layout + +\begin_layout Standard +Tras esto puede ser necesario rebalancear, para lo cual hay 3 casos de eliminaci +ón en el subárbol izquierdo según las alturas +\begin_inset Formula $h_{l}$ +\end_inset + + y +\begin_inset Formula $h_{r}$ +\end_inset + + de los subárboles respectivos izquierdo y derecho del hijo derecho, más + sus 3 casos simétricos de eliminación en el derecho. + Así, si +\begin_inset Formula $h_{l}=h_{r}$ +\end_inset + + se aplica +\begin_inset Formula $RSD$ +\end_inset + + y la altura final del árbol no cambia; si +\begin_inset Formula $h_{l}h_{r}$ +\end_inset + + se hace RDD y la altura disminuye en 1. + Así, la inserción y eliminación son +\begin_inset Formula $O(\log n)$ +\end_inset + + en todos los casos. +\end_layout + +\begin_layout Section +Árboles B +\end_layout + +\begin_layout Standard +Un árbol B de orden +\begin_inset Formula $p$ +\end_inset + + o árbol +\begin_inset Formula $p$ +\end_inset + +-ario de búsqueda es aquel en que cada nodo está formado por hasta +\begin_inset Formula $p-1$ +\end_inset + + claves y +\begin_inset Formula $p$ +\end_inset + + hijos (siempre una clave menos que hijos), la raíz no tiene hijos o tiene + entre 2 y +\begin_inset Formula $p$ +\end_inset + +, los nodos internos (ni raíz ni hoja) tienen entre +\begin_inset Formula $\lceil\frac{p}{2}\rceil$ +\end_inset + + y +\begin_inset Formula $p$ +\end_inset + + hijos y los nodos hoja aparecen todos al mismo nivel (condición de balanceo) + y, para cada nodo con +\begin_inset Formula $M$ +\end_inset + + hijos, las claves del primer subárbol son todas menores que la primera + de este, los del +\begin_inset Formula $M$ +\end_inset + +-ésimo son mayores que las de la última clave, las del +\begin_inset Formula $k$ +\end_inset + +-ésimo, +\begin_inset Formula $1$ +\end_inset + + 1 +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Un +\series bold +camino de Euler +\series default + es aquel que visita todas las aristas exactamente una vez. + Si además es un ciclo, se llama +\series bold +circuito de Euler +\series default +. + Un grafo no dirigido tiene un circuito de Euler si y sólo si todos los + nodos tienen grado par y, tras eliminar los de grado 0, es conexo. + El siguiente algoritmo busca un ciclo de Euler, supuesto que exista, a + partir del vértice 1, supuesto que cada arista +\family sans +(u, v) +\family default + tiene una marca +\family sans +disponible(u, v) +\family default + que inicialmente está establecida a verdadero. + Insertar un elemento en un iterador lo inserta antes del elemento al que + apunta y devuelve un iterador al elemento insertado. +\end_layout + +\begin_layout Standard +\begin_inset Box Boxed +position "t" +hor_pos "c" +has_inner_box 1 +inner_pos "t" +use_parbox 0 +use_makebox 0 +width "100col%" +special "none" +height "1in" +height_special "totalheight" +thickness "0.4pt" +separation "3pt" +shadowsize "4pt" +framecolor "black" +backgroundcolor "none" +status open + +\begin_layout Plain Layout + +\family sans +\series bold +var +\series default + ciclo: Lista[entero] +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +visitado: +\series bold +array +\series default + [1..n] +\series bold +de +\series default + booleano +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +v: entero +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +j: Iterador[Lista[entero]] +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +operación +\series default + circuito(i: Iterador[Lista[entero]], u: entero) +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\series bold +para cada +\series default + nodo v adyacente a u +\series bold +hacer +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + + +\series bold +si +\series default + disponible(u, v) +\series bold +entonces +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + +disponible(u, v) +\begin_inset Formula $:=$ +\end_inset + + falso; disponible(v, u) +\begin_inset Formula $:=$ +\end_inset + + falso +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + +tour(i.insertar(u), v) +\end_layout + +\begin_layout Plain Layout + +\family sans +circuito(iterar(ciclo), 1) +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +La idea es partir de un vértice, tomar una arista no visitada, añadirla + al ciclo y repetir el proceso partiendo de este nuevo vértice. +\end_layout + +\begin_layout Section +Otros problemas +\end_layout + +\begin_layout Itemize + +\series bold +Flujo máximo +\series default +: Los nodos representan puntos de una red, las aristas son canales de comunicaci +ón entre ellos y los pesos de estas son el caudal máximo que puede circular. + El problema es hallar el flujo (caudal) máximo que puede haber desde un + cierto nodo (origen) a otro (destino), con las restricciones de que la + suma del flujo que entra a cada nodo interior (no origen ni destino) debe + ser igual a la que sale y el flujo en cada arista no puede superar el máximo. +\begin_inset Newline newline +\end_inset + +Un posible algoritmo es encontrar un camino del origen al destino, sumar + al flujo el mínimo caudal de las aristas que lo forman, restar dicho flujo + de estas aristas y repetir hasta que no haya caminos con peso no nulo, + si bien esto no garantiza solución óptima. +\end_layout + +\begin_layout Itemize + +\series bold +Ciclo hamiltoniano +\series default + o +\series bold +de Hamilton +\series default +: Es un ciclo simple que visita todos los nodos. + Determinar si existe en un grafo es un problema NP-completo, y en la práctica + se usan +\series bold +heurísticas +\series default +, soluciones aproximadas que pueden o no funcionar. +\end_layout + +\begin_layout Itemize + +\series bold +Problema del viajero +\series default + o +\series bold +del viajante +\series default +: Dado un grafo no dirigido, completo y con pesos, encontrar el ciclo de + menor coste que pase por todos los nodos. + También es NP-completo, y podemos usar heurísticas, técnicas probabilísticas, + algoritmos genéticos, etc. + para obtener aproximaciones. +\end_layout + +\begin_layout Itemize + +\series bold +Coloración de grafos +\series default +: Asignar un color o etiqueta a cada nodo de forma que dos nodos unidos + por una arista no tengan el mismo color, usando un mínimo número de colores. + Es NP-completo. +\end_layout + +\begin_layout Itemize + +\series bold +Isomorfismo +\series default +: Dos grafos +\begin_inset Formula $G:=(V,E)$ +\end_inset + + y +\begin_inset Formula $G':=(V',E')$ +\end_inset + + son +\series bold +isomorfos +\series default + si existe una biyección +\begin_inset Formula $\sigma:V\rightarrow V'$ +\end_inset + + tal que +\begin_inset Formula $(v,w)\in E\iff(\sigma(v),\sigma(w))\in E'$ +\end_inset + +. + Determinar si existe es NP-completo. +\end_layout + +\end_body +\end_document -- cgit v1.2.3