| Competències |
| Tipus A | Codi | Competències Específiques |
| FB1 | Capacitat per resoldre els problemes matemàtics que puguin plantejar-se en l'enginyeria. Aptitud per aplicar els coneixements sobre àlgebra lineal, càlcul diferencial i integral, mètodes numèrics, algorísmia numèrica, estadística i optimització. | |
| FB3 | Capacitat per comprendre i dominar els conceptes bàsics de matemàtica discreta, lògica, algorítmica i complexitat computacional, i l'aplicació per resoldre problemes propis de l'enginyeria. | |
| Tipus B | Codi | Competències Transversals |
| B2 | Coneixement de les matèries bàsiques i tecnologies, que capacitin per a l’aprenentatge i desenvolupament de nous mètodes i tecnologies, així com les que els dotin d’una gran versatilitat per adaptar-se a noves situacions. | |
| Tipus C | Codi | Competències Nuclears |
| Resultats d'aprenentage |
| Tipus A | Codi | Resultats d'aprenentatge |
| FB1 |
Coneix la tècnica de les funcions generadores i aplicar a la solució de problemes combinatoris. Aplica les eines de la combinatòria bàsica i les recurrències lineals per a resoldre problemes de compteig, analitza els resultats i avalua si són coherents amb les hipòtesis del problema. Aplica eines de la teoria de grafs per a modelar problemes reals, analitza els resultats i avalua si són coherents amb les hipòtesis del problema | |
| FB3 |
Coneix i sap aplicar els principis bàsics del càlcul combinatori (principi de les caixes, principi de la multiplicació, principi d'inclusió exclusió). Coneix les tècniques de compteig del nombre de mostres ordenades o no ordenades, amb repetició o sense repetició. Coneix els nombres de Stirling, nombres de Bell, nombres combinatoris i nombres multinomials i aplicar a la solució de problemes. Coneix la tècnica de les funcions generadores i aplicar a la solució de problemes combinatoris. Calcula el nombre de desarranjaments d'un conjunt finit. Resol equacions recurrents lineals amb coeficients constants. Aplica les eines de la combinatòria bàsica i les recurrències lineals per a resoldre problemes de compteig, analitza els resultats i avalua si són coherents amb les hipòtesis del problema. Coneix els conceptes de graf simple, graf dirigit, pseudograf, multigraf, hipergraf i subgraf. Coneix el concepte d'isomorfisme de grafs i sap aplicar tests de no isomorfisme. Coneix les tècniques d'emmagatzematge de grafs. Determina si una seqüència de nombres enters positius és gràfica Determina el graf línia d'un graf. Calcula el complementari d'un graf. Calcula el producte (cartesià, corona i complet) de dos grafs. Calcula distàncies en grafs. Coneix la caracterització de grafs bipartits. Coneix les caracteritzacions dels arbres. Coneix els procediments d'exploració d'arbres binaris. Determina un arbre generador (minimal) d’un graf. Caracteritza grafs eulerians i sap determinar circuits eulerians. Coneix el concepte graf hamiltonià i aplica condicions necessàries per a que un graf sigui hamiltonià. Coneix el problema del viatjant de comerç i l'algorisme TSP aproximat. Coneix el teorema del flux-màxim tall-mínim. Coneix el concepte de graf planar. Coneix la fórmula d'Euler i el teorema de Kuratowski Coneix els conceptes de vèrtex coloració, aresta-coloració i nombre cromàtic. Aplica eines de la teoria de grafs per a modelar problemes reals, analitza els resultats i avalua si són coherents amb les hipòtesis del problema | |
| Tipus B | Codi | Resultats d'aprenentatge |
| B2 |
Coneix i sap aplicar els principis bàsics del càlcul combinatori (principi de les caixes, principi de la multiplicació, principi d'inclusió exclusió). Coneix les tècniques de compteig del nombre de mostres ordenades o no ordenades, amb repetició o sense repetició. Coneix els nombres de Stirling, nombres de Bell, nombres combinatoris i nombres multinomials i aplicar a la solució de problemes. Resol equacions recurrents lineals amb coeficients constants. Coneix els conceptes de graf simple, graf dirigit, pseudograf, multigraf, hipergraf i subgraf. Coneix el concepte d'isomorfisme de grafs i sap aplicar tests de no isomorfisme. Coneix les tècniques d'emmagatzematge de grafs. Determina si una seqüència de nombres enters positius és gràfica Calcula distàncies en grafs. Coneix les caracteritzacions dels arbres. Coneix el concepte de graf planar. Coneix els conceptes de vèrtex coloració, aresta-coloració i nombre cromàtic. | |
| Tipus C | Codi | Resultats d'aprenentatge |
| Continguts |
| Tema | Subtema |
| 1. Principis bàsics del càlcul combinatori | |
| 2. Mostres ordenades i no ordenades | |
| 3. Particions d'un conjunt. Nombres multinomials | |
| 4. Tècnica de les funcions generadores | |
| 5. Equacions recurrents lineals amb coeficients constants | |
| 6. Grafs: conceptes basics | |
| 7. Operacions amb grafs | |
| 8. Recorreguts i connectivitat |
|
| 9. Àrbres | |
| 10. Grafs eulerians i hamiltonians | |
| 11. Grafs planars | |
| 12. Coloració de grafs |
| Planificació |
| Metodologies :: Proves | ||||||||||
| Competències | (*) Hores a classe |
Hores fora de classe |
(**) Hores totals | |||||||
| Activitats Introductòries |
|
2 | 2.5 | 4.5 | ||||||
| Sessió Magistral |
|
23 | 34.5 | 57.5 | ||||||
| Resolució de problemes, exercicis a l'aula ordinària |
|
24 | 48 | 72 | ||||||
| Atenció personalitzada |
|
4 | 6 | 10 | ||||||
| Proves pràctiques |
|
6 | 0 | 6 | ||||||
| (*) En el cas de docència no presencial, són les hores de treball amb suport vitual del professor. (**) Les dades que apareixen a la taula de planificació són de caràcter orientatiu, considerant l’heterogeneïtat de l’alumnat | ||||||||||
| Metodologies |
| Descripció | |
| Activitats Introductòries | Presentació dels objectius, continguts, metodologia i criteris d'avaluació de l'assignatura |
| Sessió Magistral | Desenvolupament dels continguts |
| Resolució de problemes, exercicis a l'aula ordinària | Plantejament de problemes. Resolució de problemes. Resolució d'exercicis que s'han plantejat amb anterioritat. |
| Atenció personalitzada | Atenció personal a l'aula, ajudant a la resolució dels exercicis. Atenció personal al despatx per resoldre dubtes |
| Atenció personalitzada |
| Descripció |
|
Atenció personal (per resoldre dubtes) al despatx o a través de l’aplicació Teams de videoconferència o una altra eina virtual. |
| Avaluació |
| Metodologies | Competències | Descripció | Pes | ||||
| Proves pràctiques |
|
Tres proves individuals en le quals l’alumne ha de resoldre diferents problemes plantejats. Pes de cada prova: Prova 1: 40% Prova 2: 30% Prova 3. 30% |
100% | ||||
| Altres |
| Altres comentaris i segona convocatòria | |||
|
Les activitats avaluatives es desenvoluparan a través de l'espai Moodle. Avaluació segona convocatòria: una prova global de problemes i qüestions teòriques. |
|||
| Fonts d'informació |
| Bàsica |
Jonathan Gross, Jay Yellen, Graph theory and its applications , 2a, 2005
F. Comellas et al, Matemàtica discreta, 3a, 2001
Juan Alberto Rodriguez Velazquez, Matemática Discreta , , No |
||||||||
Els apunts de l'assignatura estan en el següent enllaç: http://deim.urv.cat/~juanalberto.rodriguez/ApuntesMDI.pdf |
|||||||||
| Complementària |
Joan Gimbert Quintilla, Apropament a la teoria de grafs i als seus algorismes , , 1998 |
||||||||
| Recomanacions |
| Assignatures que en continuen el temari | ||
|
||
| Assignatures que es recomana haver cursat prèviament | ||
|
||
| Altres comentaris | |
| Requereix una dedicació constant, per part de l’alumne, tenint molta cura d’entendre els conceptes i de dedicar un temps a la resolució de problemes. |
(*)La Guia docent és el document on es visualitza la proposta acadèmica de la URV. Aquest document és públic i no es pot modificar, llevat de casos excepcionals revisats per l'òrgan competent/ o degudament revisats d'acord amb la normativa vigent