2. BASE TEÓRICA - biblus.us.es

SOFTWARE PARA

2. BASE TEÓRICA

2.1 INTRODUCCIÓN

En capítulos posteriores se describirá la aplicación

vista del usuario, lo que nos

estructura externa del programa y conocer las posibilidades que este tiene.

En este capítulo vamos comenzar con un nivel más bajo que el del

usuario, se trata de la base teórica en la cual se ha fundamentado el

desarrollo de la aplicación. Dos son los puntos importantes a tener en

cuenta aquí, por un lado la Teoría de Grafos y por otro las operaciones con

secuencias

2.2 TEORÍA DE GRAFOS

LaTeoríade Grafosjuegaunpap

matemáticadelasCiencias

herramientabásicaparamo

sonfundamentalesparala

comprensióndelasestruc

Enmatemáticasycienciasdela

laspropiedadesdelosgrafo

nodos) conectados por

tener

grafoestádiseñadoporuna

depuntos(losvértices)con

Ennuestro caso, la representación de la información en el área de

trabajo de nuestra aplicación tomará la forma de un grafo dirigido, donde

diferentes cajas (fuentes, sumideros y operaciones),

entre sí por medio de aristas dirigidas.

Necesitaremos conocer la estructura del grafo del área de trabajo

para poder obtener los resultados de las diferentes operaciones que se

realizarán en la misma.

utilizados son descritos en esta sección.

PARA CÁLCULO Y APRENDIZAJE DE SEÑALESDISCRETAS

9

BASE TEÓRICA

INTRODUCCIÓN

En capítulos posteriores se describirá la aplicación desde el punto de

vista del usuario, lo que nos servirá para tener una visión general de la



a base teórica en la cual se ha fundamentado el



TEORÍA DE GRAFOS

ade Grafosjuegaunpapelimportanteenla fu

ciasdela Computación.Losgrafoscon

ramodelarfenómenosdiscretosy

la

cturasdedatosyelanálisisdealgoritmos.

nciasdelacomputación,lateoríadegrafosdadesdelosgrafos,quesoncoleccionesdeobjetosllamadosv

nectados por líneas llamadas aristas (o arcos) que pueden

orientación(direcciónasignada).T

ñadoporunaserie

onectadosporlíneas(lasaristas).



diferentes cajas (fuentes, sumideros y operaciones), nodos, estarán unidas

entre sí por medio de aristas dirigidas.



realizarán en la misma. El cómo se obtiene la topología, los algoritmos

utilizados son descritos en esta sección.

SEÑALES

desde el punto de

para tener una visión general de la



a base teórica en la cual se ha fundamentado el



undamentación

.Losgrafosconstituyenuna

sestudia

amadosvértices(o

o arcos) que pueden

ónasignada).Típicamente,un



nodos, estarán unidas



, los algoritmos

SOFTWARE PARA CÁLCULO Y APRENDIZAJE DE SEÑALES DISCRETAS

10

2.2.1 Definición

Llamaremos grafo, G, al par ordenado formado por un conjunto finito no

vacío, V, y un conjunto, A, de pares no ordenados de elementos del mismo.

V es el conjunto de los vértices o nodos del grafo.

A será el conjunto de las aristas o arcos del grafo.

Utilizaremos la notación G = (V, A) para designar al grafo cuyos

conjuntos de vértices y aristas son, respectivamente, V y A.

Llamaremos orden, n, al número total de vértices, |V|, y tamaño, m, al

número total de aristas, |A|.

La notación para las aristas es (x,y), donde x e y representan los

extremos (vértices) de la arista. En caso de grafos dirigidos, x representa el

vértice origen e y el vértice destino.

En el grafo anterior tendremos, por ejemplo:

• V(G)={1, 2, 3, 4, 5, 6, 7}

• A(G)={(1,2), (4,2), (7,2), (4,5), (4,6), (4,7), (5,3), (5,6), (3,6),

(6,7)}

Este grafo tendría orden n=7 y tamaño m=10.

En la representación de un grafo, laformadelasaristas suele

representarse por una línea y los vértices por puntos o polígonos. La forma

