Estudia > Oferta formativa > Oferta d'assignatures > Detall de l'assignatura
Anar al contingut (clic a Intro)
UdG Home UdG Home
Tancar
Menú

Estudia

Dades generals

Curs acadèmic:
2013
Descripció:
Esquemes algoritmics. Backtraking. Algorismes probabilístics.
Crèdits:
6
Idioma principal de les classes:
Català
S’utilitza oralment la llengua anglesa en l'assignatura:
Gens (0%)
S’utilitzen documents en llengua anglesa:
Poc (25%)

Grups

Grup A

Durada:
Semestral, 1r semestre
Professorat:

Competències

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

Altres Competències

  • 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 de l’eficiència dels algoritmes.

Continguts

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

Tipus d’activitat Hores amb professor Hores sense professor Total
Prova d'avaluació 0 10,00 10,00
Sessió expositiva 2,00 1,00 3,00
Sessió participativa 25,00 28,00 53,00
Sessió pràctica 24,00 37,00 61,00
Total 51,00 76,00 127

Bibliografia

  • Brassard, Gilles, Bratley, Paul (1990). Algorítmica : concepción y análisis. Barcelona: Masson.
  • Brassard, Gilles, Bratley, Paul (1997). Fundamentos de algoritmia. Madrid [etc.]: Prentice Hall.
  • Gonzalo Arroyo, Julio, Rodríguez Artacho, Miguel (1997). Esquemas algorítmicos : enfoque metodológico y problemasresueltos. Madrid: Universidad Nacional de Educación a Distancia.
  • Horowitz, Ellis, Sahni, Sartaj, Rajasekaran, Sanguthevar (1997). Computer algorithms. New York: Computer Science Press.
  • Leiserson, Charles Eric, Rivest, Ronald L., Cormen, Thomas H., Stein, Clifford. Introduction to algorithms (2nd ed.). Cambridge, Mass.: MIT PressNew York.
  • Preiss, Bruno R. (cop. 1999). Data structures and algorithms : with object-oriented designpatterns in C++. New York [etc.]: John Wiley and Sons.
  • Stroustrup, Bjarne (cop. 2002). El Lenguaje de programación C++ (3ª ed.). Madrid [etc.]: Addison Wesley.
  • Wirth, Niklaus (cop. 1987). Algoritmos y estructuras de datos. México, D.F. [etc.]: Prentice-Hall Hispanoamericana.

Avaluació i qualificació

Activitats d'avaluació:

Descripció de l'activitat Avaluació de l'activitat %
M.2: Divideix i venç 25% de la nota de laboratori (si escau)
M.3: Algoritmes sobre grafs 30% de la nota de laboratori (si escau)
M.4: Backtracking 45% de la nota de laboratori (si escau)
Examen de validació final 50% de la nota (part de teoria i problemes)

Qualificació

S'han deixat les activitats que es feien quan hi havia docència presencial per recordar la manera de treballar de l'assignatura. Tanmateix, com reflexa la guia docent, l'avaluació es farà bàsicament a partir de l'examen de teoria-problemes.

Només aquelles persones que tinguin de l'examen una nota entre 4 i 5 tindran opció a un sistema d'avaluació alternatiu, en cas que hagin presentat les pràctiques de l'assignatura.

Hi ha més detalls a la guia docent de l'assignatura.

Criteris específics de la nota «No Presentat»:
Obtindran un NP aquelles persones que no presentin cap activitat d'avaluació

Observacions

Els detalls de l'avaluació són a la guia docent de l'assignatura.

Assignatures recomanades

  • Introducció a les estructures de dades
  • Matemàtica discreta

Escull quins tipus de galetes acceptes que el web de la Universitat de Girona pugui guardar en el teu navegador.

Les imprescindibles per facilitar la vostra connexió. No hi ha opció d'inhabilitar-les, atès que són les necessàries pel funcionament del lloc web.

Permeten recordar les vostres opcions (per exemple llengua o regió des de la qual accediu), per tal de proporcionar-vos serveis avançats.

Proporcionen informació estadística i permeten millorar els serveis. Utilitzem cookies de Google Analytics que podeu desactivar instal·lant-vos aquest plugin.

Per a oferir continguts publicitaris relacionats amb els interessos de l'usuari, bé directament, bé per mitjà de tercers (“adservers”). Cal activar-les si vols veure els vídeos de Youtube incrustats en el web de la Universitat de Girona.