Estructuras Discretas II 01
Páginas: 7 (1724 palabras)
Publicado: 8 de abril de 2015
Estructuras Discretas II
Mgter. Carlo Corrales Delgado
Docente Universidad Católica de Santa María
Prog. Profesional Ingeniería de Sistemas
carlocorrales@Hotmail.com
Contenidos
Árboles
Árboles Binarios
Introducción y Aplicaciones
Modelo de Redes
Árboles de decisión, Tiempo mínimo para ordenar, Isomorfismo de árboles
Árboles de Juegos
Introducción, Recorrido enárboles
Aplicaciones con Árboles
Introducción, Árboles de Expansión y de expansión mínima
Introducción a Modelo de Redes
Teorema de Flujo Máximo y Corte Mínimo
Algoritmo de flujo máximo y corte mínimo, Acoplamiento
Bibliografía
Johnsonbaugh, R. Matemáticas Discretas. México. Pearson. 6ta Edición.
2005
Susanna S. Matemática Discretas con Aplicaciones. Mexico. Cengage
Learning. 4taEdic. 2011
Jimenez Murillo J. Matemáticas para la computación. México.
AlfaOmega. 2009
Otros.
Laboratorios
Python. Clases y módulos
Implementaciones en Python
Clase 01: Árboles
Mgter. Carlo Corrales Delgado
Introducción
Los árboles forman una de las subclases de gráficas que más se utilizan.
La ciencia de la computación hace uso de los árboles ampliamente. Son
útiles paraorganizar y relacionar datos en una base de datos. Los
árboles surgen en problemas teóricos como el tiempo óptimo para
ordenar.
Veremos las subclases de árboles (como árboles con raíz y árboles
binarios) y muchas aplicaciones de árboles (como árboles de expansión,
árboles de decisión y árboles de juegos). El análisis de isomorfismos de
árboles es una extensión del isomorfismos de gráficas. Ejemplo: Semifinales y finales en
Winbledon
torneo por eliminación sencilla
Definición Formal
Un árbol T (libre) es una gráfica simple que satisface lo siguiente: si v y
w son vértices en T, existe una trayectoria simple única de v a w.
Un árbol con raíz es un árbol en el que un vértice específico se designa
como raíz.
Árbol a) girado, b) comparado con un
árbol natural.
Observeque si v y w son vértices en esta gráfica, existe una trayectoria
simple única de v a w. Por ejemplo, la trayectoria simple única de v2 a v7 es
(v2, v1, v3, v7).
los vértices v4, v5, v6 y v7, se llega desde la raíz por trayectorias simples de
longitud 2
Como la trayectoria simple de la raíz a cualquier vértice dado es única,
cada vértice está en un nivel determinado de manera única.
El nivel de la raíz es el nivel 0.
El nivel de un vértice v es la longitud de la trayectoria simple de la
raíz a v.
La altura de un árbol con raíz es el número máximo de nivel que
ocurre.
Un árbol T y un árbol con raíz T ′.
T ′ se obtiene de T designando a e como la raíz.
Con frecuencia se usa un árbol con raíz para especificar relaciones
jerárquicas.
Cuando se usa un árbolde esta manera, si un vértice a está en un nivel
uno menos que el nivel del vértice b y a y b son adyacentes, entonces a
está “justo arriba” de b
Existe una relación lógica entre a y b: a domina a b o b es subordinado
de a en alguna forma.
Organigrama administrativo de la organización de una universidad
Administrador de Archivos
Árbol de definición jerárquica
Se usan para mostrar lasrelaciones entre los registros de una base de
datos.
Una base de datos es una colección de registros que maneja una
computadora.
El árbol mostrado se puede usar como modelo para establecer una base
de datos para mantener los registros de los libros disponibles en varias
bibliotecas.
Códigos Huffman
La manera de representar caracteres internamente en una computadora es usando
cadenasde bits de longitud fija (ASCII)
Los códigos Huffman representan caracteres por cadenas de bits de longitud
variable. La idea es usar cadenas de bits cortas para representar los caracteres que
se usan con más frecuencia y cadenas de bits más largas para los caracteres de uso
menos frecuente. Menos espacio.
VCR Plus+, un dispositivo que programa automáticamente una videocasetera, usa...
Mgter. Carlo Corrales Delgado
Docente Universidad Católica de Santa María
Prog. Profesional Ingeniería de Sistemas
carlocorrales@Hotmail.com
Contenidos
Árboles
Árboles Binarios
Introducción y Aplicaciones
Modelo de Redes
Árboles de decisión, Tiempo mínimo para ordenar, Isomorfismo de árboles
Árboles de Juegos
Introducción, Recorrido enárboles
Aplicaciones con Árboles
Introducción, Árboles de Expansión y de expansión mínima
Introducción a Modelo de Redes
Teorema de Flujo Máximo y Corte Mínimo
Algoritmo de flujo máximo y corte mínimo, Acoplamiento
Bibliografía
Johnsonbaugh, R. Matemáticas Discretas. México. Pearson. 6ta Edición.
2005
Susanna S. Matemática Discretas con Aplicaciones. Mexico. Cengage
Learning. 4taEdic. 2011
Jimenez Murillo J. Matemáticas para la computación. México.
AlfaOmega. 2009
Otros.
Laboratorios
Python. Clases y módulos
Implementaciones en Python
Clase 01: Árboles
Mgter. Carlo Corrales Delgado
Introducción
Los árboles forman una de las subclases de gráficas que más se utilizan.
La ciencia de la computación hace uso de los árboles ampliamente. Son
útiles paraorganizar y relacionar datos en una base de datos. Los
árboles surgen en problemas teóricos como el tiempo óptimo para
ordenar.
Veremos las subclases de árboles (como árboles con raíz y árboles
binarios) y muchas aplicaciones de árboles (como árboles de expansión,
árboles de decisión y árboles de juegos). El análisis de isomorfismos de
árboles es una extensión del isomorfismos de gráficas. Ejemplo: Semifinales y finales en
Winbledon
torneo por eliminación sencilla
Definición Formal
Un árbol T (libre) es una gráfica simple que satisface lo siguiente: si v y
w son vértices en T, existe una trayectoria simple única de v a w.
Un árbol con raíz es un árbol en el que un vértice específico se designa
como raíz.
Árbol a) girado, b) comparado con un
árbol natural.
Observeque si v y w son vértices en esta gráfica, existe una trayectoria
simple única de v a w. Por ejemplo, la trayectoria simple única de v2 a v7 es
(v2, v1, v3, v7).
los vértices v4, v5, v6 y v7, se llega desde la raíz por trayectorias simples de
longitud 2
Como la trayectoria simple de la raíz a cualquier vértice dado es única,
cada vértice está en un nivel determinado de manera única.
El nivel de la raíz es el nivel 0.
El nivel de un vértice v es la longitud de la trayectoria simple de la
raíz a v.
La altura de un árbol con raíz es el número máximo de nivel que
ocurre.
Un árbol T y un árbol con raíz T ′.
T ′ se obtiene de T designando a e como la raíz.
Con frecuencia se usa un árbol con raíz para especificar relaciones
jerárquicas.
Cuando se usa un árbolde esta manera, si un vértice a está en un nivel
uno menos que el nivel del vértice b y a y b son adyacentes, entonces a
está “justo arriba” de b
Existe una relación lógica entre a y b: a domina a b o b es subordinado
de a en alguna forma.
Organigrama administrativo de la organización de una universidad
Administrador de Archivos
Árbol de definición jerárquica
Se usan para mostrar lasrelaciones entre los registros de una base de
datos.
Una base de datos es una colección de registros que maneja una
computadora.
El árbol mostrado se puede usar como modelo para establecer una base
de datos para mantener los registros de los libros disponibles en varias
bibliotecas.
Códigos Huffman
La manera de representar caracteres internamente en una computadora es usando
cadenasde bits de longitud fija (ASCII)
Los códigos Huffman representan caracteres por cadenas de bits de longitud
variable. La idea es usar cadenas de bits cortas para representar los caracteres que
se usan con más frecuencia y cadenas de bits más largas para los caracteres de uso
menos frecuente. Menos espacio.
VCR Plus+, un dispositivo que programa automáticamente una videocasetera, usa...
Leer documento completo
Regístrate para leer el documento completo.