Anuncios


Notas tercer tercio

posted May 21, 2013, 8:47 AM by Camilo Rocha

Adjunto encuentran las notas del tercer tercio.

Problema 5, página 275

posted May 7, 2013, 7:05 PM by Camilo Rocha

Adjunto encuentran una solución derivada del problema 5 en la página 275. Además, encuentran adjunto un programa en Python que implementa el código derivado.

2-Partition

posted May 6, 2013, 4:24 PM by Camilo Rocha   [ updated May 7, 2013, 5:29 PM ]

Adjunto encuentran unas notas sobre el problema "2-Partition" (es el mismo problema llamado 'bi-particionable' de los ejercicios de la semana 9) en donde:
  • se plantea una solución recurrente
  • se usa tabulación para evitar hacer cálculos repetidos (programación dinámica)
Esta explicación complementa la vista en clase, en especial, porque la tabulación se presenta con invariantes formales y no, únicamente, con los invariantes gráficos. Hay ejercicios que les ayudarán a entender en más detalle cómo funciona la técnica y para repasar el tema de verificación de programas iterativos. Les recomiendo ENFÁTICAMENTE que resuelvan esos ejercicios.

Adicionalmente, actualicé el código en Python para que la matriz de tabulación coincida con la de la especificación formal y se encuentra como archivo adjunto.

Notas Tercio 2

posted Apr 5, 2013, 6:26 AM by Camilo Rocha   [ updated Apr 5, 2013, 10:34 AM ]

A continuación encuentran las notas correspondientes al segundo tercio.

Durante el segundo tercio tuvimos:

- 3 talleres (30%)
- 1 parcial (70%)

Un taller se califica con 1 (su fue entregado) o 0 (de lo contrario). La nota del parcial se calificó sobre 5 ajustó con curva de 4.7 (nota máxima sin ajuste) a 5.3 (nota máxima con ajuste).

Aún está pendiente consolidar la nota (entrega) del taller 3.

Ejercicios Semana 9: Ejercicios adicionales sobre recurrencia

posted Mar 18, 2013, 9:25 AM by Camilo Rocha

Para cada uno de los siguientes problemas, el estudiante debe plantear soluciones recurrentes.
  1. Considere un conjunto S de números naturales. El conjunto S se llama perfectamente bi-particionable sii S puede ser particionado en dos subconjuntos S1 y S2 (es decir, la intersección de S1 y S2 es vacia y la unión de S1 y S2 es igual a S) tales que M = |S1| = |S2|, en donde M = |S|/2. Para cualquier conjunto de números naturales R, la expresión |R| denota la suma de los elementos en R. Escriba una fución que dado un conjunto S y la suma de sus elementos |S|, determine si S es perfectamente bi-particionable. Puede suponer que S es tal que |S| es par.
    • Por ejemplo, si S = {1,2,3} la respuesta debe ser afirmativa dado que |S| = 6 y S1 = {1,2} y S2 = {3} son tales que |S1| = 3 = |S2|. Al contrario, S = {1,2,3,8} no es perfectamente bi-particionable.
  2. Considere un arreglo D[0,N) de números naturales, con N >= 1 que representa denominaciones de monedas; suponga que D[0] = 1, que D está ordenado ascendentemente, que no hay denominaciones repetidas en D y que de cada denominación hay una fuente inagotable de monedas. Defina una función que dado un número entero M >= 0, determine de cuántas formas se puede expresar M con monedas de denominaciones en D.
    • Por ejemplo, si D = [1,2,5] y M = 5, entonces hay 4 formas de expresar M con monedas de denominaciones en D:
      • 5 monedas de $1
      • 3 monedas de $1 y 1 moneda de $2
      • 1 moneda de $1 y 2 monedas de $2
      • 1 monedas de $5

Notas Tercio 1

posted Feb 25, 2013, 4:10 AM by Camilo Rocha   [ updated Feb 25, 2013, 4:12 AM ]

A continuación encuentran las notas del primer tercio.

Sección de quices

posted Feb 7, 2013, 9:51 AM by Camilo Rocha

La sección de "Bitácora y notas" ha sido actualizada a la sección de

  "Bitácora, notas y quices".

Allí encuentran el enunciado del quiz 2 y una solución.

Implementación de soluciones en Python3

posted Jan 24, 2013, 2:41 PM by Camilo Rocha   [ updated Jan 24, 2013, 2:42 PM ]

