CI-0113 - Programación II: 2024a

Filosofía de la computación, matemática, ciencia e ingeniería

Ejercicios vs problemas

Métodos de resolución de problemas: prueba y error, descomposición, analogía

Proceso de resolución de problemas: análisis, diseño, implementación, pruebas

Recursos de la máquina: procesamiento, almacenamiento, y comunicación

Paradigmas de programación

Abrir una sección de ejercicios en el juez en línea

Tutorial de uso de la interfaz del juez en línea HackerRank

Funciones (subrutinas) libres en C. Comentarios TODO

Biblioteca estándar de C. Leer un carácter con scanf()

Archivos. Entrada estándar. Cursores

Concepto de archivo. Final de archivo (EOF, end-of-file)

Valor de retorno de scanf(). Chequeo de errores en C

Inicializar todas las variables.

Leer varios valores con scanf(). Imprimir en el erro estándar

Fase de análisis: comprender el problema

Diseño procedimental: algoritmos. Diagramas de flujo. Pseudocódigo

Los ocho tipos de instrucciones procedimentales

Algoritmo para el índice de masa corporal. Abstracción. Prueba de corrección y completitud

Descomposición en subtareas. Subrutinas con múltiples puntos de retorno

Prueba del algoritmo: rastreo de procesamiento, memoria, y comunicación

Convertir pseudocódigo en comentarios. Expresiones regulares

Implementación del algoritmo en C. Reglas de estilo. Preferir constantes a variables.

Errores de implementación y de diseño

Completar la implementación del algoritmo en C (para el grupo 04)

Probar el algoritmo/código mediante rastreo

Aridad, precedencia, y asociatividad de los operadores

Corregir error de análisis y diseño en el algoritmo

Corregir el error en código. Variables lo más locales posibles

Preparar archivos para el ambiente local: código fuente

Compilar en línea de comandos. Ejecución interactiva

Redirigir la entrada, salida, y error estándar

Comparar la salida del programa con la esperada usando icdiff

Campos en la salida con formato (printf)

Makefile. Sintaxis. Regla para compilar

Makefile: Reglas para pruebas de software y limpieza

Un Makefile genérico para proyectos en C/C++

Makefile genérico: instalar dependencias. Linter de C/C++ (reglas de estilo)

Análisis del problema de combinaciones y permutaciones

Algoritmo solución en pseudocódigo

Implementación de la solución en C

Ejecución de la solución

Desbordamiento en complemento a dos. Renombrar tipos (typedef). Concatenación de literales

Aritmética de precisión arbitraria (ej.: GMP). Optimización

Optimización para calcular permutaciones sin reemplazo

Optimizaciones para las combinaciones. Error de precisión flotante con potencias enteras

Corregir entrada en cero como un remiendo (mala práctica)

Motivación: necesidad de bibliotecas

Optimización de las permutaciones y combinaciones, remiendo de la entrada en cero (para grupo 04)

Ejemplos de uso de bibliotecas (OpenSSL)

Modularización de código fuente en archivos

Archivos fuente (.c) y encabezado (.h)

Arquitectura del compilador. El preprocesador de C

El compilador de C. El enlazador (linker)

Unidades de traducción. Enlazado de múltiples archivos fuente

Evitar la múltiple inclusión

Reutilizar código compartido entre encabezados

Compilar todos los fuentes en un solo comando (no recomendable)

Bibliotecas estáticas vs dinámicas

Crear una biblioteca dinámica de código

Crear un ejecutable que usa la biblioteca dinámica

Análisis del problema del rango

Cargado del programa. Segmentos de memoria. Segmento de código (texto)

Segmento de datos. Variables globales y estáticas

Segmento de heap (memoria dinámica). Hilo de ejecución

Invocación de subrutinas. Parámetros vs argumentos

Llamado por copia (copia de los argumentos)

Variables vs punteros. Metáfora de puntero

"Desreferenciar" un puntero (obtener el valor apuntado)

Corregir con punteros la implementación del problema del rango

Rastreo de memoria de la implementación con punteros

Enteros sin signo del tamaño de la arquitectura (size_t). Arreglos de tamaño fijo de alojamiento automático

Arreglos de alojamiento estático. Argumentos de línea de comando. Arreglos de longitud variable

Vulnerabilidad por desborde de pila

Arreglo de alojamiento dinámico (en segmento de heap)

Análisis del problema de la mediana

Diseño de la solución en pseudocódigo

Tipo de datos size_t. Programación defensiva

Manejo de errores en C. Constantes en C. Enumeraciones

Error: retornar dirección de una variable

Tipos de asignación de memoria: código, estática, automática, y dinámica. Inicialización de arreglos

Pasar arreglos por parámetro

