Especificación y Complejidad en el Cálculo Científico

De Cuba-Wiki
Saltar a: navegación, buscar

Especificación y Complejidad en el Cálculo Cientifico el Arte y Especificación y Complejidad en el Cálculo Cientifico la Teoría, son dos materias optativas que se dan generalmente en simultáneo. Otorga cuatro puntos en total tanto para grado como para doctorado; se recomienda tener aprobadas Álgebra lineal, Análisis I, Algoritmos y Estructuras de Datos I, II, III . El profesor de la materia es el Dr. Joos Heintz.

Históricamente, se hace una reunión a principio de cuatrimestre para fijar horarios, es muy flexible.

Información General sobre la Cursada[editar]

La cursada es principalmente teórica, puesto que la materia no tiene ayudantes, 1 vez por semana (Arte) + 1 vez por semana (Teoría).

Se aprueba con presentación de un trabajo escrito o examen. También se hacen tareas de programación de algoritmos sencillos, su testeo y su verificación. Lectura de artículos de investigación (trabajo en grupos).

Objetivos

El curso pretende introducir a los alumnos al análisis y construcción de programas complejos mediante técnicas de verificación y derivación de programas ejecutables para el cálculo científico a partir de especificaciones formales. Se ilustrará con numerosos ejemplos como especificaciones descriptivas, formuladas en términos provenientes de la teoría de bases de datos, se convierten en especificaciones operacionales y finalmente en algoritmos sujetos a diferentes técnicas de optimización. En su aspecto práctico, el curso enseñará, de forma independiente de un lenguaje determinado, algunas técnicas de especificación y derivación de programas y algunos tipos y estructuras de datos y algoritmos básicos y eficientes para el cálculo simbólico y numérico. En su parte teórica, el curso tratará de discutir la relación entre programa (con verificación) y algoritmo, haciendo hincapié en los aspectos de complejidad. El curso desarrollará una visión unificada de la teoría de la complejidad de algoritmos, de la especificación y transformación de programas y de la teoría de bases de datos (continuas y relacionales). Todos los conceptos serán introducidos mediante de la discusión de problemas concretos provenientes principalmente de la geometría algorítmica y desarrollados hasta su formulación matemática rigurosa.

Temática

La computación científica exige con frecuencia del desarrollo de programas complejos cuyo funcionamiento práctico requiere técnicas razonadas de derivación y verificación y un estrecho control de la complejidad de los algoritmos subyacentes. A su vez, la eficiencia de los algoritmos implementados depende de la elección de los tipos y estructuras de datos que se utilizan. Esto conduce al concepto de especificación: en la práctica es imposible redactar un programa complejo en un lenguaje de bajo nivel. Tal programa sería fácilmente incorrecto, ineficiente, poco flexible y la tarea de programación no sería distribuible entre varios programadores que se tienen que comunicar entre ellos. Esto conduce al uso de diferentes niveles de abstracción que permiten derivar un programa ejecutable de una especificación descriptiva de la tarea original. Estos conceptos de la programación, introducidos en los años 70 por Hoare y Dijkstra, serán aplicados y discutidos durante el curso en el contexto específico de la computación científica. Un aspecto nuevo del curso consiste en la modelización matemática de las tareas de un programa complejo (especificación descriptiva) en terminos de la teoría de bases de datos: la ejecución de tal programa será interpretada como la evaluación de una consulta. Este punto de vista permite por vez primera la demostración de cotas inferiores de complejidad relevantes para tareas no elementales de programación. Los ejemplos serán tomados de la aritmética y de la geometría.

Contenidos

Temas básicos: Noción de algoritmo, programa y especificación. Diferentes modelos algoritmicos y medidas de complejidad. Ejemplos de estructuras de datos y algoritmos (in-) eficientes de la aritmetica y del álgebra lineal. Estructuras y tipos de datos. Longitud de programa y tiempo de su ejecución. Introducción a la lógica de predicados y especificación formal. Bases de datos continuas y relacionales y sus lenguajes de consulta. La noción de consulta genérica, evaluación de consultas y su complejidad. Un modelo algoritmico adaptado al cálculo cientifico para la recursión en tiempo polinomial ( extensión del modelo de Cook - Bellantoni ).

Temas algorítmicos: Complejidad aritmética y bit de algoritmos basicos simbolicos y numericos en algebra lineal con matrices genericos y estructuradas y su programación y verificación. El algoritmo de Newton y variantes simbolicos y numéricos. La estructura de datos straight-line program en programación orientada a objeto y programación funcional. Eliminación geométrica y algebraica ( evaluación y reescritura). Analisis numérico y aproximación diofántica.

Especificación, verficación y derivación de programas: Algunos tipos de datos fundamentales y su especificación algebraica. Especificación descriptiva de programas para tareas geométricos en terminos de la teoría de bases de datos contínuas. Ejecución de programas para tareas geométricas como evaluación de consultas. Transformación de programas descriptivos en operacionales mediante algoritmos recursivos. Diferentes tipos de recursión. Invariantes. . Cotas inferiores para el tiempo de ejecución de programas derivados de especificaciones en geometría.

Clases[editar]

La Teoria 
  • Clase 1: SAT es NP-Completo
  • Clase 2: 3-SAT es NP-Completo
  • Clase 3: 3-Coloreo es NP-Completo
  • Clase 4: Partition Problem es NP-Completo
  • Clase 5: Aplicación de Partition y Subset Sum Problem (Mochila)
  • Clase 6: Programacion Entera es NP-Difícil
  • Clase 7: Problemas de Optimización, ecuaciones lineales - Viernes 12/09
El Arte

Examen[editar]

Apuntes[editar]

  • Resumen: Resumen general de la materia.

Bibliografía Recomendada[editar]

  • Balcázar, Programación metódica. Circulante 681361 Balcazar, Biblioteca Central
  • Balcázar, Structural complexity. Circulante 519600 Balcazar, Biblioteca Central

Enlaces externos[editar]