Aplicaciones de los árboles y grafos

0

KoreanoNiu

19/6/2023

¡Estudia con miles de materiales!

Entonces, ¿te gustó este material?

Ayude a animar a otros estudiantes a mejorar el contenido

¿Te gustó este material? ¡Compartir! 🧡

Matemática Discreta

10.069 Materiales compartidos

Descarga la aplicación para disfrutar aún más

Lea materiales sin conexión, sin usar Internet. Además de muchas otras características!

Vista previa del material en texto

MATEMÁTICAS DISCRETAS
14 DE DICIEMBRE DE 2021
DOCENTE:
ISC RODRIGO GOVEA MARIANO
ALUMNOS: 
BARRIGA GARIBAY LEONARDO 
CRUZ HERNÁNDEZ JUAN MANUEL 
GARCÍA LIRA CARLOS HUMBERTO
APLICACIÓN DE LOS GRAFOS Y ARBOLES EN 
LAS CIENCIAS DE LA COMPUTACIÓN
Aplicación de los Grafos 
Podemos encontrar aplicaciones informáticas con grafos bipartitos en la 
comparación de archivos de computador, utilizando el problema de la 
Longest Common Subsequence (LCS), en español Subsecuencia Común 
Más Larga, en el cual dadas dos palabras X e Y sobre un alfabeto finito 
cualquiera, lo que pretende es encontrar cuál es el largo máximo que puede 
tener una palabra que sea subsecuencia de X e Y simultáneamente. 
Por ejemplo, si consideramos X=matemáticas e Y=astronomía, una LCS (y 
en este caso la única) es “atmia”. El largo de una LCS se usa comúnmente 
como criterio de comparación de palabras, pues está relacionada con la 
cantidad de "pasos" necesarios para ir de una palabra a la otra mediante 
operaciones de inserción, eliminación y reemplazo de caracteres. 
Vamos a visualizar un poco más el ejemplo. Todo par de palabras puede 
representarse convenientemente como un grafo bipartito donde los arcos 
unen a los caracteres coincidentes de ambas palabras. 
X=matemáticas e Y=astronomía, el grafo que los representa sería. (Figura 1). 
“A T M I A” 
 
Figura 1. [Gráfico]. ATMIA. Recuperado de: 
https://repository.javeriana.edu.co/bitstream/handle/10554/8378/tesis341.pdf?s
equence=1 
Aplicación de los Árboles 
Un área de aplicación de los árboles en las ciencias de la computación da 
lugar en la Ingeniería de Software, específicamente en el Desarrollo Web. 
Un ejemplo de aplicación de los árboles es una página web. El siguiente es 
un ejemplo de una página web sencilla escrita usando HTML. La figura. 2 
muestra el árbol que corresponde a cada una de las etiquetas HTML 
utilizadas para crear la página. 
<html xmlns="http://www.w3.org/1999/xhtml" 
 xml:lang="es" lang="es"> 
 <head> 
 <meta http-equiv="Content-Type" 
 content="text/html; charset=utf-8" /> 
 <title>Sencilla</title> 
 </head> 
 <body> 
 <h1>Una página web sencilla</h1> 
 <ul> 
 <li>Primer ítem de la lista</li> 
 <li>Segundo ítem de la lista</li> 
 </ul> 
 <h2><a href="http://www.cs.luther.edu">Luther CS </a><h2> 
 </body> 
</html> 
 
Figura 2. [Gráfico]. Un árbol que corresponde a los elementos de marcado de una 
página Web. Recuperado de: 
https://runestone.academy/runestone/static/pythoned/Trees/EjemplosDeArboles.
html 
El código fuente HTML y el árbol que acompaña a dicho código fuente 
ilustran otra jerarquía. Observa que cada nivel del árbol corresponde a un 
nivel de anidamiento dentro de las etiquetas HTML. La primera etiqueta en el 
código fuente es <html>y la última es </html>. Todas las demás etiquetas de 
la página están dentro de esa pareja. 
Referencias electrónicas 
Miller, B., Ranum, D. & College, L. (s.f.). 6.2. Ejemplos de árboles. RuneStone 
Academy. Recuperado el 13 de diciembre de 2021, de: https://normas-
apa.org/formato/alineacion-y-sangria/ 
Piedra, V & Nieto, G. (2009). APLICACIONES DE LA TEORIA DE GRAFOS EN LA 
INFORMÁTICA. (pp. 36-38). Recuperado el 13 de diciembre de 2021, de: 
https://repository.javeriana.edu.co/bitstream/handle/10554/8378/tesis
341.pdf?sequence=1