de las aristas o los vértices no es relevante, lo único que importa es a qué

vértices están conectadas las aristas. La posición de los vértices tampoco

es relevante, aunque la colocación en forma de polígono regular ayuda a

facilitar la lectura de los.

Cualquier tipo deredpuedeser modeladaconungrafo:la red telefónica, la

red eléctrica, un mapa de carreteras, etc.


11

2.2.2 Tipos de grafos

Teniendo en cuenta el tipo y número de aristas que pueden conectar un

par de vértices existen diferentes clasificaciones de grafos.

2.2.2.1 Grafos simples

Ungrafoessimplesi, como

mucho,sólounaaristaunedosvérticescualesquiera.

Estoesequivalenteadecirqueunaaristacualquieraeselúnico

elementoqueunedos vérticesespecíficos.

Ungrafoquenoessimplesedenominacomplejo.

2.2.2.2 Multigrafos

Se dice que G es un multígrafo si existe más de una arista entre el

mismo par de vértices.

2.2.2.3 Pseudografos

Se dice que G es un pseudografo si existe una arista que comienza y

termina en el mismo vértice, es decir, si existen aristas que forman bucles o

ciclos.


12

2.2.2.4 Grafos dirigidos

Se dice que G es un grafo dirigido o dígrafo si las aristas están dadas por

un conjunto de pares ordenados de vértices, es decir, las aristas tienen una

orientación (un origen y un destino) y están representadas mediante

flechas.

En el grafo anterior tendremos, por ejemplo:

• V(G)={1, 2, 3, 4, 5, 6, 7}

• A(G)={(2,1), (4,2), (2,7), (4,5), (7,4), (4,6), (3,5), (5,3), (6,5),

(3,6), (6,3), (6,7)}

Este grafo tendría n=7 y m=12.

2.2.3 Representación de grafos

En el apartado anterior se ha definido el grafo como un conjunto de

vértices y aristas. En este apartado vamos a describir otro tipo de

representaciones de grafos más amigables para su procesado a través de

computador.

2.2.3.1 Matriz de adyacencia

Supongamos que tenemos un grafo simple de orden n=k, G=(V,A), con

un conjunto de vértices V={v1, v2, v3,… vk), k=1, 2,… k-1. La matriz de

adyacencia de G, A[G]=[aij], será una matriz cuadrada de orden k x k

definida como:

1 si {vi, vj} es una arista de G.

aij=

0 en caso contrario.

Para un grafo simple la matriz es simétrica respecto de la diagonal

principal, es decir aij=aji; además, dado que un grafo simple no tiene ciclos,


13

los elementos de la diagonal principal serán todos cero. También destacar

que el número de unos de cada fila coincidirá con el grado del vértice.

2.2.3.2 Matriz de incidencia

Supongamos que tenemos un grafo simple de orden n=k, G=(V,A), con

un conjunto de vértices V={v1, v2, v3,… vk), k=1, 2,… k-1 y con un conjunto

de aristas A={a1, a2,… am}, m=1,2,… m-1. La matriz de incidencia de G,

I[G]=[bij], será una matriz de orden k x m definida como:

1 si la arista aj es incidente con el vértice vi.

bij=

0 en caso contrario.

Para un grafo simple, el número de unos de cada fila coincidirá con el

grado del vértice y el número de unos de cada columna será 2.

2.2.4 Caminos y conectividad

Un camino en un grafo G=(V,A) es una sucesión de aristas a=a1, a2,… an

tal que existe una sucesión de vértices p=p0, p1,… pn que comienza en el

vértice p0 (vértice inicial del recorrido) y acaba en el vértice pn (vértice final

del recorrido) siguiendo el recorrido de las aristas a.

Un camino es cerrado si p0=pn y n>1.

La longitud de un camino es n, el número de aristas que hay en el

mismo.

Diremos que un grafo es conexo si y sólo si hay un camino entre

cualquier par de vértices diferente del grafo. Así pues, cualquier par de

vértices del grafo se puede comunicar si el grafo es conexo.

Diremos que dos vértices del grafo están conectados sí y sólo si existe

un camino entre ellos.

2.2.5 Árboles

