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
Ser capaç de dissenyar, analitzar, implementar algorismes que resolguin problemes utilitzant tècniques algorísmiques i de programació.
Competències relacionades:
CE2,
CT4,
CT5,
CT6,
CT7,
CG1,
CG2,
CG5,
CB5,
Continguts
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.
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.
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).
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).
Contenidors bàsics.
Operacions, usos i implementacions de piles, cues, cues de prioritats i llistes.
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 (FordFulkerson).
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ó.
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:
Algorithmics and Programming II (lecture notes in English) -
Cortadella, Jordi; Petit, Jordi,
UPC, 2021.