Diferencia entre revisiones de «Final del 20/12/19 (Algoritmos III)»
De Cuba-Wiki
(Página creada con «Final escrito de Min Chih Lin. = Enunciados = == Ejercicio 1 == Escribir un algoritmo que utilice la técnica de "programación dinámica" para calcular la subsecuencia c…») |
Sin resumen de edición |
||
Línea 4: | Línea 4: | ||
== Ejercicio 1 == | == Ejercicio 1 == | ||
Escribir un algoritmo que utilice la técnica de "programación dinámica" para calcular la subsecuencia creciente máxima de una secuencia de números (el mejor algoritmo conocido es de tiempo <math>O | Escribir un algoritmo que utilice la técnica de "programación dinámica" para calcular la subsecuencia creciente máxima de una secuencia de números (el mejor algoritmo conocido es de tiempo <math>O(n . log(n))</math> y usa espacio <math>O(n)</math>). Mostrar la correctitud y determinar la complejidad del algoritmo propuesto. | ||
== Ejercicio 2 == | |||
El grafo <math>Q_d</math>, también llamado hipercubo de orden <math>d</math>, se define inductivamente de la siguiente manera: <math>Q_0 = K_1</math>, y <math>Q_d</math> con <math>d \in N_>0</math> es el grafo que se obtiene al tomar dos copias de <math>Q_d-1</math> y agrega un eje entre cada vértice de una copia y su vértice correspondiente en la otra copia. Por ejemplo <math>Q_1 = K_2</math>, <math>Q_2 = C_4</math> (ciclo simple de 4 vértices). | |||
a) Determinar los valores de <math>d</math> para los cuales <math>Q_d</math> es planar. Justificar. | |||
b) Determinar <math>\chi(Q_d)</math>. Justificar. |
Revisión del 12:31 24 ene 2020
Final escrito de Min Chih Lin.
Enunciados
Ejercicio 1
Escribir un algoritmo que utilice la técnica de "programación dinámica" para calcular la subsecuencia creciente máxima de una secuencia de números (el mejor algoritmo conocido es de tiempo y usa espacio ). Mostrar la correctitud y determinar la complejidad del algoritmo propuesto.
Ejercicio 2
El grafo , también llamado hipercubo de orden , se define inductivamente de la siguiente manera: , y con es el grafo que se obtiene al tomar dos copias de y agrega un eje entre cada vértice de una copia y su vértice correspondiente en la otra copia. Por ejemplo , (ciclo simple de 4 vértices).
a) Determinar los valores de para los cuales es planar. Justificar. b) Determinar . Justificar.