Estructures de Dades i Algorismes ( EDA )

• ÚS SOLVENT DELS RECURSOS D'INFORMACIÓ

• G6 - 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.
  

• 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.
  

1. Conèixer 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 conèixer 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
   • CT2.4,
   • CT4.1,
   • CT4.2,
   • CT5.2
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
   • CT2.4,
   • CT4.1,
   • CT4.2,
   • CT5.2
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
   • CT2.4,
   • CT4.1,
   • CT4.2,
   • CT5.2
10. Conèixer, explicar, dissenyar, analitzar, comparar i implementar algorismes de cerca exhaustiva fent servir la tècnica de backtracking.
    
    Competències relacionades
    • CT2.4,
    • CT4.1,
    • CT4.2,
    • CT4.3
11. Prendre consciència dels límits de la computació: comprendre les implicacions de la pregunta "P=NP?", 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.1,
    • CT5.2
13. Identificar i proposar solucions per problemes d'eficiència d'algorismes i de programes escrits en llenguatge de programació C++.
    
    Competències relacionades
    • CT2.3,
    • CT2.4,
    • CT4.1,
    • CT4.2,
    • CT5.2
14. Analitzar un joc estratègic per dissenyar i programar un jugador eficaç,
    eficient, col·laboratiu i competitu 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
    • CT2.3,
    • CT2.4,
    • CT4.1,
    • CT4.2,
    • CT4.3,
    • CT5.1,
    • CT5.2,
    • CT5.3,
    • CT5.4,
    • CT5.5,
    • G6.2,
    • CT8.6,
    • CT8.7
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

Llegenda

Activitat	Activitat de tipus Acte avaluatiu	T	P	L	AA	AD
Activitat	Activitat de tipus Acte avaluatiu	Hores de Teoria	Hores de Problemes	Hores de Laboratori	Hores d'Aprenentatge Autònom	Hores d'Aprenentatge Dirigit

Anàlisi d'Algorismes	T	P	L	AA	AD	Total
	4.0	2.0	2.0	8.0	0.0	16.0
Alumne: Desenvolupament del tema 1 de l'assignatura. Objectius: 1, 2, 3, 4, 5 Continguts 1. Anàlisi d'Algorismes

Algorismes de Dividir i Vèncer	T	P	L	AA	AD	Total
	4.0	2.0	2.0	8.0	0.0	16.0
Alumne: Desenvolupament del tema 2 de l'assignatura. Objectius: 3, 4, 5, 6, 12, 13 Continguts 2. Algorismes de Dividir i Vèncer

Diccionaris	T	P	L	AA	AD	Total
	4.0	2.0	2.0	8.0	0.0	16.0
Alumne: Desenvolupament del tema 3 de l'assignatura. Objectius: 4, 5, 7, 12, 13 Continguts 3. Diccionaris

Examen parcial de paper	T	P	L	AA	AD	Total
	-	-	-	4.0	2.0	6.0
S'avalua dels objectius corresponents als continguts 1 i 2. Setmana 6 (Fora l'horari de classe) Tipus Examen: Control de teoria Objectius: 1, 2, 3, 4, 5, 6, 12

Cues amb Prioritats	T	P	L	AA	AD	Total
	2.0	1.0	1.0	4.0	0.0	8.0
Alumne: Desenvolupament del tema 4 de l'assignatura. Objectius: 4, 5, 8, 12, 13 Continguts 4. Cues amb Prioritats

Grafs	T	P	L	AA	AD	Total
	4.0	2.0	2.0	8.0	0.0	16.0
Alumne: Desenvolupament del tema 5 de l'assignatura. Objectius: 4, 5, 9, 12, 13 Continguts 5. Grafs

Joc	T	P	L	AA	AD	Total
	-	-	-	16.0	1.5	17.5
S'avalua dels objectius corresponents al objectiu específic 15. Després del parcial, es lliurarà un enunciat que consistirà en la descripció d'un joc. Els estudiants hauran de programar un jugador per aquest joc (és a dir, implementar una estratègia per intentar guanyar el joc). Juntament amb l'enunciat, els professors també proveiran el codi d'un jugador molt senzill: el "tonto". Cap a mitjans de curs, hi haurà un enfrontament públic a través d'un sistema de rondes que inclourà tots els jugadors lliurats pels estudiants i el tonto. D'aquest enfrontament es deduirà una classificació i es nomenarà un campió. La nota del joc es calcula automàticament a partir de la posició a la classificació, de forma lineal i garantint que el campió tingui un 10 i que tots els participants que guanyin al tonto tinguin un nota mínima de 5. Els jugadors que no guanyin al tonto tindran una nota de 0. El lliurament de programes pel joc implica acceptar que, si es comprova que hi ha hagut frau en la seva realització, es restaran els seus punts (enlloc de sumar-los) als de l'assignatura. No calen aules. Setmana 9 (Fora l'horari de classe) Tipus Examen: Control de laboratori Objectius: 14

Algorismes de Generació i Cerca Exhaustiva	T	P	L	AA	AD	Total
	4.0	2.0	4.0	8.0	0.0	18.0
Alumne: Desenvolupament del tema 6 de l'assignatura. Objectius: 4, 5, 10, 12, 13 Continguts 6. Algorismes de Generació i Cerca Exhaustiva

Nocions d'Intractabilitat i Indecidibilitat	T	P	L	AA	AD	Total
	4.0	2.0	0.0	4.0	0.0	10.0
