Fundació TecnoCampus
eCampus
Universitat Empresa
eCampus

Que estàs buscant?

Informació general

Tipus d'assignatura: Bàsica

Coordinador: Ana Beatriz Pérez Zapata

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. 

L'aula (física o virtual) és un espai segur, lliure d'actituds masclistes, racistes, homòfobes, trànsfobes i discriminatòries, ja sigui cap a l'alumnat o cap al professorat. Confiem que entre totes i tots puguem crear un espai segur on ens puguem equivocar i aprendre sense haver de patir prejudicis d'altres. 

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. PL: Assistència i participació als seminaris i resolució de problemes de Lògica 5% (En avaluació ordinària)
  2. PG: Assistència i participació als seminaris i resolució de problemes de Grafs 5% (En avaluació ordinària)
  3. EL: Examen de Lògica 45% (En avaluació ordinària)
  4. EG: Examen de Grafs 45% (En avaluació ordinària)

Condicions per aprovar l'assignatura:

  • (PL 0,1 + EL 0,9) >= 5 (Cal  aprovar el bloc temàtic de Lògica amb un nota igual o superior a 5)
  • (PG 0,1 + EG 0,9) >= 5  (Cal  aprovar el bloc temàtic de Teoria de Grafs amb un nota igual o superior a 5)

Recuperació

  • Es por recuperar cada bloc temàtic per separat. Es recuperen i es repeteixen només els exàmens EL i EG. 
  • El resultat de la recuperació, si EL>5 i EG>5 serà APTE(5), si no serà NO APTE.
  • A la recuperació no es té en compte la nota de problemes, cada examen representa el 50%  

 

Bibliografia

Bàsic

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

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

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