Pla docent de l'assignatura

 

 

Tanca imatge de maquetació

 

Imprimeix

 

Dades generals

 

Nom de l'assignatura: Algorísmica

Codi de l'assignatura: 364298

Curs acadèmic: 2021-2022

Coordinació: Mireia Isabel Ribera Turro

Departament: Departament de Matemàtiques i Informàtica

crèdits: 6

Programa únic: S

 

 

Consideracions prèvies

 

algorismica2021.github.io   Github amb les presentacions del curs i notebooks per als exercicis

 

 

Hores estimades de dedicació

Hores totals 150

 

Activitats presencials i/o no presencials

52,5

 

-  Teoria

No presencial

 

22,5

 

(Assignatura pilot. La teoria s’impartirà amb vídeos pre-fets i amb petits tests d’autoavaluació)

 

-  Teoricopràctica

Presencial

 

15

 

(Amb un aforament del 50 %, la presencialitat serà alterna; Amb un aforament del 100 %, serà continuada)

 

-  Pràctiques d'ordinadors

Presencial

 

15

 

(Amb un aforament del 50 %, la presencialitat serà alterna; Amb un aforament del 100 %, serà continuada)

Treball tutelat/dirigit

47,5

Aprenentatge autònom

50

 

 

Recomanacions

 

És molt important que l’estudiant mantingui un ritme continuat de treball durant el curs i resolgui altres problemes a banda dels proposats a classe per agafar flexibilitat i rapidesa en la programació i resolució d’algorismes.

 

 

Competències que es desenvolupen

 

   -

9aG-GENERAL. Capacitat per resoldre problemes amb iniciativa, prendre decisions, ser autònom i creatiu.

   -

6T-TRANSV. Capacitat abstractiva: crear i utilitzar models que reflecteixin situacions reals.

   -

4T-TRANSV. Capacitat de fer raonaments crítics i lògics.

   -

3ESP - TECNOLOGIA ESPECÍFICA: COMPUTACIÓ. Capacitat per avaluar la complexitat computacional d'un problema, conèixer estratègies algorísmiques que puguin conduir a resoldre'l i recomanar, desenvolupar i implementar el que garanteixi el millor rendiment d'acord amb els requisits establerts.

   -

6FC - FORMACIÓ COMUNA. 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.

   -

3FB - FORMACIÓ BÀSICA. Capacitat per comprendre i dominar els conceptes bàsics de matemàtica discreta, lògica, algorísmica i complexitat computacional, i aplicar-los per resoldre problemes propis de l'enginyeria.

Objectius d'aprenentatge

 

Referits a coneixements

— Conèixer les tècniques algorísmiques bàsiques que permeten abordar el desenvolupament de programes correctes i eficients per resoldre problemes computacionalment no trivials. 

— Conèixer les tècniques bàsiques d’anàlisi d’algorismes que permeten avaluar la complexitat computacional d’un algorisme. 

