Algoritmos y Estructuras de Datos I

Algoritmos I es la primera materia propia de la carrera. En la primera parte, se introduce el concepto de especificación que define el que y no el cómo de un problema, que ayuda a eliminar la amigüedad de las palabras, usando lógica de primer orden. En la segundo parte, se ve implementación de problemas que consiste en programar programas en C++ que cumplan una especificación dada. 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, Organización del Computador lyMétodos Numéricos.

Información General sobre la Cursada

Algoritmos I consiste de clases teóricas, prácticas y de taller. Para aprobar la materia se deben rendir 2 exámenes parciales (especificación e implementación) y 2 trabajos prácticos. La materia se cursaba antiguamente los Lunes, Miércoles y Viernes de 17 a 22hs. Ahora también puede cursarse a la mañana y a la tarde.

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

• Prácticas 1-9 de 2020 resueltas
• Práctica 1: Lógica Proposicional y Tipos Básicos
  • Solución
• Práctica 2: Secuencias
  • Solución
• Práctica 3: Cuantificadores
  • Solución
• Práctica 4: Especificación de Problemas
  • Solución
• Práctica 5: Tipos
  • Solución
• Práctica 6: Funcional Básica
• Práctica 7: Listas
• Práctica 8: Tipos compuestos

Parciales

Primeros parciales (Especificación)

Año	Cuatrimestre	Fecha	Instancia	Links
2021	Primer Cuatrimestre	28/06/2021	Recuperatorio Online	enunciado (pdf)
2021	Primer Cuatrimestre	19/05/2021	Parcial Online	enunciado (pdf)
2020	Segundo Cuatrimestre	27/11/2020	Recuperatorio Online	enunciado (pdf)
2020	Segundo Cuatrimestre	21/10/2020	Parcial Online	enunciado (pdf)
2019	Primer Cuatrimestre	10/05/2019	Parcial	enunciado + resolución (pdf)
2018	Segundo Cuatrimestre	17/10/2018	Parcial	enunciado + resolución (pdf)
2017	Segundo Cuatrimestre	6/10/2017	Parcial	enunciado (pdf)
2017	Primer Cuatrimestre	12/05/2017	Parcial	enunciado + resolución (pdf)
2016	Segundo Cuatrimestre	14/09/2016	Parcial	enunciado + resolución (pdf)
2016	Primer Cuatrimestre	25/04/2016	Parcial	enunciado + resolución (pdf)
2015	Segundo Cuatrimestre	18/09/2015	Parcial	enunciado (pdf)
2015	Primer Cuatrimestre	24/04/2015	Parcial	enunciado + resolución (pdf)
2015	Primer Cuatrimestre	24/04/2015	Parcial	enunciado (pdf)
2013	Segundo Cuatrimestre	27/11/2013	Recuperatorio	enunciado (pdf)
2013	Segundo Cuatrimestre	13/09/2013	Parcial	enunciado (pdf)
2013	Primer Cuatrimestre	28/06/2013	Recuperatorio	enunciado (pdf)
2013	Primer Cuatrimestre	17/04/2013	Parcial	enunciado (pdf)

Segundos parciales (Imperativo)

Año	Cuatrimestre	Fecha	Instancia	Links
2021	Primer Cuatrimestre	23/06/2021	Parcial Online	enunciado (pdf)
2020	Segundo Cuatrimestre	09/12/2020	Recuperatorio Online	enunciado (pdf)
2020	Segundo Cuatrimestre	19/11/2020	Parcial Online	enunciado (pdf)
2019	Segundo Cuatrimestre	15/11/2019	Parcial	enunciado + resolución (pdf)
2019	Primer Cuatrimestre	24/06/2019	Parcial	enunciado + resolución (pdf)
2018	Segundo Cuatrimestre	23/11/2018	Parcial	enunciado (pdf)
2018	Primer Cuatrimestre	22/06/2018	Parcial	enunciado (pdf)
2017	Primer Cuatrimestre	24/11/2017	Parcial	enunciado (pdf)
2017	Primer Cuatrimestre	14/07/2017	Recuperatorio	enunciado (pdf)
2017	Primer Cuatrimestre	30/06/2017	Parcial	enunciado + resolución (pdf)
2016	Segundo Cuatrimestre	18/11/2016	Parcial	enunciado + resolución (pdf)
2016	Primer Cuatrimestre	27/06/2016	Parcial	enunciado + resolución (pdf)
2015	Segundo Cuatrimestre	20/11/2015	Parcial	enunciado (pdf)
2015	Primer Cuatrimestre	26/06/2015	Parcial	enunciado + resolución (pdf)
2013	Segundo Cuatrimestre	18/11/2013	Parcial	enunciado (pdf)
2013	Primer Cuatrimestre	24/06/2013	Parcial	enunciado (pdf)

Parciales de Funcional

• Parciales de funcional
• Parcial del 20/05/2013
• Recuperatorio del 08/07/2013
• Parcial del 09/10/2013
• Recuperatorio del 04/12/2013

Finales

• Final del 23-04-2019
• Final Online del 16-12-2020

Apuntes

• Apunte de Testing
• Resumen de Clases Teóricas y Practicas - 1C Online 2020
• El Respositorio de Fede: Apuntes de las Clases Teóricas, Ejercicios y Parciales Resueltos y Material Adicional - Segundo Cuatrimestre 2019
• Apuntes del lenguaje de especificación
• Apuntes de funcional: Apuntes y resumenes de programacion en funcional.
• Resumen Teórico (Incompleto)
• Guía de Instalación de CLion IDE C++ con Licencia Estudiantil

Enlaces Externos

• Página oficial de la materia