C pasa y retorna los arreglos como punteros, nunca por copia. size_of de un arreglo.

Indexación de arreglos a través de punteros

Aritmética de punteros.

Desreferenciar con aritmética de punteros. Cambiarle la dirección al puntero

Ordenar un arreglo. Punteros void*. Punteros a funciones (subrutinas)

Terminar la implementación de la mediana y ejecución de la solución

Datos apuntados constantes (sólo lectura). Direcciones constantes

Preguntas: Matrices. Arreglos terminados en nulo. Concuso de código ofuscado en C

Repaso: solución al problema de la mediana

Google Sanitizers. Instrumentalización de código. Address Sanitizer.

Vulnerabilidad por desbordamiento de pila (stack overflow)

Alojamiento dinámico de memoria. malloc().

Reaccionar al fallo de alojamiento dinámico. Dirección cero o nula (NULL)

Concepto de fuga de memoria

Corregir la fuga de memoria. Subrutina free().

Matrices de tamaño constante

Crear una matriz en memoria dinámica (heap). calloc()

Destruir/liberar una matriz de la memoria dinámica

Subrutinas genéricas para crear y destruir matrices con void**

Propósito de la documentación. Ejemplo: documentación de Qt

Documentación de Doxygen: cómo documentar y cómo configurarlo

Generar un archivo de configuration de proyecto (Doxyfile)

Configurar Doxygen. Exportar/generar documentación

Página principal de la documentación. Referencias a otros archivos y símbolos

Qué agregar de Doxygen a control de cambios

Comandos para compilar la biblioteca y el programa en un shell script

Sintaxis de un Makefile: reglas, dependencias (prerrequisitos), comandos

Cómo make corre un makefile

Regla clean. Reglas .PHONY

Reglas reusables. Variables automáticas de make

Variables automáticas en todas las reglas

Evitar la múltiple creación del mismo directorio con requisitos de orden

Declarar y usar variables

Vistazo del Makefile genérico provisto

Ayuda del Makefile provisto. Linting (make lint)

Problema de la mediana sin conocer la cantidad de datos

Concepto de registro de memoria. Declaración de tipos de registros en C (structs)

Tamaño en bytes de un registro. Alineamiento de palabra (world alignment). Relleno (padding)

Los registros son valores, no direcciones. Subrutinas que modifican registros

Acceso a los campos de un registro (operador .). Violación de encapsulación

Interfaz del arreglo dinámico para resolver el problema de la mediana. Acceso a los campos de un registro a través de un puntero (operador ->)

Implementación del arreglo dinámico (inicio). Supuestos (assert)

Inicialización del arreglo dinámico. Rastreo de memoria

Agregar un elemento al arreglo dinámico: versión con error por desborde

Encontrar error con análisis dinámico de código: Address Sanitizer

Incrementar la capacidad del arreglo

Implementación del incremento de capacitdy

Detectar fuga de memoria con MemCheck de Valgrind

Implementación de array_uninit() y corregir la fuga de memoria

Preguntas. Reusar arreglos dinámicos en C

Mediana v4: recibe nombres de archivo como argumentos de línea de comandos

Argumentos de línea de comandos

Manejo de archivos en C. fopen(). fclose()

Estructura interna de un registro FILE. Tabla de descriptores de archivos

Calcular la mediana de archivos nombrados

Reutilizar el código para calcular la mediana desde la entrada estándar

Los archivos de texto son archivos binarios limitados

Herramienta conversión de archivos de texto a binarios. Modo de apertura binaria

Implementación de txt2bin. Warning de variables no utilizadas

Concepto de cadenas de caracteres terminadas en nulo

Implementación de la concatenación de cadenas. sprintf()

Linter. snprintf() (grabado con el Gr02)

Longitud de cadena. La capacidad de una cadena es su longitud más 1

Invocación ineficiente de strlen() en la condición de un ciclo

Calcular la longitud de caden usando aritmética de punteros. La biblioteca estándar de cadenas de C

Escribir datos binarios a un archivo: fwrite()

Análisis de argumentos. Comparar cadenas de caracteres: strcmp(). Leer datos binarios: fread

Repaso del convertidor de archivos de texto a binario

Interfaz del analizador de argumentos para archivos binarios

Interfaz del analizador de argumentos. Inicialización. Destrucción

Implementación del análisis de argumentos. Leer de archivos binarios

Importancia de los warnings del compilador. Error de comparar cadenas literales

Función para comparar cadenas de caracteres usando indexación

Detectar argumentos inválidos. Biblioteca estándar de cadenas de C

Reseña histórica de Unix, C, C++ y otros lenguajes

El paradigma de programación genérica

C++ es un (casi) superconjunto de C. Compilar código C con el compilador de C++

