Per a qualsevol dubte i/o qüestió es recomana enviar un correu electrònic al professorat de l'assignatura.
Resoldre els problemes i exercicis de programació que es proposen diariament permet assolir els objectius d'aprenentatge establerts.
Assignatura/matèria en el conjunt del pla d'estudis (màx. 4000 caràcters)
Assignatura que s’imparteix durant el 2n semestre del 2n curs de la titulació Grau en Enginyeria Informàtica. Correspon a la Matèria “Informàtica” dins del Mòdul de “Formació Bàsica”.
Requisits per cursar-la
Prerequisits
Corequisits
Professorat
Nom
Correu
Horari de consulta
Crèdits teòrics
Crèdits pràctics
Jordi Planes Cid
jplanes@diei.udl.cat
Cita per correu electrònic
7.2
Maria Teresa Alsinet Bernadó
tracy@diei.udl.cat
Cita per correu electrònic
3.6
Competències
Competències estratègiques de la Universitat de Lleida
Competències específiques de la titulació
Capacitat per analitzar, dissenyar, construir i mantenir aplicacions de forma robusta, segura i eficient, triant el paradigma i els llenguatges de programació més adequats.
Objectius
Identificar la tipologia del problema i identificar l'estratègia algorísmia adequada.
Dissenyar i implementar estratègies algorísmies adequades per resoldre les diferents tipologies de problemes.
Dissenyar i implementar solucions algorísmies utilitzant la tècnica de divideix i venç.
Dissenyar i implementar solucions algorísmies utilitzant la tècnica voraç.
Dissenyar i implementar solucions algorísmies utilitzant la tècnica de retrocés.
Optimitzar solucions algorísmies basades en la tècnica de retrocés mitjançant el disseny i implementació d'heurístiques de poda de l'espai de cerca.
Dissenyar i implementar solucions algorísmies utilitzant la tècnica de programació dinàmica.
Analitzar la complexitat espaial i temporal de les estratègies algorísmies adoptades.
Capacitat per comprendre i dominar els conceptes bàsics de matemàtica discreta, lògica, algorísmica i complexitat computacional, i la seva aplicació per a la resolució de problemes propis de l'enginyeria.
Objectius
Dissenyar i implementar estructures de dades adecuades per representar la informació pròpia de cada problema.
Dissenyar i implementar de forma eficient les operacions associades amb les estructures de dades identificades.
Integrar de forma eficient les estructures de dades i les estratègies algorísmies necessàries per resoldrer problemes complexes.
Optimitzar l'eficiència de les solucions dissenyades.
Coneixement i aplicació dels procediments algorísmics bàsics de les tecnologies informàtiques per dissenyar solucions a problemes, analitzant la idoneïtat i complexitat dels algorismes proposats.
Objectius
Dissenyar i implementar estratègies algorísmies eficients per resoldre les diferents tipologies de problemes.
Utilitzar les funcionalitats pròpies dels llenguatges de programación per a la implementació de les solucions.
Utilitzar un entorn de desenvolupament de programes basat en un llenguatge de programació d'alt nivel.
Desenvolupar implementacions eficients.
Coneixement, disseny i utilització de forma eficient dels tipus i estructures de dades més adequats a la resolució d'un problema.
Objectius
Caracteritzar formalment els problemes.
Analitzar l'eficiència dels algorísmes mitjançant l'ús de la notació asintòtica per a l'estudi del cost temporal o temps d'execució dels algorísmes.
Analitzar l'eficiència dels algorísmes mitjançant l'ús de la notació asintòtica per a l'estudi del cost espaial dels algorísmes.
Utilitzar les tècniques de verificació formal d'algorismes aplicades sobre algorismes recursius i iteratius.
Utilitzar les tècniques de transformació d'algorismes recursius.
Utilitzar les tècniques d'optimització d'algorismes.
Competències transversals de la titulació
Continguts
Continguts de la matèria
Els continguts del curs s'estructuren en quatre unitats didàctiques. La primera té com a objectiu estudiar la caracterització formal d'algorismes. En aquest sentit estudiarem la tècnica d'especificació formal d'algorismes basada en precondició i postcondició i analitzarem l'eficiència dels algorísmes mitjançant l'ús de la notació asimptòtica per a l'estudi del cost temporal o temps d'execució dels algorísmes. La segona unitat didàctica té com a objectiu l'estudi de tècniques de verificació formal d'algorismes aplicades sobre algorismes recursius i iteratius, i l'estudi de tècniques de transformació d'algorismes recursius. La tercera unitat didàctica té com a objectiu l'estudi d'esquemes algorísmics, és a dir, analitzar, dissenyar i aplicar algorismes capaços de resoldre no únicament un problema concret, sino una família de problemes tots amb la mateixa tipificació. Els esquemes algorísmics que estudiarem són quatre: divideix i venç, voraç, retrocès i programació dinàmica. L'anàlisi i disseny sistemàtic d'algorismes a partir d'un esquema concret es centra en l'estudi i desenvolupament de solucions o estratègies concretes per resoldre un problema. Una aproximació diferent consisteix en considerar globalment tots el algorismes o estratègies que poden resoldre un problema concret. Això inclou tots els possibles algorismes o estratègies que encara no s'han definit. Aquesta aproximació és la que es considera en el camp de la complexitat computacional el qual serà breument introduït en la darrera unitat didàctica. L'estudi de cada tècnica i esquema algorísmic l'abordarem a partir de la resolució de problemes concrets per a cada tipologia. A més, les solucions algorísmiques desenvolupades al llarg del curs seran implementades en el llenguatge C++. Des del punt de vista d'implementació dels algorismes, també es realitzarà un estudi empíric del temp d'execució per a diferents instàncies dels problemes tractats. L'estudi empíric del temps d'execució de les implementacions evidenciarà de forma pràctica l'eficiència de les diferents estratègies algorísmiques estudiades al llarg del curs.
Organització del curs per temes:
1. Preliminars: algorisme, notació, lògica de predicats, tècniques de demostració.
2. Especificació formal d'algorismes basada en pre-post condicions.
3. Eficiència dels algorísmes. Notació asimptòtica. Anàlisi d'algorismes.
4. Verificació formal d'algorismes recursius i iteratius.
5. Tècniques de transformació d'algorismes recursius.
6. Esquemes algorísmics: divideix i venç.
7. Esquemes algorísmics: voraç.
8. Esquemes algorísmics: retrocès.
9. Optimització de l'esquema algorísmic de retrocès mitjançant l'ús d'heurístiques.
10. Esquemes algorísmics: programació dinàmica.
11. Introducció a la complexitat computacional.
Bibliografia
Bibliografia recomanada
Bàsica:
* G. Brassard y P. Bratley. Fundamentos de algoritmia. Prentice Hall. 1997. * M. Goodrich y R. Tamassia. Algorithm Design. John Wiley & Sons. 2011.
Primera part del curs:
* R. Peña Marí. Diseño de programas. Formalismo y abstracción 3 ed. Prentice Hall 2003 * J.L. Balcázar. Programación Metódica. McGraw-Hill, 1993.
Estructures de dades i esquemes algorísmics:
* J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley 2006. * Cormen, T.H.; Leiserson, C.E. ; Rivest, R.L.; Stein, C. Introduction to Algorithms, (3ª edición). MIT Press, 2002. * M. Weiss. Estructuras de datos y algoritmos. Addison-Wesley Iberoamericana.1995. * R. Kruse. Estructuras de Datos y Diseño de programas. .Prentice Hall. 1998.
* Skiena, S. The Algorithm Design Manual. Springer 2008.
Complexitat computacional:
* J.E. Hopcroft, R. Motwani, J. D. Ullman. Teoría de autómatas,lenguajes y computación. Pearson. Addison Wesley. Tercera Edición, 2007
Problemes resolts:
* R. Guerequeta y A. Vallecillo. Tecnicas de diseño de algoritmos. Servicio de Publicaciones de la Universidad de Málaga. 2nd Ed. 2000. http://www.lcc.uma.es/~av/Libro/indice.html * Gonzalo, J.; Rodríguez, M. Esquemas algorítmicos: enfoque metodológico y problemas resueltos, UNED, 1997. * Martí, N.; Ortega, Y.; Verdejo, J. A. Estructuras de datos y métodos algorítmicos. Prentice Práctica, 2003
Implementació:
* Stroustrup, B. The C++ Programming Language. Addison-Wesley. 3rd edition. 1997.
* Meyers, S. Effective C++. 3rd edition. 2005.
* Meyers, S. More Effective C++. 1995.
* R. Sedgewick. Algoritmos en C++. Addison-Wesley / Diaz de Santos.1995.
* M. Weiss. Estructuras de datos en JAVA. Addison Wesley/ Pearson Education. Madrid 2000.