Logo UAB
2020/2021

Seminari de matemÓtica discreta

Codi: 100098 CrŔdits: 6
Titulaciˇ Tipus Curs Semestre
2500149 MatemÓtiques OB 2 1
La metodologia docent i l'avaluaciˇ proposades a la guia poden experimentar alguna modificaciˇ en funciˇ de les restriccions a la presencialitat que imposin les autoritats sanitÓries.

Professor/a de contacte

Nom:
Salvador Comalada Clara
Correu electr˛nic:
Salvador.Comalada@uab.cat

Utilitzaciˇ d'idiomes a l'assignatura

Llengua vehicular majoritÓria:
catalÓ (cat)
Grup Ýntegre en anglŔs:
No
Grup Ýntegre en catalÓ:
Grup Ýntegre en espanyol:
No

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. 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 és la programació lineal, que s'ocupa d'optimitzar funcions lineals de vàries variables amb restriccions lineals. En un cert sentit, no pertany estrictament a la matemàtica discreta, encara
que és habitual trobar-la dins de cursos d'aquesta matèria. La teoria utilitza només àlgebra lineal, però les tècniques introduïdes s'apliquen després per resoldre problemes de planteig, els més interessants dels quals requereixen valors enters o binaris (discrets) de les variables.

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ó.

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 capacitatde 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 brevíssima introducció.
El tercer tema del curs és la programació lineal, que s'ocupa d'optimitzar funcions lineals de vàries variables
amb restriccions lineals. En un cert sentit, no pertany estrictament a la matemàtica discreta, encara
que és habitual trobar-la dins de cursos d'aquesta matèria. La teoria utilitza només àlgebra lineal, però les
tècniques introduïdes s'apliquen després per resoldre problemes de planteig, els més interessants dels quals
requereixen valors enters o binaris (discrets) de les variables. Les sessions pràctiques d'aquest tema es faran
amb ordinador.
La resta de l'assignatura consistirà en que, en grups petits, els estudiants aprofundeixin en un tema, i en facin
una presentació escrita complerta i una presentació oral breu a tot el grup. Amb aquestes exposicions es
pretén també proporcionar a tot el grup d'estudiants una visió general de diferents problemes i aplicacions de
la matemàtica discreta.
Seminari de matemàtica discreta   2011 - 2012
1Al 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ó

La matemàtica discreta és l'àrea de les matemàtiques dedicada a l'estudi d'objectes finits. Alguns dels temesdels que s'ocupa són la combinatòria, els grafs, la criptografia, els codis correctors d'errors, els dissenyscombinatoris, la teoria de jocs, la lògica, l'optimització i el disseny i anàlisi d'algorismes per resoldre problemesd'aquests àmbits. La major part té un desenvolupament relativament recent motivat per problemes relacionatssobretot amb la informàtica i amb l'optimització. Són temes força independents entre sí i, en un cursintroductori, 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 lacombinatòria que s'ha fet a l'assignatura de Fonaments de les Matemàtiques de primer curs. En els problemesd'aquest tema essegueix 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ésabstracta fins a la investigació operativa. En alguns casos, gairebé només la traducció al llenguatge dels grafsja resulta esclaridora i molt eficaç. Només en farem, però, una brevíssima introducció.El tercer tema del curs és la programació lineal, que s'ocupa d'optimitzar funcions lineals de vàries variablesamb restriccions lineals. En un cert sentit, no pertany estrictament a la matemàtica discreta, encaraque és habitual trobar-la dins de cursos d'aquesta matèria. La teoria utilitza només àlgebra lineal, però lestècniques introduïdes s'apliquen després per resoldre problemes de planteig, els més interessants dels qualsrequereixen valors enters o binaris (discrets) de les variables. Les sessions pràctiques d'aquest tema es faranamb ordinador.La resta de l'assignatura consistirà en que, en grups petits, els estudiants aprofundeixin en un tema, i en facinuna presentació escrita complerta i una presentació oral breu a tot el grup. Amb aquestes exposicions espretén també proporcionar a tot el grup d'estudiants una visió general de diferents problemes i aplicacions dela matemàtica discreta.Al llarg del curs, doncs, es presentaran diferents exemples d'aplicacions de les matemàtiques, en què, ambeines relativament senzilles i molt d'enginy, es resolen problemes interessants i difícils. Alhora, els estudiantspracticaran 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

  1. Aplicar l'esperit crÝtic i el rigor per validar o refutar arguments tant propis com de d'altres.
  2. ConŔixer el llenguatge i les aplicacions mÚs elementals de la teoria de grafs, aixÝ com algorismes de resoluciˇ de problemes en grafs.
  3. Demostrar de forma activa una elevada preocupaciˇ per la qualitat en el moment d'argumentar o exposar les conclusions dels seus treballs
  4. Plantejar i resoldre problemes de programaciˇ lineal.
  5. Plantejar problemes d'ordenaciˇ i enumeraciˇ i utilitzar tŔcniques eficients per a la seva resoluciˇ.
  6. Plantejar problemes reals com a problemes de Programaciˇ MatemÓtica.
  7. 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.
  8. Que els estudiants hagin desenvolupat les habilitats d'aprenentatge necessÓries per a emprendre estudis posteriors amb un alt grau d'autonomia.
  9. Que els estudiants puguin transmetre informaciˇn idees, problemes i solucions a un p˙blic tan especialitzat com no especialitzat
  10. 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.
  11. Utilitzar eficašment bibliografia i recursos electr˛nics per obtenir informaciˇ.
  12. 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. Programació lineal.