Encabezados de la biblioteca estándar de C para C++. Los flujos (streams) son archivos genéricos

Espacios de nombres (namespaces). Operador de resolución de alcance (::)

Imprimir en la salida estándar (std::cout) y error estándar (std::cerr)

Mala práctica: using namespace

Sobrecarga de subrutinas. Name mangling

Repaso: E/S de C++, espacios de nombres, sobrecarga de subrutinas

Repaso: Manejo de archivos en mediana v5 está hecho con E/S de C

Entrada estándar en C++ (std::cin, console in). Operadores de flujo

Leer hasta encontrar el fin de archivo con std::cin

Leer de archivos nombrados con flujos en C++: ifstream

Conversión de tipos en C++: const_cast, static_cast, dynamic_cast, reinterpret_cast

Mecanismo que permite sobrecarga de subrutinas: name mangling. Identificadores que inician con guión bajo

El paradigma de programación genérica. Pasar tipo de datos como parámetro. Plantillas

Corregir el warning de parámetros no usados en C++. Significado de subrutinas sin parámetros

Las plantillas que no son usadas, son descartadas por el compilador

Cómo las plantillas son expandidas

Qué pasa si se definen subrutinas con el mismo identificador que una plantilla

Inferencia del tipo de datos a partir de los argumentos. Pasar el tipo de datos como un argumento

Mecanismo de matching de subrutinas. Abrumante reporte de errores de plantillas

Tipos de datos genéricos y referencias

Repaso: biblioteca de combinatoria. Pruebas de caja negra

Modificaciones al Makefile para compilar el programa de pruebas de caja blanca

Programa casero de pruebas de caja blanca

Macros del preprocesador para evitar la redundancia de código de prueba

Repaso de plantillas

Referencias de memoria en C++ (alias)

Experimentos y ejemplos con referencias

Variables, copias, punteros, y referencias

Plantillas de registros. Arreglo dinámico genérico

Por qué el linker no encuentra las definiciones de subrutinas de plantillas

Plantillas en el archivo de encabezado

Ejemplos de instanciar la plantilla de arreglo dinámico

Un registro genérico para representar fracciones

Argumentos por defecto

Programa para sumar fracciones. Subrutina para imprmir una fracción

Cómo encadenar invocaciones de impresión

Notación de la sobrecarga de operadores

Reglas de sobrecarga de operadores

Sobrecarga del operador de entrada de flujo

Sobrecarga del operador de suma binaria. Suma de fracciones

Repaso de sobrcarga de operadores: Fracciones

Algoritmo de Euclides para obtener el máximo común divisor. Bibliotecas de aritmética de precisión arbitraria

Simplificar la fracción. Direcciones de referencias

Normalizar negativos en la fracción. Diferencia entre módulo y residuo

Sugerencias de ejercicios con la Fracción

El paradigma de programación orientado a objetos. UML. Modularización. Herencia de registros. Polimorfismo de subrutinas

Diseño orientado a objetos. UML. Clase. Miembros. Encapsulación

Diferencia entre struct y class en C++. Especificadores de acceso (private, public)

Convención de estilo de Google. cpplint. Historia de "linting"

Concepto de método. Puntero oculto this. Acceso a miembros con el operador punto (.)

Métodos estáticos (sin puntero this). Los registros son espacios de nombres

Repaso del ejemplo de fracciones y programación orientada a objetos

Deshabilitar las plantillas temporalmente (No se hizo en grupo 02)

Especificadores de acceso para: variables locales, miembros, y globales. Notación húngara

Método constructor

Diferencia entre asignación e inicialización. Correcta inicialización de atributos en constructores

Violación de encapsulación. Atributos privados (buena práctica)

Cuándo implementar métodos get y set

Implementar un méodo get. Métodos constantes

Retornar referencias en lugar de copias

Subrutinas en línea (inline)

Manejo de excepciones: try/catch

Subrutinas amigas al registro

Sobrecarga de operadores con métodos (subrutinas miembro). static vs friend

Sobrecarga de los operadores de flujo. Funciones amigas en línea (friend inline)

Proyecto 02: grafo genérico

Mediana v6 con objetos genéricos. Interfaz pública del objeto arreglo dinámico

Diferencia entre los operadores new, new[], y malloc()

Constructor por defecto del arreglo dinámico

Diferencia entre los operadores delete y delete[]. Recolección de basura

Agregar la aplicación de la mediana v6 al Makefile

Atrapar excepciones

Agregar elementos al arreglo. Incrementar la capacidad del arreglo. Elementos en el arreglo son copias de los originales.

Imprimir los elementos del arreglo

Repaso de construcción y destrucción del arreglo dinámico

Método append() para agregar elementos al arreglo

