Trabajos de fin de máster (TFM)

URI permanente para esta colección

hdl:123456789/37

Examinar

Examinando Trabajos de fin de máster (TFM) por Departamento "Matemática Aplicada I"

Mostrando 1 - 1 de 1
  • Miniatura
    Publicación
    El Teorema de Perron-Frobenius y su influencia en los algoritmos de Google
    (Universidad Nacional de Educación a Distancia (UNED), 2024-06-27) Aparicio Durán, Jose Antonio; Franco Leis, Daniel
    La importancia que ha tenido para el desarrollo de Internet es indiscu- tible. Sin embargo, es curioso pensar que el algoritmo PageRank, que hay detrás del buscador, tiene su fundamento matemático en un Teorema desarrollado a principios del siglo XX por el matemático Oskar Perron, inicialmente para matrices positivas y posteriormente extendido a matrices no negativas por el matemático Georg Frobe- nius. Dicho teorema permite garantizar que para una matriz no negativa e irreducible haya un autovalor positivo de módulo máximo que lleva asociado un autovector po- sitivo. Garantizar la existencia y unicidad de dicho autovector es lo que hace que el algoritmo de Google funcione, y haya permitido el desarrollo de aplicaciones que van más allá de un motor de búsqueda en Internet, como el estudio de la dinámica de po- blaciones, epidemiología, estudio de proteínas o análisis iterativo de matrices, entre otros. Este trabajo no solo presenta los conceptos necesarios para comprender el Teo- rema de Perron-Frobenius, sino que también explica en detalle una de las múltiples demostraciones disponibles en la literatura, basada en el Teorema del punto fijo de Brouwer y con un enfoque geométrico. También se introducen las cadenas de Mar- kov, fundamentales para el desarrollo del algoritmo PageRank, y se propone un algo- ritmo para el cálculo del EdgeRank de las aristas de un grafo. Por último se muestra un ejemplo de implementación en Python de los algoritmos PageRank y EdgeRank.