Alumne: Desenvolupament del tema 7 de l'assignatura. Objectius: 11 Continguts 8. Nocions d'Intractabilitat i d'Indecidibilitat

Examen parcial d'ordinador	T	P	L	AA	AD	Total
	-	-	-	4.0	2.5	6.5
S'avalua dels objectius corresponents als continguts 3 a 6 en la seva vessant de laboratori, és a dir, d'implementació. 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'envia 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. Setmana 12 (Fora l'horari de classe) Tipus Examen: Control de laboratori Objectius: 7, 8, 9, 10

Consolidació.	T	P	L	AA	AD	Total
	2.0	1.0	1.0	4.5	0.0	8.5
Alumne: Repàs. Objectius: 1, 2, 3, 4, 5, 12, 13 Continguts 1. Anàlisi d'Algorismes 2. Algorismes de Dividir i Vèncer 3. Diccionaris 4. Cues amb Prioritats 5. Grafs 6. Algorismes de Generació i Cerca Exhaustiva 8. Nocions d'Intractabilitat i d'Indecidibilitat

Tutorials Bibliotècnica-BRGF.	T	P	L	AA	AD	Total
	0.0	0.0	0.0	2.5	0.0	2.5
Alumne: Autoaprenentatge mitjançant tutorials de la Bibliotècnica de la Biblioteca Rector Gabriel Ferraté 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

Pràctica d'ús solvent de recursos d'informació.	T	P	L	AA	AD	Total
	-	-	-	5.0	0.0	5.0
S'avalua dels objectius corresponents al objectiu específic 16. Poc abans del parcial d'ordinador, es lliurarà 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 parcial d'ordinador. La competència transversal s'avalua a través d'aquest document. No calen aules. Setmana 14 (Fora l'horari de classe) Tipus Examen: Control de teoria Objectius: 15

Examen final	T	P	L	AA	AD	Total
	-	-	-	10.0	3.0	13.0
S'avalua dels objectius corresponents als continguts 1 a 7 (pels temes 3 a 6 no s'avalua la seva vessant de laboratori). Setmana 15-18 (Fora l'horari de classe) Tipus Examen: Examen final Objectius: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

Total per tipus	T	P	L	AA	AD	Total
	28.0	14.0	14.0	94.0	9.0	159.0

El temari s'exposa de forma molt pràctica, a través de la presentació de molts exemples.

Les classes de teoria introdueixen tot els coneixements, les tècniques, els conceptes necessaris que es posen en pràctica en les classes de problemes i de laboratori, així com amb treball personal utilitzant 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++.

Tipus d'avaluació

Assignatura que s'avalua en període d'examens

NPP = nota de l'examen parcial de paper (entre 0 i 10)
NPO = nota de l'examen parcial 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 (30%NPP + 30%NPO + 30%NF + 20%NJ , 30%NPO + 60%NF + 20%NJ))

Pes de les competències transversals en l'avaluació de la part específica de l'assignatura

• 5.0 % - 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.

• CORMEN, Thomas H. i LEISERSON, Charles E. i RIVEST, Ronald L. i STEIN, Clifford. , Introduction to Algorithms (3rd Edition) , The MIT Press , 2009 .



• SEDGEWICK, Robert. , Algorithms in C++, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching and Graph Algorithms (3rd Edition) , Addison-Wesley , 2001 .



• WEISS, M.A. , Data Structures and Algorithm Analysis in C++ (2nd Edition) , Addison-Wesley , 1999 .



• DASGUPTA, Sanjoy i PAPADIMITRIOU, Christos i VAZIRANI, Umesh. , Algorithms , Mc Graw Hill , 2008 .



• BRASSARD, G. i BRATLEY, P. , Fundamentos de Algoritmia , Prentice Hall , 1997 .

• WEISS, M.A. , Data Structures and Problem Solving Using C++ (2nd Edition) , Addison-Wesley , 2000 .



• MANBER, Udi. , Introduction to Algorithms. A Creative Approach , Addison-Wesley , 1989 .



• HAREL, David i FELDMAN, Yishai , Algorithmics. The Spirit of Computing (3rd. Edition) , Addison-Wesley , 2004 , ISBN:0 321 11784 0..

http://www.lsi.upc.edu/~eda

1. http://ocw.mit.edu/courses/#electrical-engineering-and-computer-science
   MIT OpenCourseWare: és una publicació gratuita dels materials dels cursos del Massachusets Institute of Technology (MIT) que mostra la majoria de temes que s'ensenyen als graus i postgraus del MIT. Conté apunts, exercicis, exercicis resolts, exàmens i videos de classes.
   
2. http://www.cs.pitt.edu/~kirk/algorithmcourses/index.html
   Algorithms Courses on the WWW: és un
   llistat exhaustiu de enllaços a portals web relacionats amb algorísmia i complexitat: cursos de diverses universitats, software, aplicacions gràfiques, pàgines personals de investigadors coneguts, entre d'altres.
3. http://www.cs.sunysb.edu/~algorith/
   The Stony Brook Algorithm Repository: és un portal web amb la intenció de servir com a col·lecció entenedora de implementacions d'algorismes de més de setente algorismes fundamentals de optimització combinatòria.
4. http://uva.onlinejudge.org/
   UVa Online Judge
5. http://www.topcoder.com
   TopCoder

Domini de 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.

Conèixer bé almenys un llenguatge imperatiu orientat a objectes, preferentment C++.

Capacitat crítica.

Maduresa matemàtica.