En las últimas sesiones de clase hemos estudiado y repasado cómo utilizar cuantificadores para especificar problemas algorítmicos. Una de las principales ventajas de definir formalmente un problema es que en muchas ocasiones, el paso es muy pequeño entre la especificación formal de un problema y la implementación de una solución en un lenguaje de programación. En este pequeño ejercicio, se implementarán en el lenguaje de programación Python3 algunas soluciones a problemas que se han especificado en tareas o en clase.

A continuación encuentran una implementación en Python (versión 3) de una función que dado un arreglo de enteros y su longitud, determina si el arreglo es ascendente (este es ejercicio 1.1.0.c del texto guia [2]).


Note que la implementación viene acompañada de la especificación del problema. Además, como vimos en clase, es posible obtener una implementación más eficiente del mismo algoritmo de tal modo que no se hagan más comparaciones de las que son necesarias, como se ve a continuación.


Note que aparentemente las dos soluciones son equivalentes (aunque en este momento no tenemos las herramientas que necesitamos para demostrarlo). Pero lo que podemos hacer es probar con algunos valores. Por ejemplo, los siguientes comandos que usan las funciones que aparecen anteriormente


producen la siguiente salida:

True
True

True
True

False
False

La idea es entonces que se ejerciten en la escritura de soluciones en Python3:
  1. Para familiarizarse con Python3, visite el sitio de Python y revise su documentación. Aspectos a tener en cuenta:
    • Identar es importante
    • No se definen tipos explícitamente
  2. Usando el código de la función ascendente como una plantilla, implemente en Python3 soluciones para los problemas
    • 1.1.0.(e)
    • 1.1.0.(l)
    • 1.1.0.(o)
    • 1.1.1.(d)
    • 1.1.1.(g)
Las implementaciones que obtenga solo pueden utilizar un 'ciclo', es decir, deben ser de orden O(N) en donde N es la longitud del arreglo.

A continuación encuentran un progrma que incluye las dos versiones de ascendente vistas antes y el código con las pruebas.



Si ascendente.py es el nombre del archivo que contiene el código del programa completo, entonces puede ejecutarse en Python3 de la siguiente manera:

python3 ascendente.py


NOTA: los laboratorios de Sistemas tienen Python3 instalado.

Mensaje de bienvenida

posted Jan 14, 2013, 4:10 PM by Camilo Rocha   [ updated Jan 14, 2013, 4:46 PM ]

Hola, mi nombre es Camilo Rocha y seré su instructor de TPRO, "Teoría de la Programación", versión 2013-1.

Por favor lea esta nota cuidadosamente - pueda que le evite un par de dolores de cabeza durante el semestre. Este es un curso que demanda trabajo constante y está diseñado para estudiantes que quieren aprender a diseñar programas correctoes, eficientes y elegantes.

Es necesario que el estudiante sea organizado, esté motivado para hacer las lecturas antes de las clases y esté pendiente del material del curso. La finalidad de este curso no es obtener una buena nota sino el de prepararlos mental y técnicamente para que adquieran habilidades que serán necesarias en al vida laboral y para cursos en semestres futuros.

Si no está preparado mentalmente para trabajar, aprender y ejércitar el cerebro durante 12 horas a la semana, con el fin de analizar y resolver problemas en cada sesión de clase o laboratorio, pueda que este curso se le dificulte. Sí, este es un compromiso de tiempo significativo pero, aún más importante, es un compromiso con su futuro personal.

TPRO tiene
  • lecturas semanales,
  • ejercicios (bi-)semanales,
  • exámenes parciales en los dos primeros tercios y
  • un examen final.
La asistencia a clase es obligatoria. Los ejercicios son individuales y aunque se permite la discusión de problemas, las soluciones a los problemas no deben discutirse entre los estudiantes. No es recomendable tomarse el curso "con calma" porque es prácticamente imposible desatrazarse. Si no puede ir a una clase, trate de ir a las horas de oficina. Por favor no trabaje en "paralelo" en clase; puede hacer los ejercicios y trabajos de TPRO en sus clases de  Cálculo, Física, etc. o mientras navega en Facebook, pero no al revés.

Este semenstre se utilizará Python para programar y no es necesario tener experiencia previa con el lenguaje para aprender en el curso.

Que disfruten el curso!!!

1-9 of 9