Informació general


  • Tipus d'assignatura: Bàsica
  • Coordinador: Enric Sesa Nogueras
  • Trimestre: 3
  • Crèdits: 6
  • Professorat:

Idiomes d'impartició


  • Català

Descripció


La matemàtica discreta estudia estructures matemàtiques que són intrínsecament discretes, es a dir, que no són contínues. Per exemple la recta de nombres reals és contínua ja que varien suaument (no podem dir quin nombre real ve després d'un altre, per exemple no sabem quin nombre va després de 1,0) en canvi la recta dels nombres enters és discreta ja que podem distingir clarament el seus valors (després del 1 ve el 2). En aquesta assignatura estudiarem la lògica proposicional i teoria de grafs que són dues disciplines molt utilitzades en el camp de la computació. La lògica és utilitzada en la programació, de fet existeix el paradigma de programació lògica de la mateixa manera que hi ha l'imperatiu i funcional, en bases de dades, en el disseny i verificació de sistemes i en la intel·ligència artificial entre d'altres. En el cas dels grafs són una estructura matemàtica molt usada en la computació (i d'altres disciplines) per representar problemes, dades, conceptes  i les seves interrelacions. Són estructures fàcilment programables de les quals es coneixen moltes propietats matemàtiques que es poden usar per validar la correctesa de la solució proposada a problemes computacionals. També estudiarem els nombres enters, els enters congruents i les equacions congruents que donen lloc a les tècniques modernes de codificació de missatges.

Resultats d'aprenentatge


A nivell general, aquesta assignatura contribueix als segu¨ents resultats d'aprenentatge especificats per a la matèria a la qual pertany (Fonaments científics):

  • Familiaritzar-se amb el llenguatge i la lògica matemàtica i conèixer les seves aplicacions en l'àmbit de la informàtica. Saber expressar amb precisió conceptes matemàtics. Ser capaç d'entendre una demostració i realitzar demostracions usant diversos mètodes.
  • Conèixer els grafs com a model abstracte de relació binària i les seves possibles aplicacions en l'àmbit de la informàtica
  • Conèixer les propietats dels nombres enters i dels enters modulars, i saber operar i resoldre equacions en aquests conjunts 

A un nivell més concret, en acabar l’assignatura l’estudiant o estudianta ha de ser capaç de:

  • RA1: Formalitzar el llenguatge natural amb enunciats 
  • RA2: Resoldre (en el sentit de la lògica) raonaments usant la lògica d'enunciats
  • RA3: Conèixer les propietats dels nombres enters congruents
  • RA4: Resoldre equacions lineals congruents 
  • RA5: Descriure els grafs com a estructures matemàtiques útils per modelar problemes
  • RA6: Implementar algorismes de recorreguts de grafs
  • RA7: Resoldre problemes usant la teoria de grafs
  • RA8: Demostrar formalment la correctesa dels algorismes sobre grafs

Metodologia de treball


Tots els conceptes teòrics de la matèria s'exposaran en classes de teoria (grups grans). En aquestes classes, i a discreció dels docents impartidors, també es resoldran exercicis i problemes de caire més pràctic. Així mateix, i sempre a discreció dels impartidors, es podrà demanar als estudiants que resolguin, de manera individual o en grup, problemes i/o exercicis breus. Aquestes activitats, breus i optatives, serviran a l'estudiant com a instrument d'autoavaluació del seu assoliment dels continguts de la matèria i podran ser utilitzades per part del docent per a prendre decisions sobre la qualificació final de l'estudiant bo i que mai en detriment de la qualificació numèrica calculada segons el sistema de qualificació especificat per l'assignatura.

Es recomana als estudiants/es que, en la mesura de les seves possibilitats, assisteixin a totes les classes amb un ordinador portàtil amb la capacitat d’executar el software escaient per a l’assignatura. Els docents impartidors informaran de quin és aquest software i com es pot obtenir.

Continguts


  1. Lògica d'enunciats
    1. Lògica d'enunciats i el seu llenguatge.
    2. Formalització Interpretació dels enunciats
    3. Categorització dels enunciats (tautologies, contradiccions i contingències)
    4. Categorització de conjunts d'enunciats (consistents i inconsistents)
    5. Raonaments vàlids i invàlids.
    6. Contraexemples
    7. Formes normals
    8. El mètode de resolució
    9. Resolució Lineal
  2. Nombres enters
    1. Propietats i divisibilitat
    2. Enters Congruents
    3. Equacions lineals de congruències
  3. Grafs i dígrafs
    1. Definicions bàsiques
    2. Representació matricial i amb llistes
    3. Camins, connectivitat i distància
    4. Isomorfisme entre grafs
    5. Recorreguts en fondària i amplada
    6. Dígrafs i DAGs
    7. Ordenació topològica
    8. Arbres d'expansió mínima: algorismes de Prim i Kruskal
    9. Camins més curts: algorisme de Dijkstra
    10. Camins més curts: algorisme de Bellman-Ford

Activitats d'aprenentatge


