Entrega de Talleres

Sé que puede haber preocupaciones acerca de la fecha de entrega de los talleres que aún están pendientes.

Vamos a seguir el calendario de la Universidad, así que en Enero fijaremos la fecha definitiva de entrega, que supongo será algún día de la semana del 23 al 27 de Enero. Sin embargo, si alguien quiere entregar antes, puede hacerlo.

Pueden seguir haciendo y respondiendo preguntas en este blog o por e-mail. También pueden optar por enviarme versiones de los trabajos para que yo les haga correcciones, pero todo esto es opcional, es decir, no habrá premios para los que entreguen antes ni castigos para los que entreguen en la fecha que fije en Enero.

Es posible que recomiende algunos sitios y/o lecuras relacionados con el curso, igualmente opcional, aunque estaré pendiente de las preguntas y/o comentarios que hagan al respecto...

Así que si pueden, descansen...

Bubble Sort

Tal vez lo primero que debe hacerse a la hora de hacer una prueba de correctitud es entender qué hace el algoritmo y cómo lo hace. En este caso creo que está claro el "qué" y para el "cómo" es suficiente con hacer un seguimiento con algún ejemplo. Si no han dado este "primer paso", les recomiendo que lo hagan antes de continuar.

Una vez tengan una idea de cómo opera el algoritmo, puede abordarse el problema en dos fases: suponer, primero, que las líneas 3 a 9 corresponden a otro procedimiento (o función) y hacer una prueba de correctitud para tal procedimiento. Una vez hecho eso, puede probarse la correctitud del procedimiento completo teniendo en cuenta que se conoce cuál es la operación del ciclo interno y además que es correcta, suponiendo que las líneas 3 a 9 se reemplazan por una llamada (en una línea) a otra función, por lo tanto sólo interesa saber qué hace esa línea.

Consideren, por ejemplo, el ciclo interno: la operación de las líneas 6 a 8 puede resumirse diciendo intercambiar(A[j], A[j+1]), aunque sería necesario probar la correctitud de intercambiar(a, b). Y en el momento de hacer la prueba del ciclo completo, se considerarían dos casos: en uno, los valores de las posiciones j y j+1 se intercambian y en el otro no, sin necesidad de recorrer de nuevo el procedimiento intercambiar.

Un inconveniente a la hora de hacer las pruebas es la escritura de las proposiciones en forma matemática. La idea es que NO vamos a ser, por el momento, demasiado rigurosos, en cambio, utilizaremos un lenguaje mixto. Por ejemplo: es válido decir que, en algún punto de la ejecución del algoritmo, los elementos de las posiciones 1 a k, o si prefieren, el subarreglo A[1..k] contiene sólo números primos...

Espero que se genere discusión al respecto...

Taller de Recuperación

Pueden descargar el Taller de Recuperación utilizando el siguiente vínculo:

Taller [.pdf (81 KB)]

La fecha de entrega es el día Jueves 17 de Noviembre de 2005. No olviden que pueden hacer preguntas a través de este medio.

El niño y la escalera: punto a su favor...

Efectivamente había considerado una relación de recurrencia que no correspondía al problema planteado. Consideré dos alternativas:

i) T(n) = T(n - 1) + 1; para n > 1; T(1) = 1

ii) T(n) = T(n - 2) + 2; para n > 2; T(1) = 1, T(2) = 2

Daré un punto de bonificación para la primera persona que describa, por este medio y de manera correcta, el error en la definición de las relaciones planteadas en i) y en ii).

¡Bienvenidos!

Espero que utilicen este espacio para escribir preguntas, comentarios, ideas, recomendaciones, etc. acerca de la clase. La idea es que nutramos entre todos este blog, es decir, si alguien escribe alguna pregunta, cualquiera puede responderla y si se genera algún tipo de discusión muchísimo mejor.

Así que comencemos...