Algoritmos y Estructuras de Datos I
De Cuba-Wiki
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 y Métodos Numéricos.
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:
- 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
Prácticas
- Prácticas 1-9 de 2020 resueltas
- Práctica 1: Lógica Proposicional y Tipos Básicos
- Práctica 2: Secuencias
- Práctica 3: Cuantificadores
- Práctica 4: Especificación de Problemas
- Práctica 5: Tipos
- Práctica 6: Funcional Básica
- Práctica 7: Listas
- Práctica 8: Tipos compuestos
Parciales
Primeros parciales (Especificación)
- Parciales de especificacion
- Parcial del 17/04/2013
- Recuperatorio del 28/06/2013
- Parcial del 13/09/2013
- Recuperatorio del 27/11/2013
- Parcial del 24/04/2015
- Parcial del 24/04/2015 (Resuelto)
- Parcial del 18/09/2015
- Parcial del 25/04/2016 (Resuelto)
- Parcial del 14/09/2016 (Resuelto)
- Parcial del 12/05/2017 (Resuelto)
- Recuperatorio del 7/07/2017 (enunciado)
- Parcial del 6/10/2017 (enunciado)
- Parcial del 17/10/2018 (Resuelto)
- Parcial del 10/05/2019 (Resuelto)
- Parcial del 21/10/2020 (Enunciado)
- Recuperatorio del 27/11/2020 (Enunciado)
Segundos parciales (Imperativo)
- Parcial del 07/07/2006
- Parcial del 30/11/2005
- Parcial del 11/07/2005
- Recuperatorio del 19/07/2006
- Recuperatorio del 16/12/2005
- Recuperatorio del 23/07/2005
- Parcial del 24/06/2013
- Parcial del 18/11/2013
- Parcial del 26/06/2015 (Resuelto)
- Parcial del 20/11/2015
- Parcial del 27/06/2016 (Resuelto)
- Parcial del 18/11/2016 (Resuelto)
- Parcial del 30/06/2017 (Resuelto)
- Recuperatorio del 14/07/2017 (enunciado)
- Parcial del 24/11/2017 (enunciado)
- Parcial del 22/06/2018
- Parcial del 24-06-2019 - Primer cuatrimestre (Resuelto)
- Parcial del 15-11-2019 (Resuelto)
- Parcial del 19-11-2020 (Enunciado)
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
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
