INF203 - Fundamentos de Programación Práctica 1 (2006-1) 1

PONTIFICIA UNIVERSIDAD CATÓLICA DEL PERÚ FACULTAD DE CIENCIAS E INGENIERÍA

FUNDAMENTOS DE PROGRAMACIÓN

1ra Hoja de Trabajos Prácticos (1er período de 2006)

Horario 0581: V. Khlebnikov

Duración: 1 h. 50 min. Pregunta 1. (Mark Allen Weiss - 6 puntos) El cuarto algoritmo de la solución al problema de la suma de la subsecuencia máxima (página 32, figura 2.8) es el siguiente:

function suma_subsecuencia_max(var a: arr_entrada; n: integer): integer; var esta_suma, suma_max, mejor_i, mejor_j, i, j: integer; begin { 1} i:=1; esta_suma:=0; suma_max:=0; mejor_i:=0; mejor_j:=0; { 2} for j := 1 to n do { 3} begin { 4} esta_suma := esta_suma + a[j]; { 5} if esta_suma > suma_max then { 6} begin { 7} suma_max := esta_suma; { 8} mejor_i := i; { 9} mejor_j := j; {10} end; {if} {11} else {12} if esta_suma < 0 then {13} begin {14} i := j + 1; {15} esta_suma := 0; {16} end; {else} {17} end; {for} {18} suma_subsecuencia_max := suma_max; end;

Es obvio que se debe recorrer todos los elementos del vector, del primero al último. Por eso existe una variable, j, que lo hace (la línea 2). También es obvio que se necesita acumular la suma de elementos, por eso existe la línea 4. Las líneas 5 – 10 registran lo que se busca mientras se hace el recorrido. Pero las líneas 12 – 16, ¿cuál es la JUSTIFICACIÓN de su existencia en este código? ¿Por qué se comprueba si la suma es NEGATIVA y no se usa ninguna otra comparación? ¿Por qué si la suma es negativa, se actualiza la variable i y ella se actualiza de esta manera y no de otra? Es que la variable i se modifica solamente en este único lugar del código. Y, ¿por qué se resetea la variable de la suma acumulada a 0 y no se usa otro valor? Entonces, en otras palabras, su tarea es explicar la IDEA que está detrás de este programa. Pregunta 2. (6 puntos – Mark Allen Weiss, ejercicio 2.12a) Proporcione algoritmo eficiente (junto con el análisis del tiempo de ejecución de su implementación en Pascal) para encontrar la suma de la subsecuencia mínima.

INF203 - Fundamentos de Programación Práctica 1 (2006-1) 2

Pregunta 3. (2 puntos – Aho, Hopcroft, Ullman, ejercicio 1.17) Supóngase que el parámetro n del procedimiento siguiente es una potencia positiva de 2, esto es, n = 2, 4, 8, 16, … Proporciónese una FÓRMULA que exprese el valor de la variable cuenta en función del valor n (cuenta = f(n)) cuando termina el procedimiento.

procedure Misterio(N: Integer); var X, Cuenta : Integer; begin Cuenta := 0; X := 2; while X < N do begin X := 2 * X; Cuenta := Cuenta + 1 end; Writeln(Cuenta) end

Pregunta 4. (3 puntos – Ian Parberry) ¿Qué valor devuelve la siguiente función (expréselo en términos de n)? Estime esta función con O-grande. Use las fórmulas conocidas:

2/)1(1

+=∑ =nnin

i y 6/)12)(1(

12 ++=∑ =

nnnin

i

function pesky(n) 1. r := 0; 2. for i := 1 to n do 3. for j := 1 to i do 4. for k := j to i+j do 5. r := r + 1 6. return(r)

Pregunta 5. (3 puntos – Ian Parberry) Demuestre que (n + 1)2 = O(n2).

------- o ------- La práctica ha sido preparada por V.K.

Pando, 27 de marzo de 2006