 |
Algoritmos
y Estructuras I CI-2611 y CI-2691 |
| |
Algoritmos
y Estructuras I CI-2611 y CI-2691 |
|
Se hace hincapié en refinamiento de programas, aunque se dá una noción básica de refinamiento de datos (tema principal del curso CI-2616). La noción de tipo abstracto de dato (Clase) y objeto deberá ser dada desde un comienzo, aún cuando sóo trabajaremos fundamentalmente con tipos básicos, tipo arreglo y tipo archivo secuencial. Se dará la noción de encapsulamiento y ocultamiento de datos en lenguajes de programación para introducir la noción de Case (implementación de tipos abstractos). Las nociones sobre derivación y corrección de programas serán tratadas más formalmente al final del curso. En las primeras semanas del curso se desarrollarán los programas de forma más intuitiva. Se deberán dar varias soluciones algorítmicas a un mismo problema, mostrando las bondades de unas respecto a las otras y resaltando el buen estilo de la programación. Es recomendable que los estudiantes ya hayan visto, o sigan en paralelo, un curso de lógica. Al comienzo del curso se dá una breve introducción de lógica y teoría de conjuntos con el fin de establecer la notación matemática a utilizar. En la primera parte del curso se determinarán especificaciones de problemas y se desarrollarán los algoritmos de manera intuitiva a partir de estas especificaciones, haciendo énfasis en esquemas de algoritmos y diseño descendente. Dejando claro en cada momento las aserciones (predicados) que representan los cambios de estado de cada acción. La noción de métodos (procedimientos y funciones) se presenta temprano en el curso, de manera de tener lo más temprano posible este mecanismo de control de la complejidad, y permita al equipo de laboratorio elaborar proyectos donde desde un comienzo se haga uso de este mecanismo de estructuración de programas. En las primeras semanas del curso se dará gradualmente el pseudo lenguaje que se utilizará para describir los algoritmos: las estructuras básicas de control y los tipos de datos necesarios para resolver problemas cada vez más complejos. También se precisarán las reglas de alcance de identificadores y paso de parámetros (distinguiendo parámetros de entrada, salida y entrada-salida). En cuanto a los tipos de datos, estos serán los tipos primitivos del lenguaje JAVA, el tipo archivo secuencial y el tipo arreglo. En cuanto a las instrucciones del pseudolenguaje, se darán en el siguiente orden: la asignación, la secuenciación de acciones, Procedimientos y Funciones (como mecanismo de abstracción procedural en la aplicación del diseño descendente, paso de parámetros: parámetros de entrada, de salida y de entrada-salida. Variables locales. Llamadas recursivas, al final del curso), constructores condicionales, constructores iterativos. En la primera parte del curso se enfatizará más el buen estilo de programación, en la segunda parte se puede incluir criterios de eficiencia (soluciones más eficientes). El tópico de eficiencia se trata en el curso CI-2616. En las últimas semanas del curso se hará énfasis en derivación formal de algoritmos iterativos. Se desarrollarán algoritmos utilizando técnicas derivación. La razón de dar derivación es para mostrar que existe una forma sistemática de desarrollar e incluso calcular un programa correcto a partir de una especificación. Al final del curso se dará una breve introducción al diseño de soluciones recursivas de problemas (utilizando para esto una variedad de ejemplos concretos). La estrategia de solución Divide y Conquistarás. Las soluciones recursivas, producto de aplicar Divide y Conquistarás, deberán ser mostradas de manera intuitiva (el tratamiento formal de corrección y/o derivación de programas recursivos no es materia de este curso). En la medida de lo posible, se dará una solución recursiva a ejemplos mostrados a lo largo del curso. Para desarrollar los algoritmos en teoría, se utilizará el pseudo lenguaje del libro Kaldewaij. Toda la notación y conceptos utilizados en el curso se encuentran en la Guía "Introducción a la Programación". En laboratorio se utilizará el lenguaje JAVA.
Breve introducción del cálculo de predicados y de la teoría de conjuntos y relaciones. Establecer la terminología y notación a utilizar a lo largo del curso. 2) Problemas y su solución mediante algoritmos (2 clases. Bibliografía: Guía): ¿Qué es un problema?. Enunciado
de un problema. Especificaciones Informales: inconsistencia,
ambiguedad, redundancia. Especificaciones Formales. Pasos a
seguir para especificar un problema (Precondición y Postcondición:
determinación de los objetos de dato y de resultado y representar las
relaciones entre estos utilizando las operaciones sobre los objetos).
Ejemplo de Especificación: Dado un número natural que representa una
cantidad de segundos, se desea calcular la representación de este
número en días, horas, minutos y segundos. 3) Construcción de Programas (12 clases). 3.1) El pseudo lenguaje (3 clases, Bibliografía: Guía, Kaldewaij): Tipos básicos y sus
operaciones, variables. Tipos básicos: enteros, reales,
booleanos, caracteres. Declaración de variables. Expresiones. Acciones
Elementales: observación, modificación (la asignación). Semántica de la
asignación. Semántica de la secuencia de acciones mediante aserciones (
Si {Q}I1{P} y {P}I2{R} entonces {Q}I1; I2{R}). Especificación,
desarrollo intuitivo y verificación de algoritmos utilizando el pseudo
lenguaje. Ejemplos sencillos sobre secuencia de acciones: suma de dos
números, intercambio de valores de dos variables. Otros ejemplos: un
número natural que representa una cantidad de segundos, se desea
calcular la representación de este número en días, horas, minutos y
segundos. 3.2. Procesos iterativos. Arreglos. Esquemas de algoritmos (6 clases. Bibliografía: Guía, Kaldewaij, Castro): Proceso Iterativo. Análisis de
Procesos Iterativos. Elementos del Análisis Iterativo: estado
inicial, estados intermedios, estado final. Noción de Invariante
de un proceso iterativo. Condición de continuación de un proceso
iterativo, acción elemental repetida, función de cota. El
constructor “Mientras”, su semántica en función de pre y post
condición. Es muy importante resaltar que el invariante debe surgir
de manera natural en el esquema de solución algorítmica del
problema, y no a la inversa, es decir, hacer el algoritmo y luego, una
vez
construido, se determina los invariantes de las acciones iterativas.
Heurísticas
básicas para determinar invariantes. Ejemplos (aplicar diseño
descendente en lo posible): Cálculo de la suma de los n primeros
términos
de una sucesión, Máximo Común Divisor (solución
iterativa, e introducir las soluciones recursivas de manera natural),
Raíz
entera de un número. Cálculo de la potencia n-ésima
de un número (ver distintas soluciones y la más eficiente y
sus planteamientos recursivos). 3.3. Diseño Descendente (4 clases. Bibliografía: Guía, Castro): Refinamiento de datos y refinamiento de acciones. Refinamiento de acciones: sección 7.2.1 de la guía. Ejemplo con la máquina de trazados: dibujo de n círculos concéntricos. Refinamiento de datos: Invariante de Acoplamiento. Ej: cálculo de las raíces complejas de un polinomio. Otro ejemplo: contar cuantas veces aparece la palabra "mu" en una secuencia de caracteres. Encapsulamiento y Ocultamiento de datos: el constructor tipo (ó clase). Ventajas. Ej: cálculo de las raíces complejas de un polinomio utilizando el constructor de tipos. 4. Derivación formal de programas y Soluciones recursivas de problemas (4 clases. Bibliografía: Guía, Kaldewaij): Derivación de programas
iterativos (uso de las heurísticas). Invariante. Tratamiento formal de
arreglos. El laboratorio deberá ser cerrado, donde los proyectos asignados a los estudiantes vayan siendo desarrollados y evaluados en el aula junto al docente. Se recomienda una hora por semana de práctica (donde discutan distintas soluciones a problemas utilizando las herramientas dadas en teoría y JAVA) y dos horas por semana de desarrollo de proyectos (donde se desarrolle o evalúe en la sala de computadores, una tarea asignada con anterioridad). Las herramientas de programación que se utilizarán (JAVA, editores, compiladores, documentación, etc.) deberán ser introducidas y explicadas claramente desde un comienzo. Durante todo el curso la actividad de laboratorio estará centrada en el desarrollo de programas (acciones para manipular objetos). La definición de clases se hará muy puntualmente a mediados del curso, con el objeto de ilustrar el encapsulamiento y ocultamiento de datos. Por lo que en el laboratorio los proyectos consistirán en el desarrollo de métodos en una clase estática que contendrá el método main( ), y serán aplicaciones “stand-alone”. Se promoverá la utilización de bibliotecas de programas y enfatizará en todo momento el buen estilo de programación. Se podrá utilizar las bibliotecas de JAVA (tipo string, tipo archivo secuencial, etc.) que determine el equipo docente del laboratorio. El equipo docente de laboratorio puede requerir la utilización de Applets, GUI’s, etc., en un proyecto. En este caso, la utilización de tales herramientas y el código necesario deberá ser proporcionado por el equipo docente, de forma tal que al estudiante se le dará una plantilla de código que él modificará para introducir el código relacionado con su proyecto concreto. Por lo que en laboratorio se promoverá la reutilización de software. Sólo al final del curso se podrá evaluar los temas sobre derivación o verificación de programas. Se deberá definir un standard basado en criterios de ingeniería de software que indique normas de estilo de programación, verificación y pruebas, y presentación y documentación de los proyectos. Los proyectos deberán ser cortos y destinados a evaluar conocimientos específicos del curso. Clase 1 (segunda semana):
Teoría de Conjuntos y Lógica.
- Jorge Castro, Felipe Cucker, Xavier Messeguer, Albert Rubio, Lluis Solano, Borja Valles. "Curso de Programación". McGraw Hill. 1993. ISBN-84-481-1959-2. Capítulos 1, 2 y 3. - Kaldewaij Anne. “Programming: the derivation of algorithms”. Prentice Hall. 1990. ISBN- 0-13-204108-1. Capítulos 1, 2, 3 y 4. - Gries David. “The Science of Programming”. Springer.Verlag.1981. ISBN 0-387-96480-0. Páginas 1-85 y 310-319 - Gries David, Schneider Fred. "A Logical Approach to Discrete Math". Springer-Verlag. 1993. - Gries David, Gries Paul. “Programlive: Introducing Programming with JAVA”. Software en CD. - Horstmann Cay, Cornell Gary. “Core JAVA 2: Volume I- Fundamentals”. Prentice Hall.1999. Capítulos 1, 2 y 3. Formato MSWord: Formato PDF:
- Contenido
Contenido
Actividades en los trimestres :
|