Algorítmia i Combinatòria en Grafs. Mètodes Heurístics
Codi: 104388Crèdits: 6
2026/2027
| Titulació | Tipus | Curs |
|---|---|---|
| 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 combinatoris 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 avaluar la seva complexitat.
Resultats d'aprenentatge
- KM02 (Distingir els objectes propis del càlcul amb funcions i de les seves propietats i utilitats.) Distingir els objectes propis del càlcul amb funcions i de les seves propietats i utilitats.
- KM05 (Descriure els conceptes i objectes matemàtics propis de la teoria de grafs.) Descriure els conceptes i objectes matemàtics propis de la teoria de grafs.
- SM05 (Desenvolupar estratègies autònomes per a la resolució de problemes propis del càlcul numèric, la probabilitat i la teoria de grafs.) 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.
- Introducció als grafs combinatoris.
- 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 |
|---|---|---|---|
| Resolució d'exercicis complementaris | 30 | 1,2 | |
| Realització de les practiques | 62 | 2,48 | |
| Assistir a les classes teòriques i pràctiques | 49 | 1,96 |
Les sessions setmanals de l’assignatura es dividiran, normalment, en dues parts:
- Una part teòrica en la que el professor introduirà els conceptes, mètodes i exemples relatius al temari de l’assignatura.
- 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ó, perquè l'alumnat completi les enquestes d'avaluació de l'actuació del professorat i d'avaluació de l'assignatura.
Avaluació
Activitats d'avaluació continuada
| Títol | Pes | Hores | ECTS | Resultats d'aprenentatge |
|---|---|---|---|---|
| Treball pràctic individual | 35% | 5 | 0,2 | KM02, KM05, SM05 |
| Lliurament d'exercicis pràctics | 25% | 0 | 0 | KM02, KM05, SM05 |
| Examen final | 40% | 4 | 0,16 | KM02, KM05, SM05 |
L'avaluació constarà de les següents activitats:
- Un examen final individual, 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 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.
Les qualificacions finals seran:
- La mitjana ponderada segons el pes de cada part per a aquells estudiants que hagin tret 3,5 o més a totes les parts.
- El mínim entre 3,5 i la mitjana ponderada segons el pes de cada part per a aquells estudiants que hagin fet alguna de les avaluacions individuals i a alguna de les parts no arribin al 3,5.
- No avaluable per a aquells estudiants que no hagin fet cap de les avaluacions individuals.
A aquells que s'hagin avaluat de les tres parts (en particular, han d'haver lliurat el treball pràctic individual i fet l'examen final) i no superin l'assignatura, es podran presentar a una recuperació de l'examen final i el treball pràctic individual.
A les instruccions de cada lliurament es farà explícit quin ús de la Intel·ligència Artificial es pot fer. Saltar-se aquestes instruccions es considerarà frau acadèmic.
Aquesta assignatura no preveu el sistema d’avaluació única.
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. Avantatges inconvenients de cada una de les opcions: Wikipedia i notes del curs
- Cà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
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 | 1 | Català | segon quadrimestre | matí-mixt |
| (PLAB) Pràctiques de laboratori | 1 | Català | segon quadrimestre | matí-mixt |
| (SEM) Seminaris | 1 | Català | segon quadrimestre | matí-mixt |