Saltar al contingut Menu
Mapa
  • Inici
  • Informació
  • Contacte
  • Mapa

Algorísmia, Calculabilitat i Complexitat (ALCC)

Crèdits Dept. Tipus Requisits
9.0 (7.2 ECTS) CS
  • Obligatòria per a l'ETIS
PS - Pre-requisit per la ETIS

Professors

Responsable:  (-)
Altres:(-)

Objectius Generals

Conèixer els elements bàsics de la teoria de la computació, incloent una introducció a l'algorísmia, a les teories de la complexitat i de la calculabilitat, i a la teoria d'autòmats i llenguatges.

Adquirir els coneixements necessaris per classificar problemes segons l'existència o no d'algorismes per a la seva resolució i, en aquest darrer cas, segons la possibilitat de trobar una solució eficient.

Objectius Específics

Coneixements

  1. Conèixer alguns models abstractes de càlcul clàssics i les seves limitacions i possibilitats.
  2. Saber classificar els problemes en les classes de complexitat definides pels diferents models de càlcul. En particular, entendre la significació dels resultats negatius (no regularitat, intractabilitat, indecidibilitat).
  3. Comprendre el concepte de reducció entre problemes i la seva utilització per mostrar-ne la tractabilitat o intractabiliat.
  4. Aprendre a analitzar el cost d'un algorisme i la complexitat computacional d'un problema. Entendre la diferència qualitativa entre temps polinòmic i temps exponencial.
  5. Conèixer problemes computacionals per als quals, a hores d'ara, no es coneixen algorismes amb cost polinòmic.
  6. Aprendre algunes tècniques algorísmiques per tractar problemes difícils; en particular, els problemes NP-complets.
  7. Entendre l'ús de la notació lògico-matemàtica per representar els problemes computacionals i els models de càlcul.

Habilitats

(Informació no introduïda)

Competències

  1. Capacitat per al raonament crític i lògico-matemàtic
  2. Capacitat per entendre i construir demostracions lògico-matemàtiques.
  3. Capacitat per resoldre problemes aplicant els mètodes de la ciència i l'enginyeria.
  4. Capacitat d'aplicar els coneixements de matemàtiques i lògica a la resolució de problemes.
  5. Capacitat d'abstracció. Capacitat d'enfrontar-se a problemes nous recorrent conscientment a estratègies que han estat útils en problemes resolts anteriorment.
  6. Capacitat d'actuar autònomament: saber treballar de forma independent, rebent només la informació indispensable i un mínim de guiatge.
  7. Capacitat per transmetre idees efectivament de forma escrita.
  8. Obertura i curiositat intel·lectual.

Continguts

Hores estimades de:

T P L Alt L Ext. Est A Ext.
Teoria Problemes Laboratori Altres activitats Laboratori extern Estudi Altres hores fora d'horari fixat

1. Part I. Fonaments
T      P      L      Alt    L Ext. Est    A Ext. Total 
12,0 12,0 0 0 0 24,0 0 48,0
Nocions matemàtiques.
Decidibilitat.
Complexitat.

2. Part II. Algorísmia
T      P      L      Alt    L Ext. Est    A Ext. Total 
12,0 12,0 0 0 0 24,0 0 48,0
Cerca exhaustiva.
Algorismes voraços.
Programació dinàmica.

3. Part III. Computació
T      P      L      Alt    L Ext. Est    A Ext. Total 
12,0 12,0 0 0 0 24,0 0 48,0
NP-completesa.
Cerca de patrons.
Anàlisi sintàctica.

4. Part IV. Classes
T      P      L      Alt    L Ext. Est    A Ext. Total 
1,0 11,0 0 0 0 12,0 0 24,0
Classificació dels llenguatges.


Total per tipus T      P      L      Alt    L Ext. Est    A Ext. Total 
37,0 47,0 0 0 0 84,0 0 168,0
Hores addicionals dedicades a l'avaluació 9,0
Total hores de treball per l'estudiant 177,0

Metodologia docent

Cada classe de dues hores es divideix en una primera hora de teoria i una segona de problemes fetes sobre pissarra. A més, es farà avaluació continuada consistent en tres proves fetes al llarg del curs (per a les parts I-III) en horari lectiu.

Mètode d'avaluació

L'assignatura té un sistema d'avaluació continuada i un examen final. L'avaluació continuada consta de 3 proves fetes al llarg del quadrimestre, mentre que l'examen final consta de 4 parts. Si les notes de les proves són p1, p2, p3 i les notes de les parts de l'examen final són f1, f2, f3, f4, la nota global de l'assignatura és

max(p1,f1) + max(p2,f2) + max(p3,f3) + f4

Els quatre valors de la suma anterior corresponen, respectivament, a les quatre parts en què es divideix el temari. Les parts I-III aporten 3 punts cadascuna, mentre que la IV aporta 1 punt.

Les proves tindran lloc dins de l'horari habitual de classe, un cop acabada la matèria que inclouen. El calendari de proves s'anunciarà al Racó a començament de curs.

Bibliografía bàsica

  • Michael Sipser Introduction to the theory of computation, Thomson Course Technology, 2006.
  • G. Brassard, T. Bratley Fundamentos de algoritmia, Prentice Hall,, 1996.
  • Maria Serna ... [et al.] Els Límits de la computació : indecidibilitat i NP-completesa, Edicions UPC, 2001.
  • Thomas H. Cormen ... [et al.] Introduction to algorithms, MIT Press, 2001.

Bibliografía complementària

  • Efim Kinber, Carl Smith Theory of computing : a gentle introduction, Prentice-Hall, 2001.
  • Christos H. Papadimitriou Computational complexity, Addison-Wesley, 1994.
  • Michael R. Garey, David S. Johnson Computers and intractability : a guide to the theory of NP-Completeness, W.H. Freeman, 1979.
  • Ian Parberry Problems on algorithms, Prentice Hall, 1995.
  • Rafel Cases, Lluís Màrquez Llenguatges, gramàtiques i autòmats : curs bàsic, Edicions UPC, 2003.

Enllaços web

(Informació no introduïda)

Capacitats prèvies

Coneixements de programació i estructures de dades.
Familiaritat amb el raonament lògico-matemàtic.


Compartir

 
logo FIB © Facultat d'Informàtica de Barcelona - Contacte - RSS
Aquest web utilitza cookies pròpies per oferir una millor experiència i servei. En continuar amb la navegació entenem que acceptes la nostra política de cookies.
Versió clàssica Versió mòbil