
Teoria de la Computació
Codi: 107891Crèdits: 6
| 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
- Joaquim Borges Ayats
- Marc Masdeu Sabate
- Sebastià Mijares i Verdú
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:
- 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
- CM05 (Integrar tècniques basades en models computacionals en problemes de la informàtica.) Integrar tècniques basades en models computacionals en problemes de la informàtica.
- KM09 (Explicar procediments algorítmics de la teoria computacional per a la resolució de problemes d’enginyeria informàtica.) Explicar procediments algorítmics de la teoria computacional per a la resolució de problemes d’enginyeria informàtica.
- SM13 (Aplicar coneixements d’autòmats, gramàtiques i de complexitat computacional per a la resolució de problemes.) 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, expressions i llenguatges regulars.
2.4. 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.
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 |
|---|---|---|---|
| Classes de Teoria / Problemes | 50 | 2 | CM05, KM09, SM13 |
| Preparació i treball autònom | 26 | 1,04 | CM05, KM09, SM13 |
| Exercicis proposats a classe | 28 | 1,12 | CM05, KM09, SM13 |
| Estudi i preparació de les proves d'avaluació | 38,5 | 1,54 | 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.
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ó. Les notes d'aquests exercicis i/o activitats de validació suposaran el 30% de la nota final. Aquesta part de la nota NO serà recuperable.
- Hi haurà un primer examen parcial (Primer Parcial = P_1) abans de mig semestre en el qual s'avaluarà la feina feta fins a aquell moment. La nota d'aquest primer examen parcial 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 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 segon examen parcial aportarà un altre 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 no tindrà dret a recuperar-lo (excepte per causa degudament justificada, cas en què es permetrà fer l'examen de recuperació).
- Aquell estudiant que no hagi fet cap examen parcial constarà com a NO AVALUABLE a efectes acadèmics.
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 NF descrita abans no sigui inferior a 9. 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ó (exàmens parcials i examen de recuperació), 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 i de l'examen de recuperació s'informaran per part de la Coordinació de la Titulació i poden estar subjectes a possibles canvis de programació per motius d'adaptació a possibles incidències; sempre s'informarà al Campus Virtual (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.
Grups i idiomes de l'assignatura
La informació proporcionada és provisional fins al 30 de novembre. 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
| Tipus de docència | 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 |