Algorísmia i Programació II

Esteu aquí

Crèdits
7.5
Tipus
Obligatòria
Requisits
Aquesta assignatura no té requisits, però té capacitats prèvies
Departament
CS
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 ( )

Altres

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

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
8h

Examen parcial (amb ordinador)


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

Examen final (sobre paper)



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

Examen final (amb ordinador)



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

Lliurament pràctica



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

Desenvolupament del contingut 2


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

Desenvolupament del contingut 3


Objectius: 1
Continguts:
Teoria
9h
Problemes
0h
Laboratori
6h
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
6h

Desenvolupament del contingut 5


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

Desenvolupament del contingut 6


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

Desenvolupament del contingut 7



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

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

Bibliografia

Bàsica:

Complementaria:

Web links

Capacitats prèvies

Les del curs AP1-GCED.