- Introducció. Exemples.
- El model. Terminologia. Resultats.
- El mètode del símplex.

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.

 

Metodologia

El treball presencial variarà al llarg del curs:

- Per als temes 1 i 2 constarà de teoria i problemes. Els estudiants disposaran de llistes de problemes que hauran de portar treballades a classe per a poder aprofitar la discussió que es farà.

- Per al tema 3 consistirà en teoria, problemes i pràctiques d'ordinador. En aquestes pràctiques es resoldran problemes de programació lineal amb el kit de programació lineal  GLPK, on els problemes es poden modelar en llenguatge GNU MathProg modeling language, el qual comparteix moltes característiques amb AMPL.

- Al cap d'un mes de començar el curs s'iniciaran els projectes, que es realitzaran en grups de quatre estudiants. En una sessió de seminari es proposaran diferents temes. Cada equip escollirà un tema i el treballarà de manera autònoma. A més,  prepararà la presentació oral per als companys i elaborarà, per entregar, una guia d'estudi del tema, amb un índex, les definicions i resultats  més importants i una bibliografia. Les dues o tres darreres setmanes de classe es dedicaran a les presentacions orals dels temes que els estudiants hauran preparat en equips.

Activitats formatives

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 amb el software de programaciˇ lineal 8 0,32 10

Avaluaciˇ

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.15 nota d'examen parcial + 0.2 nota de l'examen de pràctiques + 0.15 nota treball seminari + 0.5 nota de l'examen final

La prova parcial no eliminarà matèria. En cas que un estudiant no la pugui fer per una causa justificada, la realitzarà el dia de l'examen final o un dia pactat.

Avaluació recuperable: es farà una recuperació només de l'examen final (50%). 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 presentat 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.

Activitats d'avaluaciˇ

TÝtol Pes Hores ECTS Resultats d'aprenentatge
Avaluaciˇ de la presentaciˇ oral i escrita del treball de seminari 0.15 1 0,04 1, 3, 7, 8, 9, 10, 11
Examen de prÓctiques 0.2 2 0,08 4, 5, 12
Examen de recuperaciˇ 0.5 4 0,16 2, 4, 5, 6
Examen final 0.5 4 0,16 2, 4, 5, 6
Prova parcial 0.15 2 0,08 2, 4, 5, 6, 10

Bibliografia

Bibliografia general (excepte programació lineal):

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.

 

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.