Un árbol es un tipo especial de grafo que cumple una serie de requisitos

y que, debido a sus múltiples aplicaciones y especial implicación en el

contenido de este proyecto, se le ha dedicado un apartado especial.


14

Definimos un árbol como un grafo G=(V,A) sin ciclos y conexo. Dado que

no puede contener ciclos, tampoco podrá contener aristas múltiples, por lo

que un árbol es un grafo simple.

Un árbol es particularmente útil en computación debido a su utilidad

para organizar información, para acceder eficientemente a ella, para el

modelado de toma de decisiones, etc.

En nuestro caso, nos servirá para encontrar rutas y posibles ciclos entre

fuentes y sumideros de información.

2.2.6 Búsqueda en árboles

Para la búsqueda de información en árboles, existen dos algoritmos

fundamentales que nos evitan pasar varias veces por el mismo nodo

durante dicha búsqueda o repetir determinados pasos que lo único que

provocan son pérdidas de tiempo.

Estos dos algoritmos son:

• Algoritmo de búsqueda en profundidad (DFS, Depth First Search)

• Algoritmo de búsqueda en anchura (BFS, Breadth First Search)

2.2.6.1 Búsqueda en profundidad

La búsqueda en profundidad consiste, groso modo, en penetrar en el

grafo desde el vértice inicial hasta el más lejano que se encuentre

conectado. Una vez terminado, volver hacia atrás para seguir la búsqueda

de nodos nuevos penetrando hasta la máxima profundidad.

Las características de este algoritmo son:

• Requiere llevar la cuenta de los vértices visitados y no visitados

• El recorrido no es único y depende de la elección del vértice inicial

así como del orden de visita de los adyacentes.

• El orden de visita de unos nodos puede interpretarse como un

árbol de expansión en profundidad asociado al grafo.

En las siguientes figuras se detalla un ejemplo del mismo:


15

2.2.6.2 Búsqueda en anchura

En el algoritmo de búsqueda en anchura la filosofía es completamente

opuesta al algoritmo de búsqueda en profundidad. La idea en este caso es

tomar un vértice inicial y buscar las adyacencias a este vértice. Una vez

completadas las adyacencias del vértice inicial, buscar las adyacencias de

los siguientes vértices sucesivamente hasta finalizar con todos los vértices.

Las siguientes figuras explican de manera gráfica el algoritmo de

búsqueda en anchura.


16

Para nuestra aplicación, se ha elegido el algoritmo de búsqueda en

anchura, ya que nos permite obtener la topología completa del grafo del

área de operaciones en el menor número de iteraciones posibles y, lo más

importante, sin depender de la elección del vértice inicial.

2.3 SECUENCIAS Y OPERACIONES

2.3.1 Qué es una secuencia

Una señal es una función que contiene información acerca de un estado

o comportamiento de un sistema físico. Una secuencia es una señal discreta

en el tiempo, esto es, que la señal está definida sólo para determinados


17

puntos temporales. A los valores que toma la secuencia en estos periodos

de tiempo se les denomina muestras, y sus valores pueden ser tanto reales

como complejos.

Matemáticamente, una secuencia puede ser: �� = �� + ��, −∞ < � < ∞, siendo �� la parte real y �� la parte imaginaria de ��.

Las secuencias se pueden representar de muchas maneras diferentes;

en este proyecto, en concreto, nos van a interesar dos tipos de

representación sobre el resto:

• Representación mediante una tabla

� -2 -1 0 1 2 3 4 5 6 �� 4 3 6 2 8 10 12 -4 -7

• Representación mediante una gráfica

2.3.2 Clasificaciones de secuencias

Atendiendo a determinadas características de las secuencias se pueden

clasificar en los tipos que se describen en los siguientes subapartados.

2.3.2.1 Secuencia Simétrica y Antisimétrica Conjugada

Una secuencia es simétrica conjugada si cumple �� = �∗�−��. Una secuencia es antisimétrica conjugada si cumple �� = −�∗�−��. Para el caso de secuencias reales, la clasificación se reduce a secuencias

pares si cumplen �� = ��−�� y secuencias impares si cumplen�� =−��−��.


18

