Analisis de problema
Paola
14 de Junio del 2010
Alguien me puede ayudar con estos dos ejercicios, auxilio!!!!!!
1) Nosotros podemos usar programación dinámica sobre un grafo dirigido G=(V,E) para reconocimiento de voz. Cada arco (u,v) Є E es etiquetado con un sonido ơ(u,v) de un conjunto finito Σ de sonidos.
El grafo etiquetado es un modelo formal de una persona hablando un lenguaje limitado. Cada camino en el grafo iniciando de un vértice distinguido v0 Є V corresponde a una posible secuencia de sonidos producida por el modelo. Definimos la etiqueta de un camino dirigido a ser la concatenación de las etiquetas de los arcos en ese camino.
a. Describa un algoritmo eficiente, que dado un grafo de arcos etiquetados, con un vértice distinguido v0 y una secuencia s = ‹ơ1, ơ2,Â…, ơk› de sonidos de Σ, retorna un camino en G que empieza en v0 y tiene s como su etiqueta, si alguno de tal camino existe. De otra forma el algoritmo debería retornar NO-CAMINO. Analice el tiempo de ejecución de su algoritmo.
2) La Rinky Dink Company hace máquinas que pulen superficies de las pistas de patinaje sobre hielo. La demanda para tales productos varía de mes a mes y así, la compañía necesita desarrollar una estratégia para planear su fabricación dada la fluctuación, pero predecible, demanda. La Compañía desea diseñar un plan para los próximos n meses. Para cada mes i, la compañía sabe la demanda di, esto es, el número de máquinas que serán vendidas. Sea la demanda total sobre los próximos n meses. La compañía matiene un staff tiempo completo, quienes fabrican hasta m máquinas por mes. Si la compañía necesita hacer más de m máquinas en un mes dado, ella puede contratar jornales de medio tiempo adicionales, a un costo que resulta a c dólares por máquina. Además, si, en el fin de un mes, la compañía está guardando algunas máquinas sin vender, ella debe pagar costos de inventario. El costo por almacenar j máquinas es dado como una función h(j) para j=1,2,Â…., D, donde h(j) ≥ 0 para 1 ≤ j ≤ D y h(j) ≤ h(j+1) para j≤1≤ D-1.
a. De un algoritmo que calcule un plan para la compañía, que mimimice sus costos, mientras satisface toda la demanda. El tiempo de ejecución debería ser polinomial en n y D.
Gracias
1) Nosotros podemos usar programación dinámica sobre un grafo dirigido G=(V,E) para reconocimiento de voz. Cada arco (u,v) Є E es etiquetado con un sonido ơ(u,v) de un conjunto finito Σ de sonidos.
El grafo etiquetado es un modelo formal de una persona hablando un lenguaje limitado. Cada camino en el grafo iniciando de un vértice distinguido v0 Є V corresponde a una posible secuencia de sonidos producida por el modelo. Definimos la etiqueta de un camino dirigido a ser la concatenación de las etiquetas de los arcos en ese camino.
a. Describa un algoritmo eficiente, que dado un grafo de arcos etiquetados, con un vértice distinguido v0 y una secuencia s = ‹ơ1, ơ2,Â…, ơk› de sonidos de Σ, retorna un camino en G que empieza en v0 y tiene s como su etiqueta, si alguno de tal camino existe. De otra forma el algoritmo debería retornar NO-CAMINO. Analice el tiempo de ejecución de su algoritmo.
2) La Rinky Dink Company hace máquinas que pulen superficies de las pistas de patinaje sobre hielo. La demanda para tales productos varía de mes a mes y así, la compañía necesita desarrollar una estratégia para planear su fabricación dada la fluctuación, pero predecible, demanda. La Compañía desea diseñar un plan para los próximos n meses. Para cada mes i, la compañía sabe la demanda di, esto es, el número de máquinas que serán vendidas. Sea la demanda total sobre los próximos n meses. La compañía matiene un staff tiempo completo, quienes fabrican hasta m máquinas por mes. Si la compañía necesita hacer más de m máquinas en un mes dado, ella puede contratar jornales de medio tiempo adicionales, a un costo que resulta a c dólares por máquina. Además, si, en el fin de un mes, la compañía está guardando algunas máquinas sin vender, ella debe pagar costos de inventario. El costo por almacenar j máquinas es dado como una función h(j) para j=1,2,Â…., D, donde h(j) ≥ 0 para 1 ≤ j ≤ D y h(j) ≤ h(j+1) para j≤1≤ D-1.
a. De un algoritmo que calcule un plan para la compañía, que mimimice sus costos, mientras satisface toda la demanda. El tiempo de ejecución debería ser polinomial en n y D.
Gracias