Algorísmia i Programació III

• Professorat
• Hores setmanals
• Competències
• Objectius
• Continguts
• Activitats
• Metodologia docent
• Mètode d'avaluació
• Bibliografia
• Web links
• Capacitats prèvies

Professorat

Responsable

• Enric Rodriguez Carbonell ( )

Altres

• Albert Oliveras Llunell ( )

Hores setmanals

Competències

Competències Tècniques

Competències tècniques

• CE2 - Ser capaç de programar solucions a problemes d'enginyeria: Dissenyar solucions algorítmiques eficients a un problema computacional donat, implementar-les en forma de programari robust, estructurat i mantenible, i comprovar la validesa de la solució.
• CE7 - Demostrar coneixement i capacitat d'aplicació de les eines necessàries per a l'emmagatzematge, el processament i l'accés a les dades.

Competències Transversals

Transversals

• CT4 [Avaluable] - Treball en equip. Ser capaç de treballar com a membre d'un equip interdisciplinari, ja sigui com un membre més o realitzant tasques de direcció, amb la finalitat de contribuir a desenvolupar projectes amb pragmatisme i sentit de la responsabilitat, assumint compromisos tenint en compte els recursos disponibles.
• CT5 - Ús solvent dels recursos d'informació. Gestionar l'adquisició, l'estructuració, l'anàlisi i la visualització de dades i informació en l'àmbit de l'especialitat i valorar de forma crítica els resultats d'aquesta gestió.
• CT6 - Aprenentatge autònom. Detectar deficiències en el propi coneixement i superar-les mitjançant la reflexió crítica i l'elecció de la millor actuació per ampliar aquest coneixement.
• CT7 - Tercera llengua. Conèixer una tercera llengua, preferentment l'anglès, amb un nivell adequat oral i escrit i d'acord amb les necessitats que tindran els titulats i titulades.

Bàsiques

• CB5 - Que els estudiants hagin desenvolupat aquelles habilitats d'aprenentatge necessàries per emprendre estudis posteriors amb un alt grau d'autonomia

Competències Tècniques Generals

Genèriques

• CG1 - Concebre sistemes computacionals que integren dades de procedències i formes molt diverses, construeixen amb ells models matemàtics, raonen sobre aquests models i actuen en conseqüència, aprenent de l'experiència.
• CG2 - Elegir i aplicar els mètodes i tècniques més adequats a un problema definit per dades que representin un repte pel seu volum, velocitat, varietat o heterogeneïtat, inclosos mètodes informàtics, matemàtics, estadístics i de processament del senyal.
• CG5 - Poder recórrer a coneixements fonamentals i metodologies de treball sòlides adquirits durant els estudis per adaptar-se als nous escenaris tecnològics del futur.

Objectius

1. Prendre consciència dels límits de la computació: comprendre les implicacions de la pregunta "P=NP?", entendre l'enunciat del Teorema de Cook-Levin, reconèixer i identificar diversos problemes NP-complets clàssics.
   Competències relacionades: CG5,
2. Conèixer, explicar, dissenyar, analitzar, comparar i implementar algorismes de cerca exhaustiva fent servir la tècnica de backtracking.
   Competències relacionades: CE2, CB5,
3. Conèixer l'esquema de programació dinàmica, identificar quan es pot aplicar i com, i familiaritzar-se amb alguns algorismes de programació dinàmica fonamentals.
   Competències relacionades: CE2,
4. Conèixer l'esquema dels algorismes golafres, identificar quan es pot aplicar i com, conèixer les tècniques més habituals per a demostrar la seva correctesa i familiaritzar-se amb alguns algorismes golafres fonamentals.
   Competències relacionades: CE2,
5. Completar i modificar implementacions, en el llenguatge de programació C++, de diversos algorismes per resoldre problemes de dificultat mitjana.
   Competències relacionades: CE2, CT6,
6. Identificar i proposar solucions a possibles problemes d'eficiència en programes escrits en el llenguatge de programació C++.
   Competències relacionades: CE2, CT6,
