ALGORÍSMICA I PROGRAMACIÓ AVANÇADA

 

 

Professora coordinadora: Lina Juan (lina@eupmt.cat)

 

Tipus d’assignatura: Obligatòria

 

Nivell: 2B

 

Càrrega lectiva: 4.5 crèdits (teoria/aplicació) / 3.5 crèdits ECTS

 

Recomanacions: Haver cursat i superat  l’assignatura “Estructures de dades i Algorismes”.

 

Organització de la docència:

Teoria/aplicació: 3 hores/setmana x 12 setmanes

 

Descripció

En aquesta assignatura es donen a conèixer els grafs com a tipus abstracte de dades i  s’estudien i apliquen diferents esquemes algorísmics en la resolució de  problemes.

 

Objectius

En finalitzar el curs, l’estudiant serà capaç de:

·          Enumerar i  explicar la filosofia de funcionament de les diferents tècniques de disseny.

·          Comparar des del punt de vista de l’eficiència les diferents tècniques de disseny. 

·          Aplicar les diferents tècniques de disseny d’algorismes en la resolució problemes. 

·          Analitzar el problema per a poder determinar quina tècnica és l’adient per a la resolució d’un problema.

·          Deduir i argumentar la correcta aplicació de les diferents tècniques.

·          Exposar i discutir l’anàlisi inicial obligatori en l’aplicació de la tècnica del backtracking i la tècnica voraç.

·          Reconèixer quina de les tres variants d’esquema de backtracking cal aplicar en la resolució d’exercicis.

·          Descriure els grafs com estructures de dades i, modelar situacions de la vida real mitjançant grafs.

·          Aplicar els diferents tractaments sobre grafs i interpretar els resultats generats per l’aplicació.

·          Elegir el tractament més adient en la resolució d’un problema modelat amb un graf.

·          Argumentar i discutir la correcta aplicació del tractament.

·          Implementar els diferents tipus de grafs: grafs simètrics i dígrafs.

·          Descriure els diferents recorreguts sobre grafs.

·          Descriure i codificar els diferents algorismes de tractament de camins mínims.

·          Descriure i codificar els diferents algorismes per trobar arbres d’expansió minimal sobre grafs simètrics.

·          Adaptar implementacions d’algorismes de tractament de grafs a diferents situacions.

 

Competències transversals

En aquesta assignatura es treballen les següents competències transversals:

·          Comunicar de forma efectiva.

·          Dirigir i col·laborar en equips de treball.

·          Gestionar el treball personal.

 

Bibliografia bàsica

·          Algorísmica i Programació Avançada. Dossiers de Teoria i Problemes. L. Juan; Publicacions de l’EUPMt

·          Estructuras de datos y métodos algorítmicos. Ejercicios resueltos. N. Martí, Y. Ortega, J.A. Verdejo. Ed. Prentice Hall, 2003

 

Bibliografia complementària

·          Estructuras de datos en Java. Allen Weiss M. Ed. Addison Wesley, 2000

·          Programación orientada a objetos con Java. D. J. Barnes, Michael Kölling. ED. Prentice Hall, 2007

 

Criteris d’avaluació i mètode de qualificació

·          Prova parcial del tema 1  (30%) + Prova parcial del la primera part del tema 2 (30%) + Prova parcial de la segona part del tema 2 (30%) +  Treball dirigit (10%).

·          Recuperació del primer parcial el mateix dia que es realitza el tercer parcial. No es preveu cap recuperació del segon parcial.

·          Totes les proves de l’assignatura es poden realitzar, a criteri del propi estudiant,  amb un esquema guia dels conceptes avaluats.

·          Al llarg del quadrimestre els estudiants, per grups, resoldran a classe, problemes que seran lliurats al professor al finalitzar aquesta.  Aquesta tasca desenvolupada a classe, té un reconeixement màxim de 1 punt a afegir sobre la nota final obtinguda per l’estudiant.  

Programa de teoria

 

Tema 1. Tècniques de disseny d’algorismes

1.1.  Introducció. Esquemes bàsics

1.2.  Tècnica del backtracking:

1.2.1. Caracterització dels problemes que es poden resoldre amb aquesta tècnica

1.2.2. Esquema per trobar una, totes o la millor solució d’un problema

1.2.3. Resolució de problemes típics: creuar un laberint, salt del cavall en un taulell d’escacs, el   

          problema de la motxilla, ...

1.3.  Ramificació i Poda

1.4.  Tècnica Voraç (Greedy)

1.5.  Divideix i Venç

1.6.  Programació dinàmica

 

Tema 2. Estructures de dades no lineals: els grafs

2.1. Definicions i conceptes bàsics

2.2. Aplicacions dels grafs

2.3. Signatura del tipus abstracte de dades: Dígraf i Graf Simètric

2.4. Implementacions: matriu d’adjacència i llista d’adjacència

2.5. Recorreguts dels grafs: en fondària, en amplada i en ordenació topològica

2.6. Cerca de camins mínims:

                2.6.1. Algorisme de Dijkstra

                2.6.2. Algorisme de Floyd

                2.6.3. Algorisme de Warshall

2.7. Arbres d’expansió minimal:

                2.7.1. Algorisme de Prim

2.7.2. Algorisme de Kruskal

 

Metodologia docent

El treball a l’aula es basa en classes on el professor explica els conceptes de teoria i els aplica en la resolució de problemes,  alguns d’ells realitzats pel professor i d’altres pels propis alumnes.

Les metodologies que es seguiran a l’aula per a resolució d’exercicis seran molt variades, sempre depenent de la temàtica a treballar i dels estudiants assistents a l’aula i principalment, de l’objectiu que es pretén assolir amb la resolució de l’exercici.  Amb aquestes resolucions es pretén treballar els elements bàsics d’aprenentatge cooperatiu, demanant que els estudiants s’involucrin més en l’assignatura i, desenvolupin les habilitats interpersonals, per això les activitats es faran en grups d’estudiants, amb o sense defensa de la resolució proposada pel grup a la resta de companys d’assignatura i al professor. Aquestes activitats seran avaluades pel professor i/o companys i per tant, serà una qualificació més a tenir en compte en el càlcul de la nota final de l’assignatura. És molt important l’assistència a les classes de l’assignatura per l’assoliment de les competències transversals de l’assignatura.

  

Les activitats programades fora de l’aula son:

-          Realització d’un treball dirigit.

Treball: Resolució d’un problema d’optimització aplicant la tècnica del backtracking, treball que s’ha de codificar a llenguatge Java, realitzant prèviament l’anàlisi inicial, que s’ha de defensar a la professora per a que li doni el vist-i-plau per la codificació. El treball és individual i diferent per a cada estudiant de l’assignatura.

-          Resolució d’exercicis de recolzament a les diferents temàtiques treballades a l’assignatura i de, lliurament opcional.

 

by Bitlonia