Cursos destinados a estudiantes y profesionales de carreras informáticas y afines
Track A: Algoritmos, complejidad y matemática discreta
M1: Advanced Data Structures
9:00 a 12:00 hs
Conrado Martínez
Dept. Computer Science, Univ. Politècnica de Catalunya
Efficient strategies and techniques for structured data are key in modern computer science to design fast algorithms useful in a variety of every day applications (like web archiving, mail servers, network routers and video games). This course explores selected topics on advanced data structures including multidimensional and metric data structures, self-adjusting and probabilistic and randomized data structures. The course covers, for each topic, the fundamental concepts, major results and techniques of analysis.
Idioma: Español, con material en inglés.
Requisitos: Conocimientos elementales de teoría de la probabilidad. Conocimiento de estructuras de datos.
T1: Aspectos algorítmicos de clases de grafos cerradas por menores
13:30 a 16:30 hs
Ignasi Sau
LIRMM, Université de Montpellier, CNRS
Un grafo H es menor de un grafo G si H puede obtenerse de un subgrafo de G contrayendo aristas. La teoría de Grafos Menores desarrollada por Robertson y Seymour en una serie de más de 20 artículos (1983-2012) es uno de los resultados modernos más impresionantes en Teoría de Grafos y Combinatoria. El objetivo de esta teoría era probar la conjetura de Wagner (afirmando que no hay una anticadena infinita con respecto a la relación menor del gráfico), pero como subproducto de la prueba, también surgieron varias aplicaciones algorítmicas. En este curso nos centraremos en los aspectos algorítmicos de la teoría de grafos menores, con especial énfasis en la noción crucial de ancho de árbol. Para describir algunas de estas aplicaciones algorítmicas, utilizaremos el marco moderno de Complejidad Parametrizada desarrollado en los años 90 por Downey y Fellows, y que se ha consolidado como una de las áreas más activas de la Teoría de Grafos Algorítmicos. En pocas palabras, el principal objetivo de la Complejidad Parametrizada es analizar la complejidad de los problemas de optimización de una forma más refinada que la clásica dicotomía “P vs NP”. Para ello, se mide la complejidad de un algoritmo no sólo en términos de su tamaño de entrada, sino también en función de un parámetro adicional que puede capturar la dificultad inherente del problema considerado.
Idioma: Español, con material en inglés
Requisitos: Conocimiento de teoría de grafos, algoritmos sobre grafos, y complejidad computacional.
N1: Positional games
18:00 a 21:00 hs
Miloš Stojaković
University of Novi Sad
The Theory of Positional Games is a fairly independent branch of Combinatorial Game Theory,
nested between Theoretical Computer Science and Mathematics, with numerous applications in both fields. It deals with a class of two-player perfect-information games, ranging from popular games such as Tic-Tac-Toe and Hex to some purely abstract games played on graphs and networks. Though a close relative of the classical Game Theory of von Neumann and the Nim-like Game Theory popularized by Conway, positional games still preserve a unique flavor.
Idioma: Inglés
Requisitos: Conocimientos básicos de combinatoria y teoría de grafos.
Track B: Semántica de lenguajes, teoría de tipos y lógica
M2: Linear logic: syntax, models, and extensions
9:00 a 12:00 hs
Pierre-Louis Curien
CNRS
Linear logic arose from an analysis of models of the typed lambda-calculus, where function
spaces (corresponding to logical implication) decompose naturally into a modality called “of course” and another implication called linear implication. These two connectives are echoing the difference between terms and linear terms, which are terms in which each variable occurs exactly once. As for the modality, it expresses the ability for a function to use its argument more than once during the computation. This seminal observation led to a ressource-avare logic, combining the beautiful dualities of classical logic with the constructive features of intuitionistic logic. I will cover the syntactic aspects: sequent calculus, proof nets, cut-elimination. I shall introduce enough category theory to explain the models of linear logic. Much in the same way as linear logic arose from models of the lambda-calculus, Thomas Ehrhard found inspiration from models of linear logic to develop differential lambda-calculus and differential linear logic, establishing striking links between differentiation in the sense of mathematical analysis and the fine analysis of substitution in the syntax. Explaining Ehrhard’s ideas will occupy the second part of the lecture series.
Idioma: Inglés.
Requisitos: Conocimiento general de lenguajes de programación.
T2: On Randomization in (Higher-order) programming
13:30 a 16:30 hs
Ugo Dal Lago
Università di Bologna and INRIA Sophia Antipolis
The possibility that the execution of an algorithm may not give rise to a deterministic but rather to a stochastic process has been contemplated since the dawn of theoretical computer science. This idea has had a huge impact on many areas of the theory and practice of computing, e.g., computational complexity and cryptography. But what happens to programs and to their semantics when the former are allowed to evolve probabilistically? The purpose of this course is to introduce students to the challenges the presence of randomisation poses to the design and study of programming languages. After briefly introducing randomisation from a computational viewpoint, we will see how this feature impacts the semantics of programming languages and the task of verifying programs for correctness. We will proceed highlighting when, why, and to which extent the underlying theory diverges from the classic one. While aware of the impossibility of being exhaustive, we will try to provide pointers to the literature whenever it is not possible to go into detail. We will concentrate our attention to functional programming languages as idioms and to type-theoretical verification tools.
Idioma: Inglés
Requisitos: Estudiantes avanzados o graduados de computación o matemáticas.
N2: Behavioural types for mainstream programming languages
18:00 a 21:00 hs
António Ravara
Universidade NOVA de Lisboa | FCT — NOVA LINCS
Modern programming languages like Kotlin or Rust have advanced features to statically ensure data and memory safety, like nullable and ownership types. Other languages like C, Erlang, Go, Haskell, Java, or Scala, have static analysis tools to help the developer detect at compile-time possible safety violations that might lead to run-time errors. Most of these, however, force the developer to adopt a defensive programming style, trying to cover all possible scenarios where things might go wrong. Nevertheless, bad things still happen, being a testimony of this the Jedis bug uncovered after 9 years in Jan 2018 (issue closed 14 months later), or the MonoX Finance smart contract vulnerability exploited in December 2021. Since many applications implement protocols, as not all functionalities are available all the time (e.g., one can only pop from a non-empty stack; write in a not full buffer), behavioural types are a natural way to model and validate code enforcing that only the correct sequences of actions are allowed to happen. Static type systems ensure protocol compliance and, in some conditions, completion. Tools to use them with functional, imperative, or O.-O. mainstream languages are available, but still not widely adopted.
Idioma: Inglés
Requisitos: Familiaridad con lenguajes de programación. Idealmente, conocimiento de C, y algún lenguaje al estilo Java.
Track C: Inteligencia artificial, ciencia de datos, e ingeniería del software
M3: Combinando enfoques complementarios en inteligencia artificial para mejorar las tareas de predicción
9:00 a 12:00 hs
Maria-Cristina Marinescu
Research Staff Member at Barcelona Supercomputing Center / Associated Lecturer at Universitat Politecnica de Catalunya
Este curso va más allá de los conceptos básicos de ML estadístico para analizar el aprendizaje de big data a través de Deep Learning aplicado a imágenes y texto, pero también analiza enfoques complementarios que pueden ayudar con las tareas de predicción cuando los datos son insuficientes. Estos enfoques se basan en modelos que representan el conocimiento común y pueden generarse de arriba hacia abajo (por ejemplo, modelos semánticos) o de abajo hacia arriba (por ejemplo, modelos de lenguaje, gráficos de conocimiento).
El curso comienza con la explicación del tradeoff entre sesgo/precisión y la selección de modelo/característica, después de lo cual repasa rápidamente algunos métodos básicos de aprendizaje supervisado y no supervisado, incluido el aprendizaje en línea. El siguiente bloque analiza los grafos de conocimiento, las diferentes formas de construirlos y presenta algunas tareas de razonamiento que los hacen útiles en una variedad de aplicaciones de IA para guiar los resultados, sugerir relaciones o refinar el conocimiento existente. El último bloque introduce el aprendizaje profundo, especialmente dirigido a la visión artificial y las tareas de procesamiento del lenguaje natural. El curso concluye con ejemplos de cómo usar conjuntamente estas tecnologías, junto con la IA simbólica de arriba hacia abajo, para mejorar la predicción cuando los datos no son suficientes o los problemas involucran cuestiones de sentido común y causalidad que la inducción de abajo hacia arriba no está preparada para manejar directamente. Algunos de estos ejemplos reflejan problemas prácticos a los que nos enfrentamos en un proyecto europeo sobre patrimonio cultural (San Jorge en bicicleta) que está finalizando dentro de unos meses.
Idioma: Español
Requisitos: Programación en Python. Conocimiento de estadística.
T3: Fuzzing para Testing de Compiladores
13:30 a 16:30 hs
Guillermo Polito
CNRS, INRIA
El testing de compiladores es hoy en día un área crítica para el desarrollo de software profesional, dada la complejidad y constante evolución de los lenguajes de programación. El testing automático debe validar la interrelación entre nuevos lenguajes, nuevas representaciones intermedias de código, nuevas fases de optimización y transformación. Dentro del área de testing automatizado de compiladores, las técnicas de fuzzing proponen la creación automática de forma más o menos aleatoria, de valores de input para testear un programa.
Este curso presenta técnicas maduras de testing automático de compiladores. El curso se basa en tres ejes. En una primera parte, el curso presenta buenas prácticas de testing automatizado, aplicables no solo a compiladores. En una segunda parte, el curso estudia técnicas para generar automáticamente inputs para compiladores, y cómo guiarlos para testear distintas partes de un compilador. En tercer lugar, el curso presenta el problema del oráculo de testing y cómo este problema se instancia en el caso de los compiladores. En cada uno de esos ejes se estudian técnicas del estado del arte, acompañados de casos de estudio y artículos de investigación que ilustran los distintos casos.
El curso es teórico y práctico. La práctica tiene como objetivo la implementación de fuzzers automáticos y ponerlos en práctica para testear lenguajes de programación.
Idioma: Español
Requisitos: La parte teórica de este curso requiere conocimientos medios de programación. Es deseable, pero no bloqueante, conocimiento de sintaxis y gramática de los lenguajes de programación. La parte práctica de este curso requiere experiencia en programación. Es deseable el conocimiento de lenguajes de alto nivel como Python o Smalltalk (e.g., Pharo).
N3: Reconstrucción 3D de humanos a partir de imágenes
18:00 a 21:00 hs
Victoria Fernández Abrevaya
Max Planck Institute for Intelligent Systems
La estimación de la forma tridimensional de humanos a partir de imágenes o video es una tarea central para muchas aplicaciones, cubriendo áreas tales como AR/VR, telepresencia y entretenimiento, por nombrar algunas. Se trata de un desafío importante, ya que la recuperación de información 3D a partir de sensores 2D es esencialmente un problema ambiguo y mal condicionado. En el caso de humanos, la solución tradicional consiste en construir modelos estadísticos usando bases de datos de scans 3D (por ejemplo, de cuerpos o rostros), los cuales se ajustan luego a datos de la imágen tales como el color del pixel, puntos clave, siluetas, etc. Recientemente, los algoritmos de ajuste basados en optimización han sido reemplazados por métodos de regresión que aprovechan técnicas modernas de aprendizaje profundo, entrenando redes neuronales de forma supervisada o autosupervisada, mejorando de esta manera la performance ante situaciones difíciles así como el tiempo computacional requerido. Este curso ofrecerá una introducción y una visión general de las técnicas clásicas y actuales para la estimación de la estructura 3D de humanos a partir de imágenes o video, con especial atención a métodos que tratan específicamente el cuerpo y el rostro.
Idioma: Español
Requisitos: Conocimientos básicos de machine learning y redes neuronales (el curso no cubre una introducción a los mismos). Álgebra lineal. Python
