Any acadèmic

Logo UAB

Grafs, Topologia i Geometria Discreta

Codi: 104349 Crèdits: 6
2024/2025
Titulació Tipus Curs
2503758 Enginyeria de Dades OB 1

Professor/a de contacte

Nom:
Cesar Pablo Corcoles Briongos
Correu electrònic:
cesar.corcoles@uab.cat

Equip docent

Sebastià Mijares Verdú
David Marín Pérez

Idiomes dels grups

Podeu consultar aquesta informació al final del document.


Prerequisits

No hi ha prerequisits. En tot cas és aconsellable que l'alumnat domini les qüestions més bàsiques de la programació, i l'àlgebra fonamental com ara la teoria de conjunts i aplicacions. També és recomanable haver cursat les assignatures de Fonaments de Matemàtiques i Fonaments de Programació.

Objectius

La Matemàtica Discreta és l'àrea de les matemàtiques dedicada a l'estudi d'objectes discrets. En aquesta assignatura ens centrarem en alguns dels temes inclosos en aquesta àrea. Primer, ens centrarem en la teoria bàsica de grafs, optimització de recorreguts, algorismes sobre grafs i complexitat dels algorismes i problemes. Després, es veuran conceptes bàsics de topologia i geometria discreta, així com aspectes bàsics de geometria de corbes i superfícies.

Competències

  • Buscar, seleccionar i gestionar de manera responsable la informació i el coneixement.
  • Desenvolupar un pensament i un raonament crític i saber comunicar-los de manera efectiva, tant en les llengües pròpies com en anglès.
  • 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 destacats d'índole social, científica o ètica.
  • Representar les dades de forma adequada, tant des del punt de vista computacional com matemàtic.
  • Treballar cooperativament, en entorns complexos o incerts i amb recursos limitats, en un context multidisciplinari, assumint i respectant el rol dels diferents membres de l'equip.

Resultats d'aprenentatge

  1. Buscar, seleccionar i gestionar de manera responsable la informació i el coneixement.
  2. Desenvolupar un pensament i un raonament crític i saber comunicar-los de manera efectiva, tant en les llengües pròpies com en anglès.
  3. Identificar i interpretar els descriptors i les propietats fonamentals de les representacions basades en la geometria de les dades.
  4. Identificar i reconèixer els algoritmes bàsics de recorregut de grafs i demostrar la capacitat d'aplicar-ne l'optimització.
  5. Interpretar i aplicar les propietats bàsiques dels grafs dirigits i no dirigits.
  6. 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 destacats d'índole social, científica o ètica.
  7. Treballar cooperativament, en entorns complexos o incerts i amb recursos limitats, en un context multidisciplinari, assumint i respectant el rol dels diferents membres de l'equip.

Continguts

Part I
  1. Conceptes previs: conjunts, funcions i complexitat d'algorismes 
    1. Conjunts i operacions amb conjunts
    2. Producte cartesià i relacions binàries
    3. Elements de combinatòria
    4. Conjunts finits, infinits i numerables
    5. Complexitat d'algorismes i de problemes
    6. Funcions de complexitat. Complexitat polinòmica i no polinòmica

  2. Fonaments de grafs
    1. Definicions. Variants de grafs
    2. Camins, circuits i distàncies
    3. Graus i lema de les encaixades
    4. Subgrafs i tipus importants de grafs
    5. Seqüències gràfiques (Havel-Hakimi)
    6. Representació dels grafs

  3. Recorreguts, camins i arbres generadors òptims
    1. Exploració de grafs (DFS i BFS)
    2. Camins de cost mínim (Dijkstra, Floyd)
    3. Caracterització dels arbres
    4. Arbres generadors òptims (Kruskal)

  4. Planaritat i coloració
    1. Resultats bàsics
    2. Caracterització dels grafs planaris
    3. Coloració de grafs planaris

  5. Camins eulerians i hamiltonians

  6. Complexitat algorítmica

Part II

  1. Topologia
    1. Espai topològic i propietats bàsiques
    2. Isomorfismes
    3. Simplexs, mallats i grafs com a codificadors d'una topologia discreta

  2. Geometria de corbes i superfícies
    1. Corbes parametritzades
    2. Paràmetre arc, parametritzacions implícites i corbes de nivell
    3. Descriptors fonamentals d’una corba a l’espai: Triedre de Frenet, torsió i curvatura

  3. Geometria de superfícies
    1. Superfícies parametritzades
    2. Espai tangent
    3. Primera i segona formes fonamentals
    4. Difeomorfismes
    5. Geodèsiques i camins de cost mínim

Activitats formatives i Metodologia

Títol Hores ECTS Resultats d'aprenentatge
Tipus: Dirigides      
Classes de problemes 12 0,48 2, 3, 4, 5, 1, 6
Classes de teoria 26 1,04 2, 3, 4, 5, 1, 6
Pràctiques 12 0,48 2, 3, 4, 5, 1, 6, 7
Tipus: Supervisades      
Preparació de problemes i pràctiques 12,5 0,5 2, 3, 4, 5, 1, 6, 7
Tutories i consultes 5 0,2 2, 3, 4, 5, 1, 6
Tipus: Autònomes      
Preparació examen final 25 1 2, 3, 4, 5, 1, 6
Treball personal 50 2 2, 3, 4, 5, 1, 6

Els continguts curriculars es treballaran a les classes de teoria. El treball personal independent serà necessari per aprofitar aquestes sessions, que no es basaran en la lectura dels materials obligatoris i disponibles al CV. Aquests hauran de ser treballats abans de les sessions per maximitzar l'aprofitament.

