Programació i Algorísmia II

Crèdits
6
Tipus
Obligatòria
Requisits
Aquesta assignatura no té requisits , però té capacitats prèvies
Departament
CS
Segona part del curs d'Introducció a la Programació pels alumnes del grau d'IA (format per PA1+PA2). En aquest curs ens centrarem essencialment en l'abstracció amb dades, definint noves estructures de dades (piles, cues, llistes, arbres, grafs, heaps) o veient com s'implementen estructures de dades conegudes (conjunts i diccionaris). Al final de l'assignatura es veurà la continuació del tema de complexitat, que va començar al final de PA1

Professorat

Responsable

  • Jordi Delgado Pin (jdelgado@cs.upc.edu)

Altres

  • Caroline König (caroline.leonore.konig@upc.edu)
  • Jose Luis Balcázar Navarro (jose.luis.balcazar@upc.edu)

Hores setmanals

Teoria
2
Problemes
0
Laboratori
2
Aprenentatge dirigit
0
Aprenentatge autònom
6

Competències

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.
  • CT6 [Avaluable] - 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.

    • Competències Tècniques

    Específiques

  • CE02 - Dominar els conceptes bàsics de matemàtica discreta, lògica, algorísmica i complexitat computacional i la seva aplicació per al tractament automàtic de la informació per mitjà de sistemes computacionals i la seva aplicació per a la resolució de problemes.
  • CE03 - Identificar i aplicar els procediments algorítmics bàsics de les tecnologies informàtiques per dissenyar solucions a problemes, analitzant la idoneïtat i complexitat dels algoritmes proposats.
  • CE04 - Dissenyar i utilitzar de forma eficient els tipus i estructures de dades més adequats a la resolució d'un problema.
  • CE10 - Analitzar, dissenyar, construir i mantenir aplicacions de forma robusta, segura i eficient, triant el paradigma i els llenguatges de programació més adequats.
  • CE12 - Dominar els principis fonamentals i models de la computació i saber-los aplicar per a interpretar, seleccionar, valorar, modelar, i crear nous conceptes, teories, usos i desenvolupaments tecnològics relacionats amb la intel·ligència artificial.
  • CE13 - Avaluar la complexitat computacional d'un problema, identificar estratègies algorítmiques que puguin conduir a la seva resolució i recomanar, desenvolupar i implementar aquella que garanteixi el millor rendiment d'acord amb els requisits establerts.

    • Competències Tècniques Generals

    Genèriques

  • CG2 - Utilitzar els coneixements fonamentals i metodologies de treball sòlides adquirits durant els estudis per adaptar-se als nous escenaris tecnològics de el futur.
  • CG4 - Raonar, analitzant la realitat i dissenyant algoritmes i formulacions que la modelin. Identificar problemes i construir solucions algorísmiques o matemàtiques vàlides, eventualment noves, integrant el coneixement multidisciplinari necessari, valorant diferents alternatives amb esperit crític, justificant les decisions preses, interpretant i sintetitzant els resultats en el context de l'domini d'aplicació i establint generalitzacions metodològiques a partir de aplicacions concretes.
  • CG8 - Observar un exercici ètic de la professió en totes les seves facetes, aplicant criteris ètics en el disseny de sistemes, algoritmes, experiments, utilització de dades, d'acord amb els sistemes ètics recomanats pels organismes nacionals i internacionals, amb especial èmfasi en seguretat, robustesa , privacitat, transparència, traçabilitat, prevenció de biaixos (de raça, gènere, religió, territori, etc.) i respecte als drets humans.

    • Objectius

    1. Conèixer estructures de dades noves: Piles, Cues, Llistes, Arbres i Grafs i els algorismes associats a les operacions necessàries sobre aquestes estructures.
      Competències relacionades: CT6, CE03, CE04, CE12, CG2, CG4,
    2. Conèixer diferentes implementacions d'estructures de dades: Implementacions fent servir estructures de dades més simples proporcionades pel llenguatge de programació, i implementacions dinàmiques.
      Competències relacionades: CE03, CE04, CE12, CG2, CG4, CE02,
    3. Conèixer els principis bàsics de l'orientació a objectes: Conceptes de classe, instància, mètode, herència (simple i múltiple), etc.
      Competències relacionades: CT6, CE03, CE04, CE10, CG2, CG4,
    4. Ampliació de Complexitat Computacional: Big O, Big Omega, Master Theorems
      Competències relacionades: CT6, CE02, CE12, CE13, CG2, CG4,
    5. Resoldre en grup un problema de mida petita-mitjana aplicant allò aprés sobre orientació a objectes
      Competències relacionades: CT4, CE03, CE04, CE10, CG2, CG4, CG8,

    Continguts

    1. Arbres i Grafs
      Començarem el curs utilitzant les estructures de dades que el llenguatge de programació ens proporciona per implementar els Arbres i els Grafs. Veurem algorismes de recorregut per a les dues estructures, i d'altres algorismes importants relacionats amb aquestes, com per exemple l'algorisme de Dijkstra.
    2. Objectes i Classes
      S'introdueixen els conceptes fonamentals d'orientació a objectes: Classe, objecte, instància, delegació, herència, etc i altres particularitats de la implementació de l'orientació a objectes pròpies del llenguatge de programació amb que treballem.
    3. Estructures dinàmiques de dades
      S'estudia com implementar estructures de dades conegudes utilitzant el concepte de referència a un objecte. Es re-implementaran d'aquesta manera estrucures de dades que el llenguatge de programació proporciona per defecte, i estructures de dades noves que ja hem vist implementades de manera més senzilla.
    4. Conjunts i Diccionaris: Implementació
      Veurem diferentes maneres d'implementar conjunts i diccionaris: Taules Hash i arbres binaris de cerca (BSTs). S'estudiaran les propietats d'aquestes estructures, els avantatges i inconvenients.
    5. Ampliació de Complexitat Algorísmica
      A PA1 es va començar a veure el concepte de complexitat d'un programa, un algorisme i un problema, i vam introduir la notació asimptòtica, concretament la definició de Theta(f). Aquest tema vol ser una continuació, on veurem la Big O, la Big Omega, etc, i els Master Theorems.

    Activitats

    Activitat Acte avaluatiu


    Construint Abstraccions amb Dades: Arbres i Grafs

    Cal que l'estudiant estigui atent a classe i realitzi els exercicis proposats.
    Objectius: 1 2
    Continguts:
    Teoria
    4h
    Problemes
    0h
    Laboratori
    5h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    10h

    Construint Abstraccions amb Dades: Objectes i Classes

    Cal que l'estudiant estigui atent a classe i realitzi els exercicis proposats.
    Objectius: 2 3
    Continguts:
    Teoria
    8h
    Problemes
    0h
    Laboratori
    8h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    16h

    Construint Abstraccions amb Dades: Estructures Dinàmiques de Dades

    Cal que l'estudiant estigui atent a classe i realitzi els exercicis proposats.
    Objectius: 1 2
    Continguts:
    Teoria
    6h
    Problemes
    0h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    10h

    Conjunts i Diccionaris: Implementació

    Cal que l'estudiant estigui atent a classe i realitzi els exercicis proposats.
    Objectius: 2 3
    Continguts:
    Teoria
    4h
    Problemes
    0h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Ampliació de Complexitat Algorísmica

    Cal que l'estudiant estigui atent a classe i realitzi els exercicis proposats.
    Objectius: 4
    Continguts:
    Teoria
    6h
    Problemes
    0h
    Laboratori
    6h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Treball Pràctic

    Els estudiants faran una pràctica en parelles relacionada amb un problema de mida petita-mitjana.
    Objectius: 1 2 3 5
    Setmana: 15 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Examen Parcial


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

    Examen Final


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

    Metodologia docent

    La docència de l'assignatura està estructurada en classes de teoria i classes de laboratori.

    A les classes de teoria els professors presenten els continguts essencials de l'assignatura. A les classes de laboratori es practiquen els continguts de l'assignatura (els presentats a classe i els adquirits autònomament) mitjançant la realització de problemes pràctics. Les classes de laboratori seran una continuació de les classes teòriques, on els conceptes nous s'implementaran a mida que vagin apareixent.

    Mètode d'avaluació

    El mètode d'avaluació de l'assignatura consistirà en dues proves de caire teòric (T1 i T2), una a mitjans de curs i l'altre al final i una pràctica de mida petita-mitjana (Practica).

    Aleshores, el mètode d'avaluació seria:
    0.8 * Teoria + 0.2 * Practica
    on:
    Teoria: MAX(T2, 0.5 * T1 + 0.5 * T2)

    Reavaluació: només es poden presentar a la reavaluació aquelles persones que, havent-se presentat a l'examen final, hagin suspès la teoria. La nota màxima que es pot obtenir a la reavaluació és un 7.

    Competència transversal "Treball en equip":
    S'avalua usant una rúbrica simple en que el tutor de cada grup puntua els
    diferents aspectes del treball en equip de cada membre dels grups.

    Bibliografia

    Bàsic

    Complementari

    • Python pocket reference - Lutz, Mark, O'Reilly Media, 2014. ISBN: 9781449356941

    Web links

    • Aquest és el text PRINCIPAL de l'assignatura, la font d'informació primària per a tot allò que expliquem a classe. Tot i això, a PA2 hi ha temes que no apareixen en aquest text. http://composingprograms.com/
    • La principal referència del llenguatge de programació que fem servir: Python. No és un lloc on aprendre a programar, és un lloc on consultar detalls de les construccions i llibreries del llenguatge https://docs.python.org/3/reference/index.html

    Capacitats prèvies

    Curs PA1, o equivalent