7. Desenvolupar projectes de mida mitjana com a membre d'un equip, aprenent així a dividir un projecte en parts petites, distribuir-les entre els seus membres i actuar amb responsabilitat de manera coordinada per a la correcta finalització de les tasques assignades.
   Competències relacionades: CE2, CT4, CT5, CT6, CT7, CG1, CG2,
8. Conèixer algorismes basats en cerca local per a resoldre eficientment problemes intractables. Conèixer una varietat de metaheurístiques de diferent natura i ser capaç d'identificar quan i com es poden aplicar en problemes concrets computacionalment durs.
   Competències relacionades: CE2,
9. Conèixer els fonaments d'autòmats finits i expressions regulars per tal de poder-los usar a la pràctica (cerca de patrons en textos, etc.).
   Competències relacionades: CE7,

Continguts

1. Tractabilitat: classes de problemes P i NP
   Classes P i NP, Teorema de Cook-Levin, reduccions, NP-completesa.
2. Cerca exhaustiva
   Principis teòrics: espai de solucions, solucions parcials, poda. Exemples: subconjunts, permutacions, viatjant de comerç, suma de subconjunts.
3. Programació dinàmica
   Esquema top-down (memoització). Esquema bottom-up (tabulació). Exemples: Fibonacci, nombres binomials, motxilla, multiplicació de seqüències de matrius.
4. Algorismes golafres
   Principis teòrics: esquema general dels algorismos voraços. Exemples: planificació de tasques, etc.
5. Metaheurístiques
   Cerca local. Simulated Annealing, Tabu Search, GRASP, algorismes genètics.
6. Autòmats finits i expressions regulars
   Alfabets, mots, llenguatges. Autòmats finits deterministes, autòmats finits indeterministes, autòmats finits amb lambda-transicions, equivalència entre models d'autòmats, minimització d'autòmats. Expressions regulars, equivalència amb autòmats. Operacions.

Activitats

Activitat Acte avaluatiu

Metodologia docent

Mètode d'avaluació

Bibliografia

Bàsica:

• Introduction to algorithms - Cormen, T.H [et al.], MIT Press, 2022. ISBN: 9780262046305
  
• The C++ programming language - Stroustrup, B, Addison-Wesley, 2013. ISBN: 9780321563842
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004038849706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Data structures and algorithm analysis in C++ - Weiss, M.A.; Chandavarkar, B.R, Pearson, 2014. ISBN: 0273769383
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004000539706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Computers and intractability: a guide to the theory of NP-Completeness - Garey, M.R.; Johnson, D.S, W.H. Freeman, 1979. ISBN: 0716710447
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991000087999706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Foundations of algorithms - Neapolitan, R.E, Jones and Bartlett Learning, 2015. ISBN: 9781284049190
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004097269706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Metaheuristics - Siarry, P. (ed.), Springer, 2017. ISBN: 9783319832845
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004156469706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Llenguatges, gramàtiques i autòmats: curs bàsic - Cases, R.; Màrquez, L, Edicions UPC, 2003. ISBN: 8483017288
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991002699299706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Slides for AP3 - Oliveras, Albert; Rodríguez Carbonell, Enric,
  https://www.cs.upc.edu/~erodri/ap3-slides.zip

Complementaria:

• Handbook of metaheuristics - Gendreau, M.; Potvin, J.-Y, Springer , 2018. ISBN: 9783319910857
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004151509706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms - Dasgupta, S.; Papadimitriou, C.; Vazirani, U., Mc Graw Hill Higher Education , 2008. ISBN: 9780073523408
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003202339706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms - Sedgewick, R.; Wayne, K, Addison-Wesley , 2011. ISBN: 9780321573513
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004156419706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithm design - Kleinberg, J.; Tardos, É, Pearson , 2014. ISBN: 9781292023946
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004001669706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Introduction to automata theory, languages, and computation - Hopcroft, J.E.; Motwani, R.; Ullman, J.D, Pearson/Addison Wesley , 2007. ISBN: 0321462254
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003933959706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Web links

• Jutge automàtic per les sessions de laboratori https://jutge.org/

Capacitats prèvies