Logo UAB

Matemàtica Discreta

Codi: 102772 Crèdits: 6
2024/2025
Titulació Tipus Curs
2502441 Enginyeria Informàtica FB 1

Professor/a de contacte

Nom:
Maria Merce Villanueva Gay
Correu electrònic:
merce.villanueva@uab.cat

Equip docent

Joaquin Borges Ayats
Joan Bartrina Rapesta
Maria Merce 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.


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

  1. Calcular la complexitat computaciona dels algorismes de grafs.
  2. Comprendre i dominar la matemàtica discreta, la lògica i la complexitat, des de un punt de vista matemàtic.
  3. Comprendre les propietats bàsiques dels grafs dirigits i no dirigits.
  4. Conèixer i aplicar el mètodes matemàtics de deducció i demostració.
  5. Demostrar la capacitat d'aplicar l'optimització de recorreguts de grafs.
  6. Desenvolupar un mode de pensament i raonament crítics.
  7. Identificar i reconèixer els algorismes bàsics de recorreguts de grafs.
  8. 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

 


Activitats formatives i Metodologia

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

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

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.

Nota: es reservaran 15 minuts d'una classe, dins del calendari establert pel centre/titulació, per a la complementació per part de l'alumnat de les enquestes d'avaluació de l'actuació del professorat i d'avaluació de l'assignatura/mòdul.


Avaluació

Activitats d'avaluació continuada

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

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, 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. Cal obtenir almenys 1 punt (dels 3 punts) en cada prova parcial per poder superar l'assignatura.

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

- Avaluació continua de seminaris, 2.5 punts. Es tractarà d'avaluar les activitats desenvolupades de forma tutoritzada en aquests seminaris. Els alumnes hauran de presentar els exercicis fets en grup durant les sessions. Cal obtenir almenys 1 punt (dels 2.5 punts) per poder superar l'assignatura.

- 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 unexamen finalde recuperació. No hi ha la possibilitatde 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 2 punts (dels 6 punts) 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:

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

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.

Programari

Es fa servir python3 i per seguir els seminaris cal portar un ordinador amb un navegador web.


Llista d'idiomes

Nom Grup Idioma Semestre Torn
(PAUL) Pràctiques d'aula 411 Català segon quadrimestre matí-mixt
(PAUL) Pràctiques d'aula 412 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
(SEM) Seminaris 411 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 431 Català segon quadrimestre matí-mixt
(SEM) Seminaris 432 Català segon quadrimestre matí-mixt
(SEM) Seminaris 433 Català segon quadrimestre matí-mixt
(SEM) Seminaris 434 Català segon quadrimestre matí-mixt
(SEM) Seminaris 451 Català segon quadrimestre matí-mixt
(SEM) Seminaris 452 Català segon quadrimestre matí-mixt
(SEM) Seminaris 453 Català segon quadrimestre matí-mixt
(SEM) Seminaris 471 Català segon quadrimestre matí-mixt
(SEM) Seminaris 472 Català segon quadrimestre matí-mixt
(SEM) Seminaris 473 Català segon quadrimestre matí-mixt
(TE) Teoria 41 Català 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