20580. Algorísmia . Grup 9

Identificació de l'assignatura

Assignatura20580 - Algorísmia
Grup Grup 9 ( Campus Digital )
Any acadèmic 2018-19
Crèdits6 crèdits
Període d'impartició Primer semestre
Idioma d'impartició
Titulació
  • Doble titulació: grau de Matemàtiques i grau d'Enginyeria Telemàtica - Tercer curs
  • Grau de Matemàtiques - Tercer curs

Professors

Professor/aHorari d'atenció alumnes
Hora d'iniciHora de fiDia de la setmanaData d'iniciData de fiDespatx/Edifici
Gabriel Fiol Roig
biel.fiolbiel.fiol@uib.esuib.es
(Responsable)
Cal concertar cita prèvia amb el professor per a fer una tutoria

Contextualització

Algorísmia és una assignatura obligatòria de la branca d'Informàtica que s'imparteix el primer semestre del tercer curs. L'assignatura s'inclou en el context de la programació d'ordinadors de segon nivell, on l?alumne ha d?assolir, en el marc de la Programació Orientada a Objectes, els coneixements, habilitats i bones pràctiques adients en el disseny, 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. Per tant, 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

Essencials

Al tractar-se d'una assignatura de programació de segon nivell, resulta imprescindible haver assolit prèviament les competències bàsiques en el disseny i desenvolupament de programari, la qual cosa es pot aconseguir a través del bon aprofitament de l'assignatura Programació I (codi 20302) o altres assignatures similars relacionades amb la programació de primer nivell.

Recomanables

La pluralitat i diversitat de conceptes i tècniques emprats en l'assignatura fan recomanable l'haver cursat amb aprofitament les assignatures Matemàtica Discreta, Anàlisi Matemàtica I i Àlgebra Abstracta I.

Competències

Específiques

  • E15. Conèixer els conceptes bàsics de la teoria de grafs, així com algoritmes de resolució de problemes en grafs i algunes de les seves aplicacions.
  • E35. Capacitat d?utilitzar el formalisme matemàtic per dissenyar i verificar programes informàtics.
  • E37. Tenir capacitat de dissenyar, analitzar i implementar de manera eficient algoritmes simbòlics o numèrics en un llenguatge de programació d?alt nivell.
  • E38. Tenir capacitat per valorar i comparar diferents mètodes en funció dels problemes que cal resoldre, el cost computacional, el temps d?execució i la presència i la propagació d?errors, entre altres característiques.
  • E39. Avaluar els resultats obtinguts i obtenir conclusions després d?un procés de còmput.
  • E40. Desenvolupar la capacitat d?identificar i descriure matemàticament un problema, d?estructurar la informació disponible i de seleccionar un model matemàtic adequat per resoldre?l.

Genèriques

  • TG8. Tenir capacitat de comprendre i utilitzar el llenguatge matemàtic i enunciar proposicions en diferents camps de les matemàtiques.
  • TG9. Tenir capacitat d?assimilar la definició d?un nou objecte matemàtic, en altres termes coneguts, i ser capaç d?utilitzar aquest objecte en diferents contextos.
  • TG10. Tenir capacitat per aplicar els coneixements adquirits a la construcció de demostracions, la detecció d?errors en raonaments incorrectes i la resolució de problemes.

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 el disseny, la verificació i l'avaluació del cost computacional d'algorismes en el context de la solució d'una gran varietat de problemes.

En particular, es pretén:

1. Potenciar la resolució programada de problemes a través dels potents mecanismes que ens ofereix la programació orientada a objectes.

2. Facilitar el disseny de solucions mitjançant l'ús de la programació modular.

3. Disposar d'eines d'anàlisi de la correctesa i de l'eficiència computacional dels algorismes, per tal de garantir un alt grau de capacitat de les solucions algorísmiques als problemes plantejats.

4. Promoure l'excepcional i potent eina de la recursivitat per a la solució de problemes.

5. Conèixer solucions algorísmiques bàsiques per a una varietat de tipus de problemes i saber decidir sobre la més idònia per a cada classe de problemes.

Continguts temàtics

Tema 1 Fonaments de la Programació orientada a Objectes

Es defineixen i s'exploren els quatre pilars fonamentals que sostenen la Programació orientada a Objectes (POO):

- La gestió de memòria dinàmica.

- Els elements essencials de la POO: les classes i els objectes.

- Els disseny i modelització de lades en POO.

- Les jerarquies de classes.

Tema 2. Lògica dels programes

Introducció als aspectes de correctesa, especificació i verificació formal de programes.

