#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass book
\use_default_options true
\maintain_unincluded_children false
\language spanish
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style swiss
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header
\begin_body
\begin_layout Standard
Una
\series bold
secuencia
\series default
es un conjunto ordenado de valores.
Se expresa como
\begin_inset Formula $[a_{1},\dots,a_{n}]$
\end_inset
.
La función
\begin_inset Quotes cld
\end_inset
\begin_inset Formula $long(S)$
\end_inset
\begin_inset Quotes crd
\end_inset
devuelve la longitud de la secuencia
\begin_inset Formula $S$
\end_inset
.
Si
\begin_inset Formula $S=[a_{1},\dots,a_{n}]$
\end_inset
y
\begin_inset Formula $S'=[b_{1},\dots,b_{m}]$
\end_inset
y
\begin_inset Formula $e$
\end_inset
es un elemento, definimos conceptualmente las siguientes operaciones:
\end_layout
\begin_layout Itemize
\series bold
Añadir un elemento:
\series default
\begin_inset Formula $S\bullet e=[a_{1},\dots,a_{n},e]$
\end_inset
;
\begin_inset Formula $e\circ S=[e,a_{1},\dots,a_{n}]$
\end_inset
.
\end_layout
\begin_layout Itemize
\series bold
Concatenar secuencias:
\series default
\begin_inset Formula $S\&S'=[a_{1},\dots,a_{n},b_{1},\dots,b_{m}]$
\end_inset
.
\end_layout
\begin_layout Itemize
\begin_inset Formula $primero(S)=a_{1}$
\end_inset
;
\begin_inset Formula $último(S)=a_{n}$
\end_inset
.
\end_layout
\begin_layout Itemize
\series bold
Sucesor:
\series default
\begin_inset Formula $sucesor(S,i)=S_{i+1}$
\end_inset
.
\end_layout
\begin_layout Itemize
\series bold
Cola
\series default
y
\series bold
cabeza:
\series default
\begin_inset Formula $cola(S)=[S_{2},\dots,S_{n}]$
\end_inset
;
\begin_inset Formula $cabeza(S)=[S_{1},\dots,S_{n-1}]$
\end_inset
.
\end_layout
\begin_layout Itemize
\series bold
¿Vacía?
\series default
:
\begin_inset Formula $esvacía(S)=\begin{cases}
\text{Verdadero} & S=[]\\
\text{Falso} & S\neq[]
\end{cases}$
\end_inset
\end_layout
\begin_layout Subsection
Primer modelo
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
E.
inicial
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
E.
final
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Efecto
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
Comenzar(S)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Marcada/Consulta
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Consulta
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Comienza desde el principio.
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
Avanzar(S)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Consulta
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Consulta
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Avanza un elemento.
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
EA(S)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Consulta
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Consulta
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Obtiene el elemento actual.
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
Crear(S)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Cualquiera
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Creación
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Crea una secuencia vacía.
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
Registrar(S,e)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Creación
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Creación
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Añade un elemento.
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
Marcar(S)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Creación
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Marcada
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Añade una marca de fin de secuencia.
\end_layout
\end_inset
|
\end_inset
\end_layout
\begin_layout Standard
Por defecto una secuencia no está en ningún estado, por lo que solo podemos
usar Crear(S).
En Pascal, estas operaciones se encuentran en los archivos
\family typewriter
unitmse1
\family default
,
\family typewriter
unitmsc1
\family default
y
\family typewriter
unitmsr1
\family default
para enteros, caracteres y reales.
Debemos añadir el código justo después de la línea con el nombre del programa,
con el nombre del archivo correspondiente:
\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 typewriter
uses
\end_layout
\begin_layout Plain Layout
\family typewriter
\begin_inset space \hspace{}
\length 8ex
\end_inset
\emph on
unitms
\series bold
x
\series default
1
\emph default
;
\end_layout
\end_inset
\end_layout
\begin_layout Standard
El tipo de dato es
\begin_inset Formula $MS_{x}1$
\end_inset
(siendo
\begin_inset Formula $_{x}$
\end_inset
una
\family typewriter
e
\family default
,
\family typewriter
c
\family default
o
\family typewriter
r
\family default
), y las funciones se denominan
\begin_inset Newline newline
\end_inset
\begin_inset Formula $Comenzar\_MS_{x}1$
\end_inset
, etc.
Además, se añaden
\begin_inset Formula $Encender\_Maquina\_MS_{x}1(S)$
\end_inset
, que debe ser llamada una y sólo una vez antes de cualquier otra operación
sobre la secuencia (el
\begin_inset Quotes cld
\end_inset
constructor
\begin_inset Quotes crd
\end_inset
) y
\begin_inset Formula $Cargar\_Fichero\_MS_{x}1(S,s)$
\end_inset
, donde
\begin_inset Formula $s$
\end_inset
es una cadena de caracteres (capítulo 5), y carga en la secuencia los datos
leídos del fichero indicado en
\begin_inset Formula $s$
\end_inset
.
\end_layout
\begin_layout Subsection
Segundo modelo
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
|
\begin_inset Text
\begin_layout Plain Layout
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
E.
inicial
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
E.
final
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Efecto
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
Iniciar(S)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Cr./Inic./Cons.
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Consulta
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Comienza desde antes del
\begin_inset Formula $1^{er}$
\end_inset
elemento.
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
Avanzar(S)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Iniciada/Cons.
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Consulta
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Avanza un elemento.
Error si EsÚltimo.
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
EA(S)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Consulta
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Consulta
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Obtiene el elemento actual.
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
EsVacía(S)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Cualquiera
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
(E.
inicial)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Devuelve si la secuencia es vacía.
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
EsÚltimo(S,e)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Inic./Cons.
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
(E.
inicial)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Devuelve si el elem.
actual es el último.
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
Crear(S)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Cualquiera
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Creación
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Crea una secuencia vacía.
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
Registrar(S)
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Creación
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Creación
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Añade un elemento a la secuencia.
\end_layout
\end_inset
|
\end_inset
\end_layout
\begin_layout Standard
Estas secuencias son similares a las del primer modelo, y en Pascal se usan
igual, pero no tienen marca de fin y empiezan antes del primer elemento.
\end_layout
\begin_layout Section
Composición iterativa
\end_layout
\begin_layout Standard
Las iteraciones tienen un
\series bold
invariante
\series default
(INV), que se cumple tras cada ciclo y es un subconjunto de la post-condición,
además de tener una
\series bold
precondición
\series default
(PRE) y una
\series bold
postcondición
\series default
(POST).
\end_layout
\begin_layout Standard
\align center
\begin_inset Tabular
|
\begin_inset Text
\begin_layout Plain Layout
Lenguaje algorítmico
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
Pascal
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
\series bold
MIENTRAS
\series default
\begin_inset Formula $c$
\end_inset
\series bold
HACER
\end_layout
\begin_layout Plain Layout
\family typewriter
\begin_inset space \hspace{}
\length 8ex
\end_inset
\begin_inset Formula $e$
\end_inset
\end_layout
\begin_layout Plain Layout
\series bold
FIN_MIENTRAS
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\family typewriter
while
\begin_inset Formula $c$
\end_inset
do
\end_layout
\begin_layout Plain Layout
\family typewriter
\begin_inset space \hspace{}
\length 8ex
\end_inset
\begin_inset Formula $e$
\end_inset
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
\series bold
REPETIR
\end_layout
\begin_layout Plain Layout
\family typewriter
\begin_inset space \hspace{}
\length 8ex
\end_inset
\begin_inset Formula $s$
\end_inset
\end_layout
\begin_layout Plain Layout
\series bold
HASTA_QUE
\series default
\begin_inset Formula $c$
\end_inset
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\family typewriter
repeat
\end_layout
\begin_layout Plain Layout
\family typewriter
\begin_inset space \hspace{}
\length 8ex
\end_inset
\begin_inset Formula $s$
\end_inset
\family default
(no es necesario
\family typewriter
begin
\family default
..
\family typewriter
end
\family default
).
\end_layout
\begin_layout Plain Layout
\family typewriter
until
\begin_inset Formula $c$
\end_inset
\end_layout
\end_inset
|
|
\begin_inset Text
\begin_layout Plain Layout
\series bold
ITERAR
\end_layout
\begin_layout Plain Layout
\family typewriter
\begin_inset space \hspace{}
\length 8ex
\end_inset
\begin_inset Formula $s_{1}$
\end_inset
\end_layout
\begin_layout Plain Layout
\series bold
DETENER
\series default
\begin_inset Formula $c$
\end_inset
\end_layout
\begin_layout Plain Layout
\family typewriter
\begin_inset space \hspace{}
\length 8ex
\end_inset
\begin_inset Formula $s_{2}$
\end_inset
\end_layout
\begin_layout Plain Layout
\series bold
FIN_ITERAR
\end_layout
\end_inset
|
\begin_inset Text
\begin_layout Plain Layout
\family typewriter
repeat
\end_layout
\begin_layout Plain Layout
\family typewriter
\begin_inset space \hspace{}
\length 8ex
\end_inset
\begin_inset Formula $s_{1}$
\end_inset
;
\end_layout
\begin_layout Plain Layout
\family typewriter
if
\begin_inset Formula $c$
\end_inset
then break;
\end_layout
\begin_layout Plain Layout
\family typewriter
\begin_inset space \hspace{}
\length 8ex
\end_inset
\begin_inset Formula $s_{2}$
\end_inset
;
\end_layout
\begin_layout Plain Layout
\family typewriter
until false
\end_layout
\end_inset
|
\end_inset
\end_layout
\begin_layout Standard
En exámenes y prácticas, no podemos utilizar
\family typewriter
break
\family default
salvo en este caso.
\end_layout
\begin_layout Standard
Cualquier composición iterativa se puede expresar en términos de cualquier
otra, pero hay que saber elegir la más apropiada en cada caso.
\end_layout
\end_body
\end_document