| Additional title: |
Discrete mathematics seminar |
| Additional title: |
Seminario de matemática discreta |
| Date: |
2023-24 |
| Abstract: |
La matemàtica discreta és l'àrea de les matemàtiques dedicada a l'estudi d'objectes finits. Alguns dels temes dels que s'ocupa són la combinatòria, els grafs, la criptografia, els codis correctors d'errors, els dissenys combinatoris, la teoria de jocs, la lògica, l'optimització i el disseny i anàlisi d'algorismes per resoldre problemes d'aquests àmbits. La major part té un desenvolupament relativament recent motivat per problemes relacionats sobretot amb la informàtica i amb l'optimització. Són temes força independents entre sí i, en un curs introductori, tenen com a únics prerequisits l'àlgebra lineal, l'aritmètica modular, la combinatòria bàsica i, sobretot, el llenguatge i el raonament matemàtics. El curs comença amb funcions generadores i successions recurrents. Es tracta d'una continuació natural de la combinatòria que s'ha fet a l'assignatura de Fonaments de les Matemàtiques de primer curs. En els problemes d'aquest tema es segueix posant en pràctica la capacitat de traduir problemes d'enunciat al llenguatge matemàtic. Els grafs són una eina bàsica per resoldre problemes d'àmbits molt diversos, des de la matemàtica més abstracta fins a la investigació operativa. En alguns casos, gairebé només la traducció al llenguatge dels grafs ja resulta esclaridora i molt eficaç. Només en farem, però, una breu introducció. El tercer tema del curs és l'optimització combinatòria, que s'ocupa de qüestions combinatòries en què no es tracta de comptar objectes d'un determinat tipus sinó de cercar aquells "òptims" d'acord amb algun criteri. Les respostes en aquest cas no seran fórmules sinó algoritmes per trobar o aproximar-se a aquests òptims. Les 1 respostes en aquest cas no seran fórmules sinó algoritmes per trobar o aproximar-se a aquests òptims. Les tècniques necessàries aquí seran l'àlgebra lineal (per optimitzar funcions lineals de vàries variables amb restriccions lineals, però on habitualment els valors de les variables seran discrets) i les matroides. Al llarg del curs, doncs, es presentaran diferents exemples d'aplicacions de les matemàtiques, en què, amb eines relativament senzilles i molt d'enginy, es resolen problemes interessants i difícils. Alhora, els estudiants practicaran amb els exercicis de combinatòria i d'optimització la primera fase de la modelització matemàtica: entendre un problema i traduir-lo a un llenguatge matemàtic adequat per la seva resolució. |
| Abstract: |
Discrete Mathematics is a field of mathematics that studies finite mathematical objects. It covers topics such as combinatorics, graph theory, cryptography, error-correcting codes, combinatorial design theory, game theory, logic, optimization, or algorithm design and analysis that can be applied to solve problems in any of the above-mentioned branches. Most of discrete mathematics has evolved relatively recently, motivated by the challenges mainly in computer science and operations research. The chapters of this introductory course are quite independent from one another. A prior knowledge of linear algebra, modular arithmetic, basic combinatorics, and -fundamentally- mathematical language and reasoning should be adequate to understand the subject matter of each chapter. The first chapter addresses the topic of generating functions and recurrent sequences, this being a natural next step following the elementary combinatorics studied in the first year course Fundamental Mathematics. Once again, problems in combinatorics require training the skill of formulating a problem in terms of a mathematical statement. The second chapter deals with graphs, which are a fundamental tool for problem solving in quite different settings, ranging from the most abstract mathematics up to operations research. In some cases, a graph-theoretical formulation of the problem turns out to be, in itself, illuminating and a highly efficient step towards the solution. The last chapter deals with the topic combinatorial optimisation, which deals with combinatoric questions in which, rather than counting objects of a particular type, one is interested in finding "the optimal" ones with respect to some criterion. The answers in this case won't be given by formulas but by algorithms to find or 1 respect to some criterion. The answers in this case won't be given by formulas but by algorithms to find or approach such optimal objects. The theory used involves basic linear algebra techniques (for linear programming) and matroids. In summary, throughout this course in discrete mathematics, a variety of examples and applications will be explained, where by means of relatively simple tools and a clever approach, we get to solve interesting and difficult problems. Moreover, by their work on problem sets, students will be able to practice the first step in the process of mathematical modeling, namely, understanding a problem and finding a suitable mathematical formulation that leads to the solution. |
| Abstract: |
La matemática discreta es el área de las matemáticas dedicada al estudio de objetos finitos. Se ocupa de temas como combinatoria, grafos, criptografía, códigos correctores de errores, diseños combinatorios, teoria de juegos, lógica, optimización o diseño y análisis de algoritmos para resolver problemas en cada uno de aquellos ámbitos. La mayor parte de la matemática discreta se ha desarrollado hace relativamente poco tiempo a raíz de problemas relacionados sobretodo con la informática y la optimización. Los temas de este curso introductorio son bastante independientes entre sí y requieren solamente conocimientos de álgebra lineal, aritmética modular, combinatoria básica y, fundamentalmente, lenguaje y razonamiento matemáticos. El curso empieza con las funciones generadoras y las sucesiones recurrentes. Se trata de una continuación natural de la combinatoria estudiada en la asignatura de primer curso Fundamentos de las Matemáticas. Los problemas de este tema requieren una vez más el ejercicio de traducir un enunciado al lenguaje matemático. Los grafos son una herramienta básica para resolver problemas de origen muy diverso, que va desde la matemática más abstracta hasta la investigación operativa. En algunos casos, la simple traducción del problema al lenguaje de los grafos ya resulta esclarecedora y muy eficaz. El tercer tema del curso es la optimización combinatoria, que se ocupa de cuestiones combinatorias en las que no se trata de contar objetos de un tipo concreto sino de buscar los "óptimos" de acuerdo con cierto criterio. Las respuestas en este caso no van a ser fórmulas sino algoritmos para encontrar o aproximarse a dichos óptimos. Las técnicas necesarias aquí van a ser el Álgebra Lineal (para optimizar funciones lineals de 1 dichos óptimos. Las técnicas necesarias aquí van a ser el Álgebra Lineal (para optimizar funciones lineals de varias variables con restricciones lineales pero donde los valores de las variables a menudo serán discretos) y las matroides. Así pues, a lo largo del curso se presentaran diferentes ejemplos de aplicaciones de las matemáticas en los que, usando herramientas relativamente simples y una buena dosis de ingenio, se resolveran problemas interesantes y difíciles. A su vez, los estudiantes podran practicar, por medio de los ejercicios de combinatoria y de optimización, la primera fase en modelización matemática: entender un problema y traducirlo al lenguaje matemático adecuado para su resolución. |
| Rights: |
Aquest document està subjecte a una llicència d'ús Creative Commons. Es permet la reproducció total o parcial, la distribució, la comunicació pública de l'obra i la creació d'obres derivades, fins i tot amb finalitats comercials, sempre i quan es reconegui l'autoria de l'obra original.  |
| Language: |
Català, anglès, castellà |
| Studies: |
Matemàtiques [2500149] |
| Study plan: |
Grau en Física i Grau en Matemàtiques [1286] ; Grau en Matemàtiques [777] |
| Document: |
Objecte d'aprenentatge |
guest ::
