Seminari de matemàtica discreta
Codi: 100098 Crèdits: 6| Titulació | Tipus | Curs |
|---|---|---|
| 2500149 Matemàtiques | OB | 2 |
Professor/a de contacte
- Nom:
- Francesc Bars Cortina
- Correu electrònic:
- francesc.bars@uab.cat
Equip docent
- Laura Brustenga Moncusi
- Guillem Quingles Daví
Idiomes dels grups
Podeu consultar aquesta informació al final del document.
Prerequisits
Àlgebra Lineal i Fonaments de les Matemàtiques de primer curs del Grau de Matemàtiques.
Objectius
La matemàtica discreta és l'àrea de les matemàtiques dedicada a l'estudi d'objectes finits o més generalment discrets. 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ç.
El tercer tema del curs, si el temps ho permet, é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 ambalgun criteri. Les 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ó.
Competències
- Aplicar l'esperit crític i el rigor per validar o refutar arguments tant propis com de d'altres.
- Davant de situacions reals amb un nivell mig de complexitat, demanar i analitzar dades i informació rellevants, proposar i validar models utilitzant eines matemàtiques adequades per a, finalment, obtenir conclusions
- Demostrar de forma activa una elevada preocupació per la qualitat en el moment d'argumentar o exposar les conclusions dels seus treballs
- Que els estudiants hagin demostrat posseir i comprendre coneixements en un àrea d'estudi que parteix de la base de l'educació secundària general, i se sol trobar a un nivell que, si bé es recolza en llibres de text avançats, inclou també alguns aspectes que impliquen coneixements procedents de l'avantguarda del seu camp d'estudi.
- Que els estudiants hagin desenvolupat les habilitats d'aprenentatge necessàries per a emprendre estudis posteriors amb un alt grau d'autonomia.
- Que els estudiants puguin transmetre información idees, problemes i solucions a un públic tan especialitzat com no especialitzat
- Que els estudiants sàpiguen aplicar els seus coneixements al seu treball o vocació d'una forma professional i posseeixin les competències que solen demostrar-se per mitjà de l'elaboració i defensa d'arguments i la resolució de problemes dins de la seva àrea d'estudi.
- Utilitzar aplicacions informàtiques d'anàlisi estadística, càlcul numèric i simbòlic, visualització gràfica, optimització o altres per experimentar en Matemàtiques i resoldre problemes
- Utilitzar eficaçment bibliografia i recursos electrònics per obtenir informació
Resultats d'aprenentatge
- Aplicar l'esperit crític i el rigor per validar o refutar arguments tant propis com de d'altres.
- Conèixer el llenguatge i les aplicacions més elementals de la teoria de grafs, així com algorismes de resolució de problemes en grafs.
- Demostrar de forma activa una elevada preocupació per la qualitat en el moment d'argumentar o exposar les conclusions dels seus treballs
- Plantejar i resoldre problemes de programació lineal.
- Plantejar problemes d'ordenació i enumeració i utilitzar tècniques eficients per a la seva resolució.
- Plantejar problemes reals com a problemes de Programació Matemàtica.
- Que els estudiants hagin demostrat posseir i comprendre coneixements en un àrea d'estudi que parteix de la base de l'educació secundària general, i se sol trobar a un nivell que, si bé es recolza en llibres de text avançats, inclou també alguns aspectes que impliquen coneixements procedents de l'avantguarda del seu camp d'estudi.
- Que els estudiants hagin desenvolupat les habilitats d'aprenentatge necessàries per a emprendre estudis posteriors amb un alt grau d'autonomia.
- Que els estudiants puguin transmetre información idees, problemes i solucions a un públic tan especialitzat com no especialitzat
- Que els estudiants sàpiguen aplicar els seus coneixements al seu treball o vocació d'una forma professional i posseeixin les competències que solen demostrar-se per mitjà de l'elaboració i defensa d'arguments i la resolució de problemes dins de la seva àrea d'estudi.
- Utilitzar eficaçment bibliografia i recursos electrònics per obtenir informació.
- Utilitzar tècniques computacionals per resoldre problemes d'optimització.
Continguts
1. Funcions generadores i successions recurrents.
- Definició de funció generadora. Tècniques de càlcul. Resolució de problemes combinatoris amb
funcions generadores.
- Successions recurrents. Recurrències lineals de primer i de segon ordre.
- Resolució de relacions de recurrència amb funcions generadores.
2. Grafs.
- Definició. Alguns models matemàtics amb grafs.
- Terminologia bàsica i alguns tipus de grafs.
- Representació de grafs i isomorfismes de grafs.
- Camins i circuits.
- Arbres.
3. Optimització combinatòria.
- Introducció. Exemples.
- Programació lineal. El mètode del símplex.
- Matroides.
Activitats formatives i Metodologia
| Títol | Hores | ECTS | Resultats d'aprenentatge |
|---|---|---|---|
| Tipus: Dirigides | |||
| Classes de pràctiques amb ordinador | 8 | 0,32 | |
| Classes de teoria | 28 | 1,12 | |
| Sessions de problemes | 16 | 0,64 | 10 |
| Tipus: Supervisades | |||
| Entrevista sobre la preparació del tema en el seminari | 0 | 0 | 7, 8, 9 |
| Tipus: Autònomes | |||
| Estudi i preparació en grup del tema que es presentarà en la assignatura | 15 | 0,6 | 7, 8, 9 |
| Estudi personal de teoria | 26 | 1,04 | 7, 8, 10 |
| Fer problemes | 36 | 1,44 | 10 |
| Pràctica autònoma de resolució d'exercicis amb ordinador | 8 | 0,32 | 10 |
El treball presencial constarà de:
- Teoria. El professor exposarà els fonaments teòrics i algunes demostracions del curs.
- Així mateix, els alumnes grabaran un vídeo i presentaran un document detallat escrit en grups de quatre estudiants projectes sobre temes concres o aplicacions, en format de seminari breu:
- En un fitxer es penjaran diferents projectes a treballar. Cada equip escollirà un projecte i el treballarà de manera autònoma.
- El resultat del treball es presentarà per escrit i també en forma de vídeo públic de fins 12 minuts.
- Problemes (seminaris). Els estudiants disposaran de llistes de problemes que hauran de portar treballades a classe per a poder aprofitar la discussió que es farà.
- Pràctiques d'ordinador amb el software SageMath. Les tres primeres sessions correspondran als tres temes. La quarta sessió inclourà exercicis dels tres temes i serà avaluable.
Nota: es reservaran 15 minuts d'una classe, dins del calendari establert pel centre/titulació, per a la complementació per part de l'alumnat de les enquestes d'avaluació de l'actuació del professorat i d'avaluació de l'assignatura/mòdul.
Avaluació
Activitats d'avaluació continuada
| Títol | Pes | Hores | ECTS | Resultats d'aprenentatge |
|---|---|---|---|---|
| Avaluació de la presentació amb vídeo i escrita del treball de seminari | 0.15 | 1 | 0,04 | 1, 3, 7, 8, 9, 10, 11 |
| Examen de pràctiques | 0.20 | 2 | 0,08 | 4, 5, 12 |
| Examen de recuperació | 0.65 | 4 | 0,16 | 2, 4, 5, 6 |
| Examen final | 0.45 | 4 | 0,16 | 2, 4, 5, 6 |
| Prova parcial | 0.2 | 2 | 0,08 | 2, 4, 5, 6, 10 |
Hi ha quatre activitats avaluables: un examen parcial, un examen de pràctiques, un treball de seminari i un examen final.
L'avaluació de l'assignatura es farà segons la fórmula:
0.2 nota d'examen parcial + 0.2 nota de l'examen de pràctiques + 0.15 nota treball seminari + 0.45 nota de l'examen final
Avaluació recuperable: es farà una recuperació de les dues proves escrites (65%). Per a presentar-se a la recuperació s'ha d'haver participat en tres de les quatre activitats avaluables del curs.
La qualificació de no avaluable es posarà quan un estudiant hagi participat en dues o menys activitats avaluables i cap d'elles sigui l'examen final.
Aquesta assignatura No pot ser elegible per a Avaluació Única i per tant s'ha de fer un seguiment tant de la part pràctica i seminaris durant el curs.
Bibliografia
Bibliografia general:
Aigner, M. "Discrete Mathematics", AMS 2007.
Basart, J.M. , Rifà, J, and Villanueva, M. "Fonaments de matemàtica discreta. Elements de combinatòria i d'aritmètica". Col. Materials de la UAB, n. 36. 1997.
Basart, J.M. "Grafs: fonaments i algoritmes", Col. Manuals de la UAB, n. 13, 1998.
Comellas, F, Fàbrega,J., Sànchez, A, Serra, O. "Matemática discreta". Edicions UPC, 2001.
Gimbert, J. Moreno, R., Ribó, J.M., Valls, M. "Apropament a la teoria de grafs i als seus algoritmes". UdL, 1998.
Graham, R.L. , Knuth, D. E. , and Patashnik, O. "Concrete mathematics: a foundation for computer science". Addison-Wesley. 1990.
Grimaldi, Ralph P. "Discrete and combinatorial mathematics: an applied introduction". 5th ed. Pearson.Addison-Wesley. 2004.
Rosen, Kenneth H. "Discrete mathematics and its applications". 6th ed. McGraw-Hill. 2007.
Lawler, Eugene. Combinatorial Optimization: Networks and Matroids. Dover. ISBN 0-486-41453-1. (2001)
Grafs:
Wilson, R.J. i Watkins, J. "Graphs: an introductory approach: a first course in discrete mathematics". Wiley, cop. New York. 1990.
Programació lineal:
Alabert, A i Camps, R. "Programació Lineal, una introducció a la presa de decisions racional".
Basart, J.M. "Programació lineal". Col. Materials de la UAB, n. 58.. 1998.
Luenberger, D. "Programación lineal y no lineal". Addison-Wesley iberoamericana. 1989.
Programari
Python, SageMath, Magma
Llista d'idiomes
| Nom | Grup | Idioma | Semestre | Torn |
|---|---|---|---|---|
| (PLAB) Pràctiques de laboratori | 1 | Català | primer quadrimestre | matí-mixt |
| (PLAB) Pràctiques de laboratori | 2 | Català | primer quadrimestre | matí-mixt |
| (SEM) Seminaris | 1 | Català | primer quadrimestre | matí-mixt |
| (SEM) Seminaris | 2 | Català | primer quadrimestre | matí-mixt |
| (TE) Teoria | 1 | Català | primer quadrimestre | matí-mixt |