Algorítmia i Combinatòria en Grafs. Mètodes Heurístics
Codi: 104388 Crèdits: 62024/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
- KM02 (Coneixement) Distingir els objectes propis del càlcul amb funcions i de les seves propietats i utilitats.
- KM05 (Coneixement) Descriure els conceptes i objectes matemàtics propis de la teoria de grafs.
- 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:
- 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ó, 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 |