CI-1101 Examen #2


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1101
I Semestre 2014

$[\/]$

CI-1101 Programación I

Examen #2 [solución]

Duración: Ciento veinte minutos. Lea bien el examen antes de hacerlo. El examen es a libro abierto. Cuenta la documentación. Cuenta la redacción y la ortografía. Puede hacer el examen con lápiz. Resuelva todas las preguntas. ¡No haga más de lo que se le pide!

1) [33 pts] La función de Ackermann

En teoría de la computabilidad, la función de Ackermann, cuyo nombre viene de Wilhelm Ackermann, es uno de los primeros y más simples ejemplos de una función total que es computable pero que no es primitivo recursiva. Todas las funciones primitivo recursivas son totales y computables, pero la función de Ackermann ilustrata que no todas las funcines que son totales y computables también son primitivo recursivas. Un versión Java de este función es la siguiente:

// http://en.wikipedia.org/wiki/Ackermann_function
public static long ackermann(long m, long n) {
    if ( m==0 ) { return n+1; }
    if ( m>0 && n==0 ) { return ackermann(m-1,1); }
    return ackermann( m-1, ackermann(m,n-1));
}

1.a) [22 pts] Esta función crece enormemente rápido. Por ejemplo, ackermann(4,2) es un entero de 19,729 dígitos decimales. Dibuje los registros de activación que resultan al ejecutar ackermann(2,0).

1.b) [11 pts] Suponga que en un examen de este curso le piden dibujar loos registros de activación que de estas 3 invocaciones: { ackermann(2,0) , ackermann(2,1) , ackermann(2,2) }. ¿Cuál de todas tiene menos invocaciones recursivas y por qué?

2) [33 pts] El método voySubiendo() sirve para determinar el tamaño del pedazo ascendente de un vector, aún si no está ordenado.

{
    { int V[]= {00,10,20,30,-1};       assertTrue( 4 == voySubiendo( 0, V ) ); }
    { int V[]= {00,10,20,30,30,60,-1}; assertTrue( 3 == voySubiendo( 3, V ) ); }
    { int V[]= {00,-1};                assertTrue( 1 == voySubiendo( 0, V ) ); }
    { int V[]= {00};                   assertTrue( 1 == voySubiendo( 0, V ) ); }
    { int V[]= null;                   assertTrue( 0 == voySubiendo( 0, V ) ); }
}

2.a) [5 pts] Escriba la especificación de voySubiendo(). No olvide incluir ejemplos de uso assertTrue() y assertFalse().

2.b) [11 pts] Implemente voySubiendo(). Incluya documentación interna que explique por qué los índices usados en su algoritmo no se salen del vector.

2.c) [6 pts] Escriba la especificación de soyColina() que sirve para determinar si los valores de un vector primero ascienden y luego descienden. No olvide incluir ejemplos de uso assertTrue() y assertFalse().

2.d) [11 pts] Suponga que usted cuenta ya con la rutina voyBajando(): úsela junto con voySubiendo() para implementar soyColina().

3) [33 pts]

[2(3)] [3(26)] [4(46)]

3 2 1

26 25 24 23 22 21 20 19

46 45 44 43 42 41 40 39 38 37 36 35

3.a) [7 pts] El método estático "triangulo()" de la clase "Biblio" recibe dos números e imprime una escalera de varios peldaños a partir del segundo valor. Escriba la especificación completa de "triangulo()".

3.b) [26 pts] Implemente "triangulo()". En el ejemplo se muestra "triangulo()" para los valores [2(3)], [3(26)] y [4(46)].

Soluciones

$[/\]$

`[2(3)]`	`[3(26)]`	`[4(46)]`
3 2 1	26 25 24 23 22 21 20 19	46 45 44 43 42 41 40 39 38 37 36 35