2020/2021
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 |
La metodologia docent i l'avaluació proposades a la guia poden experimentar alguna modificació en funció de les restriccions a la presencialitat que imposin les autoritats sanitàries.
Professor/a de contacte
- Nom:
- Albert Ruíz Cirera
- Correu electrònic:
- Albert.Ruiz@uab.cat
Utilització d'idiomes a l'assignatura
- Llengua vehicular majoritària:
- català (cat)
- Grup íntegre en anglès:
- No
- Grup íntegre en català:
- Sí
- Grup íntegre en espanyol:
- No
Equip docent
- Lluís Alseda Soler
- Albert Ruíz Cirera
Prerequisits
Cal 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:
a) Una part teòrica en la que el professor introduirà els conceptes, mètodes i exemples relatius al temari de l’assignatura.
b) 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. Aquestes sessions es realitzaran a alguna de les aules d’informàtica de la facultat. 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. El lliurament serà durant el dia en que es realitza la pràctica.
També es proposaràn exercicis complementaris com activitat autònoma per ajudar la comprensió de la part aplicada de l'assignatura.
Activitats formatives
| Títol | Hores | ECTS | Resultats d'aprenentatge |
|---|---|---|---|
| Tipus: Dirigides | |||
| Assistir a les classes teòriques i pràctiques | 56 | 2,24 | 1, 7, 9, 13, 15 |
| Tipus: Supervisades | |||
| Realització de les practiques | 55 | 2,2 | 1, 2, 3, 4, 7, 9, 11, 12, 13, 14, 15 |
| Tipus: Autònomes | |||
| Resolució d'exercicis complementaris | 30 | 1,2 | 1, 2, 3, 4, 7, 9, 11, 12, 13, 14, 15 |
Avaluació
L'avaluació constarà de les següents activitats:
- un examen final recuperable, 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. Aquesta és una activitat d'avaluació continuada i no és recuperable
- 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.
Activitats d'avaluació
| 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.