diff options
Diffstat (limited to 'aed1')
| -rw-r--r-- | aed1/graph.svg | 69 | ||||
| -rw-r--r-- | aed1/n.lyx | 219 | ||||
| -rw-r--r-- | aed1/n1.lyx | 1680 | ||||
| -rw-r--r-- | aed1/n2.lyx | 788 | ||||
| -rw-r--r-- | aed1/n3.lyx | 753 | ||||
| -rw-r--r-- | aed1/n4.lyx | 3547 |
6 files changed, 7056 insertions, 0 deletions
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 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.0//EN" "http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd"> +<!-- Generated by dot version 2.8 (Fri Nov 17 20:26:27 UTC 2006) + For user: (azatoth) Carl Furstenberg,,, --> +<!-- Title: untitled Pages: 1 --> +<svg width="266pt" height="176pt" viewBox="0 0 266 176" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" style="font-family:Times-Roman;font-size:14.00;"> +<title>untitled</title> +<polygon style="fill:none;stroke:none;" points="-2,178 -2,-2 268,-2 268,178 -2,178"/> +<!-- 1 --> +<g id="node1" class="node"><title>1</title> +<ellipse style="fill:white;stroke:black;stroke-width:3;" cx="237" cy="83" rx="24" ry="24"/> +<text text-anchor="middle" x="237" y="90" style="font-family:Bitstream Vera Sans;font-size:22.00pt;">1</text> +</g> +<!-- 2 --> +<g id="node2" class="node"><title>2</title> +<ellipse style="fill:white;stroke:black;stroke-width:3;" cx="187" cy="135" rx="24" ry="24"/> +<text text-anchor="middle" x="187" y="142" style="font-family:Bitstream Vera Sans;font-size:22.00pt;">2</text> +</g> +<!-- 1--2 --> +<g id="edge5" class="edge"><title>1--2</title> +<path style="fill:none;stroke:black;stroke-width:3;" d="M220,100C215,106 209,112 204,117"/> +</g> +<!-- 3 --> +<g id="node3" class="node"><title>3</title> +<ellipse style="fill:white;stroke:black;stroke-width:3;" cx="109" cy="147" rx="24" ry="24"/> +<text text-anchor="middle" x="109" y="154" style="font-family:Bitstream Vera Sans;font-size:22.00pt;">3</text> +</g> +<!-- 2--3 --> +<g id="edge6" class="edge"><title>2--3</title> +<path style="fill:none;stroke:black;stroke-width:3;" d="M163,139C153,140 142,142 133,143"/> +</g> +<!-- 5 --> +<g id="node5" class="node"><title>5</title> +<ellipse style="fill:white;stroke:black;stroke-width:3;" cx="170" cy="58" rx="24" ry="24"/> +<text text-anchor="middle" x="170" y="65" style="font-family:Bitstream Vera Sans;font-size:22.00pt;">5</text> +</g> +<!-- 2--5 --> +<g id="edge9" class="edge"><title>2--5</title> +<path style="fill:none;stroke:black;stroke-width:3;" d="M182,111C180,102 177,91 175,82"/> +</g> +<!-- 4 --> +<g id="node4" class="node"><title>4</title> +<ellipse style="fill:white;stroke:black;stroke-width:3;" cx="92" cy="70" rx="24" ry="24"/> +<text text-anchor="middle" x="92" y="77" style="font-family:Bitstream Vera Sans;font-size:22.00pt;">4</text> +</g> +<!-- 3--4 --> +<g id="edge7" class="edge"><title>3--4</title> +<path style="fill:none;stroke:black;stroke-width:3;" d="M104,123C102,114 99,103 97,94"/> +</g> +<!-- 4--5 --> +<g id="edge3" class="edge"><title>4--5</title> +<path style="fill:none;stroke:black;stroke-width:3;" d="M116,66C126,65 137,63 146,62"/> +</g> +<!-- 5--1 --> +<g id="edge4" class="edge"><title>5--1</title> +<path style="fill:none;stroke:black;stroke-width:3;" d="M193,66C200,69 207,72 214,75"/> +</g> +<!-- 6 --> +<g id="node6" class="node"><title>6</title> +<ellipse style="fill:white;stroke:black;stroke-width:3;" cx="29" cy="29" rx="24" ry="24"/> +<text text-anchor="middle" x="29" y="36" style="font-family:Bitstream Vera Sans;font-size:22.00pt;">6</text> +</g> +<!-- 6--4 --> +<g id="edge2" class="edge"><title>6--4</title> +<path style="fill:none;stroke:black;stroke-width:3;" d="M49,42C56,47 65,52 72,57"/> +</g> +</g> +</svg>
\ 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 +<lyxtabular version="3" rows="2" columns="1"> +<features tabularvalignment="middle"> +<column alignment="left" valignment="top" width="90text%"> +<row> +<cell alignment="left" valignment="top" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +Especificación informal +\end_layout + +\end_inset +</cell> +</row> +<row> +<cell alignment="left" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none"> +\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 +</cell> +</row> +</lyxtabular> + +\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 +<lyxtabular version="3" rows="2" columns="1"> +<features tabularvalignment="middle"> +<column alignment="left" valignment="top" width="90text%"> +<row> +<cell alignment="left" valignment="top" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +Especificación informal +\end_layout + +\end_inset +</cell> +</row> +<row> +<cell alignment="left" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none"> +\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 +</cell> +</row> +</lyxtabular> + +\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 +<lyxtabular version="3" rows="6" columns="2"> +<features tabularvalignment="middle"> +<column alignment="left" valignment="top" width="45text%"> +<column alignment="left" valignment="top" width="45text%"> +<row> +<cell alignment="left" valignment="top" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +Especificación formal +\end_layout + +\end_inset +</cell> +<cell alignment="left" valignment="top" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout +Maude +\end_layout + +\end_inset +</cell> +</row> +<row> +<cell alignment="left" valignment="top" topline="true" leftline="true" usebox="none"> +\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 +</cell> +<cell alignment="left" valignment="top" topline="true" leftline="true" rightline="true" usebox="none"> +\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 +</cell> +</row> +<row> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\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 +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none"> +\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 +</cell> +</row> +<row> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\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 +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none"> +\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 +</cell> +</row> +<row> +<cell alignment="center" valignment="top" topline="true" leftline="true" usebox="none"> +\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 +</cell> +<cell alignment="center" valignment="top" topline="true" leftline="true" rightline="true" usebox="none"> +\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 +</cell> +</row> +<row> +<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout + +\end_layout + +\end_inset +</cell> +<cell alignment="center" valignment="top" topline="true" bottomline="true" leftline="true" rightline="true" usebox="none"> +\begin_inset Text + +\begin_layout Plain Layout + +\family typewriter +\series bold +endfm +\end_layout + +\end_inset +</cell> +</row> +</lyxtabular> + +\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 aplica +\begin_inset Formula $RSD$ +\end_inset + + y la altura disminuye en 1, y 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<k<M$ +\end_inset + +, están entre la +\begin_inset Formula $(k-1)$ +\end_inset + +-ésima clave y la +\begin_inset Formula $k$ +\end_inset + +-ésima, y las claves de un mismo nodo están ordenadas de menor a mayor. + Se usan mucho en bases de datos, ajustando +\begin_inset Formula $p$ +\end_inset + + para que cada nodo esté en un bloque de disco minimizando las operaciones + de E/S, y existen variantes como +\begin_inset Formula $B+$ +\end_inset + +, +\begin_inset Formula $B^{*}$ +\end_inset + +, etc. +\end_layout + +\begin_layout Standard +La búsqueda es igual que en los árboles binarios y es +\begin_inset Formula $O(\frac{\log n}{\log p})$ +\end_inset + +, siendo +\begin_inset Formula $n$ +\end_inset + + el número de elementos. + Para la inserción se empieza buscando el nodo hoja donde se debería colocar + la entrada. + Si quedan huecos libres, se inserta. + Si no, la hoja (que ya tiene +\begin_inset Formula $p-1$ +\end_inset + + claves) se divide en 2 hojas con +\begin_inset Formula $\lceil\frac{p-1}{2}\rceil$ +\end_inset + + y +\begin_inset Formula $\lfloor\frac{p-1}{2}\rfloor$ +\end_inset + + claves, añadiendo, de los +\begin_inset Formula $p$ +\end_inset + + valores, el que queda en medio en el nodo padre, repitiendo el proceso + en este recursivamente si es necesario. +\end_layout + +\end_body +\end_document diff --git a/aed1/n4.lyx b/aed1/n4.lyx new file mode 100644 index 0000000..db68fda --- /dev/null +++ b/aed1/n4.lyx @@ -0,0 +1,3547 @@ +#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 +Un +\series bold +grafo dirigido +\series default + o +\series bold +digrafo +\series default + es un par +\begin_inset Formula $(V,E)$ +\end_inset + + formado por un conjunto de +\series bold +vértices +\series default + o +\series bold +nodos +\series default + +\begin_inset Formula $V\neq\emptyset$ +\end_inset + + y un conjunto de +\series bold +aristas +\series default + +\begin_inset Formula $E\subseteq\{(a,b)\in V\times V:a\neq b\}$ +\end_inset + +, mientras que uno +\series bold +no dirigido +\series default + es un par +\begin_inset Formula $(V,E)$ +\end_inset + + con +\begin_inset Formula $V\neq\emptyset$ +\end_inset + + y +\begin_inset Formula $E\subseteq\{x\in{\cal P}(V):|x|=2\}$ +\end_inset + +. + Algunas definiciones permiten +\series bold +bucles +\series default +, aristas de un nodo a sí mismo, y entonces basta que sea +\begin_inset Formula $E\subseteq V\times V$ +\end_inset + + para que el grafo sea dirigido o que +\begin_inset Formula $E\subseteq\{x\in{\cal P}(V):|x|\in\{1,2\}\}$ +\end_inset + + para que sea no dirigido. + En adelante identificamos los grafos no dirigidos +\begin_inset Formula $(V,E)$ +\end_inset + + con los correspondientes grafos dirigidos +\begin_inset Formula $(V,\bigcup_{\{u,v\}\in E}\{(u,v),(v,u)\})$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Un +\series bold +grafo etiquetado +\series default + es una terna +\begin_inset Formula $(V,E,\sigma)$ +\end_inset + + donde +\begin_inset Formula $(V,E)$ +\end_inset + + es un grafo (dirigido o no) y +\begin_inset Formula $\sigma:E\rightarrow X$ +\end_inset + + es una función que relaciona cada arista con una +\series bold +etiqueta +\series default +. + Un +\series bold +grafo con pesos +\series default + es un grafo etiquetado +\begin_inset Formula $(V,E,\sigma)$ +\end_inset + + con +\begin_inset Formula $\sigma:E\rightarrow\mathbb{R}$ +\end_inset + +. + Un grafo es +\series bold +finito +\series default + si +\begin_inset Formula $V$ +\end_inset + + lo es. +\end_layout + +\begin_layout Standard +Un +\series bold +subgrafo +\series default + de un grafo +\begin_inset Formula $G:=(V,E)$ +\end_inset + + es un grafo +\begin_inset Formula $(V',E')$ +\end_inset + + con +\begin_inset Formula $V'\subseteq V$ +\end_inset + + y +\begin_inset Formula $E'\subseteq E$ +\end_inset + +. + Un subgrafo de un grafo etiquetado +\begin_inset Formula $G:=(V,E,\sigma)$ +\end_inset + + es un grafo etiquetado +\begin_inset Formula $(V',E',\sigma|_{E'})$ +\end_inset + + donde +\begin_inset Formula $(V',E')$ +\end_inset + + es subgrafo de +\begin_inset Formula $(V,E)$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Un nodo +\begin_inset Formula $u\in V$ +\end_inset + + es +\series bold +adyacente a +\series default + +\begin_inset Formula $v\in V$ +\end_inset + + si +\begin_inset Formula $(v,u)\in E$ +\end_inset + +, y es +\series bold +adyacente de +\series default + +\begin_inset Formula $v$ +\end_inset + + si +\begin_inset Formula $(u,v)\in E$ +\end_inset + +. + Un +\series bold +camino +\series default + de +\begin_inset Formula $u$ +\end_inset + + a +\begin_inset Formula $v$ +\end_inset + + es una secuencia +\begin_inset Formula $(w_{1},\dots,w_{q})$ +\end_inset + + de elementos de +\begin_inset Formula $V$ +\end_inset + + con +\begin_inset Formula $(w_{i-1},w_{i})\in E\forall i\in\{2,\dots,q\}$ +\end_inset + +, y es +\series bold +simple +\series default + si para +\begin_inset Formula $i,j\in\{1,\dots,q\}$ +\end_inset + + con +\begin_inset Formula $i\neq j$ +\end_inset + + e +\begin_inset Formula $\{i,j\}\neq\{1,q\}$ +\end_inset + + se tiene +\begin_inset Formula $w_{i}\neq w_{j}$ +\end_inset + +. + Si +\begin_inset Formula $w_{1}=w_{q}$ +\end_inset + +, el camino es un +\series bold +ciclo +\series default +. + Un grafo es +\series bold +acíclico +\series default + si no contiene ciclos. +\end_layout + +\begin_layout Standard +Es +\series bold +conexo +\series default + o +\series bold +conectado +\series default + si existe un camino entre cualquier par de vértices, y es +\series bold +fuertemente conexo +\series default + si además es dirigido. + Un +\series bold +componente conexo +\series default + de un grafo (también +\series bold +fuertemente conexo +\series default + si el grafo es dirigido) es un subgrafo conexo que no es subgrafo de ningún + otro subgrafo conexo del grafo. +\end_layout + +\begin_layout Standard +Un grafo es +\series bold +completo +\series default + si existe una arista entre cualquier par de vértices. + En un grafo no dirigido +\begin_inset Formula $(V,E)$ +\end_inset + +, el +\series bold +grado +\series default + de un vértice +\begin_inset Formula $v\in V$ +\end_inset + + es el número de arcos adyacentes a él ( +\begin_inset Formula $|\{X\in E:v\in X\}|$ +\end_inset + +), mientras que en uno dirigido +\begin_inset Formula $(V,A)$ +\end_inset + +, definimos el +\series bold +grado de entrada +\series default + de un vértice +\begin_inset Formula $v\in V$ +\end_inset + + como +\begin_inset Formula $|\{(a,b)\in A:b=v\}|$ +\end_inset + + y el +\series bold +grado de salida +\series default + como +\begin_inset Formula $|\{(a,b)\in A:a=v\}|$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Operaciones elementales: +\end_layout + +\begin_layout Standard +\begin_inset Formula +\[ +\begin{array}{rr} +\mathsf{Vacío}:\rightarrow G & \mathsf{Crear}:\mathbb{N}\rightarrow G\\ +\mapsto(\emptyset,\emptyset) & n\mapsto(\{1,\dots,n\},\emptyset)\\ +\\ +\mathsf{IntertarNodo}:G\times{\cal U}\rightarrow G & \mathsf{InsertarArista}:G\times({\cal U}\times{\cal U})\rightarrow G\\ +((V,E),v)\mapsto(V\cup\{v\},E) & ((V,E),(a,b))\overset{a,b\in V}{\mapsto}(V,E\cup\{e\})\\ +\\ +\mathsf{EliminarNodo}:G\times{\cal U}\rightarrow G & \mathsf{EliminarArista}:G\times({\cal U}\times{\cal U})\rightarrow G\\ +((V,E),v)\mapsto(V\backslash\{e\},\{(a,b)\in E:a,b\neq v\}) & ((V,E),e)\mapsto(V,E\backslash\{e\})\\ +\\ +\mathsf{ConsultarArista}:G\times({\cal U}\times{\cal U})\rightarrow B\\ +((V,E),(a,b))\mapsto(a,b)\in A +\end{array} +\] + +\end_inset + + +\end_layout + +\begin_layout Standard +Donde +\begin_inset Formula ${\cal U}$ +\end_inset + + es el conjunto de los vértices. + Definimos también iteradores sobre los nodos adyacentes a un cierto +\begin_inset Formula $v\in V$ +\end_inset + + o adyacentes de este. +\end_layout + +\begin_layout Section +Representación +\end_layout + +\begin_layout Standard +\begin_inset Float figure +wide false +sideways false +status open + +\begin_layout Plain Layout +\align center +\begin_inset Graphics + filename graph.svg + scale 60 + +\end_inset + + +\end_layout + +\begin_layout Plain Layout +\begin_inset Caption Standard + +\begin_layout Plain Layout +Grafo no dirigido. +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Podemos dibujar un grafo indicando los nodos mediante círculos con etiqueta + (o cualquier otra forma) y uniendo con una línea los vértices de cada arista. + Si el grafo es dirigido, cada línea es una flecha que apunta al segundo + elemento del par. + Si es etiquetado, cada línea tendrá su etiqueta indicada. +\end_layout + +\begin_layout Standard +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +begin{sloppypar} +\end_layout + +\end_inset + +En un ordenador podemos representar un grafo finito +\begin_inset Formula $(V:=\{1,\dots,n\},E)$ +\end_inset + + o +\begin_inset Formula $(V:=\{1,\dots,n\},E,\sigma:E\rightarrow X)$ +\end_inset + + mediante: +\begin_inset ERT +status open + +\begin_layout Plain Layout + + +\backslash +end{sloppypar} +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Itemize + +\series bold +Matrices de adyacencia +\series default +: Matriz +\begin_inset Formula $n\times n$ +\end_inset + + de booleanos +\begin_inset Formula $((i,j)\in E)_{ij}$ +\end_inset + +. + Si el grafo es etiquetado, cuando +\begin_inset Formula $(i,j)\in E$ +\end_inset + + se añade en la celda la etiqueta, lo que en general se hace tomando un + valor +\begin_inset Formula $c\notin X$ +\end_inset + + que representa que +\begin_inset Formula $(i,j)\notin E$ +\end_inset + + y entendiendo que cualquier otro valor implica +\begin_inset Formula $(i,j)\in E$ +\end_inset + +. + Si el grafo es no dirigido, la matriz es simétrica. + Las operaciones son sencillas y el acceso a una arista dada es +\begin_inset Formula $O(1)$ +\end_inset + +, pero si +\begin_inset Formula $|E|\ll n^{2}$ +\end_inset + + ( +\series bold +matriz escasa +\series default +) se usa mucha memoria ( +\begin_inset Formula $O(n^{2})$ +\end_inset + +). +\end_layout + +\begin_layout Itemize + +\series bold +Listas de adyacencia +\series default +: +\begin_inset Formula $n$ +\end_inset + + conjuntos +\begin_inset Formula $(C_{1},\dots,C_{n})$ +\end_inset + + (representados como listas enlazadas en una lista contigua) de los que + +\begin_inset Formula $C_{i}=\{j:(i,j)\in E\}$ +\end_inset + +. + Si el grafo es etiquetado, +\begin_inset Formula $C_{i}=\{(j,\sigma(i,j)):(i,j)\in E\}$ +\end_inset + +. + Esto es más adecuado si +\begin_inset Formula $|E|\ll n^{2}$ +\end_inset + +, pues la memoria usada es +\begin_inset Formula $O(n+|E|)$ +\end_inset + +, pero la representación es más compleja y es ineficiente para encontrar + las aristas adyacentes de un cierto nodo. +\end_layout + +\begin_layout Standard +En adelante, salvo que se indique lo contrario, suponemos un grafo +\begin_inset Formula $(V:=\{1,\dots,n\},E,\sigma:E\rightarrow X)$ +\end_inset + +, y que las variables en pseudocódigo se inicializan con su valor por defecto. +\begin_inset Foot +status open + +\begin_layout Plain Layout +Para +\family sans +booleano +\family default + es +\family sans +falso +\family default +; para +\family sans +entero +\family default +, +\family sans +real +\family default + y +\begin_inset Formula $[0,+\infty]$ +\end_inset + + es +\family sans +0 +\family default +; para +\family sans +\series bold +array +\family default +\series default +s y +\family sans +\series bold +registro +\family default +\series default +s se inicializa con el valor por defecto de cada campo; para tipos contenedor + se crea una instancia vacía, y para +\family sans +RelEquiv +\family default + las clases de equivalencia son de un solo elemento. + Las variables del resto de tipos no se inicializan por defecto. +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +Recorridos +\end_layout + +\begin_layout Standard +Ambos son +\begin_inset Formula $O(|V|^{2})$ +\end_inset + + con matrices de adyacencia y +\begin_inset Formula $O(|V|+|E|)$ +\end_inset + + con listas de adyacencia. +\end_layout + +\begin_layout Subsubsection* + +\series bold +Búsqueda primero en profundidad +\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 + visitado: +\series bold +array +\series default + [1..n] +\series bold + de +\series default + booleano() +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +operación +\series default + dfs(u: [1..n]) +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +visitado[u] +\begin_inset Formula $:=$ +\end_inset + + verdadero; visitar(u) +\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 si no +\series default + visitado[v] +\series bold +entonces +\series default + dfs(u) +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +para +\series default + i +\begin_inset Formula $:=$ +\end_inset + + 1 +\series bold +hasta +\series default + n +\series bold +hacer si no +\series default +visitado[i] +\series bold +entonces +\series default + dfs(i) +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Podemos ver el órden de visita de unos nodos a otros como un +\series bold +árbol de expansión en profundidad +\series default + asociado al grafo o, si aparecen varios árboles, como un +\series bold +bosque de expansión en profundidad +\series default +. + Para construirlo, hacemos que cada elemento de +\family sans +visitado +\family default + pueda almacenar un valor +\family sans +[1..n] +\family default + indicando el padre del nodo, lo que nos permite encontrar los componentes + conexos de un grafo no dirigido. + Decimos que +\begin_inset Formula $(a,b)\in E$ +\end_inset + + es: +\end_layout + +\begin_layout Itemize +Un +\series bold +arco de avance +\series default + si +\begin_inset Formula $a$ +\end_inset + + es padre a +\begin_inset Formula $b$ +\end_inset + + en uno de los árboles del bosque. +\end_layout + +\begin_layout Itemize +Un +\series bold +arco de retroceso +\series default + si +\begin_inset Formula $a$ +\end_inset + + es hijo de +\begin_inset Formula $b$ +\end_inset + +. +\end_layout + +\begin_layout Itemize +Un +\series bold +arco de cruce +\series default + si no es de avance ni de retroceso. +\end_layout + +\begin_layout Standard +Un grafo no dirigido contiene un ciclo si y sólo si algún arco no está en + el árbol de expansión. + Un grafo dirigido contiene un ciclo si y sólo si algún arco es de retroceso. +\end_layout + +\begin_layout Subsubsection* +Búsqueda primero en anchura o amplitud +\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 + 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 + +C: Cola[[1..n]] +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +operación +\series default + bfs(u: [1..n]) +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +visitado[u] +\begin_inset Formula $:=$ +\end_inset + + verdadero; C.meter(u); visitar(u) +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\series bold +mientras no +\series default + C.vacía +\series bold +hacer +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + +v +\begin_inset Formula $:=$ +\end_inset + + C.cabeza; C.sacar +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + + +\series bold +para cada +\series default + nodo w adyacente a v +\series bold +hacer +\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 + + +\series bold +si no +\series default + visitado[w] +\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 + + +\begin_inset space \qquad{} +\end_inset + +visitado[w] +\begin_inset Formula $:=$ +\end_inset + + verdadero; C.meter(w); visitar(w) +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +para +\series default + i +\begin_inset Formula $:=$ +\end_inset + + 1 +\series bold +hasta +\series default + n +\series bold +hacer si no +\series default + visitado[i] +\series bold +entonces +\series default + bfs(i) +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Section +Árboles de expansión mínimos +\end_layout + +\begin_layout Standard +Un +\series bold +árbol de expansión +\series default + de un grafo no dirigido y conexo es un subgrafo acíclico conexo. + El +\series bold +coste +\series default + de un grafo con pesos +\begin_inset Foot +status open + +\begin_layout Plain Layout +En general, de un grafo etiquetado por elementos de algún grupo. +\end_layout + +\end_inset + + es la suma de los costes de las aristas. + Los siguientes algoritmos obtienen coste del árbol de expansión de coste + mínimo de un grafo, donde la variable +\family sans +coste +\family default + contiene dicho coste. +\end_layout + +\begin_layout Subsubsection* +Algoritmo de Prim +\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 + 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 + +C: ColaPrioridad[ +\series bold +registro +\series default + coste: real; nodo: [1..n]] +\begin_inset Formula $//$ +\end_inset + + +\emph on +A menor coste, mayor prioridad +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +coste: real +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +operación +\series default + procesar(u: [1..n]) +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +visitado[u] +\begin_inset Formula $:=$ +\end_inset + + verdadero +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\series bold +para cada +\series default + nodo v adyancente a u con peso w +\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 no +\series default + visitado[v] +\series bold +entonces +\series default + C.meter((w, v)) +\end_layout + +\begin_layout Plain Layout + +\family sans +procesar(0) +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +mientras no +\series default + C.vacía +\series bold +hacer +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +p +\begin_inset Formula $:=$ +\end_inset + + C.cabeza; C.sacar +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\series bold +si no +\series default + visitado(p.nodo) +\series bold +entonces +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + +coste +\begin_inset Formula $:=$ +\end_inset + + coste +\begin_inset Formula $+$ +\end_inset + + p.coste +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + +procesar(p.nodo) +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Como introducir y extraer elementos de la cola de prioridad es +\begin_inset Formula $O(\log n)$ +\end_inset + +, siendo +\begin_inset Formula $n$ +\end_inset + + el total de elementos de la cola que será proporcional a +\begin_inset Formula $|E|$ +\end_inset + +, el algoritmo se ejecuta en +\begin_inset Formula $O(|E|\log|E|)$ +\end_inset + +. +\end_layout + +\begin_layout Subsubsection* +Algoritmo de Kruskal +\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 + RE: RelEquiv[[1..n]] +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +coste: real +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +para cada +\series default + arista (u, v) con peso w ordenadas por peso ascendente +\series bold +hacer +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\series bold +si +\series default + RE.encuentra(u) +\begin_inset Formula $\ne$ +\end_inset + + RE.encuentra(v) +\series bold +entonces +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + +coste +\begin_inset Formula $:=$ +\end_inset + + coste +\begin_inset Formula $+$ +\end_inset + + w +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + +RE.unión(u, v) +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +El algoritmo se ejecuta en +\begin_inset Formula $O(|E|\log|E|)$ +\end_inset + +, pues es lo que se tarda en ordenar las aristas. +\end_layout + +\begin_layout Section +Caminos mínimos +\end_layout + +\begin_layout Standard +El coste de un camino es la suma de los costes de las aristas por las que + pasa, y el +\series bold +camino mínimo +\series default + entre dos nodos es el que tiene menor coste de entre los que empiezan en + el primero y terminan en el segundo. +\end_layout + +\begin_layout Standard +El +\series bold +algoritmo de Dijkstra +\series default + obtiene el mínimo coste del camino de cierto nodo (que supondremos que + es el 1) y todos los demás. + Para ello trabaja con un conjunto de nodos +\series bold +escogidos +\series default +, para los cuales se conoce ya el camino mínimo desde el origen, y otro + de +\series bold +candidatos +\series default +, de los que no sabemos el camino mínimo salvo si nos restringimos a +\series bold +caminos especiales +\series default +, los que pasan solo por nodos escogidos (más él mismo al final). + En cada paso el algoritmo toma el nodo candidato con menor distancia al + origen, lo añade a los candidatos y recalcula los caminos mínimos del resto + de candidatos. + Tras repetir esto +\begin_inset Formula $n-1$ +\end_inset + + veces, el camino mínimo de cada nodo coincide con su camino especial. + La siguiente versión del algoritmo funciona con una matriz de adyacencia + +\family sans +C +\family default + que usa +\begin_inset Formula $+\infty$ +\end_inset + + para indicar la ausencia de arista: +\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 + coste: +\series bold +array +\series default + [2..n] +\series bold +de +\begin_inset Formula $\mathsf{real}\cup\{+\infty\}$ +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +paso: +\series bold +array +\series default + [2..n] +\series bold +de +\series default + [1..n] +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +escogido: +\series bold +array +\series default + [2..n] +\series bold +de +\series default + booleano +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +para +\series default + i +\begin_inset Formula $:=$ +\end_inset + + 2 +\series bold +hasta +\series default + n +\series bold +hacer +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +coste[i] +\begin_inset Formula $:=$ +\end_inset + + C[1, i]; paso[i] +\begin_inset Formula $:=$ +\end_inset + + 1; escogido[v] +\begin_inset Formula $:=$ +\end_inset + + falso +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +para +\series default + i +\begin_inset Formula $:=$ +\end_inset + + 1 +\series bold +hasta +\series default + n +\begin_inset Formula $-$ +\end_inset + +1 +\series bold +hacer +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +u +\begin_inset Formula $:=$ +\end_inset + + i +\series bold +si no +\series default + escogido[i] +\series bold +minimizando +\series default + coste[i] +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +escogido[u] +\begin_inset Formula $:=$ +\end_inset + + verdadero +\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 no +\series default + escogido[v] +\series bold +y +\series default + coste[u] +\begin_inset Formula $+$ +\end_inset + + C[u, v] +\begin_inset Formula $<$ +\end_inset + + coste[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 + +coste[v] +\begin_inset Formula $:=$ +\end_inset + + coste[u] +\begin_inset Formula $+$ +\end_inset + + C[u, v] +\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 + +paso[v] +\begin_inset Formula $:=$ +\end_inset + + u +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +El algoritmo almacena en +\family sans +coste[i] +\family default + el coste del camino mínimo del nodo +\family sans +1 +\family default + al +\family sans +i +\family default +, y en +\family sans +paso[i] +\family default + el vértice que precede a +\family sans +i +\family default + en este camino, con lo que accediendo sucesivamente podemos encontrar el + camino mínimo +\begin_inset Foot +status open + +\begin_layout Plain Layout +Los caminos mínimos desde un único nodo al resto forman una estructura de + árbol. +\end_layout + +\end_inset + +. + Si solo necesitamos el coste, podemos omitir del algoritmo la obtención + del camino. +\end_layout + +\begin_layout Standard +Esta implementación ejecuta +\begin_inset Formula $n-1$ +\end_inset + + veces un código que busca un mínimo de entre +\begin_inset Formula $n$ +\end_inset + + valores y actualiza hasta +\begin_inset Formula $n$ +\end_inset + + candidatos, luego en total el algoritmo se ejecuta en +\begin_inset Formula $O(|V|^{2})$ +\end_inset + +. + Otra versión con listas de adyacencia consigue llegar a +\begin_inset Formula $O(|E|\log|V|)$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Para los caminos mínimos entre todos los pares, aplicamos el +\series bold +algoritmo de +\color pink +Floyd +\series default +\color inherit +: +\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 + coste: +\series bold +array +\series default + [1..n, 1..n] +\series bold +de +\series default + +\begin_inset Formula $\mathsf{real}\cup\{+\infty\}$ +\end_inset + + +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +paso: +\series bold +array +\series default + [1..n, 1..n] +\series bold +de +\series default + [1..n] +\end_layout + +\begin_layout Plain Layout + +\family sans +coste +\begin_inset Formula $:=$ +\end_inset + + C +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +para +\series default + k +\begin_inset Formula $:=$ +\end_inset + + 1 +\series bold +hasta +\series default + n +\series bold +hacer +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\series bold +para +\series default + i +\begin_inset Formula $:=$ +\end_inset + + 1 +\series bold +hasta +\series default + n +\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 +para +\series default + j +\begin_inset Formula $:=$ +\end_inset + + 1 +\series bold +hasta +\series default + n +\series bold +hacer +\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 + + +\series bold +si +\series default + coste[i, k] +\begin_inset Formula $+$ +\end_inset + + coste[k, j] +\begin_inset Formula $<$ +\end_inset + + coste[i, j] +\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 + + +\begin_inset space \qquad{} +\end_inset + +coste[i, j] +\begin_inset Formula $:=$ +\end_inset + + coste[i, k] +\begin_inset Formula $+$ +\end_inset + + coste[k, j] +\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 + + +\begin_inset space \qquad{} +\end_inset + +paso[i, j] +\begin_inset Formula $:=$ +\end_inset + + k +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Este algoritmo +\begin_inset Formula $O(n^{3})$ +\end_inset + + funciona hallando, en cada iteración del bucle externo, los caminos mínimos + pasando por un máximo de +\begin_inset Formula $k$ +\end_inset + + vértices. + El camino de un vértice +\family sans +a +\family default + a otro +\family sans +b +\family default + distintos se obtiene como el camino mínimo de +\family sans +a +\family default + a +\family sans +paso[a, b] +\family default + y aquí a +\family sans +b +\family default +. +\end_layout + +\begin_layout Standard +El +\series bold +algoritmo de Warshall +\series default + permite obtener el +\series bold +cierre transitivo +\series default + de un grafo, una matriz de booleanos +\begin_inset Formula $(a_{ij}:=\text{existe un camino de \ensuremath{i} a \ensuremath{j}})$ +\end_inset + +, y es similar al de Floyd pero cambiando la condición dentro de los bucles + por +\family sans +A[i, j] +\begin_inset Formula $:=$ +\end_inset + + A[i, j] +\series bold +o +\series default + (A[i, k] +\series bold +y +\series default + A[k, j]) +\family default +. +\end_layout + +\begin_layout Section +Componentes fuertemente conexos +\end_layout + +\begin_layout Standard +Para hallarlos, usamos el +\series bold +algoritmo de Tarjan +\series default +: +\end_layout + +\begin_layout Enumerate +Hacer búsqueda en profundidad del grafo numerando los vértices. +\end_layout + +\begin_layout Enumerate +Construir el grafo invertido: +\begin_inset Formula $(V,E)\mapsto(V,\{(b,a)\}_{(a,b)\in E})$ +\end_inset + +. +\end_layout + +\begin_layout Enumerate +Hacer búsqueda en profundidad del grafo invertido, empezando en el nodo + con mayor número en el paso 1. + Mientras queden nodos por visitar, seguir con el nodo no visitado de mayor + número. +\end_layout + +\begin_layout Enumerate +Cada árbol del bosque resultante del paso 3 es un componente fuertemente + conexo. +\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 + componentes: Conjunto[Conjunto[entero]] +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +tiempo: entero +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +número: +\series bold +array +\series default + [1..n] +\series bold +de +\series default + entero +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +enlace: +\series bold +array +\series default + [1..n] +\series bold +de +\series default + entero +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +pila: Pila[[1..n]] +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +apilado: +\series bold +array +\series default + [1..n] +\series bold +de +\series default + booleano +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +operación +\series default + tarjan(u: [1..n]) +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +número[u] +\begin_inset Formula $:=$ +\end_inset + + tiempo; enlace[u] +\begin_inset Formula $:=$ +\end_inset + + tiempo +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +tiempo +\begin_inset Formula $:=$ +\end_inset + + tiempo +\begin_inset Formula $+$ +\end_inset + + 1 +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +pila.insertar(u); apilado[u] +\begin_inset Formula $:=$ +\end_inset + + verdadero +\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 + número[v] +\begin_inset Formula $=$ +\end_inset + + 0 +\series bold +entonces +\series default + tarjan(v) +\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 + apilado[v] +\series bold +entonces +\series default + enlace[u] +\begin_inset Formula $=$ +\end_inset + + mín(enlace[u], enlace[v]) +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\series bold +si +\series default + enlace[u] +\begin_inset Formula $=$ +\end_inset + + visitado[u] +\series bold +entonces +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + +s: Conjunto[entero] +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + + +\series bold +repetir +\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 + +v +\begin_inset Formula $:=$ +\end_inset + + pila.tope; pila.sacar; apilado[v] +\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 + +s.inserta(v) +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + + +\series bold +mientras +\series default + u +\begin_inset Formula $\neq$ +\end_inset + + v +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + +componentes.inserta(s) +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +para +\series default + i +\begin_inset Formula $:=$ +\end_inset + + 1 +\series bold +hasta +\series default + n +\series bold +hacer +\series default + +\series bold +si +\series default + número[i] +\begin_inset Formula $=$ +\end_inset + + 0 +\series bold +entonces +\series default + conectar(i) +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Tras ejecutar el algoritmo, +\family sans +componentes +\family default + es el conjunto de componentes conexos del grafo. + Llamamos +\series bold +grafo reducido +\series default + +\begin_inset Formula $G_{R}:=(V_{R},E_{R})$ +\end_inset + + de +\begin_inset Formula $G:=(V,E)$ +\end_inset + + al grafo dirigido acíclico dado por +\begin_inset Formula $V_{R}:=\{\text{componentes fuertemente conexos de \ensuremath{G}}\}$ +\end_inset + + y +\begin_inset Formula $E_{R}:=\{(A,B)\in V_{R}:\exists a\in A,b\in B:(a,b)\in E\}$ +\end_inset + +. +\end_layout + +\begin_layout Standard +Los grafos dirigidos acíclicos sirven, por ejemplo, para representar órdenes + parciales. + El +\series bold +recorrido en orden topológico +\series default + de un GDA es aquel en que un vértice solo se visita tras visitar todos + los nodos adyacentes a él. + La +\series bold +numeración en orden topológico +\series default + consiste en numerar los nodos de un GDA de forma que, si +\begin_inset Formula $a$ +\end_inset + + es adyacente a +\begin_inset Formula $b$ +\end_inset + +, el número asignado a +\begin_inset Formula $a$ +\end_inset + + es menor que el asignado a +\begin_inset Formula $b$ +\end_inset + +. +\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 + orden: Pila[[1..n]] +\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 +\series bold +operación +\series default + numerar(u: [1..n]) +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +visitado[u] +\begin_inset Formula $:=$ +\end_inset + + verdadero +\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 si no +\series default +visitado[v] +\series bold +entonces +\series default + numerar(v) +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +orden.insertar(u) +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +para +\series default + i +\begin_inset Formula $:=$ +\end_inset + + 1 +\series bold +hasta +\series default + n +\series bold +hacer si no +\series default + visitado[i] +\series bold +entonces +\series default + numerar(i) +\end_layout + +\end_inset + + +\end_layout + +\begin_layout Standard +Esto guarda un orden topológico en la pila +\family sans +orden +\family default + de forma que el elemento en la cima es el primero, el siguiente el segundo, + etc. +\end_layout + +\begin_layout Section +Grafos eulerianos +\end_layout + +\begin_layout Standard +Un +\series bold +punto de articulación +\series default + de un grafo no dirigido es un vértice que, al eliminarlo del grafo (junto + a las aristas incidentes) se divide un componente conexo en dos o más. + Un grafo no dirigido es +\series bold +biconexo +\series default + si no tiene puntos de articulación. + Un +\series bold +componente biconexo +\series default + de un grafo es un subgrafo biconexo de este que no es subgrafo de otro + subgrafo biconexo. +\end_layout + +\begin_layout Standard +Un grafo tiene +\series bold +conectividad +\series default + +\begin_inset Formula $k\in\mathbb{N}$ +\end_inset + + si es necesario eliminar +\begin_inset Formula $k$ +\end_inset + + nodos para que el grafo no sea conexo, por lo que un grafo es biconexo + si tiene conectividad 2 o más. + El siguiente algoritmo busca puntos de articulación: +\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 + tiempo: entero +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +raíz: entero +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +hijosRaíz: entero +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +número: +\series bold +array +\series default + [1..n] +\series bold +de +\series default + entero +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +enlace: +\series bold +array +\series default + [1..n] +\series bold +de +\series default + entero +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +padre: +\series bold +array +\series default + [1..n] +\series bold +de +\series default + entero +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +articulación: +\series bold +array +\series default + [1..n] +\series bold +de +\series default + booleano +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +operación +\series default + puntosArticulación(u: [1..n]) +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +número[u] +\begin_inset Formula $:=$ +\end_inset + + tiempo; enlace[u] +\begin_inset Formula $:=$ +\end_inset + + tiempo +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + +tiempo +\begin_inset Formula $:=$ +\end_inset + + tiempo +\begin_inset Formula $+$ +\end_inset + + 1 +\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 + número[v] +\begin_inset Formula $=$ +\end_inset + + 0 +\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 + +padre[v] +\begin_inset Formula $:=$ +\end_inset + + u +\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 + + +\series bold +si +\series default + u +\begin_inset Formula $=$ +\end_inset + + raíz +\series bold +entonces +\series default +hijosRaíz +\begin_inset Formula $:=$ +\end_inset + + hijosRaíz +\begin_inset Formula $+$ +\end_inset + + 1 +\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 + +puntosArticulación(v) +\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 + + +\series bold +si +\series default + enlace[v] +\begin_inset Formula $\geq$ +\end_inset + + número[u] +\series bold +entonces +\series default + articulación[u] +\begin_inset Formula $:=$ +\end_inset + + verdadero +\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 + +enlace[u] +\begin_inset Formula $:=$ +\end_inset + + mín(enlace[u], enlace[v]) +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + + +\series bold +sino si +\series default + v +\begin_inset Formula $\neq$ +\end_inset + + padre(u) +\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 + +enlace[u] +\begin_inset Formula $:=$ +\end_inset + + mín(enlace[u], número[v]) +\end_layout + +\begin_layout Plain Layout + +\family sans +\series bold +para +\series default + i +\begin_inset Formula $:=$ +\end_inset + + 1 +\series bold +hasta +\series default + n +\series bold +hacer +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\series bold +si +\series default + número[i] +\begin_inset Formula $=$ +\end_inset + + 0 +\series bold +entonces +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + +raíz +\begin_inset Formula $:=$ +\end_inset + + i; hijosRaíz +\begin_inset Formula $:=$ +\end_inset + + 0; puntosArticulación(i) +\end_layout + +\begin_layout Plain Layout + +\family sans +\begin_inset space \qquad{} +\end_inset + + +\begin_inset space \qquad{} +\end_inset + +articulación[raíz] +\begin_inset Formula $:=$ +\end_inset + + hijosRaíz +\begin_inset Formula $>$ +\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 |
