El objetivo del presente trabajo de título es estudiar el algoritmo para búsqueda de patrones en texto debido a Boyer-Moore-Horspool (BMH) bajo un enfoque de texto sometido a una ligera perturbación independiente carácter a carácter, de manera de determinar la esperanza del desempeño del algoritmo sometido a dicha perturbación. El algoritmo BMH es una simplificación de Horspool al algoritmo que había sido propuesto anteriormente por Boyer y Moore (BM). En el mismo trabajo original de Horspool, él hace notar que su versión, en cuanto a tiempo de ejecución y comparaciones entre texto y patrón, aunque más sencilla y con peor desempeño de peor caso, tiene un desempeño comparable y a veces incluso superior al del algoritmo BM. Si bien diversos trabajos han hecho un buen análisis del algoritmo BMH especialmente en el caso promedio, no es claro que un análisis promedio sea una buena respuesta a la pregunta de por qué un algoritmo funciona bien en la práctica aunque su desempeño de peor caso sea deficiente. Basados en el enfoque de análisis suavizado propuesto originalmente por Spielman y Teng pero adaptado para problemas de naturaleza discreta y más específicamente para texto, proponemos una perturbación bajo la cual analizar el desempeño esperado del algoritmo BMH cuando la entrada es sometida a una perturbación lo suficientemente pequeña como para no eliminar la influencia que la entrada ejerce sobre el desempeño del algoritmo. Para ello, en primer lugar, diseñamos herramientas que permiten encontrar una familia de constantes, indexada por parámetros del algoritmo, que acotan el peor desempeño en cada caso. También diseñamos un procedimiento para calcular dichas constantes para patrones y alfabetos pequeños. Luego encontramos una familia de constantes análoga a la anterior para acotar el desempeño esperado, bajo perturbación de texto, del algoritmo, y demostramos resultados que aseguran que dicho desempeño perturbado, bajo condiciones razonables, es mejor que el desempeño de peor caso asintóticamente con el tamaño del texto. Finalmente, mostramos alguna evidencia empírica que sugiere que dentro del espacio de entradas la mayoría lleva a un comportamiento sustancialmente mejor al del peor caso. Las herramientas desarrolladas durante el trabajo y el enfoque aplicado podrían, en un trabajo futuro, justificar la diferencia entre el desempeño teórico y el observado en la práctica para BMH.

Ce travail a pour but d'étudier les propriétés structurales et dynamiques des verres aluminosilicate de calcium CaO-Al2O3-SiO2 (CAS) par dynamique moléculaire classique, à partir d'un potentiel empirique de type Born-Mayer-Huggins, construit sur la base de résultats de dynamique moléculaire ab initio (AIMD) et expérimentaux. Il montre de bonnes propriétés de transférabilité sur toutes les concentrations pour les propriétés structurales et dynamiques étudiées. L'évolution des propriétés structurales a été étudiée en fonction de la température et de la concentration en silice pour trois rapports de concentrations R = [CaO]/[Al2O3]= 1, 1.57 et 3. Les résultats révèlent la présence d'oxygènes non-pontants et tricoordonnés et d'aluminium penta-coordonnés pour toutes les concentrations dont le nombre diminue avec l'augmentation avec la concentration en silice. L'étude de la viscosité et du temps de relaxation structural avec la température a permis de montrer que la fragilité diminue avec l'augmentation de la concentration en silice pour les trois valeurs de R. Une corrélation avec l'évolution des oxygènes non pontant indique que ces derniers jouent un rôle prépondérant pour la fragilité. Il est montré que la théorie des couplages de modes s'applique à la dynamique des CAS et qu'une violation de la relation de Stokes-Einstein se produit au-dessus du point de fusion expérimental indiquant une hétérogénéité dynamique. / The aim of this work is to study the structural and dynamic properties of calcium aluminosilicate glasses CaO-Al2O3-SiO2 (CAS) by classical molecular dynamics, using an empirical potential of the Born-Mayer-Huggins type, built on the basis of ab initio molecular dynamics (AIMD) and the experimental results. This potential proves to be transferable for all concentration and the structural and dynamic properties studied. The evolution of structural properties has been studied as a function of temperature and silica content for the three concentration ratios R = [CaO]/[Al2O3]= 1, 1.57 et 3. The results reveal the presence of non-bonding oxygen, oxygen triclusters and AlO5 structural units for all the concentrations whose number decrease with increasing silica content. The study of the temperature evolution of the viscosity and structural relaxation time shows that the fragility decreases with the increase of silica content for all values of R. A correlation with the evolution of the number non-bonding oxygen indicates that they play a preponderant role for the fragility. It is shown that the mode coupling theory can be applied to the dynamics of the CAS and that a violation of the Stokes-Einstein relation occurs well above the experimental melting point indicating a dynamical heterogeneity. Keywords: calcium aluminosilicate, diffusion, viscosity, fragility, BMH potential, molecular dynamics, dynamical heterogeneity, non-bonding oxygen.

Ce travail a pour but d'étudier les propriétés structurales et dynamiques des verres aluminosilicate de calcium CaO-Al2O3-SiO2 (CAS) par dynamique moléculaire classique, à partir d'un potentiel empirique de type Born-Mayer-Huggins, construit sur la base de résultats de dynamique moléculaire ab initio (AIMD) et expérimentaux. Il montre de bonnes propriétés de transférabilité sur toutes les concentrations pour les propriétés structurales et dynamiques étudiées. L'évolution des propriétés structurales a été étudiée en fonction de la température et de la concentration en silice pour trois rapports de concentrations R = [CaO]/[Al2O3]= 1, 1.57 et 3. Les résultats révèlent la présence d'oxygènes non-pontants et tricoordonnés et d'aluminium penta-coordonnés pour toutes les concentrations dont le nombre diminue avec l'augmentation avec la concentration en silice. L'étude de la viscosité et du temps de relaxation structural avec la température a permis de montrer que la fragilité diminue avec l'augmentation de la concentration en silice pour les trois valeurs de R. Une corrélation avec l'évolution des oxygènes non pontant indique que ces derniers jouent un rôle prépondérant pour la fragilité. Il est montré que la théorie des couplages de modes s'applique à la dynamique des CAS et qu'une violation de la relation de Stokes-Einstein se produit au-dessus du point de fusion expérimental indiquant une hétérogénéité dynamique.