2023/2024
Algorítmia i Combinatòria en Grafs. Mètodes Heurístics
Codi: 104388
Crèdits: 6
Titulació |
Tipus |
Curs |
Semestre |
2503740 Matemàtica Computacional i Analítica de Dades |
FB |
1 |
2 |
Idiomes dels grups
Podeu accedir-hi des d'aquest enllaç. Per consultar l'idioma us caldrà introduir el CODI de l'assignatura. Tingueu en compte que la informació és provisional fins a 30 de novembre de 2023.
Equip docent
- Albert Ruiz Cirera
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.
Competències
- Aplicar l'esperit crític i el rigor per validar o refutar arguments tant propis com d'altres.
- Avaluar de manera crítica i amb criteris qualitat el treball realitzat.
- Demostrar una elevada capacitat d'abstracció i de traducció de fenòmens i comportaments a formulacions matemàtiques.
- Formular hipòtesis i imaginar estratègies per confirmar-les o refutar-les.
- Que els estudiants hagin demostrat que comprenen i tenen coneixements en una àrea d'estudi que parteix de la base de l'educació secundària general, i se sol trobar a un nivell que, si bé es basa en llibres de text avançats, inclou també alguns aspectes que impliquen coneixements procedents de l'avantguarda d'aquell camp d'estudi.
- Que els estudiants puguin transmetre informació, idees, problemes i solucions a un públic tant especialitzat com no especialitzat.
- 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.
- Relacionar objectes matemàtics nous amb altres de coneguts i deduir-ne les propietats.
- Treballar cooperativament en un context multidisciplinar asumiendo y respetando el rol de los diferentes miembros del equipo.
- Utilitzar eficaçment la bibliografia i els recursos electrònics per obtenir informació.
Resultats d'aprenentatge
- Aplicar l'esperit crític i el rigor per validar o refutar arguments tant propis com d'altres.
- Avaluar de manera crítica i amb criteris de qualitat el treball desenvolupat.
- Avaluar els avantatges i els inconvenients de l'ús del càlcul i de l'abstracció.
- Contrastar, si és possible, l'ús del càlcul amb l'ús de l'abstracció per resoldre un problema.
- Descriure els conceptes i els objectes matemàtics propis de l'assignatura.
- Desenvolupar estratègies autònomes per a la resolució de problemes propis del curs, discriminar els problemes rutinaris dels no-rutinaris i dissenyar i avaluar una estratègia per resoldre un problema.
- Explicar idees i conceptes matemàtics propis del curs, així com comunicar a tercers raonaments propis.
- Identificar les idees essencials de les demostracions d'alguns teoremes bàsics i saber-les adaptar per obtenir altres resultats.
- Llegir i comprendre un text de matemàtiques del nivell del curs.
- Que els estudiants hagin demostrat que comprenen i tenen coneixements en una àrea d'estudi que parteix de la base de l'educació secundària general, i se sol trobar a un nivell que, si bé es basa en llibres de text avançats, inclou també alguns aspectes que impliquen coneixements procedents de l'avantguarda d'aquell camp d'estudi.
- Que els estudiants puguin transmetre informació, idees, problemes i solucions a un públic tant especialitzat com no especialitzat.
- 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.
- Redactar, de manera ordenada i amb precisió, petits textos matemàtics (exercicis, resolució de qüestions de teoria, etc.).
- Treballar cooperativament en un context multidisciplinari assumint i respectant el rol dels diferents membres de l'equip.
- Utilitzar eficaçment la bibliografia i els recursos electrònics per obtenir informació.
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 i programació orientada a objectes: Llistes dinàmiques i arbres.
- Algorismes de representació de grafs. Avantatgews 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.
Metodologia
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ó
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.
Activitats d'avaluació continuada
Títol |
Pes |
Hores |
ECTS |
Resultats d'aprenentatge |
Examen final |
40% |
4
|
0,16 |
5, 7, 8, 9, 12, 13
|
Lliurament d'exercicis pràctics |
25% |
0
|
0 |
1, 2, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15
|
Treball pràctic individual |
35% |
5
|
0,2 |
1, 2, 3, 4, 5, 6, 7, 9, 11, 12, 13
|
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.