Actividad Tercer Corte - Matemáticas Discretas

Área: Ciencias Basicas Virtual.
Asignatura: Matematicas Discretas

Módulo #3 : Teoría de Grafos
Informacion importante: Estimado estudioso, antes de realizar la entrega de este taller y buscando que su
nota sea la mas alta posible tenga en cuentas todas y cada una de las siguientes recomendaciones:
La entrega se debe hacer en un unico documento en formato PDF y los ejercicios se deben entregar de
forma organizada, siguiendo la numeracion que se presenta a continuacion. No olvide escribir el
enunciado de cada problema y presente la solucion de forma clara, y siguiendo un proceso
argumentativo el. En caso de realizarlo a mano alzada, asegurarse de: escanear muy bien el
documento, evite tomarle foto y organice de forma secuencial cada uno de los puntos. Mientras, que
si usa un editor de texto, asegurese de utilizar un editor de ecuaciones.
La evaluacion y retroalimentacion de este taller sera mediante la siguiente rubrica de evaluacion, en

cada ejercicio se especifica el numero de puntos que se otorgaran. En caso de no alcanzar la nota
maxima de cada ejercicio, recibir ‘a una observacion dentro de la rubrica.
La nota final se obtendra sobre el total de puntos que corresponden a 5.
RUBRICA DE EVALUACIÓN
ASPECTO A PUNTOS OBTENIDOS
#
EVALUAR
1 Recorrido 0.75 PUNTOS 0.55 PUNTOS 0.35 PUNTOS 0.15 PUNTOS
en un grafo. 4 afirmaciones 3 2 afirmaciones 1 afirmación
correctas: las afirmacion correctas: dos de correcta: tres de las
afirmaciones sobre es correctas: una las afirmaciones afirmaciones sobre
la existencia de de las sobre la existencia la existencia
circuitos eulerianos, afirmacione de circuitos de circuitos
caminos eulerianos, s sobre la existencia eulerianos, caminos eulerianos, caminos
circuitos de circuitos eulerianos, circuitos eulerianos, circuitos
hamiltonianos y eulerianos, caminos hamiltonianos y hamiltonianos y
caminos eulerianos, circuitos caminos caminos
hamiltonianos son hamiltonianos y hamiltonianos son hamiltonianos son
correctas, y estan caminos incorrectas, o no incorrectas, o no
debidamente hamiltonianos es estan debidamente estan debidamente
justificadas. incorrecta, o no esta justificadas. justificadas.
debidamente
justificada.
2 arbol de´ 1.5 PUNTOS 1.2 PUNTOS 0.8 PUNTOS 0.5 PUNTOS
Huffman. Totalmente Solo tabla Solo ´árbol Solo árbol
correcto: se correcta: se incorrecto: se correcto: el arbol
completa de forma completa de forma completa de forma de codificacion de
correcta la tabla con correcta la tabla con correcta la tabla con Huffman es
las frecuencias las frecuencias las frecuencias correcto pero, la
relativas de relativas de cada relativas de cada tabla de frecuencias
cada caracter y, desde allí caracter y, desde allí presenta varios
caracter y, desde allí se soporta la se soporta la errores que no
se soporta la construccion del construccion del permiten sustentar
construccion del arbol de arbol de la aparicion del
arbol de codificacion de codificacion de ´arbol.
codificacion de Huffman Huffman
Huffman presentado. Sin presentado. Sin
presentado. embargo, hay embargo, hay 4
maximo ramas o mas que
3 ramas que son son incorrectas.
incorrectas.
3 arbol de´ 0.75 PUNTOS 0.55 PUNTOS 0.35 PUNTOS 0.15 PUNTOS
expansion. Totalmente Solo modelo Solo respuesta Completamente
correcto: usando el correcto: usando el correcta: presenta incorrecto: tanto el
algoritmo algoritmo la respuesta modelo presentado
apropiado para apropiado para correcta de la para el desarrollo
determinar el arbol determinar el arbol pregunta planteada del ejercicio, como
de expansion de expansion pero, el modelo la respuesta de la
requerido, requerido, propuesto no tiene situacion problema
construye el arbol construye el arbol relacion con la son incorrectos.
de manera correcta de manera correcta situacion problema
y brinda una pero se equivoca en mencionada.
respuesta acertada la respuesta del
a la problema.
situacion
problema
propuesta.
4 Presentacion 0.5 PUNTOS 0.25 PUNTOS 0.1 PUNTOS 0 PUNTOS
Adecuada: El Aceptable: El Deficiente: El No entregó: No se

