Compromisos espaciales-temporales

Dr. Eduardo A. RODRÍGUEZ TELLO

CINVESTAV-Tamaulipas

14 de marzo de 2018

Dr. Eduardo RODRÍGUEZ T. (CINVESTAV) Compromisos espaciales-temporales 14 de marzo de 2018 1 / 51

1 Compromisos espaciales-temporales

2 Mejoramiento de la entraOrdenamiento por conteo-comparaciónBúsqueda de subcadenas (string matching)Búsqueda de subcadenas con preprocesamientoAlgoritmo de Horspool

3 Pre-estructuraciónHashing

4 Programación dinámica (PD)PD, alineamiento de secuencias biológicas

Compromisos espaciales-temporales

Existen dos variantes de algoritmos con compromisosespaciales-temporales:

1 Mejoramiento de la entra: preprocesa la entrada para almacenarinformación que será usada más tarde para resolver el problema

Ordenamiento por conteo-comparaciónAlgoritmos para búsqueda de subcadenas

2 Pre-estructuración: preprocesa la entrada para facilitar el accesoa sus elementos

HashingEsquemas de indexación (e.g., B-trees)

Mejoramiento de la entra Ordenamiento por conteo-comparación

Ordenamiento por conteo-comparación

El ordenamiento por conteo-comparación contabiliza, para cadamiembro de la lista a ordenar, el número de elementos menoresque él y lo almacena en una tabla.

Estos números indicarán las posiciones de los elementos de lalista ordenada

Por ejemplo, si la cuenta es 10 para un elemento determinado,este estará en la posición 11 (cero basada) en el arreglo ordenado

Así es posible ordenar la lista simplemente copiando suselementos en las posiciones adecuadas en un arreglo nuevo(ordenado)

La complejidad del algoritmo de ordenamiento porconteo-comparación es Θ(n2)

Por lo tanto hace el mismo número de comparaciones que elordenamiento por selección

La ventaja es que el algoritmo hace el mínimo número posible demovimientos de los elementos al ponerlos en su lugar correcto

Mejoramiento de la entra Búsqueda de subcadenas (string matching)

Búsqueda de subcadenas (string matching)

Problema de búsqueda de subcadenas (string matching)Dada una cadena de n caracteres, llamada texto, y una cadena de mcaracteres (m < n), llamada patrón, encontrar una subcadena deltexto que coincida con el patrón. De manera más formal, se requiereencontrar el índice i del carácter más a la izquierda de la primerasubcadena que coincida en el texto, tal que:

ti = p0, . . . , ti+j = pj , . . . , ti+m−1 = pm−1

Si se requieren todas las subcadenas coincidentes entonces se pudeseguir analizando todo el texto.

Peor caso: el algoritmo puede tener que hacer m comparacionesantes de avanzar el patrón, y esto para cada uno de los n−m+ 1intentosm(n−m+ 1) ∈ Θ(nm)

Mejoramiento de la entra Búsqueda de subcadenas con preprocesamiento

Búsqueda de subcadenas con preprocesamiento

Existen varios algoritmos para búsqueda de subcadena que se basanen la idea del mejoramiento de la entrada al preprocesar el patrón

Knuth-Morris-Pratt (KMP) preprocesa el patrón de izquierda aderecha para obtener información útil para la búsqueda posterior

Boyer-Moore preprocesa el patrón de derecha a izquierda yalmacena información útil en dos tablas

Horspool es una simplificación del algoritmo Boyer-Moore queemplea sólo una tabla de informa útil

Mejoramiento de la entra Algoritmo de Horspool

Algoritmo de Horspool

Es una versión simplificada del algoritmo Boyer-MoorePreprocesa el patrón para generar una tabla de desplazamiento(shift) que determina cuánto se debe desplazar el patrón cuandoocurre una no-coincidencia

Siempre efectúa un desplazamiento basado en el carácter c deltexto alineado con el último carácter en el patrón de acuerdo a latabla de desplazamiento para la entrada c

Consideremos como ejemplo la búsqueda del patrón BARBER en untexto dado:

Iniciando en la última R del patrón y moviéndose de derecha aizquierda se comparan todos los pares de caracteres

Si todos los pares coinciden entonces se encontró unasubcadena coincidente en el texto

Sino, se requiere desplazar el patrón a la izquierda

El algoritmo Horspool determina el tamaño del desplazamiento albuscar el carácter c del texto que está alineado con el últimocarácter del patrón

En general existen las siguientes 4 posibilidades

Caso 1 Si no hay un carácter c en el patrón (c es la letra S en elejemplo), entonces podemos desplazar el patrón tantas posicionescomo su longitud

Caso 2 Si hay ocurrencias del carácter c en el patrón pero no es elúltimo (c es la letra B en el ejemplo), entonces el desplazamientodebe alinear la ocurrencia más a la derecha de c en el patrón con elcarácter c en el texto

Caso 3 Si c es el último carácter en el patrón pero no hay máscaracteres c entre los m− 1 restantes (c es la letra R en el ejemplo),entonces la situación es como el Caso 1 y el patrón debe serdesplazado m posiciones (la longitud del patrón)

