Algorísmia i Programació II

Crèdits
7.5
Tipus
Obligatòria
Requisits
Aquesta assignatura no té requisits , però té capacitats prèvies
Departament
CS
Web
http://www.cs.upc.edu/~jordicf/Teaching/AP2
S'introdueix l'anàlisi matemàtica dels algorismes i es presenten les eines per calcular-ne el seu cost. Aquestes bases s'utilitzen per estudiar i analitzar el disseny i les diferents implementacions de diversos algorismes i estructures de dades fonamentals (piles, cues, llistes, cues de prioritat, arbres, arbres binaris de cerca, arbres equilibrats, taules de hash i grafs). Alhora, s'introdueixen les eines necessàries per a poder implementar aquestes estructures de dades i els seus algorismes associats i es profunditza en l'orientació a objectes i l'ús de llibreries externes.

Professorat

Responsable

  • Jordi Cortadella Fortuny (jordi.cortadella@upc.edu)

Altres

  • Jordi Petit Silvestre (jpetit@cs.upc.edu)
  • Pau Fernandez Duran (pau.fernandez@upc.edu)

Hores setmanals

Teoria
3
Problemes
0
Laboratori
2
Aprenentatge dirigit
0
Aprenentatge autònom
7.5

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: CB5, CT4, CT5, CT6, CT7, CE2, CG1, CG2, CG5,

    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


    Desenvolupament del contingut 1


    Objectius: 1
    Continguts:
    Teoria
    5h
    Problemes
    0h
    Laboratori
    3h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    9h

    Examen parcial (amb ordinador)


    Objectius: 1
    Setmana: 7 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Examen final (sobre paper)



    Setmana: 15 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Examen final (amb ordinador)



    Setmana: 15 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Lliurament pràctica



    Setmana: 15 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Desenvolupament del contingut 2


    Objectius: 1
    Continguts:
    Teoria
    5h
    Problemes
    0h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    12h

    Desenvolupament del contingut 3


    Objectius: 1
    Continguts:
    Teoria
    7h
    Problemes
    0h
    Laboratori
    5h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    20h

    Desenvolupament del contingut 4


    Objectius: 1
    Continguts:
    Teoria
    3h
    Problemes
    0h
    Laboratori
    2h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    7.5h

    Desenvolupament del contingut 5


    Objectius: 1
    Continguts:
    Teoria
    7h
    Problemes
    0h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    16h

    Desenvolupament del contingut 6


    Objectius: 1
    Continguts:
    Teoria
    9h
    Problemes
    0h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    21h

    Desenvolupament del contingut 7



    Continguts:
    Teoria
    7h
    Problemes
    0h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    16h

    Metodologia docent

    El temari s'exposa de forma molt pràctica, a través de la presentació de molts exemples.

    Les classes de teoria introdueixen tots els conceptes i tècniques necessaris, els quals es posen en pràctica en les classes de problemes i de laboratori mitjançant una col·lecció de problemes i exercicis en un jutge automàtic.

    Cada setmana es fan dues hores de classes de teoria, una hora de problemes i dues hores de laboratori.

    El curs utilitza els llenguatges de programació C++ i Python.

    Mètode d'avaluació

    La nota final de l'assignatura té en compte els següents actes avaluatoris:
    * P1: projecte de programació individual a entregar a mitjans de curs
    * P2: projecte de programació en parella a entregar a final de curs
    * PL: examen parcial de laboratori (amb ordinador)
    * FL: examen final de laboratori (amb ordinador)
    * FT: examen final de teoria (amb paper)

    La nota de projectes es calcula com: P = (P1 + P2)/2
    La nota d'exàmens es calcula com: X = max (0.3 PL + 0.4 FT + 0.3 FL, 0.5 FT + 0.5 FL)

    La nota final N es calcula com:
    * N = max(0.3 P + 0.7 X, 0.15 P + 0.85 X), si X >= 4
    * N = 0.15 P + 0.85 X, si X < 4

    Els alumnes que suspenen l'assignatura poden anar als exàmens de reavaluació RL (laboratori) i RT (teoria). Les notes d'aquests exàmens substituiran FL i FT, respectivament, en la fórmula de càlcul de la nota final.

    Bibliografia

    Bàsic

    Complementari

    Web links

    Capacitats prèvies

    Les del curs AP1-GCED.