Es posa a disposició dels estudiants tot un seguit d'activitats de caire eminentment pràctic (exercicis curts, problemes...) que són la base de les activitats d'aprenentatge de l'assignatura. Aquestes activitats els estudiants/es les hauran de resoldre, sovint de manera no presencial, seguint les indicacions dels docents i també seran treballades a classe. Si bé aquestes activitats tindran caràcter optatiu (els docents no en verificaran de manera individualitzada la realització per part dels estudiants), seran imprescindibles per assolir els coneixements teorico-pràctics de l'assignatura.

Amb l'objectiu de recollir evidència de l'assoliment dels resultats d'aprenentatge esperats es realitzaran les segu¨ents activitats de caràcter avaluatiu:

Prova escrita 1: Prova individual d'aplicació pràctica (resolució d'exercicis i problemes) dels conceptes teòrics i procediments pràctics de lògica d'enunciats i predicats i dels nombres enters. (Evidència dels resultats d'aprenentatge RA1 - RA4 i relacionada amb les competències EFB1, EFB3, B1 i B3)

Prova escrita 2: Prova individual d'aplicació pràctica (resolució d'exercicis i problemes) dels conceptes teòrics i procediments pràctics de la teoria de grafs (Evidència dels resultats d'aprenentatge RA5 - RA8 i relacionada amb la competència EFB3)

Resolució de problemes tipus: Els estudiants realitzaran exercicis proposats pel professor. Aquests exercicis es podran exposar a classe i seran realitzats de forma individual o en grup segons indicacions del professor. Aquests problemes tenen com a objectiu ajudar a l'estudiant a comprendre els conceptes bàsics de matemàtica discreta, i detectar mancances en el propi coneixement per superar-les amb ajuda dels companys i el professor. (Relacionada amb tots els resultats d'aprenentatge i les competències EFB1, EFB3, B1 i B3)

Implementació d'algorismes sobre grafs: Els estudiants realitzaran exercicis de programació d'algorismes sobre grafs. L'objectiu és consolidar els coneixements de la teoria de grafs, reconèixer el vincle entre la teoria dels grafs i la seva aplicació pràctica, així com detectar mancances en el propi coneixement per superar-les amb ajuda dels propis companys i el professor. (Relacionada amb RA5 - RA8 i les competències EFB1, EFB3, B1 i B3)

A continuació s'expliciten els aspectes més importants de cada competència assignada a l'assignatura:

  • B1: resolució de problemes dins de la seva àrea d’estudi.
  • B3: reunir i interpretar informació rellevant per la matèria
  • EFB1: resolució de problemes matemàtics 
  • EFB3: dominar conceptes bàsics de matemàtica discreta, lògica, algorísmica i complexitat computacional 
  • T1: tercera llengua

Per tal de superar (aprovar) les activitats avaluatives, els estudiants hauran de demostrar

  • Que han adquirit els coneixements teòrics relatius als continguts de l’assignatura i que la seva comprensió els permet de portar-los a la pràctica [MECES-2 punt a, punt c]
  • Que poden desenvolupar solucions a problemes que, si bé són semblants a d’altres vistos anteriorment, presenten aspectes que són nous [MECES- 2 punt f]

Sistema d'avaluació


La qualificació final és la suma ponderada de les qualificacions de les activitats:

ACTIVITAT i PES

  1. Prova Escrita I 45% - 50%
  2. Prova Escrita II 45% - 50%
  3. Resolució de problemes tipus 0% - 5%
  4. Implementació d'algorismes sobre grafs 0% - 5%

Per tal d'aprovar l'assignatura la nota de les dues proves escrites no serà inferior a 3

La resolució de problemes i la implementació dels algorismes serà voluntària. Comptaran a la mitja només en el cas que beneficii a l'estudiant. 

Recuperació

  • Només es podran recuperar les activitats Prova Escrita I i II. 
  • Si un estudiant no s'ha presentat a alguna de les proves escrites no podrà presentar-se a la recuperació.

Normes de realització de les activitats

Per a cada activitat, els docents n'informaran de les normes i condicions particulars que les regeixin.

Les activitats unipersonals pressuposen el compromís de l'estudiant de realitzar-les de manera individual. Es consideraran suspeses totes aquelles activitats en què l'estudiant no s'ajusti a aquest compromís,  independentment del seu paper (emissor o receptor). Igualment, les activitats que s'hagin de realitzar en grups pressuposen el compromís per part dels estudiants que l'integren de realitzar-les en el si del grup. Es consideraran suspeses totes aquelles activitat en què el grup no hagi respectat aquest compromís amb independència del seu paper (emissor o receptor).

En les activitats realitzades en grup el docent pot, en base a la informació de què disposi, personalitzar la qualificació per a cada integrant del grup.

És potestatiu dels docents acceptar o no lliuraments fora dels terminis que s'indiquin. En el cas que aquests lliuraments fora de termini s'acceptin, és potestatiu del docent decidir si aplica alguna penalització i la quantia d'aquesta.

Bibliografia


Bàsica

Enric Sesa and Josep Roure, "Propositional logics: class notes". Pubilicació interna TCM

Josep Roure, "Nombres enters congruents i equacions". Apunts de classe. Publicació interna TCM

Josep Roure, "Graphs class notes". Publicació interna TCM


Complementària

Robert Sedgewick and Kevin Wayne (2011), "Algorithms", Fourth Edition, Addison-Wesley.