En la figura siguiente se puede observar una secuencia par:

En la siguiente figura se puede observar una secuencia impar:

2.3.2.2 Secuencia Periódica y No Periódica

Una secuencia periódica cumple la relación �� = �� + ��, siendo N un

entero positivo. Es decir, al realizar un desplazamiento de N muestras a lo

largo de la secuencia, la forma y los valores de la misma se repiten.

Un ejemplo de secuencia periódica lo encontramos en la siguiente figura:

Las secuencias que no cumplen la relación anterior se denominan

secuencias no periódicas o aperiódicas.


19

2.3.2.3 Secuencia de Energía y de Potencia

Definiendo el promedio de potencia de una secuencia como:

Y definiendo la energía total de una secuencia como:

Las secuencias se pueden clasificar en:

• Secuencias de energía: Si la energía total de la misma es finita y

mayor que cero. En estas secuencias P=0.

• Secuencias de potencia: Si la potencia promedio es finito y

distinto de cero. En estas secuencias E=∞.

• Existe un tercer caso en el que no son ni de energía ni de

potencia, y son aquellas en las que E=P=∞.

En el caso que nos ocupa, nos centraremos en secuencias de energía, ya

que son finitas en el tiempo, al igual que la memoria de nuestras

computadoras.

2.3.3 Secuencias elementales

2.3.3.1 Secuencia impulso unidad o delta

Se define como:

2.3.3.2 Secuencia escalón unidad

Se define como:


20

2.3.3.3 Secuencia exponencial real

Se define como:

2.3.3.4 Secuencia exponencial compleja

Se define como:


21

2.3.4 Sistemas

Un sistema es cualquier proceso que transforma una señal de entrada en

otra de salida y puede venir dado por un operador matemático que da

cuenta de dicha transformación.

La representación gráfica de un sistema es la siguiente:

Los sistemas se pueden clasificar en varios tipos que veremos a

continuación. Para nosotros, los sistemas más importantes serán los

sistemas LTI (Lineales e invariantes en el tiempo), puesto que serán los

sistemas que implementemos en nuestro software.

2.3.4.1 Sistemas lineales

Si �� es la salida de un sistema ante una entrada �� e �� es la

salida del mismo sistema ante la entrada ��, si el sistema es lineal, ante

una entrada �� = �� + �� el sistema dará una salida del tipo

�� = �� + ��, es decir, el sistema cumple con el principio de

superposición.


22

2.3.4.2 Sistemas invariantes en el tiempo

Si �� es la salida de un sistema ante una entrada ��, ante una

entrada �� = �� − �� el sistema dará una salida del tipo �� = �� − ��, es decir, ante una misma entrada, el sistema dará una misma salida

independientemente de cuándo se aplique esta entrada.

2.3.4.3 Sistemas causales

Un sistema es causal si la salida en el instante �� sólo depende de la

entrada en ese instante �� ó anteriores y de su propia salida en instantes

anteriores a ��, es decir, se trata de un sistema no anticipativo, puesto que

su salida no se anticipa a lo que pueda ocurrir en su entrada.

2.3.4.4 Sistemas sin memoria

Un sistema sin memoria es aquel en el que su salida en el instante �� depende sólo de su entrada en el instante ��.

2.3.4.5 Sistema estable BIBO

Un sistema será estable bajo el criterio BIBO (Bounded Input Bounded

Output) si ante cualquier entrada acotada |��| ≤ � < ∞, su salida está

también acotada |��| ≤ � < ∞.

2.3.4.6 Sistemas FIR

Un sistema FIR es un sistema cuya respuesta al impulso es finita (Finite

Impulse Response), es decir, la respuesta al impulso del sistema es

diferente de cero sólo para � ≤ � ≤ �, siendo A y B enteros finitos.

Por contraposición, un sistema IIR (Infinite Impulse Response) tiene una

respuesta al impulso infinita, es decir, es diferente de cero para ∞ ≤ � ≤ ∞

2.3.5 Operaciones con secuencias

Una vez introducidos a los conceptos de secuencia y sistema, pasemos a

describir los tipos de operaciones básicas que se pueden realizar con

secuencias y sistemas.


