• Programa

    Objetivos:

    La materia tiene por objetivo que los alumnos:

    • Aprendan las herramientas para resolver con seguridad una clase sencilla de problemas: el tratamiento de secuencias
    • Aprendan a demostrar que los programas construidos son correctos
    • Resuelvan pequeños proyectos donde se apliquen las herramientas aprendidas

    Contenidos:

    Parte I - Corrección de programas imperativos:

    • Contratos. Obligaciones y derechos del programador y del usuario
    • Conceptos básicos de los programas imperativos: variables - estructuras de control - funciones - ciclos
    • Corrección de programas
      • Especificación formal de contratos: tipos de datos básicos, secuencias, n-uplas, operadores de lógica condicionales (cand y cor) y sus propiedades
      • Demostración de corrección parcial: precondicicón más débil. Teorema de corrección parcial para ciclos. Invariantes de ciclo.
      • Demostración de terminación: Función variante

    Parte II - Algoritmos sobre secuencias

    • Buenas prácticas para el desarrollo de software. El software pensado para consumo humano.
    • Fundamentos de testing estructural: cubrimiento de líneas, branches, condiciones básicas. Diagramas de flujo de control. 
    • Tiempo de ejecución de peor caso de un algoritmo. Notación O grande.
    • Algoritmos de búsqueda sobre secuencias: búsqueda lineal, búsqueda binaria
    • Algoritmos de ordenamiento sobre secuencias: ordenamiento por selección, ordenamiento por inserción, ordenamiento por burbujea, problema de la bandera holandesa
    • Algoritmos sobre secuencias ordenadas: problema de apareo entre secuencias, problema del welfare crook
    • Algoritmos de matching de strings: algoritmo ingenuo de búsqueda de patrones, algoritmo Knuth-Morris-Pratt