Aquesta versió de la guia docent és provisional fins que no finalitzi el període d’edició de les guies del nou curs.

Logo UAB

Teoria de la Computació

Codi: 107891 Crèdits: 6
2025/2026
Titulació Tipus Curs
Enginyeria Informàtica FB 1

Professor/a de contacte

Nom:
Joan Serra Sagrista
Correu electrònic:
joan.serra@uab.cat

Equip docent

Joaquin Borges Ayats

Idiomes dels grups

Podeu consultar aquesta informació al final del document.


Prerequisits

Avís sobre la llengua d’impartició i les traduccions de la guia docent

 En principi, l’idioma d’impartició de tots els grups d’aquesta assignatura és el català.

S’ofereixen traduccions automàtiques de la guia docent a l’anglès i al castellà amb finalitats informatives.

En cas de discrepància o incongruència entre les versions en diferents idiomes, prevaldrà sempre la versió en català, com a referència oficial.

 

==

Encara que no hi ha prerequisits oficials és fonamental que els alumnes tinguin molt bon domini de les nocions més bàsiques de les matemàtiques, com ara:

  • Dominar la manipulació del llenguatge matemàtic
  • Dominar les demostracions per inducció i per contradicció
  • Dominar la capacitat d’abstracció

L’alumnat  que no tingui un mínim bagatge de matemàtiques prèvies haurà de fer un esforç en preocupar-se per resoldre aquestes deficiències.


Objectius

  • Ordenar les propietats dels models formals en què es basen els ordinadors 
  • Identificar les possibilitats i els límits de la computació
  • Adquirir bons hàbits de programació

Resultats d'aprenentatge

  1. CM05 (Competència) Integrar tècniques basades en models computacionals en problemes de la informàtica.
  2. KM09 (Coneixement) Explicar procediments algorítmics de la teoria computacional per a la resolució de problemes d'enginyeria informàtica.
  3. SM13 (Habilitat) Aplicar coneixements d'autòmats, gramàtiques i de complexitat computacional per a la resolució de problemes.

Continguts

1. Llenguatges formals i models abstractes de càlcul.
1.1. Alfabets, paraules i llenguatges.
1.2. Problemes, llenguatges formals i models de càlcul.
1.3. Sistemes digitals.
1.4. Mètodes de demostració.

2. Autòmats finits i llenguatges regulars.
2.1. Autòmats finits deterministes.
2.2. Autòmats finits no deterministes.
2.3. Operacions, experssions i llenguatges regulars.
2.4. Minimització del nombre d'estats interns.
2.5. Autòmats amb sortida.

3. Gramàtiques independents del context.
3.1. Introducció.
3.2. Definicions. Generació de llenguatges.
3.3. Simplificació de gramàtiques.
3.4. Formes normals de Chomsky i Greibach.

4. Autòmats amb pila.
4.1. Descripció.
4.2. Acceptació per estat final i per pila buida.
4.3. Autòmats amb pila i llenguatges independents del context.
4.4. Propietats dels llenguatges independents del context.

5. Màquines de Turing.
5.1. Descripció del model bàsic.
5.2. Llenguatges i funcions calculables.
5.3. Variants de la màquina de Turing.
5.4. Hipòtesi de Church. Màquina de Von Neumann.
5.5. Màquines de Turing com a enumeradors.

6. Indecidibilitat.
6.1. Problemes i llenguatges decidibles i indecidibles.
6.2. Llenguatges recursius i recursivament enumerables.
6.3. Màquina universal de Turing i problemes indecidibles.
6.4. El problema de la correspondència de Post i el problema de l'aturada.
6.5. Exemples de llenguatges no recursius.

7. Complexitat computacional.
7.1. Introducció. Tipus de problemes.
7.2. Classes de complexitat.
7.3. NP-Completesa,
7.4. Alguns problemes NP-Complets.


Activitats formatives i Metodologia

Títol Hores ECTS Resultats d'aprenentatge
Tipus: Dirigides      
Classes de Teoria / Problemes 50 2 CM05, KM09, SM13
Tipus: Supervisades      
Exercicis proposats a classe 28 1,12 CM05, KM09, SM13
Tipus: Autònomes      
Estudi i preparació de les proves d'avaluació 38,5 1,54 CM05, KM09, SM13
Preparació i treball autònom 26 1,04 CM05, KM09, SM13

