Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
Profesor Adolfo Di Mare
CI-1101
I Semestre 2014
[<=] [home] [<>] [\/] [=>]
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

[mailto:] Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2014
Derechos de autor reservados © 2014
[home] <> [/\]