Caso 4 Si c es el último carácter en el patrón y hay más caracteres centre los m− 1 restantes (c es la letra R en el ejemplo), entonces lasituación es como el Caso 2 y la ocurrencia más a la derecha de centre los primeros m− 1 caracteres en el patrón deben alinearse conel carácter c en el texto

Los tamaños de los desplazamientos pueden ser precalculadosmediante la siguiente fórmula

t(c) =

m : si c no está en los primeros m− 1

caracteres del patrón

d(c, last) : de otro modo

donde d(c, last) es la distancia entre el c más a la derecha del patrón yel último carácter last de este.

Algoritmo de Horspool, eficiencia

En el peor caso el algoritmo de Horspool pertenece a la claseO(nm)

Pero para textos aleatorios es Θ(n)

Aunque están en la misma clase de eficienca, el algoritmo deHorspool es obviamente más rápido en promedio que el algoritmode fuerza bruta

De hecho es generalmente más eficiente que el algoritmo deBoyer-Moore (más sofisticado).

Pre-estructuración Hashing

Hashing

Un método eficiente de implementar un diccionario, i.e., unconjunto con las siguientes operaciones:

búsquedainserciónborrado

Basado en cambio de representación y compromisosespaciales-temporales

Aplicaciones importantes:Tablas de símbolosBases de datos

Hashing, tablas y funciones

La idea detrás del método de hashing es mapear llaves de unarchivo de tamaño n a una tabla de tamaño m, llamada tablahash, al usar una función predefinida, llamada función hash,

h : K → celda en la tabla hash (dirección hash)

Ejemplo: registros de estudiantes, llave Matricula, función hash:

h(K) = K mod m ,

donde m es un entero (típicamente primo)

Si m = 1000, dónde se encuentra almacenado el registro conMatricula= 314159265?

Generalmente, una función hash debe:Ser fácil de calcularDistribuir las llaves de forma balanceada en la tabla hash

Hashing, colisiones

Si h(K1) = h(K2), entonces se da una colisiónLas buenas funciones de hash resultan en pocas colisiones perose debe estar preparado para procesarlas

Existen dos esquemas principales para manejar las colisiones:Hashing abierto, cada celda es el nodo cabeza de una lista ligadaque contiene todas las llaves mapeadas a esa celdaHashing cerrado

Una llave por celdaEn caso de colisión, encuentra otra celda: (a) muestreo lineal(siguiente libre), (b) hashing doble para calcular incremento

Hashing, abierto

A, FOOL, AND, HIS, MONEY, ARE, SOON, PARTED.

h(A) = 1 mod 13 = 1, h(FOOL) = (6 + 15 + 15 + 12) mod 13 = 9

Colisión: h(ARE) = (1 + 18 + 5) mod 13 = 11 andh(SOON) = (19 + 15 + 15 + 14) mod 13 = 11

Hashing, abierto

Si una función de hash distribuye las llaves de manera uniforme lalongitud promedio de la lista ligada será α = n/m. Esta razón esllamada factor de carga.

El número promedio de muestreos en las búsquedas exitosas S, yno exitosas U :

S ≈ 1 + α/2 , U = α

El valor del factor de carga α debe mantenerse pequeño(idealmente cercano a 1)

La eficiencia de las tres operaciones (búsqueda, inserción yborrado) es Θ(1) en el caso promedio

El hashing abierto funciona incluso si n > m

Hashing, cerrado

Utiliza una llave por celda. En caso de colisión, encuentra otracelda con muestreo lineal (siguiente libre)

Hashing, cerrado

No funciona si n > m

Evita el uso de punterosEl borrado no es directoEl número de muestreos para búsqueda/inserción/borrado de unallave depende del factor de carga α = n/m y de la estrategia deresolución de colisiones. Para muestreo lineal:

1− α

), U =

(1− α)2

Hashing, cerrado

Conforme la tabla se va llenando (α se aproxima a 1), el númerode muestreos lineales aumenta dramáticamente

Programación dinámica (PD) PD, alineamiento de secuencias biológicas

PD, alineamiento de secuencias biológicas

El método de programación dinámica para alineamiento desecuencias biológicas se compone de 3 pasos fundamentales:

1 Inicialización2 Construcción de la matriz de puntajes3 Rastreo del alineamiento

Veamos un ejemplo de alineamiento de secuencias globalutilizando el algoritmo de programación dinámica deNeedleman/Wunsch

Ejemplo:Para este ejemplo las dos secuencias a alinear son:G A A T T C A G T T A (secuencia 1)G G A T C G A (secuencia 2)

Por lo tanto las longitudes de las secuencias son X = 11 y Y = 7respectivamente

Utilizaremos el siguiente esquema de puntaje simple:Si,j = 1, si el residuo en la posición i de la secuencia uno es elmismo que el de la posición j de la secuencia dos; sinoSi,j = 0 (no hay coincidencia)w = 0 (penalidad por hueco)

InicializaciónEl primer paso consiste en crear una matriz con X + 1 columnas yY + 1 filas donde X y Y son los tamaños de las secuencias

