21711. Algorísmia . Grup 2

Identificació de l'assignatura

Assignatura21711 - Algorísmia
Grup Grup 2 ( Campus Digital )
Any acadèmic 2018-19
Crèdits6 crèdits
Període d'impartició Primer semestre
Idioma d'impartició Català
Titulació -

Professors

Professor/aHorari d'atenció alumnes
Hora d'iniciHora de fiDia de la setmanaData d'iniciData de fiDespatx/Edifici
Antoni Jaume Capó
antoni.jaumeantoni.jaume@uib.esuib.es
(Responsable)
12:00h13:00h Dimarts 01/09/201831/07/2019 D170 Edifici Anselm Turmeda

Contextualització

Algorísmia és una assignatura del mòdul comú de la branca d'Informàtica que s'imparteix el primer semestre del segon curs. És una assignatura obligatòria de segon nivell relacionada amb la programació d'ordinadors, on l?alumne ha d?assolir els coneixements, habilitats i bones pràctiques adients sobre el paradigma de la programació orientada a objectes (POO), la correcció i optimalitat dels algorismes, l'ús del disseny recursiu en la resolució de problemes i l'aplicació d'una sèrie de tècniques avançades de programació per a la resolució de problemes.

En definitiva, es tracta d'adquirir les competències necessàries en l'aplicació dels procediments algorísmics bàsics de les tecnologies informàtiques per dissenyar solucions a problemes, analitzant la idoneïtat, optimalitat i complexitat dels algorismes desenvolupats i/o proposats.

Requisits

Es tracta d'una assignatura eminentment relacionada amb les tècniques de programació, per tant els coneixements prèvis essencials de què l'alumne/a ha de disposar estaran lligats amb conceptes relacionats amb el disseny i desenvolupament de programari (software).

Recomanables

És molt recomanable haver cursat i aprovat les assignatures "Programació informàtica I" (codi 20302) "Programació informàtica II" (codi: 21707) del primer curs del grau en ingenyeria informàtica.

També es recomana haver cursat les següent assignatures: 1) Matemàtica discreta (codi: 20300). 2) Matemàtica II, càlcul (codi:20301). 3) Matemàtiques III, estadística (codi: 20305). 4) Mètodes de l'àlgebra lineal (codi: 21705). 5) Estructura de computadors I (codi: 21706).

Encara que no és obligatòri haver cursat aquestes assignatures, si que és recomenable haver-ho fet, ja que molts dels conceptes que es veuen a elles estan relacionats, directa o indirectament, amb el desenvolupament i disseny de tècniques algorísmiques.

Competències

Les competències són els coneixements, capacitats, habilitats, destreses i conductes que condueixin inexorablement a la maduresa en la tasca d'aprenentatge, l'assoliment de les quals garantirà la superació de l'assignatura Algorísmia per part de l'alumnat.

Per a l'assoliment de les competències resulta fonamental que els alumnes interioritzin tres actituts essencials: la responsabilitat, l'autonomia i la col.laboració amb l'entorn docent. La gestió del temps i la planificació de les tasques són dos aspectes fonamentals en l'organització de l'alumne per aconseguir l'èxit del seu procés d'aprenentatge.

Específiques

  • CCM06: 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.
  • CCM08: Capacitat per analitzar, dissenyar, construir i mantenir aplicacions de forma robusta, segura i eficient, seleccionant el paradigma i els llenguatges de programació més adequats.

Genèriques

  • CTR01: Capacitat d'anàlisi i síntesi, d'organització, de planificació i de presa de decisions.
  • CTR02: Capacitat d'anàlisi crítica i de proposta i aplicació de noves solucions.
  • CTR07: Capacitat per comunicar conceptes propis de la informàtica de manera oral i escrita en diferents àmbits d'actuació.

Bàsiques

Podeu consultar les competències bàsiques que l'estudiant ha d'haver assolit en acabar el grau a l'adreça següent: http://estudis.uib.cat/grau/comp_basiques/

Continguts