Incrementar la capacidad del arreglo

Imprimir los elementos del arreglo. Obtener la cantidad de elementos del arreglo. Subrutinas en línea (inline)

Operador corchetes (arr[index]): versión mutable e inmutable

Rastreo de memoria del constructor de copia por defecto

Sobrescribir el constructor de copia para evitar que arreglos compartan elementos

Sobrescribir el operador de asignación de copia para evitar fuga de memoria y que arreglos compartan elementos (completa regla de los 3)

Implementación del constructor de traslado

Implementación del operador de asignación de traslado (completa regla de los 5)

Convertir la clase Array en una plantilla para generar clases de arreglos dinámicos

Expandir una plantilla para generar registros

Plantillas de subrutinas: el compilador puede inferir los parámetros de la plantilla

Parámetros de plantillas que no son tipos de datos

std::vector: arreglo dinámico de la biblioteca estándar de C++. Construir matrices con std::vector

Comparación entre arreglos y listas

pragma once. Estructura de datos lista. Decidir entre clase o struct para los nodos

Declaración del nodo de la lista. Campos puntero hacia el registro mismo. Diferencias entre Java y C++

Declaraciones anidadas de registros. El nodo declarado dentro de la clase lista

Atributos de la lista: first/head y last/tail

Constructor por defecto de lista. Agregar a la lista vacía

Métodos de acceso: isEmpty(), operator!(), getCount(). Constructor por defecto de Node

Aplicación para usar la list: extractor de palabras. Actualizar el Makefile

Imprimir la lista. Recorrido usando un puntero

Agregar a una lista no vacía. Constructor por defecto de Node completo

Ejemplo de ejecución de la lista

Explicación del recorrido usando un puntero

Preguntas: diseño UML de plantillas, destrucción de objetos cuando ocurre excepciones (RAII)

Árboles: acceso en tiempo logarítmico

Nodos de las listas, árboles, y grafos. Árboles binarios, ternarios, n-arios.

Arreglo asociativo (mapa o diccionario)

Declaración de la plantilla Map<key, value>

Declaración del nodo. Invariante de orden

Constructor por defecto de Map::Node

Atributos del mapa. Constructor por defecto

Declaración del método insert(). El orden de inserción es controlado por el árbol

Inserción en un árbol vacío

Inserción de un elemento hijo de la raíz

Inserción usando ciclos en lugar de recursión

Permitir duplicados dentro del árbol? Conjunto vs bolsa (map vs multimap)

Reutilizar el código para crear el nodo

Operador [] para obtener el valor asociado e insertar en el mapa

Versión pública y privada del método insert()

Imprimir los elementos del árbol. Recorrido de árboles: pre-orden, en-orden, post-orden

Destructores recursivos

Pruebas unitarias (caja blanca) con Catch2

Repaso del arreglo asociativo construido con árbol binario de búsqueda

Eliminación del código de impresión (operator<<)

Código que usa iteradores para imprimir en main()

Implementación de begin() y end()

Comparación de iteradores. Acceso a la llave y valor a través del iterador.

Encontrar el nodo mínimo de un subárbol

Encontrar el nodo siguiente sin utilizar pilas: código

Encontrar el nodo siguiente sin utilizar pilas: explicación

Macros para deshabilitar la copia de registros (objetos)

Functor (objetos que se comportan como funciones): la primitiva que permite implementar programación funcional en C++

Pasar un parámetro a la plantilla para cambiar el orden de almacenamiento de los elementos en el árbol

Sesión de preguntas sobre el segundo proyecto

Corregido error de establecer el nodo padre al insertar uno nuevo en el árbol

Cuándo usar arreglos normales y cuándo arreglos asociativos

Imprimir las palabras más usadas en la entrada estándar

Problema de imprimir la tabla de notas

Cargar los valores en el arreglo asociativo

Recorrer (iterar por) arreglos asociativos: imprimir la tabla de notas

Palabra reservada auto para tipos de datos inferibles. Ciclo por colección (foreach)

Problema del juego Trivia

UML. Análisis orientado a objeto. Casos de uso (guiones de teatro). Diagrama de casos de uso

Ideas sobre análisis de requerimientos

Diseño orientado a objetos. Identificación de objetos candidatos (sustantivos)

Diagrama de clases. Diagramas de interacción: diagrama de secuencia

Relación de composición vs agregación. Mutiplicidad de la asociación. Generación de código e ingeniería inversaa

Patrón de diseño modelo-vista-controlador (MVC)

El controlador general de la aplicación. La función main() orientada a objetos: instanciar el controlador general y delegarle el control

Archivos fuente con mayúsculas para clases, minúsculas sin clases. Deshabilitar copias de objetos