Estructures de Dades i Algorismes

Crèdits
6
Tipus
Obligatòria
Requisits
Departament
CS
Web
http://www.cs.upc.edu/~eda
Aquesta assignatura comença introduint els conceptes d'eficiència i cost d'un algorisme i les eines matemàtiques bàsiques per analitzar-los. A continuació s'utilitzen aquestes bases per estudiar i analitzar el disseny i les diferents implementacions d'algorismes i estructures de dades clàssics i fonamentals.

Professorat

Responsable

Altres

Hores setmanals

Teoria
2
Problemes
1
Laboratori
1
Aprenentatge dirigit
0.4
Aprenentatge autònom
5.6

Competències

Competències Tècniques

Competències tècniques comunes

  • CT2 - Utilitzar d'una manera apropiada teories, procediments i eines en el desenvolupament professional de l'enginyeria informàtica en tots els seus àmbits (especificació, disseny, implementació, desplegament -implantació- i avaluació de productes) de manera que es demostri la comprensió dels compromisos adoptats a les decisions de disseny.
    • CT2.3 - Dissenyar, desenvolupar, seleccionar i avaluar aplicacions, sistemes i serveis informàtics i, al mateix temps, assegurar-ne la fiabilitat, la seguretat i la qualitat en funció de principis ètics i de la legislació i la normativa vigents.
    • CT2.4 - Demostrar coneixement i capacitat per a aplicar les eines necessàries a l'emmagatzematge, el processament i l'accés als sistemes d'informació, fins i tot els que es basen en la web.
  • CT4 - Demostrar coneixement i capacitat d'aplicació dels procediments algorísmics bàsics de les tecnologies informàtiques per a dissenyar solucions a problemes, analitzant la idoneïtat i la complexitat dels algorismes
    • CT4.1 - Identificar les solucions algorísmiques més adequades per a resoldre problemes de dificultat mitjana.
    • CT4.2 - Raonar sobre la correcció i l'eficiència d'una solució algorísmica.
    • CT4.3 - Demostrar coneixement i capacitat d'aplicació dels principis fonamentals i de les tècniques bàsiques dels sistemes intel·ligents i de la seva aplicació pràctica.
  • CT5 - Analitzar, dissenyar, construir i mantenir aplicacions de forma robusta, segura i eficient, triant el paradigma i els llenguatges de programació més adequats.
    • CT5.1 - Triar, combinar i explotar diferents paradigmes de programació, en el moment de construir software, tenint en compte criteris com la facilitat de desenvolupament, l'eficiència, la portabilitat i la mantenibilitat.
    • CT5.2 - Conèixer, dissenyar i utilitzar de forma eficient els tipus i les estructures de dades més adients per a la resolució d'un problema.
    • CT5.3 - Dissenyar, escriure, provar, depurar, documentar i mantenir codi en un llenguatge d'alt nivell per a resoldre problemes de programació aplicant esquemes algorísmics i utilitzant estructures de dades.
    • CT5.4 - Dissenyar l'arquitectura dels programes utilitzant tècniques d'orientació a objectes, de modularització i d'especificació i implementació de tipus abstractes de dades.
    • CT5.5 - Usar les eines d'un entorn de desenvolupament de software per a crear i desenvolupar aplicacions.
  • CT8 - Planificar, concebre, desplegar i dirigir projectes, serveis i sistemes informàtics en tots els àmbits, liderar-ne la posada en marxa, la millora contínua i valorar-ne l'impacte econòmic i social.
    • CT8.6 - Demostrar comprensió de la importància de la negociació, dels hàbits de treball efectius, del lideratge i de les habilitats de comunicació en tots els entorns de desenvolupament de software.
    • CT8.7 - Controlar versions i configuracions del projecte.

    • Competències Transversals

    Ús solvent dels recursos d'informació

  • G6 [Avaluable] - Gestionar l'adquisició, l'estructuració, l'anàlisi i la visualització de dades i d'informació de l'àmbit de l'enginyeria informàtica, i valorar de forma crítica els resultats d'aquesta gestió.
    • G6.2 - Després d'identificar les parts d'un document acadèmic i d'organitzar les referències bibliogràfiques, dissenyar i executar una bona estratègia de cerca avançada amb recursos d'informació especialitzats, seleccionant la informació pertinent tenint en compte criteris de rellevància i qualitat.

    • Objectius

    1. Comprendre les definicions de les notacions asimptòtiques O gran, Omega i Theta i el seu ús per caracteritzar l'eficiència en temps i espai dels algorismes.
      Competències relacionades: CT4.2,
    2. Calcular l'eficiència d'algorismes iteratius aplicant les regles de càlcul adients.
      Competències relacionades: CT4.2,
    3. Descriure l'eficiència dels algorismes recursius utilitzant recurrències i comprendre i aplicar els teoremes mestres per resoldre-les.
      Competències relacionades: CT4.2,
    4. Dissenyar algorismes per resoldre problemes diversos de dificultat mitjana amb restriccions tant de temps com d'espai.
      Competències relacionades: CT4.1, CT4.2,
    5. Comparar l'eficiència de diferents algorismes per resoldre un mateix problema i seleccionar el més adient.
      Competències relacionades: CT4.1, CT4.2,
    6. Conèixer, explicar, dissenyar, analitzar, comparar i implementar algorismes (com poden ser mergesort, quicksort, Karatsuba i Strassen, entre d'altres) fent servir la tècnica de dividir i vèncer.
      Competències relacionades: CT4.1, CT4.2, CT5.3,
    7. Conèixer, explicar, dissenyar, analitzar, comparar i implementar les principals estructures de dades que es poden fer servir per implementar diccionaris (taules, taules ordenades, llistes, llistes ordenades, taules de dispersió, arbres binaris de cerca, arbres AVL).
      Competències relacionades: CT4.1, CT4.2, CT5.2, CT2.4,
    8. Conèixer, explicar, dissenyar, analitzar, comparar i implementar les principals estructures de dades que es poden fer servir per implementar cues de prioritat (arbres, heaps).
      Competències relacionades: CT4.1, CT4.2, CT5.2, CT2.4,
    9. Conèixer, explicar, dissenyar, analitzar, comparar i implementar algorismes que resolguin problemes clàssics en grafs com recorreguts, ordenació topològica i camins mínims entre d'altres.
      Competències relacionades: CT4.1, CT4.2, CT5.2, CT2.4,
    10. Conèixer, explicar, dissenyar, analitzar, comparar i implementar algorismes de cerca exhaustiva fent servir la tècnica de backtracking.
      Competències relacionades: CT4.1, CT4.2, CT2.4, CT4.3,
    11. Prendre consciència dels límits de la computació: comprendre les implicacions de la pregunta "P=NP?", entendre l'enunciat del Teorema de Cook-Levin, reconèixer i identificar diversos problemes NP-complets clàssics.
      Competències relacionades: CT4.2,
    12. Completar i modificar implementacions, en llenguatge de programació C++, de diversos algorismes per resoldre problemes de dificultat mitjana.
      Competències relacionades: CT4.2, CT5.2, CT5.1,
    13. Identificar i proposar solucions per problemes d'eficiència d'algorismes i de programes escrits en llenguatge de programació C++.
      Competències relacionades: CT4.1, CT4.2, CT5.2, CT2.4, CT2.3,
    14. Analitzar un joc estratègic per dissenyar i programar un jugador eficaç,
      eficient, col·laboratiu i competitiu que maximitzi les possibilitats de guanyar
      al joc i que sigui capaç d'establir aliances i de coordinar-se amb altres jugadors.
      Competències relacionades: CT8.6, CT8.7, CT4.1, CT4.2, CT5.2, CT5.4, CT5.5, G6.2, CT2.4, CT4.3, CT5.1, CT5.3, CT2.3,
    15. Executar estratègies de recerca d'informació (referències bibliogràfiques, articles científics, patents, recursos web de qualitat...) per elaborar un document que descrigui, per a un problema donat, un algorisme ben conegut que el resolgui, tot estructurant-lo correctament, citant adequadament les fonts usades i fent un ús ètic de la informació recopilada.
      Competències relacionades: G6.2,
    16. Calcular el cost d'un algorisme en els casos pitjor, millor i mitjà.
      Competències relacionades: CT4.2,

    Continguts

    1. 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.
    2. Dividir i Vèncer
      Principis: partició en subproblemes, recombinació de solucions. Exemples: mergesort, quicksort, algorisme de Karatsuba per multiplicar nombres grans, algorisme de Strassen per multiplicar matrius.
    3. Diccionaris
      Operacions de diccionaris i diccionaris ordenats. Implementacions bàsiques: taules i llistes. Implementacions avançades: taules de dispersió, arbres binaris de cerca, arbres AVL.
    4. Cues amb Prioritats
      Operacions de cues amb prioritats. Implementacions amb heaps. Heapsort.
    5. Grafs
      Representacions: matrius d'adjacència, llistes d'adjacència i implícita. Cerca en profunditat (DFS). Cerca en amplada (BFS). Ordenació topològica. Algorisme de Dijkstra per camins mínims. Algorisme de Prim per arbres d'expansió mínims.
    6. Generació i Cerca Exhaustiva
      Principis: espai de solucions, solucions parcials, poda. Generació de subconjunts i permutacions. Exemples: motxilla, viatjant de comerç.
    7. Nocions d'Intractabilitat
      Introducció bàsica a les classes P i NP, al Teorema de Cook-Levin, a les reduccions i a la NP-completesa.

    Activitats

    Activitat Acte avaluatiu


    Anàlisi d'Algorismes

    Desenvolupament del tema 1 de l'assignatura.
    Objectius: 1 2 3 5 4 16
    Continguts:
    Teoria
    4h
    Problemes
    2h
    Laboratori
    2h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Dividir i Vèncer

    Desenvolupament del tema 2 de l'assignatura.
    Objectius: 3 5 4 6 12 13
    Continguts:
    Teoria
    4h
    Problemes
    2h
    Laboratori
    2h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Diccionaris

    Desenvolupament del tema 3 de l'assignatura.
    Objectius: 5 4 7 12 13
    Continguts:
    Teoria
    3.5h
    Problemes
    2h
    Laboratori
    2h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Cues amb Prioritats

    Desenvolupament del tema 4 de l'assignatura.
    Objectius: 5 4 8 12 13
    Continguts:
    Teoria
    1.5h
    Problemes
    2h
    Laboratori
    1h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    4h

    Examen parcial de paper

    S'avalua dels objectius corresponents als continguts 1 i 2.
    Objectius: 1 2 3 5 4 6 12
    Setmana: 6 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Grafs

    Desenvolupament del tema 5 de l'assignatura.
    Objectius: 5 4 9 12 13
    Continguts:
    Teoria
    4h
    Problemes
    2h
    Laboratori
    2h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Presentació del Joc

    Familiarització amb el Joc: primeres partides, visualitzacions i depuració.
    Objectius: 14
    Continguts:
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    2h
    Aprenentatge autònom
    0.5h

    Joc

    S'avalua dels objectius corresponents al objectiu específic 15. Es publicarà un enunciat que consistirà en la descripció d'un joc d'estratègia. Els estudiants hauran de programar un jugador per aquest joc (és a dir, implementar una estratègia per intentar guanyar el joc). Es durà a terme una competició en què els estudiants competiran els uns contra els altres, de la que s'obtindrà una classificació. Per participar en aquesta competició, els jugadors dels estudiants hauran de superar un test de qualificació. La nota corresponent a aquesta part es calcularà a partir de la posició a la classificació de forma proporcional, garantint que el campió tingui un 10 i que tots els participants que tinguin un jugador qualificat tinguin un nota mínima de 5. Els estudiants que no hagin aconseguit cap jugador qualificat tindran una nota de 0.
    Objectius: 14
    Setmana: 9 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Desenvolupament del Joc

    Aprentatge de les estratègies més apropiades pel joc. Resolució dubtes existents a nivell grupal.
    Objectius: 14
    Continguts:
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    2h
    Aprenentatge autònom
    2.5h

    Generació i Cerca Exhaustiva

    Desenvolupament del tema 6 de l'assignatura.
    Objectius: 5 4 10 12 13
    Continguts:
    Teoria
    4h
    Problemes
    2h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Nocions d'Intractabilitat i Indecidibilitat

    Desenvolupament del tema 7 de l'assignatura.
    Objectius: 11
    Continguts:
    Teoria
    4h
    Problemes
    3h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    4h

    Gran Final del Joc

    Assistència a la Gran Final del Joc. Aprenentatge de les estratègies emprades pel guanyadors.
    Objectius: 14
    Continguts:
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    2h
    Aprenentatge autònom
    1.5h

    Tutorials Bibliotècnica-BRGF.

    Autoaprenentatge mitjançant tutorials de la Bibliotècnica de la BRGF sobre: la propietat intel·lectual, l'ús ètic de la informació i l'ús de software de gestió de referències bibliogràfiques.
    Objectius: 15
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    2.5h

    Pràctica d'ús solvent de recursos d'informació.

    S'avalua dels objectius corresponents al objectiu específic 16. Es publicarà un enunciat que consistirà en la descripció d'un problema computacional i el nom d'un algorisme que el resol. Els estudiants hauran de cercar (a la biblioteca, a la web, ... ) informació sobre el problema i l'algorisme i elaborar un document breu i ben estructurat que inclogui correctament les fonts consultades. El document s'haurà de lliurar el dia de l'examen final. La competència transversal s'avalua a través d'aquest document.
    Objectius: 15
    Setmana: 14 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Examen d'ordinador

    S'avalua la seva vessant de laboratori, és a dir, d'implementació, dels continguts tractats fins la data de l'examen. Davant de l'ordinador, els estudiants reben dos o tres problemes. Un problema es defineix amb un enunciat, un o més jocs de proves públics i, potser, cert codi ja implementat. Quan un estudiant vulgui lliurar la seva solució per algun dels problemes, l'enviarà a un jutge automàtic que, en poc segons, li retornarà el veredicte sobre el comportament del seu programa. L'estudiant pot reenviar fins a 10 solucions per al mateix problema. Els professors corregiran el darrer enviament realitzat per cada problema.
    Objectius: 7 8 9 10
    Setmana: 15 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Examen final

    S'avalua dels objectius corresponents als continguts 1 a 7.
    Objectius: 1 2 3 5 4 6 7 8 9 10 12 13 11
    Setmana: 15 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    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.

    Les dues hores de classes de teoria es fan setmanalment. Les dues hores de classes de laboratori es fan quinzenalment. Les dues hores de classes de problemes es fan quinzenalment.

    La programació del joc integra els coneixements i les competències de tot el curs.

    El curs utilitza el llenguatge de programació C++.

    Mètode d'avaluació

    NPP = nota de l'examen parcial de paper (entre 0 i 10)
    NO = nota de l'examen d'ordinador (entre 0 i 10)
    NF = nota de l'examen final (entre 0 i 10)
    NJ = nota del joc (entre 0 i 10)

    NOTA = mín(10, màx (22.5%NPP + 22.5%NF + 45%NO + 20%NJ , 45%NF + 45%NO + 20%NJ))

    Bibliografia

    Bàsic

    Complementari

    Web links

    • MIT OpenCourseWare: és una publicació gratuïta dels materials dels cursos del Massachusets Institute of Technology (MIT) que mostra la majoria de temes que s'ensenyen en el MIT. Conté apunts, exercicis, exercicis resolts, exàmens i videos de classes. MIT OpenCourseWare: es una publicación gratuita de los materiales de los cursos del Massachusets Institute of Technology (MIT) que muestra la mayoría de temas que se enseñan en el MIT. Contiene apuntes, ejercicios, ejercicios resueltos, exámenes y vídeos de clases. MIT OpenCourseWare: it is a free publication of the materials of the courses of the Massachusets Institute of Technology (MIT) that shows most of the topics that are taught in MIT. Contains notes, exercises, solved exercises, exams and videos of classes. http://ocw.mit.edu/courses/#electrical-engineering-and-computer-science
    • UVa Online Judge http://uva.onlinejudge.org/
    • Algorithms Courses on the WWW: és un llistat exhaustiu d'enllaços a portals web relacionats amb algorísmia i complexitat: cursos de diverses universitats, software, aplicacions gràfiques, pàgines personals d'investigadors coneguts, entre d'altres coses. Algorithms Courses on the WWW: es un listado exhaustivo de enlaces a portales web relacionados con la algoritmia y complejidad: cursos de varias universidades, software, aplicaciones gráficas, páginas personales de investigadores conocidos, entre otras cosas. Algorithms Courses on the WWW: it is an exhaustive listing of links to web sites related to algorithms and complexity: courses of several universities, software, graphic applications, personal pages of well-known researchers, among other things. http://www.cs.pitt.edu/~kirk/algorithmcourses/index.html
    • The Stony Brook Algorithm Repository: és un portal web amb una col·lecció d'implementacions de més de setanta algorismes fonamentals d'optimització combinatòria. The Stony Brook Algorithm Repository: es un portal web con una colección de implementaciones de más de setenta algoritmos fundamentales de optimitzación combinatoria. The Stony Brook Algorithm Repository: it is a web site with a collection of implementations of more than seventy fundamental algorithms of combinatorial optimitzation. http://www.cs.sunysb.edu/~algorith/
    • TopCoder http://www.topcoder.com
    • Transparències de K. Wayne per al curs "Algorithms and Data Structures" de la Princeton University https://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures.php
    • Jutge https://www.jutge.org/

    Capacitats prèvies

    S'espera que els estudiants estiguin familiaritzats amb les tècniques de programació imperativa basada en objectes:
    - pas de paràmetres,
    - classes,
    - objectes,
    - mètodes,
    - punters,
    - memòria dinàmica,
    - genericitat,
    - recursivitat,
    - ús de classes estàndard,
    - iteradors.

    També s'espera que coneguin bé almenys un llenguatge imperatiu orientat a objectes, preferentment C++.

    Són també requisits la capacitat crítica i la maduresa matemàtica.