Aquesta versió de la guia docent és provisional fins que no finalitzi el període d’edició de les guies del nou curs.

Logo UAB

Optimització

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

Professor/a de contacte

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

Equip docent

Albert Ruiz Cirera
Judit Chamorro Servent

Idiomes dels grups

Podeu consultar aquesta informació al final del document.


Prerequisits

  • Coneixement de matemàtiques a nivell d'un grau de ciències o d'enginyeria.
  • 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 a l'alumnat 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 Dijkstra 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.

Activitats formatives i Metodologia

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

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.


Avaluació

Activitats d'avaluació continuada

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, 5, 6, 7, 8, 9, 10
Projectes de casos realistes de forma individual 30% 21 0,84 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Projectes en casos realistes en grups de 2 (excepcionalment 3) 40% 28 1,12 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Hi ha tres tipus d'avaluació:
  • Treballs individuals: informe resumit i codi resolent el problema plantejat.
  • Treballs en grups de 2: informe resumit i codi resolent el problema plantejat.
  • Treball en grups de 4: informe, (pot incloure codi) i presentació oral.

Bibliografia

  • David Beasley, David R. Bully and Ralph R. Martinz, An Overview of Genetic Algorithms (Part 1: Fundamentals and Part 2: Research Topics).
  • Ben-Tal, A., & Nemirovski, A. (2001). Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Society for industrial and applied mathematics. 
  • Borwein, J., & Lewis, A. (2006). Convex Analysis and Nonlinear Optimization. CMS Books in Mathematics. Springer, New York, NY.
  • Boyd, S. P., & Vandenberghe, L. (2004). Convex optimization. Cambridge university press.
  • Marco Dorigoa and Christian Blum, Ant colony optimization theory: A survey, Theoretical Computer Science 344 (2005) 243 - 278.
  • Hansen, P. C. (2010). Discrete inverse problems: insight and algorithms. Society for Industrial and Applied Mathematics.
  • 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.
  • Nocedal, J., & Wright, S. J. (2006). Quadratic programming. Numerical optimization, 448-492.
  • Nocedal, J., & Wright, S. J. (2006). Sequential Quadratic Programming. Numerical Optimization, 529-562.
  • 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

Llista d'idiomes

Nom Grup Idioma Semestre Torn
(TEm) Teoria (màster) 1 Anglès primer quadrimestre tarda