Matemàtica Discreta
Codi: 102772 Crèdits: 6| Titulació | Tipus | Curs | Semestre |
|---|---|---|---|
| 2502441 Enginyeria Informàtica | FB | 1 | 2 |
Professor/a de contacte
- Nom:
- Mercè Villanueva Gay
- Correu electrònic:
- Merce.Villanueva@uab.cat
Utilització d'idiomes a l'assignatura
- Llengua vehicular majoritària:
- català (cat)
- Grup íntegre en anglès:
- No
- Grup íntegre en català:
- Sí
- Grup íntegre en espanyol:
- No
Equip docent
- Joaquim Borges Ayats
- Joan Bartrina Rapesta
- Carlos Vela Cabello
- Mercè Villanueva Gay
- Bernat Gaston Braso
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.
Competències
- Adquirir hàbits de pensament.
- 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.
- Conèixer les matèries bàsiques i les tecnologies que capacitin per a l'aprenentatge i el desenvolupament de nous mètodes i tecnologies, així com d'aquelles que els dotin d'una gran versatilitat per a adaptar-se a noves situacions.
Resultats d'aprenentatge
- Calcular la complexitat computaciona dels algorismes de grafs.
- Comprendre i dominar la matemàtica discreta, la lògica i la complexitat, des de un punt de vista matemàtic.
- Comprendre les propietats bàsiques dels grafs dirigits i no dirigits.
- Conèixer i aplicar el mètodes matemàtics de deducció i demostració.
- Demostrar la capacitat d'aplicar l'optimització de recorreguts de grafs.
- Desenvolupar un mode de pensament i raonament crítics.
- Identificar i reconèixer els algorismes bàsics de recorreguts de grafs.
- Reconèixer i identificar els models matemàtics d'un problema d'enginyeria.
Continguts
1. Conceptes previs: conjunts, funcions i complexitat d’algorismes
1.1. Conjunts i operacions amb conjunts
1.2. Producte cartesià i relacions binàries
1.3. Elements de combinatòria
1.4. Conjunts finits, infinits i numerables
1.5. Complexitat d’algorismes i de problemes
1.6. Funcions de complexitat. Complexitat polinòmica i no polinòmica
2. Fonaments de grafs
2.1. Definicions. Variants de grafs
2.2. Camins, circuits i distàncies
2.3. Graus i lema de les encaixades
2.4. Subgrafs i tipus importants de grafs
2.5. Seqüències gràfiques (Havel-Hakimi)
2.6. Representació dels grafs
3. Recorreguts, camins i arbres generadors òptims
3.1. Exploració de grafs (DFS i BFS)
3.2. Camins de cost mínim (Dijkstra, Floyd)
3.3. Caracterització dels arbres
3.4. Arbres generadors òptims (Kruskal)
4. Planaritat i coloració
4.1. Resultats bàsics
4.2. Caracterització dels grafs planaris
4.3. Coloració de grafsplanaris
4.4. Annex: el polinomi cromàtic
5. Grafs eulerians i grafs hamiltonians
5.1. Camins i circuits eulerians
5.2. Mètode de Fleury (o bé Hierholzer)
5.3. El problema del carter xinès
5.4. Camins i circuits hamiltonians
5.5. El problema del viatjant
6. Complexitat computacional
6.1. Problemes de decisió, de càlcul i d’optimització
6.2. Problemes resolubles i irresolubles
6.3. Classes de complexitat. Problemes NP-Complets
6.4. Altres problemes intractables
Metodologia
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: planteig de casos reals, es realitzarà un projecte per grups que relaciona pàgines web i teoria de grafs. S'utilitzarà el Campus Virtual com a mitjà de comunicació entre el professorat i els estudiants (material, actualitzacions, noticies, etc.)
COMPETÈNCIES TRANSVERSALS
- T01.01. Desenvolupar un mode de pensament i raonament crítics. El projecte en grup desenvolupat als seminaris sobre preguntes que formula el professor, en tractar d'aplicacions al món real, suposa necessàriament que els estudiants desenvolupin el raonament crític i la capacitat d'anàlisi, síntesi i abstracció per poder modelitzar situacions reals com a problemes de teoria de grafs. Cal tenir en compte que les activitats desenvolupades en els seminaris tenen un pes d'un 25% en l'avaluació global de l'assignatura.
Activitats formatives
| Títol | Hores | ECTS | Resultats d'aprenentatge |
|---|---|---|---|
| Tipus: Dirigides | |||
| Classes d'exercicis | 15 | 0,6 | 2, 3, 4, 5, 7, 8 |
| Classes de teoria | 30 | 1,2 | 1, 2, 3, 4, 5, 7, 8 |
| Seminaris | 5 | 0,2 | 2, 3, 6, 7, 8 |
| Tipus: Supervisades | |||
| Preparació d'exercicis i seminaris | 12,5 | 0,5 | 1, 2, 3, 4, 5, 6, 7, 8 |
| Tutories i consultes | 5 | 0,2 | 1, 2, 3, 4, 5, 6, 7, 8 |
| Tipus: Autònomes | |||
| Preparació examen final | 25 | 1 | 1, 2, 3, 4, 5, 7, 8 |
| Treball personal | 50 | 2 | 1, 2, 3, 4, 5, 7, 8 |
Avaluació
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, sobre 10 punts, es farà de la següent forma:
- Dos exàmens parcials durant el curs (3+3), 6 punts. Com a part de l'avaluació continuada, el primer parcial es realitzarà durant les classes; i el segon serà en la data especificada pel coordinador. 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.
- Proves basades en exercicis a classes de problemes, 1.5 punts. Com a part de l'avaluació continuada, es tractarà de solucionar qüestionaris (poden ser on-line) i resolució de problemes mitjançant l'aplicació dels algorismes vistos. Les activitats i exercicis que no siguin on-line es realitzaran durant les classes de problemes.
- Lliurament d'un petit projecte en grup que s'haurà anat treballant en els seminaris, 2.5 punts. Com a part de l'avaluació continuada, es tractarà d’avaluar les activitats desenvolupades de forma tutoritzada en aquests seminaris. Per al lliurament hi haurà una data de recuperació.
- Examen final, 6 punts. 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.
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:
1. la còpia parcial o total de qualsevol activitat d'avaluació;
2. permetre a altres copiar;
3. presentar un treball en grup que no hagi estat realitzat enterament pels membres del grup;
4. 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;
5. 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 una puntuació de com a mínim 5 punts. 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 el projecte 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.
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
Activitats d'avaluació
| Títol | Pes | Hores | ECTS | Resultats d'aprenentatge |
|---|---|---|---|---|
| Dues proves parcials | 60% | 3 | 0,12 | 1, 2, 3, 4, 5, 7, 8 |
| Proves basades en exercicis a la classe de problemes | 15% | 0,5 | 0,02 | 2, 3, 4, 5, 7, 8 |
| Proves en grup a seminaris | 25% | 4 | 0,16 | 2, 3, 6, 7, 8 |
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.