Les sessions s'impartiran segons la tipologia de Pràctiques d'Aula (PAUL):  Discussió i realització d’exercicis i activitats en grup o individuals.

 

La metodologia docent està orientada a l’aprenentatge de la matèria de forma continuada. Activitats que es desenvoluparan al llarg del curs:

  • Sessions de teoria i problemes, on el professorat subministrarà informació sobre els coneixements i sobre estratègies per adquirir, ampliar i organitzar-los. Es fomentarà la participació activa de l'alumnat. Es realitzarà un seguiment de l'aprenentatge mitjançant el desenvolupament individual i/o en grup d'activitats de validació i assoliment.

  

Nota: es reservaran 15 minuts d'una classe, dins del calendari establert pel centre/titulació, perquè els alumnes completin les enquestes d'avaluació de l'actuació del professorat i d'avaluació de l'assignatura.


Avaluació

Activitats d'avaluació continuada

Títol Pes Hores ECTS Resultats d'aprenentatge
Lliurament exercicis i/o activitats validació 30 3,5 0,14 CM05, KM09, SM13
Prova Parcial 1 35 2 0,08 CM05, KM09, SM13
Prova Parcial 2 35 2 0,08 CM05, KM09, SM13

Durant el curs s'aniran fent un seguit de lliuraments d'exercicis i/o activitats de validació al final de cadascun dels temes. Les notes d'aquests exercicis i/o activitats suposaran el 30% de la nota final. Aquesta part de la nota NO serà recuperable.