23

2.3.5.1 Suma

La suma de dos señales, �� y ��, es una señal �� cuyo valor en

cualquier instante es igual a la suma de los dos valores en ese instante de

las dos señales de partida.

�� = �� + ��

2.3.5.2 Multiplicación por un escalar

La multiplicación por un escalar o escalado en amplitud de una señal por

una constante A se obtiene multiplicando el valor de cada muestra de la

señal por esa constante.

�� = � · ��

2.3.5.3 Desplazamiento en el tiempo

El desplazamiento (adelanto o retardo) de una señal �� en el tiempo se

obtiene al coger las distintas muestras de �� y colocarlas a la salida en

posiciones adelantadas o retrasadas tantas posiciones como indique el

índice de desplazamiento.

�� = �� − ��

2.3.5.4 Inversión temporal

La inversión de una señal �� en el tiempo se obtiene al coger las

distintas muestras de �� y colocarlas a la salida en posiciones opuestas

(desde cero).

�� = ��−��

2.3.5.5 Multiplicación entre secuencias

El producto de dos señales, �� y ��, es una señal �� cuyo valor en

cualquier instante es igual al producto de los dos valores en ese instante de

las dos señales de partida.

�� = �� · ��


24

2.3.5.6 Convolución

La operación siguiente se denomina suma de convolución o convolución

a secas.

�� = �� ∗ �� La expresión matemática es equivalente a:

�� = � �� · �� − ��

� !�= � �� − �� · ��

�

� !�

Esta operación es muy importante, ya que permite calcular la salida de

un sistema LTI ante cualquier entrada con tan sólo conocer la respuesta al

impulso del sistema.

2.3.6 DFT e IDFT

La Transformada Discreta de Fourier (Discrete Fourier Transform, DFT)

de N puntos se define como

"�� = ∑ �� · $!%�&'()*!�& � , � = 0,1,…� − 1

Teniendo en cuenta esto, podemos decir:

• Si la longitud de �� es mayor que N, se desprecian directamente

las muestras que caigan fuera del rango del sumatorio, es decir,

las situadas a partir de N. Se perderá información necesaria en

este caso.

• Si la longitud de �� es menor que N, se tomarán tantas

muestras nulas como sea necesario, rellenando con ceros el

sumatorio hasta completar la cantidad de N. Se obtendrá más

información de la necesaria en este caso.

La Transformada Discreta de Fourier Inversa (Inverse DFT, IDFT) de N

puntos se define como:

�� = ∑ "�� · $%�&'()*!�� , � = 0,1,…� − 1 La señal recuperada mediante la IDFT no es exactamente ��, sino sus

N primeras muestras. Por esta razón, sólo podremos recuperar ��a partir

de la IDFT de "�� sí y sólo si, �� tiene longitud finita y menor o igual que

N.


25

2.3.6.1 Fast Fourier Transform

El cálculo directo de la DFT e IDFT mediante las expresiones

anteriormente citadas puede llegar a ser bastante costoso en cuanto a

recursos computacionales a partir de una cantidad de muestras N no

demasiado elevada, ya que se requieren �� multiplicaciones y sumas

complejas.

Por esta razón, existen algoritmos computacionales que permiten

realizar el cálculo de la DFT. Uno de estos algoritmos, el más ampliamente

utilizado es el FFT (Fast Fourier Transform). Este algoritmo se basa en la

descomposición del cálculo de la DFT completa en otros cálculos más

pequeños.

El método más famoso para el cálculo de la FFT es el basado en el

diezmado en el tiempo, diseñado por J.W. Cooley y John Tukey en 1965.

Este algoritmo se basa en dividir la señal de entrada en dos señales de N/2

muestras, una para los coeficientes pares y otra para los impares. A su vez,

estas dos señales se pueden volver a descomponer, así sucesivamente

hasta aplicar la DFT a las múltiples subseñales obtenidas, resultando así en

un cálculo más rápido de la DFT. Es decir, en lugar de necesitar �� multiplicaciones y sumas complejas, necesitaríamos tan sólo � · /01��

operaciones.


26

Documents

2. BASE TEÓRICA - biblus.us.es