A les classes de problemes, es treballaran problemes d'una selecció, basada en els continguts de l'assignatura. Es demanarà treball personal abans d'aquestes sessions, concretament d'una llista de problemes preacordada.

A les pràctiques, s'ajudarà a obtenir experiència aplicada en temes relacionats amb l'assignatura. El desenvoluparan microprojectes com a part del treball personal i hi haurà lliurables obligatoris.

Nota: es farà docència predominantment en anglès.

 

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 3, 4, 5, 1, 6
Lliurament entregables de pràctiques 25% 3 0,12 2, 3, 4, 5, 1, 6, 7
Proves basades en exercicis a la classe de problemes 15% 1,5 0,06 2, 3, 4, 5, 1

La comunicació de les dates d'avaluació continua (i qualsevol canvi) es farà al Campus Virtual.

L'avaluació de l'assignatura, sobre 10 punts, es farà de la següent forma:

Teoria (6 punts):

Dos exàmens parcials durant el curs, 6 punts (3.5 corresponen al primer parcial i 2.5 al segon). 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. La primera prova serà després dels primers tres capítols. La segona, al finalitzar les classes.

Examen de re-avaluació, 6 punts. En cas de no haver aprovat amb els parcials, es farà un sol examen final de tota la part de teoria, amb format similar al dels parcials.

Problemes (1.5 punts):

Proves basades en exercicis, a les classes de problemes, 1.5 punts (1.2 corresponen a la primera part de l'assignatura i 0.3 a la segona). Es tractarà de solucionar qüestionaris (poden ser online) i resolució de problemes per aplicació dels algorismes vistos a classe. Forma part de l'avaluació continuada.

Pràctiques (2.5 punts):

Pràctiques: 2.5 punts (1.8 corresponen a la primera part de l'assignatura i 0.7 a la segona). Hi haurà lliurables obligatoris, degudament anunciats al CV. La nota final serà la mitjana de la dels lliurables.

Cal obtenir una nota global de 5 per superar l’assignatura. En cas de presentar-se a alguna de les proves parcials ja no es pot ser considerat com a "no avaluable". Qui es presenta a l'examen final tampoc no pot ser considerat com a "no avaluable". No hi haurà cap tractament especial per a l'alumnat repetidor, excepte que el projecte de seminaris/pràctiques es podrà convalidar de l'any anterior. Per obtenir una matrícula d’honor cal tenir una nota global de 9 o superior. En cas que hi hagi més notes per sobre del 9 que al màxim de matrícules d’honor assignables (5% del total) s'atorgarà la qualificació "matrícula d'honor" a les millors notes, amb prioritat per a aquells que no fan l'examen de recuperació.

És important tenir en compte que no s’admetran activitats d’avaluació per a cap estudiant en una data o hora diferent de l’establerta, llevat per causes justificades degudament avisades abans de l’activitat i amb el consentiment previ del professor. En la resta de casos, si no s’ha realitzat cap activitat, aquesta no es podrà tornar a avaluar.

En el cas de la resolució d'exercicis, es pot sol·licitar una revisió després de la data de l'activitat o la data de tancament del qüestionari. Per a la resta d’activitats d’avaluació, s’indicarà un lloc, data i hora de revisió que permetrà als estudiants revisar l’activitat amb el professor. En aquest context, els estudiants poden discutir la nota d’activitat atorgada pels professors responsables de la matèria. Si els estudiants no participen en aquesta revisió, no hi haurà més oportunitats disponibles.

Avaluació única

Si es vol seguir el model d'avaluació única, es realitzarà una prova de síntesi, amb un pes del 50% i es proposaran exercicis (similars als realitzats a les classes de problemes, amb un pes del 25%) i pràctiques (similars a les realitzades a l'avaluació continuada, també amb un pes del 25%) que podran ser lliurats fins al dia de l'examen final, per a la seva avaluació juntament amb aquest.

Plagi i altres irregularitats acadèmiques

Sense perjudici d'altres mesures disciplinàries ques'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). Per exemple, plagiar, copiar, deixar copiar, etc., a una activitat d'avaluació, implicarà suspendre aquesta activitat d'avaluació 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 aprovar l'assignatura, aquesta assignatura quedarà suspesa directament, sense oportunitat de recuperar-la enel mateix curs.

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.
  • 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.
  • F.S. Roberts. Applied combinatorics. Prentice-Hall, 1984.
  • M. P. do Carmo. Geometría diferencial de curvas y superficies. Alianza Editorial, 1995.
  • J. R. Munkres, Topología, Prentice-Hall, 2a edición, 2002.
  • M. Spivak. Cálculo en variedades. Editorial Reverté, 2a edición, 1970.
  • W. A. Sutherland, Introduction to metric and topological spaces, 2nd edition, Oxford University Press, 2009.

Programari

Les pràctiques de l'assignatura es faran en Python.


Llista d'idiomes

Nom Grup Idioma Semestre Torn
(PAUL) Pràctiques d'aula 811 Català segon quadrimestre matí-mixt
(PAUL) Pràctiques d'aula 812 Català segon quadrimestre matí-mixt
(PLAB) Pràctiques de laboratori 811 Català segon quadrimestre matí-mixt
(PLAB) Pràctiques de laboratori 812 Català segon quadrimestre matí-mixt
(PLAB) Pràctiques de laboratori 813 Català segon quadrimestre matí-mixt
(TE) Teoria 81 Català segon quadrimestre matí-mixt