Diferencia entre revisiones de «Introducción a la Programación»

De Cuba-Wiki
Línea 8: Línea 8:


== Contenidos ==
== Contenidos ==
*Especificación de programas utilizando contratos.
<big>'''Parte I - Corrección de programas imperativos:'''</big>
*Tipos de datos: algebraicos y abstractos.
*Contratos. Obligaciones y derechos del programador y del usuario
*El tipo de datos lista
*Conceptos básicos de los programas imperativos: variables - estructuras de control - funciones - ciclos
*Conceptos básicos de los programas imperativos. Estructuras de control - variables.
*Corrección de programas:
*El tipo de dato arreglo.
# Especificación formal de contratos: tipos de datos básicos, secuencias, n-uplas, operadores de lógica condicionales (cand y cor) y sus propiedades
*Fundamentos de ordenamiento
# Demostración de corrección parcial: precondicicón más débil. Teorema de corrección parcial para ciclos. Invariantes de ciclo.
*Funciones y procedimientos - pasaje de parámetros.
# Demostración de terminación: Función variante
*Ciclos - Construcción, terminación y corrección.
 
<big>'''Parte II - Algoritmos sobre secuencias'''</big>
* 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


==Prácticas==
==Prácticas==

Revisión del 01:26 17 jul 2020

Algoritmos I es la primera materia propia de la carrera. Según el Plan de la Carrera es una materia a ser cursada en Primer año. Es correlativa con Álgebra I y necesaria para cursar Algoritmos y Estructuras de Datos II.

Información General sobre la Cursada

Algoritmos I consiste de clases teóricas y prácticas. Para aprobar la materia se deben rendir 2 exámenes parciales (especificación e imperativo) y 2 trabajos prácticos.

La materia se cursa los Lunes, Miércoles y Viernes de 17 a 22hs.

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:
  1. Especificación formal de contratos: tipos de datos básicos, secuencias, n-uplas, operadores de lógica condicionales (cand y cor) y sus propiedades
  2. Demostración de corrección parcial: precondicicón más débil. Teorema de corrección parcial para ciclos. Invariantes de ciclo.
  3. 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

Prácticas

Parciales

Primeros parciales (Especificación)

Segundos parciales (Imperativo)

Parciales de Funcional

Apuntes

Enlaces Externos