Es defineix un llenguatge formal que soporta els aspectes d'especificació i verificació formal d'un programa, de manera que ens permet garantir la seva correctesa a priori (abans de l'execució del programa). El llenguatge es basa en la lògica de programes, la qual es recolza en la lògica de primer ordre, entre els conceptes de la qual cal destacar: conjunt d'estats, predicats, inferència lògica i precondició més feble.

Tema 3 Anàlisi delcost dels algorismes

Es defineix el concepte d'eficiència computacional d'un algorisme com el consum de recursos de d'aquest, independentment de les plataformes hardware i software que el soporten. Per tant, es tracta d'una mesura que es fa a priori de l'execució real de l'algorisme. Aquests recursos són el temps de còmput de l'algorisme i la quantitat de memòria emprada per assolir una solució.

Es defineixen i apliquen una sèrie de mesures de caràcter assimptòtic que permeten calcular l'eficiència computacional dels algorismes des de diferents perspectives.

Tema 4 Recursivitat

Es presenten 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 Tècniques de resolució de problemes

S'estudien les principals tècniques de resolució d'una varietat 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 procedir 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
Seminaris i tallers Activitats formatives presencials Grup mitjà (M)

Planificar, discutir, proposar i resoldre diferents cuestions relacionades amb la resolució d'activitats.

Les principals metodologies en les quals s'emmarquen aquestes activitats son: l'aprenentatge basat en projectes, l'aprenentatge basat en problemes i la gamificació.

19
Classes pràctiques Aplicació i reforç. Grup gran (G)

Aplicar els conceptes, resultats i procediments en la resolució de problemes i pràctiques.

Les metodologíes implicades en aquestes activitats són: l'aprenentatge basat en problemes, el flipped classroom i la gamificació.

12
Avaluació Examen global Grup gran (G)

Avaluació acreditativa sobre el nivell d'aprenentatge i habilitats adquirides pels estudiants en la resolució de petites i mitjanes situacions.

3
Avaluació Activitats d'avaluació formativa. Grup gran (G)

Desenvolupar, individualment o en grup, diferents activitats per tal de reforçar els processos d'aprenentatge dels estudiants i adquirir consciència de la seva evolució.

Aquestes activitats es fan en l'àmbir de les metodologies del flipped classroom, la gamificació i l'aprenentatge basat en problemes.

8
Altres Classes teòriques i de reforç. Grup gran (G)

1. Presentar els conceptes, resultats i procediments principals del temari.

2. Discutir, aprofundir i resoldre questions relacionades amb la temàtica.

La finalitat 1 es durà a terme mitjançant la metodologia expositiva per part del professor. Mentre, per a la finalitat 2 s'aplicarà el flipped classroom.

18

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 en grup Projectes

A través del treball en grups petits, els alumnes hauran de desenvolupar els projectes proposats. La solució dels projectes s'haurà de presentar correctament documentada d'acord amb les directrius establertes pel professor.

45
Estudi i treball autònom individual o en grup Activitats formatives no presencials

De manera individual o en grups petits, els alumnes hauran de desenvolupar les activitats (en forma de problemes, projectes reduits,etc.) proposades. La solució s'haurà de presentar correctament documentada d'acord amb les directrius establertes pel professor.

25
Estudi i treball autònom individual o en grup Estudi individual o en grup

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

18

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

Activitats formatives presencials
Modalitat Seminaris i tallers
Tècnica Carpeta d'aprenentatge ( no recuperable )
Descripció

Planificar, discutir, proposar i resoldre diferents cuestions relacionades amb la resolució d'activitats.

Les principals metodologies en les quals s'emmarquen aquestes activitats son: l'aprenentatge basat en projectes, l'aprenentatge basat en problemes i la gamificació.

Criteris d'avaluació

Es valoraràn, de forma individual o en grup reduit, la planificació, la proposta de solucions i alternatives, l'evolució en la resolució i la capacitat d'expresió oral i escrita.

Les competències cobertes són: TG8, TG9, TG10, E15, E35, E37, E38, E39, E40.

Percentatge de la qualificació final: 4%

Aplicació i reforç.
Modalitat Classes pràctiques
Tècnica Carpeta d'aprenentatge ( no recuperable )
Descripció

Aplicar els conceptes, resultats i procediments en la resolució de problemes i pràctiques.

Les metodologíes implicades en aquestes activitats són: l'aprenentatge basat en problemes, el flipped classroom i la gamificació.

Criteris d'avaluació

Els alumnes hauran de demostrar de manera individual o en grup reduit, la seva participació en les activitats pràctiques través de la presentació i/o exposició de les tasques que el professor haurà proposat prèviament oproposarà,

Les competències cobertes són: TG10, E15, E35, E38, E39, E40.

Percentatge de la qualificació final: 4%

Examen global
Modalitat Avaluació
Tècnica Proves objectives ( recuperable )
Descripció

Avaluació acreditativa sobre el nivell d'aprenentatge i habilitats adquirides pels estudiants en la resolució de petites i mitjanes situacions.

Criteris d'avaluació

Prova escrita individual, en la que es valorarà el nivell global de coneixements i habilitats en la resolució de questions i problemes de tamañy reduit. S'avaluarà la correcció del plantejament, la resolució del problema, la claretat de l'exposició i la rigorositat dels raonaments.

Les competències cobertes són: TG8, TG9, TG10, E15, E35, E37, E38, E39, E40.

Percentatge de la qualificació final: 30% amb qualificació mínima 5

Activitats d'avaluació formativa.
Modalitat Avaluació
Tècnica Carpeta d'aprenentatge ( no recuperable )
Descripció

Desenvolupar, individualment o en grup, diferents activitats per tal de reforçar els processos d'aprenentatge dels estudiants i adquirir consciència de la seva evolució.

Aquestes activitats es fan en l'àmbir de les metodologies del flipped classroom, la gamificació i l'aprenentatge basat en problemes.

Criteris d'avaluació

Exposicions escrites, individuals o en grup, en les que es posarà de relleu el nivell de coneixements i habilitats en la resolució d'activitats. S'avaluarà la correcció del plantejament, la resolució del problema, la claretat de l'exposició i la rigorositat dels raonaments.

Les competències cobertes són: TG8, TG9, TG10, E15, E35, E38, E39, E40.

Percentatge de la qualificació final: 15%

Classes teòriques i de reforç.
Modalitat Altres
Tècnica Carpeta d'aprenentatge ( no recuperable )
Descripció

1. Presentar els conceptes, resultats i procediments principals del temari.

2. Discutir, aprofundir i resoldre questions relacionades amb la temàtica.

La finalitat 1 es durà a terme mitjançant la metodologia expositiva per part del professor. Mentre, per a la finalitat 2 s'aplicarà el flipped classroom.

Criteris d'avaluació

Els alumnes hauran de demostrar de manera individual la seva participació en les activitats a través de la presentació i/o exposició de les tasques que el professor haurà proposat prèviament.

Les competències cobertes són: TG8, TG9, E15, E35, E38, E39, E40.

Percentatge de la qualificació final: 4%

#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 el justificant d'assistència.

Percentatge de la qualificació final: 3%

Projectes
Modalitat Estudi i treball autònom en grup
Tècnica Proves d'execució de tasques reals o simulades ( recuperable )
Descripció

A través del treball en grups petits, els alumnes hauran de desenvolupar els projectes proposats. La solució dels projectes s'haurà de presentar correctament documentada d'acord amb les directrius establertes pel professor.

Criteris d'avaluació

1. Cada grup durà a terme presencialment amb el professor, una sèrie de proves d'execució dels projectes on es posarà de relleu el seu correcte funcionament i la claritat i adequacitat de les interfícies de dades.

2. Si escau, els estudiants hauran de presentar una memòria en paper en format electrònic, on s'il.lustrarà de forma clara les característiques del desenvolupament de les diferents etapes del projecte.

Aquestes activitats abracen les següents competències: TG8, TG9, TG10, E15, E37, E38, E39, E40.

Percentatge de la qualificació final: 35% amb qualificació mínima 5

Activitats formatives no presencials
Modalitat Estudi i treball autònom individual o en grup
Tècnica Carpeta d'aprenentatge ( no recuperable )
Descripció

De manera individual o en grups petits, els alumnes hauran de desenvolupar les activitats (en forma de problemes, projectes reduits,etc.) proposades. La solució s'haurà de presentar correctament documentada d'acord amb les directrius establertes pel professor.

Criteris d'avaluació

Resolució d'un conjunt d'activitats o petits projectes de forma escrita o mitjançant proves d'execució de tasques simulades.

Les competències cobertes són: TG8, TG9, TG10, E15, E35, E37, E38, E39, E40.

Percentatge de la qualificació final: 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.

Bibliografia complementària

Fundamentos de Algoritmia
Brassard, G.; Bratley, P.
Prentice Hall, 1997

Diseño de programas. Formalismo y abstracción
Peña Marí, R.
Prentice Hall, 1998

Introduction to algorithms
Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.
Ed. McGraw Hill, 1990