Estudia

• Ser capaç d'analitzar, dissenyar i implementar un algorisme i la seva estructura de dades.

• Entendre bé el concepte d’esquema algorítmic i la necessitat de disposar de diferents esquemes per poder obtenir algoritmes.
• Fer un estudi dels principals esquemes algoritmics (divideix i venç, backtracking, mètode voraç i tècniques probabilistes).
• Fer un estudi dels grafs i els algoritmes de manipulació.
• Formalitzar l’estudi d’algoritmes des del punt de vista teòric.

1. Introducció

          1.1. Nomenclatura

          1.2. Disseny d’algorismes (iteratiu, recursiu)

          1.3. Eficiència (mesures d’eficiencia, cas mig, cas pitjor, relacions)

          1.4. Estructures de dades (referències, estructures dinàmiques, classes definides)

2. Introducció als esquemes: el tractament seqüencial.

          2.1. Concepte d’esqueme algorítmic

          2.2. Tractament seqüencial (recorregut, cerca)

          2.3. Exemples

3. Divideix i venç.

          3.1. Introducció

          3.2. Càlcul de l’eficiencia

          3.3. L’esquema Divideix i venç

          3.4. Exemples d’aplicació

4. Algoritmes voraços i grafs.

          4.1. Introducció

          4.2. Esquema voraç i la seva demostració

          4.3. Exemples

          4.4. Grafs i algoritmes de tractament de grafs

          4.5. Algoritmes voraços sobre grafs

          4.6. Algoritmes quasi-òptims

5. Exploració de grafs: Backtraking, Branch and bound i altres.

          5.1. Introducció a l’exploració de grafs

          5.2. Backtracking (una solució, totes les solucions, solució òptima)

          5.3. Exemples d’aplicació

          5.4. Altres recorreguts de grafs (en amplada, Brach & Bound,…)

6. Algoritmes probabilistes.

          6.1. Introducció

          6.2. Generació de valors aleatoris

          6.3. Algorismes numèrics

          6.4. Algorismes de Monte-Carlo

          6.5. Algorismes de Las Vegas

          6.6. Algorismes de Sherwood

          6.7. Estructures de dades i algorismes probabilistes

Activitats d'avaluació:

Mètodes docents:
Classes de teoria: 2 hores/setmana (3 crèdits)
Classes de problemes i laboratori: 2 hores/setmana (3 crèdits)
Tipus d'exàmens:
Qualificació:
examen (teoria + problemes): 70%
treballs de laboratori: 30%

Prerequisits:
Recomentats: Introducció a les Estructures de Dades, Matemàtica Discreta.