Logo UAB
2022/2023

Optimització

Codi: 42250 Crèdits: 6
Titulació Tipus Curs Semestre
4313136 Modelització per a la Ciència i l'Enginyeria / Modelling for Science and Engineering OB 0 1

Professor/a de contacte

Nom:
Albert Ruiz Cirera
Correu electrònic:
albert.ruiz@uab.cat

Utilització d'idiomes a l'assignatura

Llengua vehicular majoritària:
anglès (eng)

Equip docent

Albert Ruiz Cirera
Judit Chamorro Servent

Prerequisits

  • Coneixement de matemàtiques a nivell d'un grau de ciències.
  • Saber programar.

Objectius

El curs està dedicat a estudiar i practicar diversos algorismes d’optimització heurística i combinatòria, fent especial èmfasi en l’enrutament i l'optimització convexa. El curs tractarà també altres temes d'optimització.
Aquest curs pretèn donar als estudiants els coneixements necessaris i eines bàsiques per a programar algorismes que puguin resoldre problemes d'optimització actuals.

Competències

  • "Aplicar el pensamiento lógico/matemático: el proceso analítico a partir de principios generales para llegar a casos particulares; y el sintético, para a partir de diversos ejemplos extraer una regla general."
  • Analitzar, sintetitzar, organitzar i planificar projectes del seu camp d'estudi. 
  • Aplicar la metodologia de recerca, tècniques i recursos específics per investigar en un determinat àmbit d'especialització.
  • Aplicar les tècniques de resolució dels models matemàtics i els seus problemes reals d'implementació.
  • Comunicar en llengua anglesa els resultats dels treballs de l'àmbit d'estudi.
  • Concebre i dissenyar solucions eficients, aplicant tècniques computacionals, que permetin resoldre models matemàtics de sistemes complexos.
  • Extreure d'un problema complex la dificultat principal, separada d'altres qüestions d'índole menor.
  • Formular, analitzar i validar models matemàtics de problemes pràctics de diferents camps.
  • Usar mètodes numèrics apropiats per solucionar problemes específics.

Resultats d'aprenentatge

  1. "Aplicar el pensament lògic/matemàtic: el procés analític a partir de principis generals per arribar a casos particulars; i el sintètic, para a partir de diversos exemples extreure una regla general."
  2. Analitzar, sintetitzar, organitzar i planificar projectes del seu camp d'estudi. 
  3. Aplicar la metodologia de recerca, tècniques i recursos específics per investigar en un determinat àmbit d'especialització.
  4. Aplicar tècniques d'optimització per estudiar models associats a problemes pràctics.
  5. Comunicar en llengua anglesa els resultats dels treballs de l'àmbit d'estudi.
  6. Extreure d'un problema complex la dificultat principal, separada d'altres qüestions d'índole menor.
  7. Identificar problemes que requereixin aplicar tècniques d'optimització per construir models associats a problemes pràctics.
  8. Implementar els algorismes que consten al programa
  9. Implementar les solucions proposades de forma fiable i eficient.
  10. Usar programaris específics per a la resolució de problemes d'optimització. 

Continguts

Continguts principals:
  • Algorismes combinatoris per a grafs i enrutaments: algorismes Dijstra i A *. Optimització sobre grafs.
  • Optimització determinista (problemes amb restriccions i sense).
Possibles tòpics addicionals:
  • Algorismes genètics.
  • Simulated annealing.
  • Algorismes de colònies de formigues.
  • Altres.

Metodologia

La metodologia consisteix en classes teòriques (presentacions amb transparències i pissarra), i sessions pràctiques.

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.

Activitats formatives

Títol Hores ECTS Resultats d'aprenentatge
Tipus: Dirigides      
Assistir a classe i activitats relacionades 37,75 1,51 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Avaluació del professorat i de l'assignatura 0,25 0,01
Tipus: Autònomes      
Tasques (implementació dels algorismes – activitat individual i en grup) 42 1,68 1, 2, 3, 4, 6, 7

Avaluació

Hi ha tres tipus d'avaluació:
  • Treballs individuals: informe resumit i codi resolent el problema plantejat.
  • Treballs en grups de dos: informe resumit i codi resolent el problema plantejat.
  • Treball en grups de quatre: informe, codi i presentació oral.

Activitats d'avaluació

Títol Pes Hores ECTS Resultats d'aprenentatge
Lliurament i exposició del treball final (grups de 4) 30% 21 0,84 1, 2, 3, 4, 6, 7, 8, 9, 10
Projectes de casos realistes de forma individual 40% 28 1,12 1, 2, 3, 4, 6, 7, 8, 9, 10
Projectes en casos realistes en grups de dos alumnes (excepcionalment tres) 30% 21 0,84 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Bibliografia

  • David Beasley, David R. Bully and Ralph R. Martinz, An Overview of Genetic Algorithms (Part 1: Fundamentals and Part 2: Research Topics).
  • Marco Dorigoa and Christian Blum, Ant colony optimization theory: A survey, Theoretical Computer Science 344 (2005) 243 - 278.
  • S. Kirkpatrick, C. D. Gelatt Jr. and M. P. Vecchi, Optimization by Simulated Annealing, Science, May 1983, Vol. 220, no. 4598,  671-680.
  • Melanie Mitchell, An Introduction to Genetic Algorithms, A Bradford Book, The MIT Press, Cambridge Massachusetts, 1999.
  • Judea Pearl, A* Algorithms and such: Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley, 1984.
  • William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery, Numerical Recipes in C. The Art of Scientific Computing (second edition), Cambridge University Press.
  • Alfio Quarteroni, Riccardo Sacco, Fausto Saleri, Numerical Mathematics, Texts in Applied Mathematics 37, Springer, 1991.

 

Programari

Programari recomanat:

  • C
  • MATLAB