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.

Professors

Responsable

  • Jordi Cortadella Fortuny ( )

Altres

  • Jordi Petit Silvestre ( )

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

  • CT5 - Ú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ó.
    Related competences: CB5, 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
0h
Aprenentatge dirigit
2h
Aprenentatge autònom
0h

Examen final (sobre paper)



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

Examen final (amb ordinador)



Setmana: 15 (Fora d'horari lectiu)
Tipus: examen final
Teoria
0h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
2h
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 del curs es calcula en funció d'una nota obtinguda de dos projectes de laboratori (NL), un examen parcial realitzat sobre ordinador (NP), i un examen final que consta de dues proves: una sobre paper (NF1) i l'altra sobre ordinador (NF2).

La nota final és el màxim de:
* 0.15 NL + 0.25 NP + 0.3 NF1 + 0.3 NF2
* 0.15 NL + 0.425 NF1 + 0.425 NF2

Reavaluació:
A l'examen de reavaluació es podran presentar només aquells estudiants que s'hagin presentat als actes d'avaluació i no hagin aprovat el curs. Per l'examen de reavaluació es realitzen dues proves semblants a l'examen final: una sobre paper (R1) i l'altra sobre ordinador (R2). En cas de no presentar-se a alguna de les proves, es mantindrà la nota corresponent de l'examen final (NF1 o NF2).

En cas de reavaluació, la nota final del curs es calcula com el màxim de:
* 0.5 R1 + 0.5 R2
* 0.15 NL + 0.425 R1 + 0.425 R2

Bibliografia

Bàsica:

Complementaria:

Web links

Capacitats prèvies

Les del curs AP1-GCED.