Fundació TecnoCampus
eCampus
Universitat Empresa
eCampus

Que estàs buscant?

Informació general

Tipus d'assignatura: Bàsica

Coordinador: Rosa Herrero Antón

Trimestre: Tercer trimestre

Crèdits: 6

Professorat: 

Alfons Palacios Gonzàlez
Carles Bonet Papell 

Idiomes d'impartició

  • Català

Aquesta assignatura s'imparteix en català, però la bibliografia i la documentació és majoritàriament en anglès. 

Competències

Competències bàsiques

  • B1_Que els estudiants hagin demostrat tenir i comprendre coneixements en una àrea d'estudi que tingui la seva base en l'educació secundaria general, i s'acostumi a trobar a un nivell que, tot i que amb el suport de llibre de text avançats, inclogui també alguns aspectes que impliquen coneixements procedents de la vanguardia del seu camp d'estudi

  • B3_Que els estudiants tinguin la capacitat de reunir i interpretar dades rellevants (normalment dins de la seva àrea d'estudi), per emetre judicis que incloguin una reflexió sobre temes rellevants de caire social, científica o ètica

Competències específiques

  • EFB1_Capacitat per a la resolució dels problemes matemàtics que puguin plantejar-se a l'enginyeria. Aptitud per aplicar els coneixements sobre: àlgebra lineal, càlcul diferencial i integral, mètodes numèrics, algorítmica numèrica, estadística i optimització

  • EFB3_Capacitat per comprendre i dominar els conceptes bàsics de matemàtica discreta, lògica, algorítmica i complexitat computacional, i la seva aplicació per a la resolució de problemes propis de l'enginyeria

Competències transversals

  • T1_Que els estudiants coneixin un tercer idioma, que serà preferentment l'anglès, amb un nivell adequat de forma oral i per escrit, d'acord amb les necessitats que tindran les graduades i els graduats a cada titulació

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

Aquesta assignatura disposa de recursos metodològics i digitals per fer possible la seva continuïtat en modalitat no presencial en el cas de ser necessari per motius relacionats amb la Covid-19. D'aquesta forma s'assegurarà l'assoliment dels mateixos coneixements i competències que s'especifiquen en aquest pla docent.

Continguts

  1. Lògica proposicional
    1. Raonament, llenguatge natural i llenguatge proposicional
    2. El llenguatge de la lògica proposicional, CP0
    3. Formalització de sentències i interpretació d'enunciats
    4. Teoria de models (tautologies, contradiccions i contingències)
    5. Teoria de la demostració
    6. Raonaments vàlids i invàlids, consistència i inconsistència, contraexemples
    7. Formes normals
    8. El mètode de resolució
    9. Resolució Lineal
  2. Teoria de grafs
    1. Definicions bàsiques: camins, connectivitat i distància, Isomorfisme entre grafs
    2. Representació de grafs
    3. Algoritmes sobre grafs: recorreguts en fondària i amplada (DFS, BFS)
    4. Dígrafs i DAGs
    5. Ordenació topològica
    6. Arbres d'expansió mínima: algorismes de Prim i Kruskal
    7. Camins més curts: algorisme de Dijkstra

Sistema d'avaluació

La qualificació final és la mitja de la nota de les dues parts de l'assignatura

ACTIVITAT i PES

  1. Examen de Lògica 45% - 50%
  2. Examen de Grafs 45% - 50%
  3. Resolució de problemes de lògica a classe 0% - 5%
  4. Resolució de problemes de grafs a classe 0% - 5%

Per tal d'aprovar l'assignatura les notes de les dues parts de l'assignatura han de ser iguals o superiors a 5

La resolució de problemes és voluntària

Recuperació

  • Només es poden recuperar els exàmens, no pas la participació a classe
  • L'estudiant només es pot presentar a la recuperació si s'ha presentat a l'examen ordinari. 

 

Bibliografia

Bàsic

Kenneth H. Rosen, "Discrete Mathematics and its Applications". Eighth Edition. McGraw-Hill-Education, 2019. ISBN 978-1-260-09199-1.

K. Erciyes, "Discrete Mathematics and Graph Theory, a concise study companion and guide (Undergrate Topics in Computer Science)". Springer, 2021. ISBN 978-3-030-61114-9

Complementary

Robert Sedgewick and Kevin Wayne, "Algorithms", Fourth Edition, Addison-Wesley, 2011. ISBN 978-0321573513.

Gabriel Valiente, "Algorithms on Trees and Graphs: With Python Code (Texts in Computer Science)". Second Edition. Springer, 2021. ISBN 

978-3030818845

K. Erciyes, "Algebraic Graph Algoritms, a practical gunide using Python (Undergrate Topics in Computer Science)". Springer, 2021. ISBN 978-3-030-87885-6