L'assignatura cobreix un conjunt de tècniques i eines per al desenvolupament i verificació d'algorismes eficients en el context de la solució d'una gran varietat de problemes. En particular, es pretén: potenciar la resolució de problemes a través dels potents mecanismes que ens ofereix la programació orientada a objectes, facilitar el disseny de solucions mitjançant l'ús de la programació modular, facilitar i garantir un alt grau de correctesa de les solucions algorísmiques dissenyades, disposar d'eines per tal d'analitzar l'eficiència computacional dels algorismes, trobar solucions idònies per a una varietat de tipus de problemes i promoure l'excepcional i potent eina de la recursivitat per a la solució de problemes.

Continguts temàtics

Tema 1 Fonaments de la programació orientada a objecte

Aquí es repassen, reforcen i estenen els coneixements que l'alumnat ja ha après de cursos inferiors sobre la programació orientada a objectes. D'una banda, es fonamenten els principals conceptes, en particular les nocions d'objecte, classe, instància, encapsulament, herència, sobrecàrrega, polimorfisme, missatges i esdeveniments. D'altra banda, es desenvolupa una metodologia de disseny de programes en programació orientada a objectes.

Tema 2 Lògica de programes

Aquest tema tracta sobre la correctesa, especificació i verificació formal de programes. Per això, es defineix un lenguatge que possibiliti l'especificació formal de programes orientat a la verificació de la seva correctesa; s'estableixen els conceptes fonamentals, com la lògica de programes, conjunt d'estats, predicats, inferència lògica i precondició més feble, i es presenten els mecanismes per a la verificació formal dels programes. Es fa un tractament formal d'una sèrie d'exemples senzills.

Tema 3 Anàlisi del cost dels algorismes

En aquest tema l'alumne/a aprendrà com avaluar els costs del algoritmes, en consum de memòria i en temps de computació. Per això, es defineix el concepte d'eficiència dels algorismes en termes del cost de complexitat asimptòtic, de manera totalment independent de la plataforma en què aquests s'executin. L'estudi s'estén tant al càlcul del cost de complexitat asimptòtic dels algorismes no recursius com dels recursius (en aquests darrers a través de l'anàlisi de recurrències).

Tema 4 Recursivitat

En aquest tema s'estudien els fonaments del raonament inductiu com a base del disseny recursiu de programes, s'estableixen les bases per a la verificació formal de programes recursius, es confronten les principals habilitats del programes recursius i iteratius, presentant métodes de transformació recursiu-iteratiu i es presenten les principals tècniques recursives per a la solució de problemes.

Tema 5 Problemes d'assignació

En aquest tema s'estudien les principals tècniques de resolució de problemes a través dels corresponents esquemes algorísmics. Els alumnes aprendran a categoritzar els problemes d'acord amb les tècniques de resolució més adients i proccedir al disseny de les corresponents solucions.

Metodologia docent

La metodologia docent és el conjunt de tècniques, metodologies i estratègies d'ensenyament emprades pel professor per tal d'assolir els objectius de l'assignatura. Constitueix la guia del procés d'aprenentatge dels estudiants. La metodologia docent emprada a l'assignatura es basa en la combinació dels anteriors elements, la selecció dels quals ve motivada per les característiques del temari, el nivell de competències prèvies dels alumnes i, sobretot, la intenció de motivar els estudiants en la seva tasca d'aprenentatge.

Els principals elements metodològics implantats a l'assignatura són: L'aprenentatge basat en problemes, l'aprenentatge basat en projectes, el flipped classroom (aprenentatge invertit), la gamificació, les lliçons magistrals i les tutories individuals i de grup.

Les activitats d'aprenentatge són les tasques que han de dur a terme els alumnes en el seu procés d'aprenentatge. El desenvolupament d'aquestes es fa d'acord amb els elements metodològics implantats per el professor, el qual s'encarrega de guiar-les, monitoritzar-les i avaluar-les. Un aspecte important és la diversificació de les activitats d'aprenentatge i la possibilitat de dur-les a terme individualment o en grup, segons l'establert pel professor.

A continuació s'exposen les línies generals que han de conduir a un desenvolupament exitós de l'assignatura, sempre i quan factors aliens a la voluntad del professor no ho impedeixin.

Volum de treball

La distribució del volum de treball presencial és orientativa i representa la planificació de l'assignatura realitzada pels professors, sense tenir en compte els imprevists que puguin aparèixer durant el curs.

