Logo UAB
2022/2023

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

Professor/a de contacte

Nom:
Lluís Alseda Soler
Correu electrònic:
lluis.alseda@uab.cat

Utilització d'idiomes a l'assignatura

Llengua vehicular majoritària:
català (cat)
Grup íntegre en anglès:
No
Grup íntegre en català:
Grup íntegre en espanyol:
No

Equip docent

Lluís Alseda Soler
Albert Ruiz 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

  1. Aplicar l'esperit crític i el rigor per validar o refutar arguments tant propis com d'altres.
  2. Avaluar de manera crítica i amb criteris de qualitat el treball desenvolupat.
  3. Avaluar els avantatges i els inconvenients de l'ús del càlcul i de l'abstracció.
  4. Contrastar, si és possible, l'ús del càlcul amb l'ús de l'abstracció per resoldre un problema.
  5. Descriure els conceptes i els objectes matemàtics propis de l'assignatura.
  6. 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.
  7. Explicar idees i conceptes matemàtics propis del curs, així com comunicar a tercers raonaments propis.
  8. Identificar les idees essencials de les demostracions d'alguns teoremes bàsics i saber-les adaptar per obtenir altres resultats.
  9. Llegir i comprendre un text de matemàtiques del nivell del curs.
  10. 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.
  11. Que els estudiants puguin transmetre informació, idees, problemes i solucions a un públic tant especialitzat com no especialitzat.
  12. 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.
  13. Redactar, de manera ordenada i amb precisió, petits textos matemàtics (exercicis, resolució de qüestions de teoria, etc.).
  14. Treballar cooperativament en un context multidisciplinari assumint i respectant el rol dels diferents membres de l'equip.
  15. 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.

Nota: es reservaran 15 minuts d'una classe, dins del calendari establert pel centre/titulació, perquè l'alumnat empleni les enquestes d'avaluació de l'actuació del professorat i d'avaluació de l'assignatura/mòdul.

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, 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ó

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.

Programari

C