Pel que fa al document «ACM & IEEE, Computing Curricula 2020 CC2020: Paradigms for Global Computing Education» (https://www.acm.org/binaries/content/assets/education/curricula-recommendations/cc2020.pdf), els continguts d’aquesta assignatura cobreixen els descriptors següents: 

— Analyze correctness, efficiency, performance and complexity of the algorithms using order of complexity terms and present honestly and comprehensively the results of the analysis for either a professional or non-professional audience.

— A. Present to a group of peers the data characteristics of conditions or assumptions that can lead to different behaviors of specific algorithms and from the analysis, illustrate empirical studies to validate hypotheses about runtime measures.

— B. Illustrate informally the time and space complexity of algorithms and use big-O notation formally to show asymptotic upper bounds and expected case bounds on time and space complexity, respectively.

— C. Use recurrence relations to determine the time complexity of recursively defined algorithms by solve elementary recurrence relations and present the results to a group of scholars.

— D. (Partially) Determine an appropriate algorithmic approach to an industry problem and use appropriate techniques (e.g. greedy approach, divide-and-conquer algorithm, recursive backtracking, dynamic programming or heuristic approach) that considers the trade-offs between the brute force to solve a problem.

— E. (Partially) Implement basic numerical algorithm methods (e.g. search algorithms, common quadratic and O(N log N) sorting algorithms, fundamental graph algorithms, string-matching algorithm) to solve an industry problem and select the appropriate algorithm for a particular context.

— SDF-A. Create an appropriate algorithm to illustrate iterative, recursive functions, as well as divide-and-conquer techniques and use a programming language to implement, test, and debug the algorithm for solving a simple industry problem.

 

 

 

Blocs temàtics

 

1. Bases de programació en Python

2. Introducció als algorismes

3. Algorismes numèrics

4. Algorismes i text

5. Estratègies de dividir i vèncer. Recursivitat. Cerca

 

 

Metodologia i activitats formatives

 

A causa de l’emergència sanitària de la COVID-19, el curs 2021-2022 s’iniciarà amb un model de docència alternada. L’alumnat es dividirà en dos grups que alternaran la presencialitat per setmanes. Si les restriccions d’aforament es relaxen, la docència presencial serà continuada. La docència s’estructurarà d’aquesta forma:

En la mesura que sigui possible s’incorporarà la perspectiva de gènere en el desenvolupament de l’assignatura

  • L’assignatura té un bloc no presencial asíncron d’una hora i mitja en què els professors expliquen els conceptes teòrics bàsics de l’assignatura, i es proposen petites proves d’autoavaluació o material complementari.
  • L’assignatura té un altre bloc presencial d’una hora i mitja que es dedica a classes de pràctiques de laboratori, en què l’estudiant ha de resoldre les pràctiques que li ha proposat el professorat, de manera individual. Durant l’horari d’aquest bloc el professor de pràctiques donarà indicacions a les classes presencials i també atendrà els alumnes en línia. Durant el període d’aforament limitat, cada pràctica tindrà una durada de dues setmanes: a la primera es plantejarà la pràctica, es donaran instruccions i materials; a la segona l’estudiant assistirà al laboratori, resoldrà dubtes i finalitzarà la pràctica lliurant-la. Si l’aforament es relaxa, les pràctiques tindran el mateix format però els alumnes podran assistir al laboratori totes les setmanes.
  • Finalment, l’assignatura té un bloc presencial d’una hora i mitja a la setmana, corresponent a activitats teoricopràctiques. En aquestes classes es dedica un període de temps al reforçament dels conceptes teòrics, a la resolució de problemes i a la realització de proves d’avaluació.


En cas que l’autoritat sanitària decretés un nou confinament de la població, es passaria a un format totalment no presencial, conservant la càrrega horària.

 

 

 

Avaluació acreditativa dels aprenentatges

 

L’avaluació de l’assignatura segueix un model d’avaluació continuada

L’avaluació continuada es basa en tres instruments d’avaluació: proves de coneixement al llarg del curs, el lliurament de problemes resolts amb ordinador i un examen final. Més concretament: 

  • Es fa un examen parcial (EP) al llarg del curs i un examen final (EF) amb una part pràctica i una part teòrica. A l’examen final es permet recuperar la part de l’examen parcial en cas de suspens. Depenent de la situació sanitària, els exàmens es faran en modalitat presencial o no presencial.
  • Lliurament de pràctiques. El professorat proposa diverses pràctiques de laboratori a resoldre individualment. Si l’estudiant no lliura els problemes dins del període assenyalat, obté un 0. La nota final (LP) de la part de lliurament de problemes és la mitjana de tots els lliuraments.


La nota d’avaluació continuada és AC = 0,3 * LP + 0,3 * EP + 0,4 EF, sempre que (LP > 4,0) i ((EP+EF)/2 > 4,0). Altrament, la nota d’avaluació continuada és min(4,0 ; ( 0,3 * LP + 0,3 * EP + 0,4 EF)). 

En el cas de no arribar a l’aprovat per avaluació continuada, tots aquells alumnes que obtinguin una AC >= 3,5 tenen dret a un examen de reavaluació. La nota final de l’assignatura és llavors la nota de la reavaluació.

Qualsevol intent de frau comporta l’aplicació de la normativa acadèmica general de la Universitat de Barcelona i l’inici d’un procés disciplinari.

 

Avaluació única

L’avaluació única (AU) consisteix en un examen final únic que consta d’una part de teoria i una prova pràctica, que té lloc el mateix dia que l’examen final. Depenent de la situació sanitària, aquests exàmens es faran en modalitat presencial o no presencial.

L’estudiant que es vulgui acollir a l’avaluació única ho ha de sol·licitar a la Secretaria de la Facultat dins dels terminis establerts cada curs acadèmic.

Aquells alumnes que obtinguin una AU que compleixi 3,5 <= AU < 5,0 tenen dret a una reavaluació. La nota final de l’assignatura és llavors la nota de la reavaluació.

 

 

Fonts d'informació bàsica

Consulteu la disponibilitat a CERCABIB

Llibre

Cormen, T.H. [et al]. Introduction to algorithms. 3rd ed. Cambridge, Mass. : MIT Press ; New York : McGraw-Hill, 2009.  Enllaç

  eTextbook option https://mitpress.ublish.com/book/introduction-algorithms#purchase renting

Dasgupta, S. Papadimitriou, C. ; Vazirani, U. Algorithms. Borston [etc.] : Mc Graw Hill / Higher Education, 2008. (ebook)  Enllaç

Levitin, A. Introduction to the design and analysis of algorithms. 3rd ed. Ebook edition Boston, MA : Addison Wesley, 2014  Enllaç

  https://www.dymocks.com.au/book/introduction-to-the-design-and-analysis-of-algorithms-by-anany-levitin-9781292014111

Skiena, S. The algorithm design manual. 3rd ed. London : Springer, 2020.

  (L’edició de 2008 està accessible en línia amb Springer a través del CRAI)

Downey, A. ; Elkner, J. ; Meyers, C. How to think like a computer scientist : learning with python. Wellesley : Green Tea Press, 2009.  Enllaç

Accés lliure al text complet  Enllaç
Segona edició: Think Python (O’Reilly, 2015)  Enllaç
Accés lliure al text complet  Enllaç

Desafíos de programación: El manual de entrenamiento para concursos de programación OJ Books, 2020 ISBN 8412238044

  L’edició anterior està disponible en anglès a https://link-springer-com.sire.ub.edu/book/10.1007%2Fb97559

Vitrià, Ribera, Laiz, Gilabert Problemes bàsics d’algorísmica Publicacions UB [en premsa]