En quan a la distribució de treball no presencial, que també és orientativa, representa la distribució ideal planificada pels professors. Les activitats de l'assignatura estan planificades per què l'estudiant mitjà, per a cada hora de treball presencial, treballi una hora i mitja de forma autònoma (estudi individual, resolució d'exercicis, etc...). Sense un treball no presencial d'aquesta magnitud serà difícil assolir un nivell suficient de coneixements i les competències desitjades.

Activitats de treball presencial (2,4 crèdits, 60 hores)

ModalitatNomTip. agr.DescripcióHores
Classes teòriques Temes 1-4 Grup gran (G)

Mitjançant el mètode expositiu, el professor establirà els fonaments teòrics, així com l'exemplificació pràctica dels temes 1-4 (el 4 parcialment). La participació dels alumnes serà molt important.

21
Classes teòriques Temes 4-5 Grup gran (G)

Mitjançant el mètode expositiu, el professor establirà els fonaments teòrics, així com l'exemplificació pràctica dels temes 4 (parcialment) i 5. La participació dels alumnes serà molt important.

24
Classes de laboratori Sessions de Laboratori i Pràctiques Grup mitjà (M)

Es resoldran diferents problemes mostrant-hi solucions alternatives i comparar-les dels temes 1 a 5. Per algunes problemes proposats, un cop acabada la sessió de classes pràctiques o laboratori, l'alumnat haurà de pujar les seves solucions en Aula Digital. Algunes solucions es pujaran com glossari perquè tot el grup pugui veure totes les solucions. Altres es pujaran com a taller perquè l'alumnat pugui autoavaluar i coavaluar.

15

A començament del semestre hi haurà a disposició dels estudiants el cronograma de l'assignatura a través de la plataforma UIBdigital. Aquest cronograma inclourà almenys les dates en què es faran les proves d'avaluació contínua i les dates de lliurament dels treballs. A més, el professor o la professora informarà els estudiants si el pla de treball de l'assignatura es durà a terme a través del cronograma o per una altra via, inclosa la plataforma Campus Extens.

Activitats de treball no presencial (3,6 crèdits, 90 hores)

ModalitatNomDescripcióHores
Estudi i treball autònom individual #somEPS

Assistència a una de les sessions #somEPS (http://eps.uib.es/someps/) relacionades amb els continguts i competències de l'assignatura.

2
Estudi i treball autònom individual o en grup Projecte de Programació Orientada a Objectes

En aquest projecte es proposa a l'alumnat un problema que per solucionar-ho de forma òptima s'hagin d'utilitzar els conceptes d'objecte, classe i instància; d'herència; i d'encapsulament, sobrecàrrega i polimorfisme.

15
Estudi i treball autònom individual o en grup Projecte sobre disseny i la verificació d'algoritmes recursius

En aquest projecte es presenta un algorisme simple perquè l'alumnat ho verifiqui formalment, analitzi el seu cost i apliqui l'anàlisi per al disseny i la verificació d'algoritmes recursius per proposar una solució més òptima.

10
Estudi i treball autònom individual o en grup Projecte d'Esquemes algorísmics

En aquest projecte es presenta un problema perquè l'alumnat implementi la solució més òptima amb els esquemes algorítmics vistos en hores de treball presencial, i justifiqui l'esquema escollit i els esquemes descartats.

35
Estudi i treball autònom individual o en grup Estudi de l'assignatura

Estudi individual o en grup dels continguts de l'assignatura i del que el professor ha encarregat.

28

Riscs especifics i mesures de protecció

Les activitats d'aprenentatge d'aquesta assignatura no comporten riscs específics per a la seguretat i salut dels alumnes i, per tant, no cal adoptar mesures de protecció especials.

Avaluació de l'aprenentatge dels estudiants

CONSIDERACIONS GENERALS.

S'estableixen dos itineraris d'avaluació diferents:

* Itinerari A: és l'itinerari per defecte.

* Itinerari B: està pensat per alumnes a temps parcial. L'accés a aquest itinerari està condicionat a l'obtenció del certificat d'alumne a temps parcial.

Observacions:

* Els estudiants que segueixin l'itinerari A hauran d'assistir obligatòriament a un mínim d'un 80% de les classes.

* Per defecte, tots els estudiants seran avaluats mitjançant l'itinerari A.

* Aquells alumnes que desitjin ser avaluats mitjançant l'itinerari B, hauran de presentar el certificat d'alumne a temps parcial.

* Les activitats marcades com NO RECUPERABLES tendran uns plaços d'entrega que han de ser respectats pels estudiants per poder ser avaluades positivament.

* Els alumnes podran reclamar la nota de les activitats durant els 7 dies següents a la seva publicació. No s'admetran reclamacions fora de plaç.

D'acord amb l'article 33 del Reglament Acadèmic, "amb independència del procediment disciplinari que es pugui seguir contra l'estudiant infractor, la realització demostradorament fraudulenta d'algun dels elements d'avaluació inclosos en guies docents de les assignatures comportarà, a criteri del professor, una menysvaloració en la seva qualificació que pot suposar la qualificació de «suspens 0» a l'avaluació anual de l'assignatura".

Temes 1-4
Modalitat Classes teòriques
Tècnica Proves de resposta llarga, de desenvolupament ( no recuperable )
Descripció

Mitjançant el mètode expositiu, el professor establirà els fonaments teòrics, així com l'exemplificació pràctica dels temes 1-4 (el 4 parcialment). La participació dels alumnes serà molt important.

Criteris d'avaluació

Examen amb preguntes de desenvolupament que inclouen conceptes teòrics, procediments i problemes. En cada apartat de l'examen s'indica la seva puntuació.

Competències: CCM06 CTR01

Percentatge de la qualificació final: 15% per a l'itinerari A
Percentatge de la qualificació final: 15% per a l'itinerari B

Temes 4-5
Modalitat Classes teòriques
Tècnica Proves de resposta llarga, de desenvolupament ( recuperable )
Descripció

Mitjançant el mètode expositiu, el professor establirà els fonaments teòrics, així com l'exemplificació pràctica dels temes 4 (parcialment) i 5. La participació dels alumnes serà molt important.

Criteris d'avaluació

Examen amb preguntes de desenvolupament que inclouen conceptes teòrics, procediments, algoritmes i problemes. En cada apartat de l'examen s'indica la seva puntuació.

Competències: CCM06 CCM08 CTR01 CTR02 CTR07

Percentatge de la qualificació final: 30% per a l'itinerari A amb qualificació mínima 5
Percentatge de la qualificació final: 35% per a l'itinerari B amb qualificació mínima 5

Sessions de Laboratori i Pràctiques
Modalitat Classes de laboratori
Tècnica Carpeta d'aprenentatge ( no recuperable )
Descripció

Es resoldran diferents problemes mostrant-hi solucions alternatives i comparar-les dels temes 1 a 5. Per algunes problemes proposats, un cop acabada la sessió de classes pràctiques o laboratori, l'alumnat haurà de pujar les seves solucions en Aula Digital. Algunes solucions es pujaran com glossari perquè tot el grup pugui veure totes les solucions. Altres es pujaran com a taller perquè l'alumnat pugui autoavaluar i coavaluar.

Criteris d'avaluació

La solucions pujades com glossari s'avaluen com lliurada o no lliurada. Les solucions pujades com a taller disposen d'una rúbrica. Per a cada tasca, s'indicarà el pes per a la nota total d'aquesta activitat avaluativa.

Competències: CCM06 CCM08

Percentatge de la qualificació final: 5% per a l'itinerari A
Percentatge de la qualificació final: 0% per a l'itinerari B

#somEPS
Modalitat Estudi i treball autònom individual
Tècnica Informes o memòries de pràctiques ( no recuperable )
Descripció

Assistència a una de les sessions #somEPS (http://eps.uib.es/someps/) relacionades amb els continguts i competències de l'assignatura.

Criteris d'avaluació

L'alumne ha d'entregar un petit informe resum del taller i entregar el justificant d'assistència.

Percentatge de la qualificació final: 5% per a l'itinerari A
Percentatge de la qualificació final: 0% per a l'itinerari B

Projecte de Programació Orientada a Objectes
Modalitat Estudi i treball autònom individual o en grup
Tècnica Sistemes d'autoavaluació ( no recuperable )
Descripció

En aquest projecte es proposa a l'alumnat un problema que per solucionar-ho de forma òptima s'hagin d'utilitzar els conceptes d'objecte, classe i instància; d'herència; i d'encapsulament, sobrecàrrega i polimorfisme.

Criteris d'avaluació

El projecte es puja com a taller a Aula Digital, on hi ha una rúbrica per a l'autoavaluació i coavaluació.

Competències: CCM06 CTR01 CTR02 CTR07

Percentatge de la qualificació final: 10% per a l'itinerari A
Percentatge de la qualificació final: 10% per a l'itinerari B

Projecte sobre disseny i la verificació d'algoritmes recursius
Modalitat Estudi i treball autònom individual o en grup
Tècnica Sistemes d'autoavaluació ( no recuperable )
Descripció

En aquest projecte es presenta un algorisme simple perquè l'alumnat ho verifiqui formalment, analitzi el seu cost i apliqui l'anàlisi per al disseny i la verificació d'algoritmes recursius per proposar una solució més òptima.

Criteris d'avaluació

L'informe es puja com a taller a Aula Digital, on hi ha una rúbrica per a l'autoavaluació i coavaluació.

Competències: CCM06 CTR01 CTR02 CTR07

Percentatge de la qualificació final: 10% per a l'itinerari A
Percentatge de la qualificació final: 10% per a l'itinerari B

Projecte d'Esquemes algorísmics
Modalitat Estudi i treball autònom individual o en grup
Tècnica Treballs i projectes ( recuperable )
Descripció

En aquest projecte es presenta un problema perquè l'alumnat implementi la solució més òptima amb els esquemes algorítmics vistos en hores de treball presencial, i justifiqui l'esquema escollit i els esquemes descartats.

Criteris d'avaluació

El projecte es puja com a tasca a Aula Digital com una tasca. El professor corregeix presencialment el projecte usant una rúbrica.

Competències: CCM06 CTR01 CTR02 CTR07

Percentatge de la qualificació final: 25% per a l'itinerari A amb qualificació mínima 5
Percentatge de la qualificació final: 30% per a l'itinerari B amb qualificació mínima 5

Recursos, bibliografia i documentació complementària

El material bibliogràfic resulta imprescindible pel procés d'ensenyança aprenentatge dels estudiants. A més, les característiques metodològiques implantades exigeixen certa originalitat dels materials. En aquest sentit, és important que el professor ofereixi materials adaptats als processos d'ensenyança aprenentatge dissenyats per a l'assignatura.

La bibliografia bàsica és un recull dels materials elaborats pel professor i adaptats al procés d'ensenyança aprenentatge aplicat. Els texts complementaris que es presenten són de caire general i constitueixen alternatives per a l'ampliació i consolidació de determinats coneixements i habilitats. De totes formes, durant el curs el professor recomanarà, si és necessari, materials específics per a tasques concretes.

Bibliografia bàsica

- Materials del professor.
- Manuals de tallers i activitats.

Brassard, G., & Bratley, P. (1996). Fundamentals of algorithmics. Prentice Hall.
Cormen, T. H., Leiserson, C.E., Rivest, R., & Stein, C. (2009). Introduction to algorithms. MIT press.
Peña Marí, R. (2005). Diseño de Programas. Formalismo y Abstracción. Pearson Education.
The Java? Tutorials. Oracle. (https://docs.oracle.com/javase/tutorial/)

Bibliografia complementària

Álvez, J., Arregi, X., Gaintzarán, J., Lucio, P., & Maritxalar, M. (2014). Especificación, Verificación y Derivación Formal de Programas. Pearson.
Barnes, D. J. (2000). Object-oriented programming with Java: an introduction. Prentice Hall.
Dasgupta, S., Papadimitriou, C. H., & Vazirani, U. V. (2008). Algorithms, McGraw-Hill.
Horowitz, E., & Sahni, S. (1984). Fundamentals of computer algorithm. Computer Science Press.
Kleinberg, J., & Tardos, E. (2014). Algorithm design. Pearson.
Llemosí, A. (2014) A Primer on Program Construction III. Advanced Skills. Author draft.
Mitzenmacher, M., & Upfal, E. (2005). Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press.
Moore, C., & Mertens, S. (2011). The nature of computation. Oxford University Press.
Motwani, R., & Raghavan, P. (1995). Randomized algorithms. Cambridge University Press.
Parberry, I., & Gasarch, W. (1995). Problems on algorithms. Prentice Hall?.
Skiena, S. S. (2008). The algorithm design manual. Springer.