documento documento documento evidencia ningun
entregado, es entregado, es presentado no proceso del
facilmente legible y facilmente legible, cumple con las ejercicio de calculo
se caracteriza por el pero carece de condiciones de areas por exceso
orden en la orden en el mínimas de buena y por defecto.
presentacion de desarrollo de los presentacion. Por
cada uno de los ejercicios ejemplo, ecuaciones
ejercicios entregados. escritas sin editor
entregados. de ecuaciones, mala
caligrafía o
problemas al
escanear el
documento.
EJERCICIOS
1. Recorridos en un Grafo: Para cada uno de los siguientes grafos, determine si tiene circuitos
eulerianos, caminos eulerianos, circuitos y caminos hamiltonianos. Debe justificar su respuesta y,
respuesta que no sea justificada no se tendra en cuenta. (Aspecto a evaluar: #1
Teoría de Grafos.)
a)
b)
2. Árbol de codificación de Huffman:´ una persona escribe en un editor de texto la siguiente frase
celebre: “Los encantos de esta ciencia sublime, las matematicas, solo se le revelan a aquellos que
tienen el valor de profundizar en ella.” Carl Friedrich Gauss. La persona desea comprimir el archivo
para que pese menos, y para ello usa una aplicacion encargada de ese proceso que aplica la
codificacion de Huffman. Buscando saber la longitud de la cadena de bits que permiten comprimir la
frase, usted debe:
a) Construya la tabla de frecuencias absolutas y relativas (en fraccion) de cada caracter que aparece
en el mensaje, incluyendo el espacio en blanco (ultimo valor)
b) Construya el arbol de codificacion de Huffman.
(Aspecto a evaluar: #2 arbol de Huffman.)´
3. Árbol de expansión: El siguiente grafo representa los diferentes puntos de acceso que se deben
ubicar en una oficina bancaria. La distancia (peso de la arista en metros) corresponde a la longitud
entre cada punto de acceso debido a la tubería ubicada dentro de las paredes para las conexiones de
datos.
Debido a que se debe cablear de forma optima, se realizan las siguientes propuestas:
Situacion 1: ubicar en el vertice F el punto de conexion a internet y, desde allí construir un arbol
de expansion mínima ubicando en cada vertice interno un switch que sirva de repetidor.
Situacion 2: ubicar en el vertice F el punto de conexion a internet y, desde allí construir un
arbol de busqueda a lo ancho ubicando en cada vertice interno un switch para que sirva de
repetidor.
Si se tiene en cuenta que el metro de cable UTP Cat 5 cuesta 950 pesos y, cada switch de 8 puertos vale
72000 pesos. Buscando determinar cual opcion es la mas economica:
a) Construya el arbol indicado para la situacion 1 y determine su costo. (Aspecto a evaluar:

#3 arbol de expansion.)
b) Construya el arbol indicado para la situacion 2 y determine su costo. (Aspecto a evaluar:#3
arbol de expansion.)

Actividad Tercer Corte - Matemáticas Discretas

Cargado por

Copyright:

Formatos disponibles

Actividad Tercer Corte - Matemáticas Discretas

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Actividad Tercer Corte - Matemáticas Discretas

Cargado por

Copyright:

Formatos disponibles

Área: Ciencias Basicas Virtual.

Asignatura: Matematicas Discretas

La evaluacion y retroalimentacion de este taller sera mediante la siguiente rubrica de evaluacion, en

La nota final se obtendra sobre el total de puntos que corresponden a 5.

Adecuada: El Aceptable: El Deficiente: El No entregó: No se

(Aspecto a evaluar: #2 arbol de Huffman.)´

a) Construya el arbol indicado para la situacion 1 y determine su costo. (Aspecto a evaluar:

También podría gustarte