En este ejemplo asumimos que no hay penalidad por huecos(w = 0) por lo que llenamos la primera fila y columna con 0

Construcción de la matriz de puntajesSe inicia en la esquina superior izquierda y se encuentra elmáximo puntaje Mi,j para cada posición i, j

Para conocer Mi,j se necesita saber el puntaje de las posicionesMi−1,j , Mi,j−1 y Mi−1,j−1 y usar la siguiente fórmula:

Mi,j = Max[Mi−1,j−1 + Si,j , Mi,j−1 + w, Mi−1,j + w] (1)

Usando esta información el puntaje para la posición 1,1 en lamatriz puede ser calculado

En ambas secuencias el primer residuo es G entonces, S1,1 = 1, ycomo w = 0, entonces

M1,1 = Max[M0,0 + 1, M1,0 + 0, M0,1 + 0] = Max[1, 0, 0] = 1 (2)

Como w = 0, el resto de la fila 1 y columna 1 puede llenarse con1’s

Tomemos de ejemplo la fila 1 columna 2

M1,2 = Max[M0,1 + 0, M1,1 + 0, M0,2 + 0] = Max[0, 1, 0] = 1 (3)

Ahora llenemos la columna 2. En la fila 2 que tendra el valor:

M2,2 = Max[M1,1 + 0, M2,1 + 0, M1,2 + 0] = Max[0, 1, 0] = 1 (4)

Y la columna 2, fila 3:

M3,2 = Max[M2,1 + 1, M3,1 + 0, M2,2 + 0] = Max[2, 1, 1] = 2 (5)

Usando el mismo procedimiento se llena la columna 3

Después de calcular todos los valores, la matriz de puntajesqueda así:

Rastreo del alineamientoDe la matriz anterior observamos que el puntaje máximo delalineamiento es 6

El paso de rastreo del alineamiento determina el alineamiento quelleva a este resultado

Éste comienza en la posición MX,Y de la matriz y verifica suspredecesores directos:

Vecino a la izquierda (hueco en secuencia 2)Vecino en la diagonal (coincidencia/no coincidencia)Vecino hacia arriba (hueco en secuencia 1)

Se elige uno de los vecinos (marcados en rojo)

Debido a que la celda actual vale 6, el único vecino que es posibleelegir es el de la diagonal

Lo que da el alineamientoAA

Ahora determinamos cual es el predecesor directo de la celdaactual, en este caso la celda roja con el 5

Esto agrega un hueco a la secuencia 2, por lo que el alineamientoactual es:T A_ A

Una vez más, el predecesor directo produce un hueco en lasecuencia 2:T T A_ _ A

Continuado estos pasos llegamos al siguiente alineamiento:G A A T T C A G T T AG G A _ T C _ G _ _ A

Una solución alternativa es el siguiente alineamiento:G _ A A T T C A G T T AG G _ A _ T C _ G _ _ A

Compromisos espaciales-temporales - CINVESTAV

Documents

Archivo cinvestav

cdigital.dgb.uanl.mxcdigital.dgb.uanl.mx/la/1080066373/1080066373_14.pdf100 m, incluso en depresiones topográficas. Las variaciones espaciales y temporales de la tasa de recarga en

Patrones espaciales y temporales de la productividad primaria …ri.agro.uba.ar/files/download/tesis/doctorado/2017blanco... · 2019. 12. 3. · Patrones espaciales y temporales de

PATRONES TEMPORALES Y ESPACIALES DE LA PRECIPITACIÓN EN

MANUAL DE PROCEDIMIENTOS - CINVESTAV

Informe final* del Proyecto S004 Biodiversidad ... · BIODIVERSIDAD FITOPLACTÓNICA DE CENOTES PATRONES ESPACIALES Y TEMPORALES PROYECTO S004 INFORME FINAL MARZO 2001 Responsable

Scan - Universidad Autónoma de Madrid · Elementos formales y compositivos. — Factores temporales y espaciales. — Recursos técnicos e iluminación. — Contenido y mensaje

Introducción - CINVESTAV

Unidad Tamaulipas - CINVESTAV

169 Estructuras temporales y espaciales en la música

Bases de datos temporales, espaciales, espacio- temporales BD.pdf · combinados con conectores lógicos AND, OR y NOT. El maximizar la cantidad de documentos relevantes obtenidos

RAMO: DIFICULTADES DE APRENDIZAJE EN MATEMÁTICASbiblioteca.iplacex.cl/MED/Dificultades de aprendizaje en... · matemático (audio-temporales, viso-espaciales, etc.), la cual no afecta

Freddy Guerrero - Experiencias Temporales y Espaciales Campesinas

Acerca de Cinvestav

Proyecto Ejercicio 1 - biblio3.url.edu.gtbiblio3.url.edu.gt/CDTK/Saravia-Evelyn.pdf · • Posee restricciones espaciales y reglas temporales establecidas de antemano o improvisados

Investigaciones Cinvestav

Aplicaciones y Servicios - CINVESTAV

Estudio de los elementos espaciales y temporales en

Nociones temporales y espaciales

Modelamiento de Datos Espaciales y Datos Espacio-Temporales