Titulació | Tipus | Curs | Semestre |
---|---|---|---|
2500149 Matemàtiques | OB | 2 | 1 |
Podeu accedir-hi des d'aquest enllaç. Per consultar l'idioma us caldrà introduir el CODI de l'assignatura. Tingueu en compte que la informació és provisional fins a 30 de novembre de 2023.
Àlgebra Lineal i Fonaments de les Matemàtiques de primer curs del Grau de Matemàtiques.
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 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ó.
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.
4. Seminaris d'introducció molt breu a altres temes de Matemàtica Discreta.
- Dissenys combinatoris.
- Criptografia.
- Grafs planars.
- Grafs hamiltonians.
- Grafs aleatoris.
- Teoria de codis.
- Teoria de Ramsey
- Teoria de jocs.
El treball presencial constarà de:
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.
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 | 1 | 0,04 | 7, 8, 9 |
Tipus: Autònomes | |||
Estudi i preparació en grup del tema que es presentarà al seminari | 14 | 0,56 | 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 |
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.25 nota d'examen parcial + 0.2 nota de l'examen de pràctiques + 0.2 nota treball seminari + 0.35 nota de l'examen final
Avaluació recuperable: es farà una recuperació de les dues proves escrites (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.
Títol | Pes | Hores | ECTS | Resultats d'aprenentatge |
---|---|---|---|---|
Avaluació de la presentació oral i escrita del treball de seminari | 0.20 | 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.60 | 4 | 0,16 | 2, 4, 5, 6 |
Examen final | 0.35 | 4 | 0,16 | 2, 4, 5, 6 |
Prova parcial | 0.25 | 2 | 0,08 | 2, 4, 5, 6, 10 |
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.
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.
Python, SageMath.