
Matemàtica Discreta
Codi: 102772Crèdits: 6
| Titulació | Tipus | Curs |
|---|---|---|
| Enginyeria Informàtica | FB | 1 |
Professor/a de contacte
- Nom :
- Mercè Villanueva Gay
- Correu electrònic :
- merce.villanueva@uab.cat
Equip docent
- Miguel Hernández Cabronero
- Joan Bartrina Rapesta
- Mercè Villanueva Gay
- Bernat Gaston Braso
Idiomes dels grups
Podeu consultar aquesta informació al final del document.
Prerequisits
No hi ha prerequisits. En tot cas és aconsellable que l’estudiant domini les qüestions més bàsiques de l’àlgebra fonamental com ara la teoria de conjunts i aplicacions.
Objectius
La Matemàtica Discreta és l'àrea de les matemàtiques dedicada a l'estudi d'objectes discrets. Alguns dels temes dels que s'ocupa són: combinatòria, teoria de grafs, disseny i anàlisi d’algorismes relacionats amb aquests problemes, criptografia, teoria de codis correctors d'errors, optimització, etc. De tots aquests temes, ens centrarem en: teoria bàsica de grafs, optimització de recorreguts, algorismes sobre grafs i complexitat dels algorismes i problemes.
Resultats d'aprenentatge
- CM01 (Fer servir els coneixements i les habilitats relacionats amb la matemàtica discreta per a la resolució de problemes amb equips multidisciplinaris.) Fer servir els coneixements i les habilitats relacionats amb la matemàtica discreta per a la resolució de problemes amb equips multidisciplinaris.
- KM01 (Explicar procediments algorítmics relacionats amb els grafs, els conjunts i la combinatòria.) Explicar procediments algorítmics relacionats amb els grafs, els conjunts i la combinatòria.
- SM01 (Aplicar coneixements de grafs i combinatòria en la resolució de problemes d’enginyeria informàtica.) Aplicar coneixements de grafs i combinatòria en la resolució de problemes d’enginyeria informàtica.
Continguts
1. Conceptes previs: conjunts, funcions i complexitat d’algorismes
- Conjunts i operacions amb conjunts
- Producte cartesià i relacions binàries
- Elements de combinatòria
- Conjunts finits, infinits i numerables
- Complexitat d’algorismes i de problemes
- Funcions de complexitat. Complexitat polinòmica i no polinòmica
2. Fonaments de grafs
- Definicions. Variants de grafs
- Camins, circuits i distàncies
- Graus i lema de les encaixades
- Subgrafs i tipus importants de grafs
- Seqüències gràfiques (Havel-Hakimi)
- Representació dels grafs
3. Recorreguts, camins i arbres generadors òptims
- Exploració de grafs (DFS i BFS)
- Camins de cost mínim (Dijkstra, Floyd)
- Caracterització dels arbres
- Arbres generadors òptims (Kruskal)
4. Planaritat i coloració
- Resultats bàsics
- Caracterització dels grafs planaris
- Coloració de grafsplanaris
- Annex: el polinomi cromàtic
5. Grafs eulerians i grafs hamiltonians
- Camins i circuits eulerians
- Mètode de Fleury (o bé Hierholzer)
- El problema del carter xinès
- Camins i circuits hamiltonians
- El problema del viatjant
6. Modelatge i resolució de problemes
- Abstracció i formulació de problemes amb grafs
- Exemples de modelatge i resolució de problemes reals
Activitats formatives i Metodologia
| Títol | Hores | ECTS | Resultats d'aprenentatge |
|---|---|---|---|
| Preparació d'exercicis i seminaris | 12,5 | 0,5 | CM01, KM01, SM01 |
| Classes de teoria | 30 | 1,2 | KM01 |
| Seminaris | 5 | 0,2 | CM01 |
| Preparació examen final | 25 | 1 | KM01, SM01 |
| Tutories i consultes | 5 | 0,2 | CM01, KM01, SM01 |
| Treball personal | 50 | 2 | CM01, KM01, SM01 |
| Classes d'exercicis | 15 | 0,6 | KM01, SM01 |
Les classes de teoria es basaran en lliçons magistrals, si bé s’intentarà fomentar la participació de l’estudiant en la resolució d’exemples, càlculs de complexitat, etc. A les classes de problemes, se seguirà una llista d’exercicis. Es fomenta que els estudiants intentin solucionar els exercicis abans. Es fomentarà també l’exposició de la resolució de problemes per part dels estudiants. En els seminaris es tractaran temes relacionats en profunditat: es realitzaran diversos exercicis sobre algoritmes explicats a teoria aplicats a casos reals i en format pràctic. S'utilitzarà el Campus Virtual com a mitjà de comunicació entre el professorat i els estudiants (material, actualitzacions, noticies, etc.)
Avaluació
Activitats d'avaluació continuada
| Títol | Pes | Hores | ECTS | Resultats d'aprenentatge |
|---|---|---|---|---|
| Dues proves parcials | 60% | 3 | 0,12 | KM01, SM01 |
| Proves basades en exercicis a la classe de problemes | 15% | 0,5 | 0,02 | KM01, SM01 |
| Proves en grup a seminaris | 25% | 4 | 0,16 | CM01, KM01, SM01 |
Aquesta assignatura no preveu el sistema d'avaluació única.
Les dates per a l'avaluació continuada es publicaran al Campus Virtual (CV). Si es produeix algun canvi de programació en les dates, aquest serà comunicat als estudiants a través del CV, ja que s'entén que el CV és el mecanisme habitual de comunicació entre el professorat i els estudiants.
L’avaluació de l’assignatura es farà de la següent forma:
- Dos exàmens parcials durant el curs (30% + 30% de la nota final). El primer parcial serà al final dels tres primers temes, i el segon al final de curs. Aquestes proves individuals consistiran majoritàriament en exercicis a l’estil dels que s’han anat fent durant el curs. Una part menor consistirà en qüestions més teòriques. Cal obtenir almenys un 3 sobre 10 en cada prova parcial per poder superar l'assignatura.
- Proves basades en exercicis a classes de problemes (15% de la nota final). Com a part de l'avaluació continuada, es durant a terme qüestionaris (que poden ser on-line) i exercicis de resolució de problemes mitjançant l'aplicació dels conceptes treballats a classe. Les activitats i exercicis que no siguin on-line es realitzaran durant les classes de teoria o problemes. Aquests exercicis no seran recuperables.
- Avaluació contínua de seminaris (25% de la nota final). S’avaluaran les activitats en grup desenvolupades de manera tutoritzada en aquests seminaris (50 % de la nota). La superació dels seminaris requerirà també l’aprovació de les proves individuals realitzades durant les sessions (50% de la nota). En aquestes proves s’avaluarà l’assimilació tant dels conceptes teòrics com pràctics associats a cada activitat. Per poder superar aquesta part de l’assignatura, caldrà obtenir almenys un 4 sobre 10 i assistir, com a mínim, al 80% de les sessions. En cas de no superar-la, caldrà realitzar una prova individual, que representarà el 100% de la qualificació d’aquesta part, en la qual també s’haurà d’obtenir un mínim de 4 sobre 10.
- Examen final (60% de la nota final). Aquells estudiants que no hagin superat l'assignatura a través dels dos exàmens parcials, tindran l'opció de realitzar un examen final de recuperació. No hi ha la possibilitat de recuperar els exàmens parcials per separat, l'examen final cobreix tots els temes del curs. Consistirà en major part en exercicis de l'estil dels que s'han realitzat durant el curs; i una part més petita constarà de qüestions teòriques. Cal obtenir almenys un 3 sobre 10 per poder superar l'assignatura.
Sense perjudici d'altres mesures disciplinàries que s'estimin oportunes, i d'acord amb la normativa acadèmica vigent, les irregularitats comeses per un estudiant que puguin conduir a una variació de la qualificació es qualificaran amb un zero (0). Les activitats d'avaluació qualificades d'aquesta forma i per aquest procediment no seran recuperables. Si és necessari superar qualsevol d'aquestes activitats d'avaluació per a superar la matèria, aquest curs se suspendrà directament, sense oportunitat de recuperar en el mateix curs. Les irregularitats contemplades inclouen, entre d'altres:
- la còpia parcial o total de qualsevol activitat d'avaluació;
- permetre a altres copiar;
- presentar un treball en grup que no hagi estat realitzat enterament pels membres del grup;
- presentar qualsevol material preparat per una altra persona com si fos propi, fins i tot si aquests materials són traduccions o adaptacions, incloent treballs que no són originals o exclusius de l'estudiant;
- disposar de dispositius de comunicació (com ara telèfons mòbils, rellotges intel·ligents, etc.) accessibles durant la realització dels exàmens individuals teòrics o pràctics.
Per superar l'assignatura es requereix que l'avaluació de cadascuna de les parts superi el mínim exigit i que l'avaluació total sigui com a mínim de 5 punts. En cas de no superar l'assignatura degut a que alguna de les activitats d'avaluació no arriba a la nota mínima requerida, la nota numèrica de l'expedient serà el valor menor entre 4.5 i la mitjana ponderada de les notes. Si un estudiant es presenta a alguna de les proves parcials ja no pot ser considerat com a \"no avaluable\". Si un estudiant es presenta a l'examen final tampoc pot ser considerat com a "no avaluable". No hi haurà cap tractament especial per als estudiants repetidors, excepte que la nota de seminaris es podrà convalidar de l'any anterior. S'atorgarà la qualificació "matrícula d'honor" a tots aquells estudiants que tinguin un excel·lent i entrin dintre del percentatge que la normativa permeti de les millors notes, amb prioritat per a aquells que no fan l'examen de recuperació.
En el cas de les proves basades en resolucions d'exercici, es pot sol·licitar una revisió després de la data de l'activitat o la data de tancament del qüestionari. Per a totes les altres activitats d’avaluació, s’indicarà un lloc, data i hora de revisió que permetran als estudiants revisar l’activitat. Si els estudiants no participen en aquesta revisió, no tindreu cap altra oportunitat disponible.
El protocol de “sol·licitud de reprogramació d’activitats d’avaluació” es troba disponible al web de l’Escola d’Enginyeria i és aplicable en els casos descrits als criteris i instruccions d’avaluació del centre.
En aquesta assignatura es permet l'ús de tecnologies d'Intel·ligència Artificial (IA) exclusivament en tasques de suport a l'aprenentatge, com ara la cerca bibliogràfica o d’informació, la correcció de textos o l'estudi personal. No es permet l'ús de tecnologies d'IA per a la resolució d'activitats lliurables (és a dir, les pràctiques, els exercicis lliurables, o els exàmens). Qualsevol treball que inclogui fragments generats amb IA serà considerat una falta d'honestedat acadèmica i pot comportar una penalització parcial o total en la nota de l'activitat, o sancions majors en casos de gravetat.
Normativa Acadèmica de la UAB aprovada pel Consell de Govern de la UAB (19/03/2015) - Títol IV- Avaluació: http://www.uab.cat/doc/TR_Normativa_Academica_Plans_Nous
Bibliografia
- J.M. Basart. Grafs: fonaments i algorismes. Manuals de la UAB, 13. Servei de publicacions de la UAB, 1994.
- C. Berge. Graphs. North-Holland, 1991.
- N.L. Biggs. Matemàtica discreta. Vicens-Vives, 1994.
- N. Christofides. Graph theory, an algorithmic approach. Academic Press, 1975.
- M.R. Garey, D.S. Johnson. Computers and intractability. A guide to the theory of NP-Completeness. W.H. Freeman, 1979.
- F.S. Roberts. Applied combinatorics. Prentice-Hall, 1984.
- J. Gimbert, R. Moreno, J.M. Ribó, M. Valls. Apropament a la teoria de grafs i als seus algorismes. Eines 23, edicions de la UdL, 1998.
- R. J. Wilson, Introduction to graph theory. 5th edition. Pearson, 2010.
Programari
Grups i idiomes de l'assignatura
La informació proporcionada és provisional fins al 30 de novembre. A partir d'aquesta data, podreu consultar l'idioma de cada grup a través d'aquest enllaç. Per accedir a la informació, caldrà introduir el CODI de l'assignatura
| Tipus de docència | Grup | Idioma | Semestre | Torn |
|---|---|---|---|---|
| (TE) Teoria | 41 | Espanyol | segon quadrimestre | matí-mixt |
| (TE) Teoria | 43 | Català | segon quadrimestre | matí-mixt |
| (TE) Teoria | 45 | Català | segon quadrimestre | tarda |
| (TE) Teoria | 47 | Català | segon quadrimestre | tarda |
| (PAUL) Pràctiques d'aula | 411 | Català | segon quadrimestre | matí-mixt |
| (SEM) Seminaris | 411 | Català | segon quadrimestre | matí-mixt |
| (PAUL) Pràctiques d'aula | 412 | Català | segon quadrimestre | matí-mixt |
| (SEM) Seminaris | 412 | Català | segon quadrimestre | matí-mixt |
| (SEM) Seminaris | 413 | Català | segon quadrimestre | matí-mixt |
| (SEM) Seminaris | 414 | Català | segon quadrimestre | matí-mixt |
| (SEM) Seminaris | 415 | Català | segon quadrimestre | matí-mixt |
| (SEM) Seminaris | 416 | Català | segon quadrimestre | matí-mixt |
| (SEM) Seminaris | 417 | Català | segon quadrimestre | matí-mixt |
| (SEM) Seminaris | 418 | Català | segon quadrimestre | matí-mixt |
| (SEM) Seminaris | 419 | Català | segon quadrimestre | matí-mixt |
| (SEM) Seminaris | 420 | Català | segon quadrimestre | matí-mixt |
| (SEM) Seminaris | 421 | Català | segon quadrimestre | matí-mixt |
| (SEM) Seminaris | 422 | Català | segon quadrimestre | matí-mixt |
| (SEM) Seminaris | 423 | Català | segon quadrimestre | matí-mixt |
| (SEM) Seminaris | 424 | Català | segon quadrimestre | matí-mixt |
| (SEM) Seminaris | 425 | Català | segon quadrimestre | matí-mixt |
| (PAUL) Pràctiques d'aula | 431 | Català | segon quadrimestre | matí-mixt |
| (PAUL) Pràctiques d'aula | 432 | Català | segon quadrimestre | matí-mixt |
| (PAUL) Pràctiques d'aula | 451 | Català | segon quadrimestre | tarda |
| (PAUL) Pràctiques d'aula | 452 | Català | segon quadrimestre | tarda |
| (PAUL) Pràctiques d'aula | 471 | Català | segon quadrimestre | tarda |