Hi haurà un examen (Primer Parcial = P_1) abans de mig semestre en el qual s'avaluarà la feina feta fins a aquell moment. La nota d'aquest examen aportarà el 35% de la qualificació final. Tots els estudiants que facin aquest examen ja no podran ser qualificats com a NO AVALUABLE. Aquell estudiant que no hagi fet aquest examen constarà com a NO AVALUABLE a efectes acadèmics i no tindrà dret a recuperar-lo (excepte per causa degudament justificada, cas en què es permetrà fer l'examen de recuperació).

Al final del semestre hi haurà un segon examen parcial (Segon Parcial = P_2) en el qual s'avaluaran el coneixements impartits després del primer parcial. La nota d'aquest examen aportarà un altre 35% de la qualificació final. Aquell estudiant que no hagi fet aquest examen no tindrà dret a recuperar-lo (excepte per causa degudament justificada, cas en què es permetrà fer l'examen de recuperació).

Qualificació:

Si la mitjana de les notes (sobre 10) dels dos parcials M=(P_1+P_2)/2 és inferior a 2.5 l'alumne ha suspès l’assignatura, amb nota final M, sense dret a anar a l'examen de recuperació.

Si M és superior a 2,5 però menor o igual 3.5 l'alumne ha d'anar a l'examen de recuperació.

Si M és superior o igual a 3,5 llavors si NF=0,7 M+ 0,3 S, (on S és la nota mitjana del lliurament d'exercicis i/o activitats de validació, sobre 10) és més gran o igual que 5 l’alumne/a ha aprovat i té NF com a nota final; en cas contrari, ha d’anar a l’examen de recuperació

Si l'alumne/a ha de fer l’examen de recuperació, llavors si la nota de recuperació R, és inferior a 3.5, l'alumne ha suspès amb nota final R; si R és superior o igual a 3,5  la nota final serà min({0,7 R + 0,3 S},7) on R és la nota de l'examen de recuperació (sobre 10).

L’ús de calculadora en els exàmens parcials i en el de recuperació no està permès.

Podran obtenir la qualificació de Matrícula d'Honor el 5% de les notes més altes sempre que: la nota de cada parcial no sigui inferior a 9 i la nota NF descrita abans superi 9.1. Aquestes condicions d'avaluació seran iguals per a tots els estudiants matriculats a l'assignatura, independentment de si són de primera matrícula o si ja s'havien matriculat en cursos anteriors. La decisió final sobre la qualificació de MH la decidirà el professorat.

Per a cada activitat d'avaluació, s'indicarà un lloc, data i hora de revisió en la que l'estudiant podrà revisar l'activitat amb el professorat. En aquest context, es podran fer reclamacions sobre la nota de l'activitat, que seran avaluades pel professorat responsable de l'assignatura. Si l'estudiant no es presenta a aquesta revisió, no es revisarà posteriorment aquesta activitat. Les dates dels exàmens parcials es publicaran al Campus Virtual (CV) i poden estar subjectes a possibles canvis de programació per motius d'adaptació a possibles incidències; sempre s'informarà al CV sobre aquests canvis ja que s’entén que el CV és el mecanisme habitual d'intercanvi d'informació entre professor i estudiants.

En aquesta assignatura, NO es permet l'ús de cap tipus de dispositiu digital a l'aula (ni ordinadors, ni tablets, ni telèfons mòbils, ...); consegüentment, no es permt l'ús de tecnologies d'Intel·ligència Artificial (IA) a l'aula.  Qualsevol treball fet a l'aula que inclogui fragments generats amb IA serà considerat una falta d'honestedat acadèmica i pot comportar una penalització parcial o total en la nota de l'activitat, o sancions majors en casos de gravetat. Es permet l'ús de tecnologies d'Intel·ligència Artificial (IA) en les activitats autònomes fora de l'aula.

Sense perjudici d'altres mesures disciplinàries que es considerin oportunes i d'acord amb la normativa acadèmica vigent, les irregularitats comeses per un estudiant que puguin conduir a una variació de la qualificació es qualificaran amb un zero (0). Per exemple, plagiar, copiar, deixar copiar, tenir dispositius de comunicació (com telèfons mòbils, smart watches, etc.) en una activitat d'avaluació, implicarà suspendre aquesta activitat d'avaluació amb un zero (0). Les activitats d'avaluació qualificades d'aquesta forma i per aquest procediment no seran recuperables. Si és necessari superar qualsevol d'aquestes activitats d'avaluació per aprovar l'assignatura, aquesta assignatura quedarà suspesa directament, sense oportunitat de recuperar-la en el mateix curs. La nota numèrica de l'expedient serà el valor menor entre 3.0 i la mitjana ponderada de les notes en cas que l'estudiant hagi comès irregularitats en un acte d'avaluació (i per tant no serà possible l'aprovat per compensació).  L'avaluació de les competències transversals està integrada en la rúbrica (o pauta de correcció dels problemes) dels exàmens parcials. La puntuació dels apartats de la rúbrica corresponents a competències transversals té un valor d'entre el 5% i el 10% de la puntuació del problema corresponent.

Aquesta assignatura no contempla un tractament diferenciat per als estudiants repetidors.

Aquesta assignatura no preveu el sistema d’avaluació única.


Bibliografia

 

BIBLIOGRAFIA BÀSICA 

Borges, J.; Serra, J i Arqués, J. M. (1996). Teoria d’autòmats. Materials 28, Publicacions de la UAB.

 

 

BIBLIOGRAFIA COMPLEMENTÀRIA 

Casas, R. i Màrquez, L. (2000). Llenguatges, gramàtiques i autòmats. Curs bàsic. Aula teòrica 41, UPC.

Hopcroft, J. E.; Motwani, R. and Ullman, J. D. (2002). Introducción a la teoría de autómatas, lenguajes y computación. Addison Wesley.

(https://docencia.eafranco.com/materiales/teoriacomputacional/books/TeoriaDeAutomatas,lenguajesYComputacion-Hopcroft.pdf)

Linz, P. (2001). An Introduction to Formal Languages and Automata. Jones and Bartlett Publishers.

Martin, J. C. (2004) [2003]. Lenguajes formales y teoría de la computación. McGraw-Hill Interamericana.


Programari

No hi ha Pràctiques de Laboratori; en principi, no farem servir cap programari.


Grups i idiomes de l'assignatura

La informació proporcionada és provisional fins al 30 de novembre de 2025. A partir d'aquesta data, podreu consultar l'idioma de cada grup a través d’aquest enllaç. Per accedir a la informació, caldrà introduir el CODI de l'assignatura

Nom Grup Idioma Semestre Torn
(PAUL) Pràctiques d'aula 411 Català segon quadrimestre matí-mixt
(PAUL) Pràctiques d'aula 412 Català segon quadrimestre matí-mixt
(PAUL) Pràctiques d'aula 431 Català segon quadrimestre matí-mixt
(PAUL) Pràctiques d'aula 432 Català segon quadrimestre matí-mixt
(PAUL) Pràctiques d'aula 451 Català segon quadrimestre tarda
(PAUL) Pràctiques d'aula 452 Català segon quadrimestre tarda