
Matemàtica Discreta i Algorítmica
Codi: 107928Crèdits: 6
| Titulació | Tipus | Curs |
|---|---|---|
| Matemàtiques | OB | 2 |
Professor/a de contacte
- Nom :
- Joaquim Roé Vellvé
- Correu electrònic :
- joaquim.roe@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 i II i Fonaments de les Matemàtiques I i II.
Objectius
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 i els codis, els dissenys combinatoris, 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 tractant funcions generadores i successions recurrents. Es tracta d'una continuació natural de temes tractats a les assignatures de Fonaments de les Matemàtiques de primer curs, on es posa en pràctica la capacitat de traduir problemes d'enunciat al llenguatge matemàtic i algorítmic. 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 tècniques necessàries aquí seran l'àlgebra lineal 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ó.
Resultats d'aprenentatge
- CM14 (Reformular problemes reals com a problemes de programació matemàtica.) Reformular problemes reals com a problemes de programació matemàtica.
- CM15 (Plantejar problemes d’ordenació i enumeració, utilitzant tècniques eficients per a la seva resolució.) Plantejar problemes d’ordenació i enumeració, utilitzant tècniques eficients per a la seva resolució.
- KM22 (Identificar els resultats bàsics de teoria combinatòria.) Identificar els resultats bàsics de teoria combinatòria.
- KM23 (Identificar algorismes elementals de resolució de problemes amb grafs.) Identificar algorismes elementals de resolució de problemes amb grafs.
- KM24 (Identificar els algorismes elementals de la programació lineal.) Identificar els algorismes elementals de la programació lineal.
- SM18 (Resoldre problemes de programació lineal, mitjançant els mètodes de resolució principals (mètode simplex, mètode de les dues fases, mètode de punts interiors).) Resoldre problemes de programació lineal, mitjançant els mètodes de resolució principals (mètode simplex, mètode de les dues fases, mètode de punts interiors).
- SM19 (Fer servir tècniques computacionals en la resolució de problemes d’optimització. (mètode del simplex, mètode del gradient, etc.).) Fer servir tècniques computacionals en la resolució de problemes d’optimització. (mètode del simplex, mètode del gradient, etc.).
Continguts
- Funcions generadores i successions recurrents.
- Definició de funció generadora. Tècniques de càlcul. Resolució de problemes combinatoris amb funcions generadores.
- Successions recurrents. Resolució de relacions de recurrència amb funcions generadores.
- Algoritmes i complexitat.
- Grafs.
- Definició. Alguns models matemàtics amb grafs.
- Terminologia bàsica. Invariants i isomorfismes de grafs.
- Camins, circuits i arbres.
- Optimització combinatòria.
- Algoritmes de cerca i ordenació
- Matroides
- Optimització en grafs.
Activitats formatives i Metodologia
| Títol | Hores | ECTS | Resultats d'aprenentatge |
|---|---|---|---|
| Classes de teoria | 26 | 1,04 | CM14, CM15, KM22, KM23, KM24, SM18 |
| Resolució autònoma de problemes | 26,25 | 1,05 | CM14, CM15, KM22, KM23, KM24, SM18, SM19 |
| Estudi de la teoria | 31,25 | 1,25 | CM14, CM15, KM22, KM23, KM24 |
| Seminaris | 16 | 0,64 | CM14, CM15, KM22, KM23, KM24, SM18, SM19 |
| Pràctiques d'ordinador | 8 | 0,32 | CM15, KM23, KM24, SM18, SM19 |
| Preparació de la presentació oral | 31,25 | 1,25 | CM14, CM15, KM22, KM23, KM24, SM18 |
El treball presencial constarà de:
- Teoria. El professor exposarà els fonaments teòrics i algunes demostracions del curs. L'exposició d'alguns temes concrets o aplicacions de la teoria aniran a càrrec de l'alumnat: en una sessió de teoria es proposaran diversos temes. En equips de tres o quatre estudiants s'escollirà un tema a estudiar de forma autònoma. El resultat de l'estudi es presentarà per escrit i també oralment a la classe.
- 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.
Avaluació
Activitats d'avaluació continuada
| Títol | Pes | Hores | ECTS | Resultats d'aprenentatge |
|---|---|---|---|---|
| Pràctica avaluable | 0.2 | 2 | 0,08 | CM14, KM23, KM24, SM18, SM19 |
| Presentació oral | 0.2 | 0,25 | 0,01 | CM14, CM15, KM22, KM23, KM24 |
| Examen parcial | 0.25 | 3 | 0,12 | CM14, CM15, KM22 |
| Examen final | 0.35 | 3 | 0,12 | CM14, CM15, KM22, KM23, KM24, SM18 |
| Examen de recuperació | 0.6 | 3 | 0,12 | CM14, CM15, KM22, KM23, KM24 |
Hi ha quatre activitats avaluables: un examen parcial, una presentació oral, una pràctica avaluable i un examen final. L'avaluació de l'assignatura es farà segons la fórmula: 0.25 nota d'examen parcial + 0.2 nota presentació oral + 0.2 pràctica avaluable + 0.35 nota de l'examen final.
Avaluació recuperable: es farà una recuperació dels dos exàmens (60%). 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.
Després de l'examen final s'atorgaran les matrícules d'honor que es considerin clares. Aquestes matrícules seran ja definitives. Si el nombre màxim de matrícules permès no s'ha assolit, es reconsiderararà la possibilitat d'atorgar-ne més després de l'examen de recuperació, al qual els estudiants poden anar a millorar la seva nota de curs.
Per l'avaluació d'aquesta assignatura, es permet l'ús de tecnologies d'"Intel·ligència Artificial" (IA) exclusivament en la preparació de l'exposició oral com a tasques de suport com la cerca bibliogràfica o d’informació, la correcció de textos o les traduccions. L'estudiantat haurà d'identificar clarament quines parts han estat generades amb aquesta tecnologia, especificar les eines emprades i incloure una reflexió crítica sobre com aquestes han influït en el procés i el resultat final de l’activitat. La no transparència de l’ús de la IA en aquesta activitat avaluable es considerarà falta d'honestedat acadèmica i pot comportar una penalització parcial o total en la nota de l'activitat, o sancions majors en casos de gravetat. En les activitats d'avaluació presencial, no es permet l'ús de cap ajut extern, de tipus IA o altre.
Avaluació única
L’alumnat que s’hagi acollit a la modalitat d’avaluació única haurà de realitzar un examen que inclourà tot el contingut del curs. Aquest examen es durà a terme el mateix dia, hora i lloc que l'examen final de la modalitat d'avaluació continuada, i a continuació es farà l'avaluació de les pràctiques i una entrevista sobre els temes explicats pels companys i companyes. Si la nota d'aquest examen no arriba a 5, l’estudiant té l'opció de presentar-se a l'examen de recuperació en les mateixes condicions que l'estudiantat en avaluació continuada.
Bibliografia
Bibliografia general:
- Basart, J.M, Rifà, J i Villanueva, M. "Fonaments de matemàtica discreta. Elements de combinatòria i d'aritmètica". Col. Materials de la UAB, n. 36. 1997.
- Graham, R.L, Knuth, D. E., 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:
- Bondy, J.A. i Murty, U.S.R. "Graph Theory". Springer. 2008.
- Wilson, R.J. i Watkins, J. "Graphs: an introductory approach: a first course in discrete mathematics". Wiley, cop. New York. 1990.
Optimització:
- Alabert, A i Camps, R. "Programació Lineal, una introducció a la presa de decisions racional".
- Cormen, Thomas H.; Leiserson, Charles Eric.; Rivest, Ronald L., "Introduction to algorithms", Cambridge Mass. etc. : MIT Press cop. 1990
- Gordon, Gary.; McNulty, Jennifer, "Matroids : a geometric introduction", Cambridge University Press, 2012
Programari
Python, SageMath.
Grups i idiomes de l'assignatura
La informació proporcionada és provisional fins al 30 de novembre. A partir d'aquesta data, podreu consultar l'idioma de cada grup a través d'aquest enllaç. Per accedir a la informació, caldrà introduir el CODI de l'assignatura
| Tipus de docència | Grup | Idioma | Semestre | Torn |
|---|---|---|---|---|
| (TE) Teoria | 1 | Català | primer quadrimestre | matí-mixt |
| (PLAB) Pràctiques de laboratori | 1 | Català | primer quadrimestre | matí-mixt |
| (SEM) Seminaris | 1 | Català | primer quadrimestre | matí-mixt |
| (PLAB) Pràctiques de laboratori | 2 | Català | primer quadrimestre | matí-mixt |
| (SEM) Seminaris | 2 | Català | primer quadrimestre | matí-mixt |
| (PLAB) Pràctiques de laboratori | 3 | Català | primer quadrimestre | matí-mixt |