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 (
)
Jordi Puig Rabat (
)
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:
CB5,
CT4,
CT5,
CT6,
CT7,
CE2,
CG1,
CG2,
CG5,
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 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.2 NL + 0.25 NP + 0.3 NF1 + 0.25 NF2
* 0.2 NL + 0.4 NF1 + 0.4 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 0.2 NL + 0.4 R1 + 0.4 R2
Bibliografia
Bàsica:
Algorithmics and Programming II (lecture notes in English) -
Cortadella, Jordi; Petit, Jordi,
UPC, 2021.