Algorísmia i Programació II

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

Professorat

Responsable

• Jordi Cortadella Fortuny ( )

Altres

• Jordi Petit Silvestre ( )
• Pau Fernandez Duran ( )

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

Competències Transversals

Transversals

• CT4 - 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 [Avaluable] - Ú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. Ser capaç de dissenyar, analitzar, implementar algorismes que resolguin problemes utilitzant tècniques algorísmiques i de programació.
   Competències relacionades: CE2, CT4, CT5, CT6, CT7, CG1, CG2, CG5, CB5,

Continguts

1. Tipus Abstractes de Dades.
   Especificació i implementació. Abstracció, descomposició funcional i per dades, ocultació i encapsulació de la informació. Llenguatges orientats a objectes: clases i objectes, mètodes privats i públics, constructors i destructors. Genericitat. Exemples: punt, rectangle, nombres racionals.
2. Anàlisi d'algorismes.
   Cost en temps i espai. Cas pitjor, millor i mitjà. Notació asimptòtica. Anàlisi del cost d'algorismes iteratius i recursius. Exemples: ordenació per inserció i selecció, subseqüència de suma máxima, envolupant convexa.
3. Dividir i vèncer.
   Principis: partició en subproblemes, recombinació de solucions. Teorema Master. Exemples: cerca binària, ordenació per fusió, ordenació i selecció ràpides, càlcul dels dos punts més propers en un pla. Transformada ràpida de Fourier (FFT).
4. Gestió de memòria.
   Representació de les dades a memòria. Punters i referències. Gestió dinàmica de memòria (classe vector). Estructura de la memòria d'un programa (codi, pila, heap).
5. Contenidors bàsics.
   Operacions, usos i implementacions de piles, cues, cues de prioritats i llistes.
6. Grafs.
   Representacions: matrius d'adjacència, llistes d'adjacència i representació implícita. Cerca en profunditat (DFS). Cerca en amplada (BFS). Ordenació topològica. Algorismes per camins mínims (Dijsktra, Bellman-Ford). Algorismes per arbres d'expansió mínims (Prim i Kruskal). Algorismes per a fluxos màxims (Ford–Fulkerson).
7. Conjunts i diccionaris.
   Arbres i la seva representació. Arbres binaris i recorreguts (pre-ordre, post-ordre, in-ordre i per nivells). Arbres de cerca binaris i arbres balancejats: operacions i implementació. Taules de dispersió.

Activitats

Activitat Acte avaluatiu

Metodologia docent

Mètode d'avaluació

Bibliografia

Bàsica:

• Algorithmics and Programming II (lecture notes in English) - Cortadella, Jordi; Petit, Jordi, UPC, 2021.
  
• Data structures and algorithm analysis in C++ - Weiss, Mark Allen, Pearson, 2014. ISBN: 9780273769385
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004000539706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms - Dasgupta, Sanjoy.; Papadimitriou, Christos; Vazirani, Umesh, Mc Graw Hill Higher Education, 2008. ISBN: 9780073523408
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991003202339706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Introduction to algorithms - Cormen, T.H. [et al.], MIT Press, 2022. ISBN: 9780262046305
  
• Fundamentos de algoritmia - Brassard, Gilles.; Bratley, Paul, Prentice Hall, 1997. ISBN: 9788489660007
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991001484479706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Complementaria:

• Introduction to algorithms: a creative approach - Manber, Udi, Addison-Wesley , 1989. ISBN: 9780201120370
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991000704999706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms in C++ - Sedgewick, Robert, Addison-Wesley , 1998-2002. ISBN: 9780201350883
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991002417629706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms illuminated. Part 1: The Basics - Roughgarden, Tim, Soundlikeyourself Publishing , 2017-2020. ISBN: 9780999282908
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004186919706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms illuminated. Part 2: Graph Algorithms and Data Structures - Roughgarden, Tim, Soundlikeyourself Publishing , 2017-2020. ISBN: 9780999282922
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004186919706711&context=L&vid=34CSUC_UPC:VU1&lang=ca
• Algorithms illuminated. Part 3: Greedy Algorithms and Dynamic Programming - Roughgarden, Tim, Soundlikeyourself Publishing , 2017-2020. ISBN: 9780999282946
  https://discovery.upc.edu/discovery/fulldisplay?docid=alma991004186919706711&context=L&vid=34CSUC_UPC:VU1&lang=ca

Web links

• Pàgina principal del curs. http://www.cs.upc.edu/~jordicf/Teaching/AP2
• Jutge.org https://jutge.org

Capacitats prèvies