Ciencias de la Computación (plan 2013) 2018-1

Optativas, Seminario de Ciencias de la Computación A

Seminario de Ciencias de la Computación A
Algoritmos basado en álgebra lineal.

Presentación

El álgebra lineal es una herramienta potentísima para la computación, tanto para el modelado y análisis teórico, como para la implementación de sistemas.
Este curso se enfoca en un subconjunto útil y representativo de conceptos y técnicas de álgebra lineal relevantes a algoritmos con diversas áreas de aplicación.
Incluyendo el análisis de sistemas dinámicos discretos, motores de búsqueda de internet, análisis y procesamiento de imágenes, cifrado, búsqueda de clips en archivos de audio, graficación, aprendizaje automatizado, estadística y teoría de gráficas y combinatoria.
El enfoque es práctico, complementando la teoría con prácticas de laboratorio en python para procesar y análizar datos mayormente del mundo real.

Se espera que el alumno haya cursado, aprobado y entendido el material de álgebrá superior 1 y 2, álgebra lineal 1 y análisis de algoritmos.
En este curso no se desarrollará la teoría de álgebra lineal. El alumno ya debe haberla adquirido y dominado.
Lo que haremos será aplicar de forma no trivial esa teoría para resolver problemas inspirados en el mundo real.
No se presupone experiencia anterior en los dominios de aplicación específico.

Este curso está basado en el curso "Coding the Matrix" de la Universidad de Brown.
El libro de texto será principalmente el de ese curso, con el mismo nombre, y escrito por Phillip N. Klein.

Temario

Introducción
Algoritmos basados en cambios de base
Algoritmos basados en el producto interno
Algoritmos basados en ortogonalización
Bases especiales
Algoritmos basados en descomposición en valores singulares
Algoritmos basados en vectores propios
Programación lineal

Introducción
Vectores como matrices.
Matrices como vectores.
Estructuras de datos para representar vectores y matrices abstractas.
Bibliotecas de álgebra lineal. Python.

Algoritmos basados en cambios de base
Compresión de imágenes
Bósques generadores mínimos
Corrección automática de perspectiva en imágenes

Algoritmos basados en el producto interno:
Introducción a aprendizaje automatizado
Los datos
Aprendizaje supervisado
Clase de hipótesis
Selección del clasificador que minimiza el error en el conjunto de entrenamiento
Optimización no-lineal con ascenso de colina
Gradiente

Algoritmos basados en ortogonalización
Proyección ortogonal a múltiples vectores
Proyección ortogonal a múltiples vectores ortogonales
Punto más cercano a la cubierta de vectores múltiples
Factorización QR
Mínimos cuadrados
Regresión lineal
Regresión cuadrática
Regresión cuadrática en dos variables
Aplicación de mínimos cuadrados a aprendizaje automático

Bases especiales
Vector k-ralo más cercano
Vector más cercano cuya representación respecto a una base es k-rala
Wavelets
Evaluación e interpolación de polinomios
Transformada de Fourier
Transformada de Fourier Discreta
Matrices circulantes
Aplicaciones de wavelets a compresión

Algoritmos basados en descomposición en valores singulares
Aproximación de una matriz por medio de otra de rango menor
El problema de la línea de trolebús
Espacio vectorial de dimensión k más cercano
Cuadrádos mínimos con SVD
Análisis de componentes principales

Algoritmos basados en vectores propios
Procesos dinámicos discretos
Representación de coordenadas en términos de valores propios
Propagación de virus y gusanos
Método de potencia
Cadenas de Markov
El algoritmo PageRank de Google

Programación lineal
El problema de la dieta
Dualidad
Método Simplex
Teoría de juegos
Juegos de suma no cero
Compresión en el uso de sensores