Examen de análisis de algoritmos

Problema 1

1. Sea un alfabeto de longitud  finita y sea   su diccionario, es decir, el conjunto de palabras de longitud finita con símbolo en Σ. Considere las siguientes tres funciones primitivas:[pic 1][pic 2]

• inserta:  x N x  : inserta(σ,i,α) es la palabra resultante de insertar el símbolo α inmediatamente a la derecha del i-ésimo símbolo de σ.[pic 3][pic 4]
• borra: Σ* x N →Σ*: borra(σ,i) es la palabra resultante de borrar el i-ésimo símbolo de σ.
• sustituye: Σ* x N x Σ→Σ*: sustituye(σ,i,α) es la palabra resultante de sustituir el i-ésimo símbolo de σ por el símbolo α.

Diseñe un algoritmo con el menor número de aplicaciones de las tres funciones primitivas dadas dos palabras σ, τ ϵ   que transforme σ en τ.[pic 5]

[pic 6]

[pic 7]

Un algoritmo que realiza tal transformación, pero no necesariamente es optimo, borra cada uno de los símbolos de σ y luego escribe uno a uno los símbolo de τ.

Teniendo un alfabeto de longitud finita determinado por:

Σ={0,1,2,3,4,5,6,7,8,9}

y siendo Σ* su diccionario el cual contiene al conjunto de palabras que podemos usar para construir σ y τ, ejemplo:

σ = {123}

τ = {14}

Problema 2

1. Diseñe un algoritmo en pseudocódigo dada una sucesión de números enteros (positivos o negativos) encuentre el tramo en ella que dé la suma más grande. Es decir, dada , encuentre  y  máxima sobre todas las posibles elecciones de.[pic 8][pic 9][pic 10][pic 11]

Tomando una sucesión cualquiera de número enteros, ya sean negativos o positivos, debemos hallar el intervalo donde la suma sea máxima, tomamos como ejemplo la siguiente sucesión.

{-1, 9, - 5, 3, 1}

Problema 3

1. Diseñe un algoritmo en pseudocódigo dada una sucesión de números enteros (positivos o negativos) que ordene de menor a mayor esta sucesión. Es decir, dada , encuentre  sobre todas las posibles elecciones de. [pic 12][pic 13][pic 14]

...