Aquesta versió de la guia docent és provisional fins que no finalitzi el període d’edició de les guies del nou curs.

Logo UAB

Algorítmia i Combinatòria en Grafs. Mètodes Heurístics

Codi: 104388 Crèdits: 6
2024/2025
Titulació Tipus Curs
2503740 Matemàtica Computacional i Analítica de Dades FB 1

Professor/a de contacte

Nom:
Albert Ruiz Cirera
Correu electrònic:
albert.ruiz@uab.cat

Equip docent

Albert Ruiz Cirera

Idiomes dels grups

Podeu consultar aquesta informació al final del document.


Prerequisits

És recomanable que l’estudiant hagi cursat Matemàtiques en els dos cursos de batxillerat i s’hagi examinat d’aquesta matèria a les PAU.


Objectius

  • Conèixer els grafs combinatòris i la seva terminologia.
  • Conèixer els diferents algorismes de busca i moviment en grafs.
  • Conèixer els tipus de dades dinàmics per a representació de grafs i la seva implemnentació en C.
  • Conèixer els algorismes bàsics de cerques óptimes en grafs i la seva complexitat.

Resultats d'aprenentatge

  1. KM02 (Coneixement) Distingir els objectes propis del càlcul amb funcions i de les seves propietats i utilitats.
  2. KM05 (Coneixement) Descriure els conceptes i objectes matemàtics propis de la teoria de grafs.
  3. SM05 (Habilitat) Desenvolupar estratègies autònomes per a la resolució de problemes propis del càlcul numèric, la probabilitat i la teoria de grafs.

Continguts

  • Algorismes combinatoris per a gràfs.
  • Grafs combinatòris i cerques en gràfs.
    • Teoria de grafs: introducció.
    • Cerca en grafs: Depth-first and Breadth-first.
    • Algorismes Greedy.
    • Recursivitat.
  • Tipus abstractes de dades: llistes dinàmiques i arbres.
  • Algorismes de representació de grafs. Avantatges i inconvenients de cada una de les opcions.
  • Tipus abstractes i dinàmics de dades per a grafs i la seva implementació en C.
  • Algorismes bàsics de cerques óptimes en grafs i la seva complexitat.
    • Càlcul de distàncies a partir de la latitud i la longitud.
    • Algorisme de Dijkstra per a rutes òptimes en grafs.
    • Algorisme A*: cerca heurística per a rutes òptimes en grafs.

Activitats formatives i Metodologia

Títol Hores ECTS Resultats d'aprenentatge
Tipus: Dirigides      
Assistir a les classes teòriques i pràctiques 49 1,96
Tipus: Supervisades      
Realització de les practiques 62 2,48
Tipus: Autònomes      
Resolució d'exercicis complementaris 30 1,2

Les sessions setmanals de l’assignatura es dividiran, normalment, en dues parts:

  1. Una part teòrica en la que el professor introduirà els conceptes, mètodes i exemples relatius al temari de l’assignatura.
  2. Una part pràctica en la que es proposarà als estudiants una sèrie de problemes o exercicis en els que es posarà de manifest i es treballarà de forma concreta el que s’ha vist a la part teòrica. Cada pràctica tindrà un enunciat diferent, que es publicarà al Campus Virtual i implicarà el lliurament de les respostes a algunes qüestions plantejades.

També es proposaràn exercicis complementaris com activitat autònoma per ajudar la comprensió de la part aplicada 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
Examen final 40% 4 0,16 KM02, KM05, SM05
Lliurament d'exercicis pràctics 25% 0 0 KM02, KM05, SM05
Treball pràctic individual 35% 5 0,2 KM02, KM05, SM05

L'avaluació constarà de les següents activitats:

  • Un examen final, que compta el 40% de la nota.
  • Un treball pràctic individual amb termini de lliurament on caldrà desenvolupar i implementar algorismes, que compta el 35% de la nota.
  • Lliurament, durant les sessions pràctiques, d'exercicis pràctics que es realitzaràn en grups de dos. Compten un 25% de la nota. Aquesta és una activitat d'avaluació continuada i no és recuperable.

La nota mínima a cada una de les tres activitats d'avaluació per a poder aprovar l'assignatura és de 3,5 punts sobre 10.

A aquells que, després d'avaluar-se de les tres parts, no superin l'assignatura, es podran presentar a una recuperació de l'examen final i el treball pràctic individual.

 


Bibliografia

  • Fundamentos de programación (algoritmos, estructuras de datos y objetos), Luis Joyanes, McGraw-Hill, Madrid etc. (2003).
  • Algoritmos y estructuras de datos – una perspectiva en C, Luis Joyanes y Ignacio Zahonero, McGraw-Hill, Madrid etc. (2004).
  • Grafs combinatòris i cerques en gràfs:Wikipedia
  • Tipus abstractes de dades i programació orientada a objectes: Llistes dinàmiques i arbres; Tipus abstractes i dinàmics de dades per a grafs i la seva implementació en C.
    • Notes del curs
    • Algoritmos + Estructura de datos = Programas, Niklaus Wirth, Ediciones del Castillo, Madrid (1986).
    • C algoritmos, programación y estructuras de datos, Luis Joyanes Aguilar et al., McGraw-Hill, Madrid etc. (2005).
  • Algorismes de representació de grafs. Avantatgews inconvenients de cada una de les opcions: Wikipedia i notes del curs
  • ACàlcul de distàncies a partir de la latitud i la longitud: Wikipoedia i notes del curs
  • Algorisme de Dijkstra per a rutes òptimes en grafs: Presentació d'Eric Demaine
  • Algorisme A*: cerca heurística per a rutes òptimes en grafs
    • Heuristics: Intelligent Search Strategies for Computer Problem Solving, Judea Pearl
      Addison-Wesley Pub (Sd) | ISBN: 0201055945 | 1984-04 | djvu (ocr) | 399 pages | 3.66 Mb
      Pagines: 33 to 46, 48, 49, 64, 65, 73--85.L'exemple a les pàgines 52--54 pot ser relevant.

Programari

C


Llista d'idiomes

Nom Grup Idioma Semestre Torn
(PLAB) Pràctiques de laboratori 1 Català segon quadrimestre matí-mixt
(SEM) Seminaris 1 Català segon quadrimestre matí-mixt
(TE) Teoria 1 Català segon quadrimestre matí-mixt