Programació i Algorísmia II

Esteu aquí

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 ( )
  • Jose Luis Balcázar Navarro ( )

Hores setmanals

Teoria
2
Problemes
0
Laboratori
2
Aprenentatge dirigit
0.4
Aprenentatge autònom
4

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: CG2, CG4, CT6, CE03, CE04, CE12,
  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: CG2, CG4, CE02, CE03, CE04, CE12,
  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: CG2, CG4, CT6, CE03, CE04, CE10,
  4. Ampliació de Complexitat Computacional: Big O, Big Omega, Master Theorems
    Competències relacionades: CG2, CG4, CT6, CE02, CE12, CE13,
  5. Resoldre en grup un problema de mida petita-mitjana aplicant allò aprés sobre orientació a objectes
    Competències relacionades: CG2, CG4, CG8, CT4, CE03, CE04, CE10,

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
6h
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
4h
Problemes
0h
Laboratori
4h
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: 17 (Fora d'horari lectiu)
Tipus: entrega
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
2h
Aprenentatge autònom
10h

Examen Parcial


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

Examen Final


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

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.6* Teoria + 0.4*Practica
on:
Teoria: MAX(T2, 0.5* T1 + 0.5* T2)

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àsica:

Complementaria:

  • 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